2019 南京邮电大学研究生入学考试试题
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. 根据图画出所有拓扑排序序列