admin 管理员组文章数量: 1086019
2024年4月21日发(作者：如何制作网页游戏比如奥拉星)
数据结构试卷(四)
一、 选择题（每题2分，共20分）
1. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为( C )。
A. O(n)
B. O(nlog
2
n)
C. O(1)
2
D. O(n)
2. 设一棵二叉树的深度为k，则该二叉树中最多有( D )个结点。
A. 2k-1
k
B. 2
k-1
C. 2
k
D. 2-1
3. 设某无向图中有n个顶点、e条边，则该无向图中所有顶点的入度之和为( D )。
A. n
B. e
C. 2n
D. 2e
4. 在二叉排序树中插入一个结点的时间复杂度为( C )。
A. O(1)
B. O(n)
C. O(log
2
n)
2
D. O(n)
5. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( C )条有向边。
A. n
B. n-1
C. m
D. m-1
6. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行( A )
趟的分配和回收才能使初始关键字序列变成有序序列。
A. 3
B. 4
C. 5
D. 8
7. 设用链表作为栈的存储结构，则退栈操作( B )。
A. 必须判别栈是否为满
B. 必须判别栈是否为空
C. 判别栈元素的类型
D. 对栈不做任何判别
8. 下列4种排序中( D )的空间复杂度最大。
A. 快速排序
B. 冒泡排序
C. 希尔排序
D. 堆
9. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为N1，度数为2的结点数为
N2，则下列等式成立的是( C )。
A. N
0
=N
1
+1
B. N
0
=N
1
+N
2
C. N
0
=N
2
+1
D. N
0
=2N
1
+1
10. 设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数
不超过( A )。
A. log
2
n+1
B. log
2
n-1
C. log
2
n
D. log
2
(n+1)
二、 填空题（除第2题2分外每空1分，共20分）
2
1. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为 O(n) ，快速排序的平均
时间复杂度为 O(nlog
2
n) 。
2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为
p->llink->rlink = p->rlink; p->rlink->llink = p->llink; (设结点中的两个指针域
分别为llink和rlink)。
3. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为 3 。
k-1
4. 深度为k的完全二叉树中最少有 2 个结点。
5. 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从 [n/2] 第个元
素开始进行筛选。
6. 设哈夫曼树中共有99个结点，则该树中有 50 个叶子结点；若采用二叉链表作为存储
结构，则该树中有 100 个空指针域。
7. 设一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储 M-1 个队列元
素； 当前实际存储 (R – F + M) % M 个队列元素(设头指针F指向当前队头元素的前一
个位置，尾指针R指向当前队尾元素的位置)。
8. 设顺序线性表中有n个数据元素，则在第i个位置上插入一个数据元素需要移动表中的
n- i + 1 个数据元素； 删除第i个位置上的数据元素需要移动表中的 n – i 个元素。
9. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排
序的结果为 (18, 16, 19, 20, 22, 30) 。
10. 设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列
建成的初始堆为 (16, 18, 19, 20, 30, 22) 。
11. 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互
为邻接点的条件是 A[i][j]=A[j][i]=1 。
12. 设无向图对应的邻接矩阵为A，则A中第i行上非0元素的个数 等于 第i列上非0元
素的个数(填等于、大于或小于)。
13. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该
二叉树的序列为 BDCA 。
14. 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法画线处填上
正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键
字的指针，不成功时返回标志0。
1 class Node(object):
2 def __init__(self,key=None,next=None):
3 = key
4 = next
5
6 def createlkHash(hashTable):
7 for i in range(m):
8 hashTable[i] = 0
9 for i in range(n):
10 s = Node()
11 = a[i]
12 k = a[i] % P
13 = hashTable[k]
14 hashTable[k] = s
三、 计算题(每题10分，共30分)
1. 画出广义表LS=(( ),(e),(a,(b,c,d)))的头尾链表存储结构。
2. 设有如图A.6所示的森林：
(1) 求树(a)的先根序列和后根序列；
ABCDEF
BDEFCA
(2) 求森林的先序序列和中序序列；
ABCDEFGHIJK
BDEFCAIJKHG
(3) 将此森林转换为相应的二叉树。
图A.6森林图
3. 设散列表的地址范围是[ 0..9 ]，散列函数为H(key)= (key2+2)mod 9,并采用链表处理
冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。
四、 算法设计题(每题10分，共30分)
1. 设单链表中仅有3类字符的数据元素(大写字母、数字和其他字符)，要求利用原单链表
版权声明：本文标题：数据结构-Python语言描述试卷(四)附答案 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1713672679a646365.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论