重庆邮电大学

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

科目名称： 数据结构(A)

科目代码： 802

考生注意事项

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

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

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

$$ \begin{array}{l} \mathbf {m} = 1 0; \mathbf {n} = 1 0; \mathbf {s} = 0; \ f o r (i = 0; i < m; i + +) \ f o r (j = 0; j < n; j + +) \ s + = i ^ {*} j; \ \end{array} $$

A. $0\left(\mathrm{m}^{2}\right)$

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

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

D. O(1)

  1. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。

A. 插入

B. 删除

C. 排序

D. 查找

  1. 线性表采用链表存储时地址（ ）。

A. 必须是连续的

B. 部分地址必须是连续的

C. 一定是不连续的

D. 连续不连续都可以

  1. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依相同次序从该缓冲区中取出数据打印。该缓冲区作为数据结构是一个（ ）结构。

A. 棱

B. 队列

C.哈希表（Hash Table）

D.线性表

  1. 一个栈的输入序列为1,2,3,4，下面哪一个序列不可能是这个栈的输出序列（ ）？

A. 2,3，4，1

B. 4, 3, 1, 2

C. 1,3，2，4

D. 3, 4, 2, 1

  1. 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。

A. 栈

B. 队列

C. 顺序结构线性表

D. 链式结构线性表

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

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

A. 0

B.i

C. 1

D. $n - i + 1$

  1. 链表不具有的特点是（ ）。

A.可随机访问任一元素

B.插入、删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与线性表长度成正比

  1. 将一个 A[20][20] (下标从 1 开始计算) 的矩阵按行优先顺序存放，每个元素占 4 个存储单元，并且 A[1][2] 的存储地址是 1004，则 A[20][2] 的地址是（ ）。

A. 1004

B. 1380

C. 1520

D. 2524

  1. 树根的层数为 1, 则一棵含 12 个结点的二叉树的高度至多为 ( )。

A. 3

B. 4

C. 11

D. 12

  1. 已知二叉树如下图，下列序列中，（ ）是后序遍历后得到的序列。

A. 3 5 4 2 8 9 7 6 1

B. 3 4 5 2 8 9 7 6 1

C. 1 2 3 4 5 6 7 8 9

D. 2 3 4 5 6 7 8 9 1

  1. 已知数据表 A 中每个元素距其最终位置不远，则采用（ ）排序算法最节省时间。

A. 堆排序

B.直接插入排序

C.快速排序

D.简单选择排序

  1. 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键字12需做多少次关键码比较（ ）。

A.2

B.3

C. 5

D. 4

  1. 查找 Hash 表，不会发生冲突的哈希函数是（ ）。

A. 除留余数法

B. 伪随机探测再散列

C. 直接地址法

D. 线性探测再散列法

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

A、为 $O(\log_2N)$

B、为 $O(N)$

C、不直接依赖于 $\mathbf{N}$

D、上述三者都不是

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

  1. 下面四棵树中，数字表示相应叶子结点的权值，则（ ）是哈夫曼树。

  1. 下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费时间反而最多。

A. 堆排序

B. 罩泡排序

C. 快速排序

D. 直接插入排序

  1. 给定下列有向图和初始结点 V1, 按深度优先遍历的结点序列为（ ）。

A、V1，V3，V4，V5，V2

B、V1，V2，V3，V4，V5

C、V1，V2，V5，V3，V4

D、V1，V2，V4，V5，V3

  1. 下面关于图的存储的叙述中，哪一个是正确的（ ）。

A. 用邻接矩阵法存储图, 占用的存储空间数只与图中结点个数有关, 而与边数无关。
B. 用邻接矩阵法存储图, 占用的存储空间数只与图中边数有关, 而与结点个数无关。
C. 用邻接表法存储图, 占用的存储空间数只与图中结点个数有关, 而与边数无关。
D. 用邻接表法存储图, 占用的存储空间数只与图中边数有关, 而与结点个数无关。

  1. 在有向图的邻接表存储结构中，顶点 $\mathbf{v}$ 在表结点中出现的次数等于（ ）。

A. 顶点 $v$ 的度

B. 顶点 $v$ 的出度

C. 顶点 $v$ 的入度

D. 依附于顶点 $v$ 的边数

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

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

  1. 设有一空队列 Q，经 Q.EnQueue(1)，Q.DeQueue()，Q.EnQueue(2)，Q.EnQueue(3)，Q.EnQueue(4)，Q.DeQueue(); Q.EnQueue(5)一系列操作后。队列中从队首到队尾的元素依次是
  2. 设栈 S 和队列 Q 的初始状态为空，元素 a、b、c、d、e、f 将依次入栈 S，一个元素出栈后即进入队列 Q。若这 6 个元素出队列的顺序是 b、d、c、f、e、a，则栈 S 的容量至少应该是 _______，上述过程才不会错。
  3. 已知完全二叉树的第6层（根结点为第1层）总共只有5个结点，则其叶子结点数是
  4. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组 R[0,...,n-1]（下标从 0 开始计）中，结点 R[j]若有右子女，则右子女结点的下标是 ________。
  5. 某表达式二叉树按先序遍历的结果为 $+a^{*} + bcd$ ，令 $a = 6, b = 3, c = 4, d = 2$ ，则该表达式的值等于 ________。
  6. n 个元素的线性表, 采用顺序存储结构, 插入一个元素要平均移动表中_____个元素 (假定在线性表任何位置上插入元素都是等概率的)。
  7. 在一棵二叉树中，度为2的结点有50个，度为1的结点有20个，该二叉树共有条边。
  8. 含12个结点的平衡二叉树的最大深度是 (设根节点的深度是1)。
  9. 设二叉树 $T$ 的前序遍历序列和中序遍历序列分别是：b,d,c,a,e,f和c,d,e,a,b,f,则其后序遍历序列为
    10.6阶B-树（B-Tree）中，每个结点至多包含5个关键码，除根和叶结点外，每个结点至少包含 个关键码。
  10. 具有 $\mathbf{n}$ 个叶子结点的哈夫曼树中，其结点总数为 ______ 个。
  11. G 为无向图，如果从 G 的某个顶点出发进行一次遍历，即可访问图的每个顶点，则该图一定是 图。
  12. 在一个图中，所有顶点的度数之和等于图的边数的 ______ 倍。
  13. 已知一个无向图的邻接矩阵表示，计算第j个结点的度的方法是
  14. 两个不同的关键字，其哈希函数值相同，因而被映射到同一表位置上，这种现象称为

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

  1. 对长度为 $n$ 的关键字序列进行快速排序的时间复杂度为 ________。
  2. 对于键值序列 ${12, 13, 11, 18, 60, 15, 7, 18, 25, 100}$ 里建初始堆，必须从键值为 ______ 的结点开始对每个结点进行一次堆调整。

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

  1. 现有2棵树的森林如下图所示，请画出对应的二叉树。

  1. 已知关键字序列为 36, 31, 20, 32, 66, 48, 依次将各元素插入到一棵初始为空的二叉排序树，画出对应的二叉排序树。
  2. 假设用于通信的电文由字符集 ${A, B, C, D, E, F, G}$ 中的字母构成，这 7 个字母在电文中出现的频率依次为 ${3,12,7,4,2,8,11}$ 。请画出对应的编码哈夫曼树（Huffman）；求出每个字符的哈夫曼编码（约定编码时左分支编码“0”，右分支编码为“1”。生成哈夫曼时，同一层节点按左大右小排列）。
  3. 简要说明快速排序的排序思想。根据所给序列（49，38，65，97，76，13，27，50），设选第一个元素为支点/参考值（pivot），写出快速排序的第一趟排序的结果。

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

  1. 图G各顶点的连接关系及相应权值如下图所示。（1）画出该图的邻接距阵；（2）从顶点V1开始对图进行广度优先遍历，写出遍历结果（3）使用Kruskal算法求该图的最小生成树，画出其生成过程。

  1. 以关键字序列(265, 301, 751, 129, 937, 863, 742, 694, 076, 438)为例，分别写出执行以下排序算法的各趟排序状态和排序结束时关键字序列的状态。

(1) 直接插入排序 (2) 希尔排序，增量序列为 5,3,1。上述方法中，哪些是稳定的排序？哪些是非稳定的排序？

  1. 已知一组Key: (19 14 23 01 68 20 84 27 55 11 10 79), 按H(key) = key MOD 13 和线性探测再散列 $\mathrm{Hi} = (\mathrm{H(key)} + \mathrm{di})$ MOD 13 方法处理冲突, 请画出最后得到的哈希表并填写相应的探测次数（完整下列表格即可）。

答：哈希表如下：

0123456789101112
哈希表
探测次数
  1. 利用Dijkstra算法求下图中从定点V1到其他各定点间的最短路径，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成下表（最短路径用下划线标出）：

最短路径求解

终点\Di=1i=2i=3i=4i=5i=6
b15(a,b)
c2(a,c)
d12(a,d)
e∞
f∞
g∞
S终点集{a,c}

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

  1. 设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。

1）先给出算法思想；
2）再描述具体算法，必要时请给予注释说明；
3）请分析算法的时间复杂度。

  1. 设计一算法判断某一二叉树是否为二叉排序树

1）二叉树用二叉链表的形式表示，定义如下：

typedef struct node{ DataType data; struct node \*]child,\*rchild; }BinTNode;

2）先给出算法思想，再描述算法，必要时请给予注释说明。