2021 南京邮电大学研讨生入学考试试题
811 数据规划仿照卷（一）
一、选择题
1. 判别哪个表规划是逻辑规划（ )
a 次序表b 哈希表c 有序表d 单链表
2. 关于算法的优胜性判别，以下正确的是( )
a 算法原地作业是指不需要额定的辅佐空间
b 健旺性是指程序不因为新鲜的输出而发生新鲜的状况
c 若算法的时刻凌乱度是o(n 外，标明它的疑问规划n2
d 算法的输入是指至少要有一个输入，这些输入取自于某个特定目标的集结
3. 假定要在最终一个元素之后刺进一个元素和删去第一个元素，那么哪种存储方法最省时
间（）
a 单链表b 仅有头指针的单循环链表c 双链表d 仅有尾指针的单循环链表
4. 次序表的1 个是占2 个存储的单元，若第一元素a。地址100, 则as 在内存中的存储地
址是（ )
a 105? b
110? c 115? d 120
5. 6 5 4 5 3 2 1 次序进栈判别不合法的出栈的序列（ )
a 1235456 b 6545321 c 6545123 d 2545631
6. 根据一个式子a*(b+c)-d 写出后缀表达式（ )
a) abed*+= b) abc+*d- c)abc*+d- d)-+*abcd
7. 100*90 的稀少矩阵有非0 元素10 个每个类型占2 个字节求用三元组存储该矩阵时所需
要字节数（ )
a 60? ? ?b 66? ? ?c 20? ? ?d 10
8. 判别对稀少矩阵的紧缩意图（ )
a 表达变得简略
b 对矩阵元素的存取变得愈加简略
c 去掉矩阵中的剩下元素
d 削减不必要的存储空间
9. 先序和后序中，叶子节点的次序不一样点判别（ )
a) 都纷歧样b) 完全相同c) 前序和中序相同d) 中序和后序相同，而与前序不一样
10. n 个结答应绪求二叉树富含的条理( )
a) 2n b) n-1 c)n+l d)n
11. 长度为n 的有序单链表，若查找每个元素的概率相同，则次序查找表中任一元素的查找
成功的均匀查找长度为（ )
a) n/2 b)(n+l)/2 c)(n-1)/2 d)n/4
12. 对序列11 、14 、21 、25 、34 、46 、56 、78 进行减半查找，查找元素78, 次序是( )
a 25 46 56 78? b 25 56 46 78? c 25 46 78? d 25 46 56
13. 二叉平衡树中任意节点的平衡因子的判别（ )
a .左面－右边=1? ? b.左面－右边<=1? ? c.i 左面－右边l =l? ?d.i 左面－右边1? <=1
14. 除根节点外的m 阶b 树的每个非叶子节点有几个孩子（ )
a 「m/21 b 「(m/2)-11 c 「m/21-l d 「m/27 +1
15. 有向图g 对拓扑序列中，若极点w 在vj 之前，则下列景象不能呈现的是（ )
a) g 中有弧<v, vj>
b) g 中有一条v; 到vi 得到途径
c) g 中没有弧<v;, vj>
d) g 中有一条v」到v; 的途径
16. 领接表存储最小生成树prime 算法的时刻凌乱度（ )
ao (n2)? ? bo(n 3）c o(n+e) d o(log2n)
17. 从以下选出平稳的排序（ )
a 快速排序b 希尔排序c 简略选择d 冒泡排序
18. 对包括n 个元素的散列表进行查找，均匀查找长度（ )
a) 为o?(log2n)? ? ?b) 为o?(1)? ? c)不直接依靠于n? ? ?d)直接依靠于表长m
19. 用直接刺进排序对下列四个序列进行递加排序，比照次数最少的是（ )
a94 、2 、40 、90 、80 、46 、21 、69
b 32 、40 、21 、46 、69 、94 、90 、80
c21 、32 、46 、40 、80 、69 、90 、94
d 90 、69 、80 、46 、21 、32 、94 、40
20. 对序列40 、30 、50 、60 、70 、10 、20 、80 用简略选择排序要交流几回结束递加排序（ )
a) 8? ? ?b)7? ? ? c)6? ? ? d)5
二、归纳题
1.1000 个元素要害词是0-9999 将数据存入长度为200 拉链法散列中，方案散列函数处置此
疑问并阐明散列函数的优点。
2.one:非空二叉树先序和后序相反是啥形状
? ?two:非空二叉树先序和后序相同是啥形状
3. abcdef 表别离有10 35 40 50 60 和200 个元素各个表中都升序，求经过5 次两两兼并
6 个表合1 升序表，并在最坏情况下比照总次数与兼并进程并求出最坏情况下比照的次数是多
少。
4. 证明m 叉满二叉树上叶子节点数no 和非叶子结点数n 之间满足以下联络n0= (m-1)*n+1
5. 有序10 、12 、21 、23 、30 、39 、43 、50 、60 有一串对下标从0?初步符号进行对半查找
one:查找10, 描绘对半查找的进程
two:求对半查找成功的均匀查找长度
6. 序列15 、25 、70 、38 、50 、80 、75, 请画出avl 树
7. 根据图像出一切拓扑排序序列
