课程代码：21049
适用专业：计算机应用、计算机网络
一、判断题 (每小题1分，共10分)
1.一个完整算法可以没有输入，但是必须有输出。( )
2.算法与程序没有区别。( )
3.用循环链表作为存储结构的队列称为循环队列。( )
4.满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。( )
5.除了插入和删除以外，数组的操作还有存取、修改、检索和排序。( )
6.任意图都是其自身的子图。( )
7.一个图具有生成树的必要条件是该图必须是连通图。( )
8.折半查找方法也可以用于按值大小链接的线性链表的查找。( )
9.在B树中查找与在B+树中查找的过程完全相同。( )
10.对具有n个元素的序列采用泡排序法进行排序，排序趟数为n-1。( )
二、单项选择题 (每小题2分，共10分)
1.正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是( )。
A.top不变 B.top←0
C.top←top+1 D.top←top-1
2.中缀表达式(A-B*C)/D+E的后缀形式是( )。
A.A-BC*D/E+ B.ABC*-D/E+
C.ABC*-DE/+ D.ABC*-D/+E
3.对二叉树进行_______遍历可以得到结点的排序序列。( )
A.前序 B.中序
C.后序 D.按层次
4.一个具有n个顶点的连通图的生成树中有_______条边。( )
A.n-1 B.n
C.┗n/2┛ D.n+1
5.对具有八个元素的序列(49,38,65,97,76,13,27,50)按从小到大排序，_______是选择排序法第一趟的结果。( )
A.13,65,38,97,76,49,27,50
B.13,27,38,49,50,65,76,97
C.97,76,65,50,49.38,27,13
D.13,38,65,97,76,49,27,50
三、填空题 (每空2分，共20分)
1.一般情况下，将一个递归算法变换成等价的非递归算法主要设置_______机制。
2.循环单链表与循环非循环单链表的主要不同是___________________________________。
3.若具有n个结点的非空二叉树采用二叉链表存储结构，该链表一共有____个指针域，其中_____个指针域存放非空指针，有_____个指针域存放空指针(nil)。
4.具有n个顶点的无向图的边数最多为_______________________，具有n个顶点的有向图的边数最多为_____________________。
5.在散列文件(Hash文件)中，处理冲突的方法通常有__________、___________、___________三种。
四、简答题 (共20分)
1.一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)
2.有人说一个m×n阶的矩阵是一个广义表结构，你认为如何？请拘役说明你的结论。(5分)
3.插入排序法的时间花费主要取决于元素之间的比较次数。若具有n个元素的序列初始时为递增序列，采用插入排序法排序一共要进行多少次元素的比较？若序列初始为递减序列，一共要进行多少次元素的比较？(10分)
五、问题求解题 (每小题10分，共20分)
1.给定一带权连通图如下，先写出其邻接矩阵，然后根据Prim算法求出其所有可能的最小生成树。
9
6
7 8
V1--------V2--------V3--------V4--------V5
4
4
2.若一棵树有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，求该树中叶结点的个数。(要求写出推导过程)
六、算法题 (共20分)
1.已知具有n个记录的排序连续顺序文件，其关键字序列满足key[1]≤key[2]≤...≤key[n]，下面是在该文件中查找关键字为k的记录的算法，若查找成功，算法返回被查到记录在文件中的位置，若查找失败，返回信息0。请在算法的空缺处填入适当内容，使之能够正常工作。(8分)
function BINSRCH(key,n,k)
low←1
high←n
while ┏━━━━━━━━━┓do
┗━━━━━━━━━┛
mid←┗(low+high)/2 ┛
if key [mid]=k then
return (mid)
if key [mid]
┏━━━━━━━━━┓
┗━━━━━━━━━┛
else
┏━━━━━━━━━┓
┗━━━━━━━━━┛
end
return (0)
end
2.已知二叉树采用二叉链表存储结构，链接点的构造为lchild | data | rchild 根结点的指针为T，下面给出的是交换该二叉树中所有结点的左、右子树相对位置的算法，算法中设置了一个空间足够大的书许存储结构的队列Q，队头指针与队尾指针分别用front和rear表示，队列中保存的是链接点的地址。请在算法的空缺处填入适当内容，使之能够正常工作。(12分)
procedure EXCHANGE(T)
if T=nil the
return
Q[1]←T
rear←1
front←0
while┏━━━━━━━━━┓do
┗━━━━━━━━━┛
┏━━━━━━━━━━━━┓
┗━━━━━━━━━━━━┛
p←Q[front] // 从队列中退出一个元素 //
┏━━━━━━━━━━━┓
┃ ┃
┃ ┃
┃ ┃ // 交换左右子树位置 //
┃ ┃
┃ ┃
┃ ┃
┗━━━━━━━━━━━┛
if lchild(p)≠nil then
[┏━━━━━━━━━┓
┗━━━━━━━━━┛
Q[rear]←lchild(p) // 进队 // ]
if rchild(p)≠nil then
[┏━━━━━━━━━┓
┗━━━━━━━━━┛
Q[rear]←lchild(p) // 进队 // ]
end
end
|
论坛热贴
