重庆邮电大学

2014年攻读硕士学位研究生入学考试试题

科目名称： 数据结构（B）

科目代码： 802

考生注意事项

1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。
2、所有答案必须写在答题纸上，写在其他地方无效。
3、填（书）写必须使用黑色字迹钢笔、圆珠笔或签字笔。
4、考试结束, 将答题纸和试题一并装入试卷袋中交回。
5、本试题满分 150 分, 考试时间 3 小时。

一、选择题（本大题共20小题，每小题2分，共40分）

  1. 下面程序段的时间复杂度是（？）。

$$ \begin{array}{l} f o r (i = 0; i < m; i + +) \ A [ i ] = 0; \ f o r (i = 0; i < m; i + +) \ f o r (j = 1; j < n; j + +) \ A [ i ] + = 5; \ \end{array} $$

A $\mathrm{O}(\mathrm{m} + \mathrm{n})$

B $\mathrm{O}\left( {\mathrm{m} + \mathrm{n} + 1}\right)$

C O(n)

D $O(m^{*}n)$

  1. 计算机算法指的是（？），它必须具备输入、输出和可行性、确定性和有穷性等5个特性。

A 计算方法

B 排序方法

C 解决问题的有限指令序列

D 调度方法

  1. 若某栈的输入序列为 $1,2,3,\dots ,n$ ，输出序列的第2个元素为 $\mathbf{n}$ ，则第3个输出元素为（？）。

A 1或2

B 1或n-1

C n-1或n-2

D n-1

  1. 线性表的链式存储结构与顺序（连续）存储结构相比优点是（？）。

A. 便于插入和删除

B. 便于随机存取

C. 所有的操作/运算的算法简单

D. 便于查找

  1. 设循环队列中数组的下标范围是 0.. n-1，其头指针 front 指向队首元素，rear 指向队尾元素，则队列的长度为（？）。

A rear-front

B rear-front+1

C (rear-front+1) % (n+1)

D (rear-front+n+1) %n

  1. 如果某应用在线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（？）存储方式最节省运算时间。

A. 仅有头指针的单链表

B.仅有头指针的单循环链表

C.双链表

D.仅有尾指针的单循环链表

  1. 在长度为 $n$ 且带头结点的链式存储实现的线性表的第 $i (0 \leqslant i \leqslant n)$ 个位置插入一个元素，需要查找运算（？）次。

A. 1

B. n-i

C. i

D. n-2

  1. 在长度为 $n$ 顺序实现的线性表的第 $i (1 \leq i \leq n)$ 个位置之前插入一个元素，需要后移（？）个元素。

注：所有答案必须写在答题纸上，试卷上作答无效！ 第2页（共7页）

A. i

B. n-i+1

n

D. 1

  1. 数组 A 中，每个元素 A 的长度为 4 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 S 开始连续存放在存储器内，该数组按行优先存放时，元素 A[5][6]的起始地址为（？）。

A. S+160

B. S+180

C. S+220

D. S+140

  1. 设高度为 $h$ 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（？）。

A. $2\mathrm{;h} - 1$

B. 2h

C. $2\mathrm{h} + 1$

D.h+1

  1. 已知完全二叉树有 10 个结点，则整棵二叉树有（？）个度为 1 的结点？

A. 2

B. 1

C. 0

D. 不确定

  1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（？）

A. 直接插入排序

B. 希尔(Shell)排序

C. 简单选择排序

D 冒泡排序

  1. 在常用的哈希表处理冲突的方法中，（？）方法容易产生“二次聚集”，导致哈希表性能变差。

A. 开放定址法一线性探测

B. 再哈希法

C. 链地址法

E. 开放定址法一二次探测

  1. 对包含 $n$ 个元素的散列表进行查找，平均查找长度（？）

A. 为 $O(\log_2 n)$

B. 为 $O(n)$

C. 不直接依赖于 $n$

D. $O(n \log_2 n)$

  1. 对一棵二叉排序（升序、查找）树的根结点而言，左子树中所有结点的关键字都（？）右子树中所有结点的关键字。

A. 不等于

B. 不大于

C. 等于

D. 大于

  1. 在对 n 个关键字进行简单选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第 i 趟排序之前，无序区中关键字元素的个数为（？）

A. i

B. $i + 1$

C. n-i

D. n-i+1

  1. 下面的关键码序列中哪一个是堆（？）。

A. 18, 72, 35, 23, 94, 53

B. 18, 31, 23, 94, 53, 72

C. 18, 53, 23, 94, 40, 72

D. 94, 55, 18, 72, 16, 23

  1. 设连通图 G 采用邻接表存储，则深度优先遍历算法的时间复杂度是（？）。

A.O(n)

B.O(n+e)

C. $\mathrm{O}\left( {\mathrm{n}}^{2}\right)$

D.O(n*e)

  1. 已给右图，（？）是该图的拓扑排序？

A. 1, 2, 3, 4, 5

B. 1, 2, 4, 3, 5

C. 1, 3, 2, 4, 5

D. 1, 2, 3, 5, 4

  1. 图的邻接矩阵表示法适用于表示（？）

A. 稠密图

B. 有向图

C. 无向图

D. 稀疏图

二、填空题（本大题共17小题，每小题2分，共34分）

  1. 设一循环队列 Q 中，rear 指针指向队尾元素的下一个位置，front 指针指向队首元素，则判断队列中元素为空的条件是________。
  2. 设栈 S 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5，a6 和 a7 依次通过一个栈，一个元素出栈 即进入队列 Q，若 7 个元素出队列的顺序是 a3，a5，a4，a7，a6，a2，a1 则栈 S 至少应该容纳 ______ 个元素。
    3.广义表 $\mathrm{L} = ((\mathrm{a}),(\mathrm{b},\mathrm{c}),(\mathrm{d}))$ ，L的长度是
    4.二叉树中第5层上（根在第1层）的结点个数最多为
  3. 某算法中的语句频度之和为 $\mathrm{T}(\mathrm{n}) = 3\mathrm{n}^2 + 2\mathrm{n} + 7$ ，则其时间复杂度为 ______。
  4. 某表达式语法树(二叉树)按后序遍历的结果为 abc-d+*h-, 令 $a = 2, b = 6, c = 4, d = 5, h = 8$ , 则该表达式的值等于
  5. 采用特殊字符作为结尾的顺序存储方式存储，若两个串的长度分别为 $m$ 和 $n$ ，则两个串相等与否的比较运算的时间复杂度为 ______。
  6. n 阶矩阵中三角矩阵使用压缩存储方式时需要 ______ 个数据元素空间来存储。
  7. 一棵含有20个结点的二叉树的高度至少为 （空树高度为0）。
  8. 已知某二叉树的先序序列 ABCFDG，中序序列 CBDFAG，那么它的后序遍历序列是
    11.含n个顶点的无向连通图中至少含有 条边。
  9. 采用特殊字符作为结尾的顺序存储方式存储，则串“GLuckyUProgram”至少需要

注：所有答案必须写在答题纸上，试卷上作答无效！ 第4页（共7页）

个字符的存储空间。

  1. 请指出在顺序表{3、6、8、10、14、15、18、36、44、62}中，用二分法/折半法查找关键字码10需做____次关键字码比较。

  2. 高度为 5 的 AVL 树（平衡二叉树）至少有____个结点。（空树高度为 0）

  3. 应用 Dijkstra's 算法 (单源最短路径) 求下图顶点 A 到顶点 D 的最短路径, 第 1 步、第 2 步求出的是顶点 A 到顶点 , A 到顶点 的最短路径。

  1. 对于键值序列 ${16, 85, 28, 58, 17, 5, 18, 25, 81, 32, 98}$ , 建里初始堆, 必须从键值为____的结点开始对前面的每个结点进行一次堆调整。

  2. 排序过程中，对尚未确定最终位置的所有数据元素进行一遍处理称为一趟排序，下列五种排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法有

I. 简单选择排序

II.希尔（Shell）排序

III. 快速排序

IV. 唯排序

V. 两路归并排序

三、问答题（本大题共8小题，每小题7分，共56分）

  1. 在顺序表中插入一个结点需平均移动多少个结点？分析此操作的时间复杂度。
  2. 设下图为某树的二叉树表示，请画出该树。

  1. 已知关键字序列为 45, 32, 22, 37, 70, 42，依次将各元素插入到一棵初始为空的二叉排序树，画出对应的二叉排序树。
  2. 简要说明快速排序的排序思想，并给出算法时间复杂度。根据所给序列（50，25，35，80，90，15，99，68），设选第一个元素为支点/参考值（pivot），采用双向交替向中间扫描的方式，写出快速排序的第一趟排序的结果。
  3. 下图有六个顶点 A、B、C、D、E、F，其连接关系及相应权值如图所示。给出邻接矩阵表示结果，然后从顶点 A 开始对图进行广度优先遍历，写出遍历结果。

  1. 使用 Kruskal 算法求第 5 题所给图（上图）的最小生成树，必须给出树的生成过程。

  2. 已给输入关键字序列 ${23, 12, 17, 60, 30, 36, 40, 42}$ , 哈希函数为 H (key) = key %9, 哈希表的地址空间为 0, 1, ..., 8, 开始时哈希表为空,用线性探测法解决冲突, 请依次画出插入键值后的 Hash (哈希) 表, 出现冲突时单独标示清楚。

  3. 假设用于通信的电文由字符集 ${\mathrm{X},\mathrm{Y},\mathrm{C},\mathrm{D},\mathrm{F}}$ 中的字母构成，这5个字母在电文中出现的频率依次为 ${35,20,10,13,22}$ 。请画出对应的编码哈夫曼树（Huffman）。

四、算法设计、分析题（本大题共2小题，每小题10分，共20分）

  1. 现有二叉平衡树（或为空树，或者根结点的左右子树高度差最大为 1 且左、右子树为二叉平衡树），试设计一算法判断该二叉树是否为二叉平衡树。

1）先给出设计思想；
2）再描述具体算法，必要时请给予注释说明。

  1. 现有某比赛活动中某选手的 n 个评分结果（百分制，已知都在 60 以上的整数）已存入顺序表中，并且已按升序排序。为了分析相关规律，现需分析评分的 k-均值直方图（以当前分数为中位数（位置在中间），计算最邻近的 k 个分数平均值并取为整数，然后统计分数的频率得到。若当前分左边或右边数据不足时直接忽略，不计入统计数据），请设计一尽量快速的算法，求得打印直方图前的统计结果。

1）先给出设计思想；
2）再描述具体算法，必要时请给予注释说明。