第一部分 选择题 (共20分)
一、单项选择题 (本大题共10小题，每小题2分，共20分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选、多选或未选均无分。
1.线性链表中各链结点之间的地址 [ ]
A.连续与否都可以 B.部分地址必须连续
C.一定不连续 D.必须连续
2.删除非空双向循环链表中由q所指的链结点的过程是依次执行以下三个动作：
rlink(llink(q))←rlink(q),__________________,call RET(q)。 [ ]
A.llink(q)←q B.llink(rlink(q))←q
C.llink(rlink(q))←llink(q) D.llink(q)←rlink(q)
3.在包含有1000个元素的线性表中实现如下四个操作，所需要的执行时间最长的是 [ ]
A.线性表采用顺序存储结构，在第10个元素后面插入一个新的元素
B.线性表采用链式存储结构，在第10个元素后面插入一个新的元素
C.线性表采用顺序存储结构，删除第990个元素
D.线性表采用链式存储结构，删除p指的链结点
4.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 [ ]
A.a B.b
C.c D.d
5.若不考虑结点的数据信息的组合情况，具有3个结点的二叉树共有_____种形态。 [ ]
A.2 B.3
C.4 D.5
6.对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0= [ ]
A.n1+1 B.n1+n2
C.n2+1 D.2n1+1
7.已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即
ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为 [ ]
A.G,D,B,A,F,H,C,E B.G,B,D,A,F,H,C,E
C.B,D,G,A,F,H,C,E D.B,G,D,A,F,H,C,E
8.在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN)，散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6] ，采用线性再散列法处理冲突。插入后的散列表应该如__________ 所示。[ ]
A. 0 1 2 3 4 5 6
THU TUE WED FRI SUN SAT MON
B. 0 1 2 3 4 5 6
TUE THU WED FRI SUN SAT MON
C. 0 1 2 3 4 5 6
TUE THU WED FRI SAT SUN MON
D. 0 1 2 3 4 5 6
TUE THU WED SUN SAT FRI MON
9.下面的序列中________是大顶堆积。 [ ]
A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2
C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,1
10.在下述的排序方法中，不属于内排序方法的是是 [ ]
A.插入排序法 B.选择排序法
C.拓扑排序法 D.归并排序法
第二部分 非选择题 (共80分)
二、填空题 (本大题共10小题，每空2分，共20分)
请在每小题的空格上填上正确答案。错填、不填均无分。
11.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。
12.若频繁地对线性表进行插入与删除操作，该线性表应采用______________存储结构。
13.若链结点的构造为data|link，那么，判断由list所指的单向循环链表中只有一个结点的条件是______________。
14.求串T在主串S中首次出现的位置的操作是______________。
15.完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是______________。
16.一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________。
17.在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行______________次元素之间的比较。
18.若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key MOD 9，与18发生冲突的元素有______________个。
19.每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为______________排序法。
20.排序过程中所进行的元素之间的比较次数与参加排序的序列的初始状态无关的排序方法是______________排序法。
三、简答题 (本大题共2小题，共15分)
21.(7分) 堆栈和队列都是特殊线性表，其特殊性是什么？
22.(8分) 在建散列表时，通常情况下，采用链地址法处理冲突比采用开放地址法处理冲突的时间效率要高，为什么？
四、问题求解题 (本大题共2小题，每小题10分，共20分)
23.折半查找过程可以利用一棵称之为“判定树”的二叉树来描述，请画出在长度为13的表中进行折半查找对应的判定树。
24.若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟排序的结果。
原 始 序 列 49 38 27 13 97 76 50 65
第1趟的结果
第2趟的结果
第3趟的结果
第4趟的结果
五、算法填空题 (本大题共2小题，共25分)
25.(10分)已知线性表A与线性表B的长度分别为n与m，并且都采用顺序存储结构，下面的算法是在线性表A的第i个位置插入线性表B。约定：不考虑存储空间溢出问题。
请在算法的空缺处填入适当内容，使之能够正常工作。
procedure INSERT(A,n,B,m)
for j←n downto i do
A[┏━━━━━━┓]←A[j]
┗━━━━━━┛
end // 将A中某些元素依次后移m个位置 //
for j←1 to m do
A[┏━━━━━━┓]←B[j]
┗━━━━━━┛
end // 从A中第i个位置开始依次插入B中元素 //
n←┏━━━━━━┓
┗━━━━━━┛ // 修改插入以后A的长度 //
end
26.(15分)已知不带头结点的非空线性链表的链结点的构造为data|link，第一个链结点的指针为list，下面的算法将链表中数据域最大的那个链结点移到链表最后面。
请在算法的空缺处填入适当内容，使之能够正常工作。
procedure REMOVE(list)
p←┏━━━━┓
┗━━━━┛ // p初始时指向链表第二个链结点 //
q←list
r←list
while┏━━━━━━┓do
┗━━━━━━┛
if (data(p)>data(q)) then
[ s←r
q←p ]
r←p
┏━━━━━━┓ // 将p指向下一个结点 //
┗━━━━━━┛
end // q指向值最大的那个链结点，s指向其前驱结点 //
if (q≠r) then // 若最大值的链结点不是链表最后的那个链结点 //
[ if (q=list) then // 若最大值的结点是链表的第一个结点 //
┏━━━━━━┓
┗━━━━━━┛
else // 若最大值的结点不是链表的第一个结点 //
┏━━━━━━━━┓
┗━━━━━━━━┛
link(r)←q
link(q)←nil ]
end
|
论坛热贴
