南京邮电大学
2006年攻读硕士学位研究生入学考试
数据结构 试题
考生注意：本试卷共4页。所有答题均写在答题纸上（包括单选和填空题），请务必准确标明所答题的题号和填空号。
一、单选题（每题3分，共30分）
南京比较好考研的大学A. O n
B. O
C. O n log n
D. n n 2n nlog n 2n n n nlogn n nlog n O log n
术语中，_____B
2. 下列_____与数据的存储结构无关。
A. 循环队列
B. 堆栈
C. 散列表
结点的单循环链表，一个链表指针指向表头结点 个结点 个节点 配第一趟失配后
下一趟匹配开始时，子串指针指示的字符是____A
3. 设线性表非空，采用下列_____D_____所描述的链表可以在O(1)时间内在表尾插入一个
A. 带表头结点的单链表，一个链表指针指向表头结点
B. 带表头
C. 不带表头结点的单链表，一个链表指针指向标的第一
D. 不带表头结点的单循环链表，一个链表指针指向表的第一
4. 设主串为“abceabceyabceabceab ”，字串为“abceabcea ”。则在KMP 匹____。 A. a B. b C. c D. e
广州市人社局网上办事大厅5. 二叉树中第5层上的结点个数最多为____C____，假定根节点层次为1.
A. 8
B. 15
C. 16
D. 32 回时打印当前顶点，则输出的顶点序列
是____C
6. 用DFS 遍历一个有向无环图，并在DFS 算法退栈返____。 D. 按顶点编号次序的
7. A. 拓扑有序的 B. 无序的 C. 逆拓扑有序的
下面____A____算法可于无向图的所有连通分量用求
. 广度优先遍历 B. 拓扑排序 叶结点的8路合并胜方树。在输出一个元
河北省学考成绩查询2020素后，将有一个新元素补充到相应的叶结点中。在重构的胜方树中，应有____D A C. 求最短路径 D. 求关键路径
8. 设有以元素10，9，20，6，8，23，21，17为____个杂度为____D 元素需要修正。 A. 1 B. 2 C. 3 D. 4
9. 在一棵二叉搜索树上搜索一个元素的平均时间复____。
A. O n
B. O(n)
C. O nlog n
D. O log n
B
10. 下面关于倒排文件的说法中正确的是______。
A. 倒排文件是对主关键字建立索引的
B. 倒排文件是对次关键字建立索引的 A ）开始顺序存放，每个元素占2个字节。元素
A[4,4]在行优先方式下的存储地址为____(1)C. 倒排序文件的优点是维护简单
D. 采用倒排文件是为了节省存储空间
二、填空题（每题6分，共48分）
1. 设有二维数组A[0…5,0…6]，从地址Loc （____，在列优先方式下的存储地址为____(2)____。 解答：
(1) Loc(A) + 2*7*4 + 2*4 = Loc(A) + 64 (2) Loc(A) + 2*6*4 + 2*4 = Loc(A) + 56
)*C – E/D ，其后缀形式为____(3)2. 已知一算术表达式的中缀形式为(A +B ____。另有一算术
0至9的一位数。此表达式的值为____(4)表达式的后缀形式为2 6 4 ‐ * 2 /，每个操作数均为____。 = 2
夫曼树实现对字符集{F,G,H,I,J}的哈夫曼编码。
文为：011101011101，则利用
此哈夫曼树进行译码得到的电文为____(5)解答：
(3) A B + C * E D / ‐ (4) 2*(6 – 4) / 23. 使用如图1所示的哈已知编码后得到的码
____。设
该字符集中各字符的使用频率各不相同，则其中使用频率最小的两个字符应当是____(6)____。
解答： (5) G I H J G (6) I J
2所示。则所有
拓扑有序序列为____(7)4. 设有向图如图可能的____。 ③ ⑥ ⑤ ②
③ ⑥
5. 已知对一棵二叉树的先序和中序遍历的结点次序可以唯一确定该二叉树。设某棵二叉树
的先 ABCDEFG 和 BDCAEGF ，则其后续次序为____(8)解答：安徽教师资格证考试
(7) ① ② ④ ⑤ ③ ⑥ ① ④ ② ⑤① ④序和中序次序分别为____。此外，已知后序和____(9)____序遍历次序也可以唯一确定一棵二叉树。 解答：
(8) D C B G F E A (9) 中
本原因是____(10)6. 引入B ‐ 树的最根____。在有n 个元素的访问外存的次数至多为____(11)m 阶 B ‐
树中，搜索一个元素的
算法需要____。 解答：
(10) 为了减少外搜索的磁盘访问次数，为修改过程提供简单的平衡算法
(11) l og 取上整
中国人才卫生网N 1
7. 分别采用直接插入排序和快速排序方法对下面所列出的四个序列进行排序（由小到大）。
直接插入排最长的序列是____(12)使得序时间____，使得快速排序时间最短的序列是____(13)____
A. 10，20，30，40，50，60，70 ，30，50，70，60 辑结构是指____(14)_
B. 70，60，50，40，30，20，10
C. 40，10，30，20，60，50，70
D. 40，20，10解答： (12) B (13) C D
8. 数据的逻___，数据的存储结构是指____(15)____。
据逻辑关系的描述
(15) 数据在存储器中的存储方法 三、解答题（每题8分，共40分）
贵州人事考试信息网阵实现矩阵快速转置算法时，需要附设两个一维数组，设
矩阵第col 列中非零元素个数。现有稀疏矩阵如右图所示
示的示意图；
解下列关于散列表的问题
) 除法（除留余数法）散列函数是最常用的一种散列函数，请写出散列函数的一般形
式。
) 设有散列表Ht 如下，现采用二次探查法解决冲突。已知H(38) = 5，H(25) = 3，请将
当位置。请在答题纸上画出完整的插入两个新元素后的散
解答：(14) 对数
1. 当采用行三元组表存储稀疏矩为num 和k ，其中num[col]表示原(1) 请给出它的转置前后的行三元组表(2) 计算数组num 和k 的元素值。
2. 求(1(238和25依次插入表中适列表。
3. 已知AOE 网如第二题第4小题图2所示。
(1) 计算每个顶点代表的事件可能的最早发生时间。(2) 列出计算顶点代表事件允的最发生时 计算关键路径长度，并列出关键路径的顶点序列。. 设有向图如图3所示， 连通分量。
、算法设计题（共32分）
题要求：
) 只允许使用pascal ，C 和C++语言中的一种语言描述数据结构和算法。 上以实现的过程或函数。 ) 要求对算法的每一条语句加明确注释。 借助于一个一维数组，设为第k 个元素小的元素个数。因此count[k]也表明了第k 个元素在有序序列中的位置。请设计一个算法计算数组count 的值。分析此算最好和平均情况时间复杂度。
2. 递归用普通二叉链表存储的二叉树。二叉链表的个结点有三个域：lChild ，rChild 和element 。算法返回所构造的新二叉树的根结点地址。
的计式和计结果 ，22。请画出每插入一个元素后
4所的许迟间算算。(3)
4. 从空二叉平衡树开始，依次插入：19，25，43，16，18的二叉平衡树。
5
(1) 画出邻接表存储表示的示意图； (2) 求它的全部强
四
解(1(2) 算法描述中不允许直接调用教材(3
1. （14分）
设有n 个元素保存在一维数组A 中。枚举排序的基本思想是count 。count[k]记录在初始序列A 中，比法的最坏、（18分）
设一棵n 个结点的完全二叉树采用顺序存储结构，保存在一维数组A 中。试设计一个算法，复制该完全二叉树，得到一棵新的采每
发布评论