重庆邮电大学

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

科目名称： 数据结构（A卷）

科目代码： 802

考生注意事项

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

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

  1. 下列程序的时间复杂度为（ ）。
$\mathrm{i} = 0$ $\mathbf{s} = 0$  n=100;   
while（s<n） { i++; s=s+i;

A) $O(\sqrt{n})$

B) $O(\sqrt{2\pi})$

C) $O(n)$

D) $0(n^{2})$

  1. 若线性表的操作主要是查找，很少涉及到插入、删除操作时，宜采用以下存储结构较为合适（ ）。

A) 双链表

B）单链表

C）顺序表

D）循环链表

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

A）必须是连续的

B）连续不连续都可以

C）一定是不连续的

D）部分地址必须是连续的

  1. 若允许表达式内多种括号混合嵌套，则设计检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（ ）。

A) 機

B) 线性表

C) 队列

D) 二叉排序树

  1. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )。

A) 2, 4, 3, 1, 5, 6

B) 3, 2, 4, 1, 6, 5

C) 4, 3, 2, 1, 5, 6

D) 2, 3, 5, 1, 6, 4

  1. 栈和队列的共同点是（ ）。

A) 都是先进先出

B) 都是先进后出

C) 只允许在端点处插入和删除元素

D) 没有共同点

  1. 在长度为 $n$ 的顺序表中删除第 $i (1 \leq i \leq n)$ 个元素时，需要移动元素的次数为（ ）。

A) $n - i + 1$

B) i

C) $i + 1$

D) n-i

  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[12][18]采用列优先的存储方法, 若每个元素各占 3 个存储单元, 且 A[0][0]地址为 150, 则元素 A[9][7]的地址为( )。

A) 429

B）432

C) 435

D) 438

  1. 含有 10 个结点的二叉树中，度为 0 的结点数个数为 4，则度为 2 的结点个数为（ ）。

A) 3

B) 4

C) 5

D) 6

  1. 关于树和森林，下列说法错误的是( )。

A) 树的结点数可以为 0
B）树的度是树内各结点的度的最大值
C) 树的子树可以有顺序, 也可以无顺序
D）二叉树不是树

13．在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。

A) $1 / 2$

B) 1

C) 2

D) 4

  1. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）。

A) 深度优先搜索算法

B) 广度优先搜索算法

C) 求最小生成树的普里姆算法（Prim 算法）

D) 拓扑排序算法

  1. 下面哪一方法可以判断出一个有向图是否有环（即回路）（ ）。

A) 求节点的度

B) 拓扑排序

C) 求最短路径

D) 求关键路径

  1. 已知无向图的邻接表如下图所示，根据算法，则从顶点 $\mathbf{V}_0$ 出发按深度优先遍历的顶点序列是（ ）。

A) $\mathrm{V}_1\mathrm{V}_3\mathrm{V}_2\mathrm{V}_0$

B) V0 V2 V3 V1

C) $\mathrm{V}_0\mathrm{V}_3\mathrm{V}_2\mathrm{V}_1$

D) $V_{0} V_{1} V_{2} V_{3}$

  1. 能进行二分查找的线性表，必须以（ ）。

A) 顺序方式存储，且元素按关键字分块有序
B) 链式方式存储，且元素按关键字有序
C) 顺序方式存储，且元素按关键字有序
D) 链式方式存储，且元素按关键字分块有序

  1. 快速排序在下列哪种情况下最易发挥其长处。（ ）

A) 被排序的数据中含有多个相同排序码
B) 被排序的数据已基本有序
C) 被排序的数据完全无序
D) 被排序的数据中的最大值和最小值相差悬殊

  1. 非空的单循环链表的头指针为 head，尾指针为 rear，则下列条件成立的是（ ）。

A)rear->next->next= =head

B) rear->next = =head

C) head->next = rear

D) head->next->next = rear

  1. 已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的深度优先遍历序列为（ ）。

A) a d b e f c
B) a d c e f b
C) a d c b f e
D) adefcb

二、填空题（本大题共15小题，每小题2分，共30分）

  1. 假设长度为 $n$ 的顺序表查找每个数据元素的概率相等，即 $P_i = 1 / n$ ，则顺序查找算法的平均查找长度为：__________。
  2. 设指针变量 p 指向单链表中结点 A, 则删除结点 A 的语句序列为: q=p->next; p->data=q->data; p->next= ____________; fee(q)。
  3. 设栈 S 和队列 Q 的初始状态为空，元素 S1，S2，S3，S4，S5，S6 将依次入栈 S，一个元素出栈后即进入队列 Q。如果这 6 个元素的出队顺序为 S2，S3，S4，S6，S5，S1，则栈 S 的容量至少应该是 _______，上述过程才不会错。
  4. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为 ________（要求填写大 O 表示的时间复杂度）。
  5. 假定一棵树的广义表表示为 A (C, D (E, F, G), H (I, J))，则树的深度为 ________。
  6. 设有 $n$ 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则编号为 i 的节点的右孩子结点的编号为 ________。
  7. 一棵具有257个结点的完全二叉树，它的深度为
  8. 设某无向图中顶点数和边数分别为 $n$ 和 $e$ ，所有顶点的度数之和为 $d$ ，则 $e =$ ________。
  9. 具有 100 个叶子节点的哈夫曼树中, 其节点总数为_____个。
  10. 含有 12 个节点的平衡二叉树的最大深度是 ________（设平衡二叉树的根节点的深度是 1）。
  11. 设二叉树 $T$ 的前序遍历序列和中序遍历序列分别是：b，d，c，a，e，f和c，d，e，a，b，f；则其后续遍历序列为
  12. 设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 x，则最多需要比较 _______ 次就可以断定数据元素 x 是否在查找表中。
  13. 设有一稀疏图 G，则 G 采用 _______ (若只考虑采用邻接矩阵或邻接表存储)存储较省空间。
  14. 折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素 20，它将依次与表中元素 ________ 比较大小。
  15. 在插入和选择排序中，若初始数据基本正序，则选用 ______ 排序。

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

  1. 将如题图 1 (a) 所示的一棵树转换为对应的二叉树，并画出二叉树；将图 1 (b) 所示的一棵二叉树转换成森林。


(a)


(b)
图1

  1. 如题图 2 所示有一棵二叉树, 写出该二叉树的先根遍历 (先序遍历) 序列和中根遍历 (中序遍历) 序列。


图2

  1. 如题图 3 矩阵表示一个无向连通网（其中 $\infty$ 表示没有边，距离为 $\infty$ ），试画出它所表示的连通网及该连通网的最小生成树。

  2. 如题图 4 是带权的有向图 G，画出其邻接表（要求：邻接表中）并根据邻接表写出其深度优先遍历序列。


图4

  1. 试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。
  2. 请利用迪杰斯特拉（Dijkstra）算法求出图5中从顶点 $\mathbf{V}_0$ （标号为0的顶点）到其他各顶点间的最短路径，请跟据表中已经完成的寻找第1个最短路径的点提示完成下表。


图5

终点从V0到各终点的D值和最短路径的求解过程
i=1i=2i=3i=4i=5i=6
V113<V0,V1>
V28<V0,V2>
V3∞
V430<V0,V4>
V5∞
V632<V0,V6>
VjV2.
S{V0,V2}
  1. 已知哈希函数为 $\mathrm{H}(\mathrm{K}) = (3^{*}\mathrm{K})$ mod 11，采用线性探测再散列解决冲突 $\mathrm{H_i = (H(K) + di)mod11}$ ，对下列线性表(6，8，10，17，20，23，53，41，54，57)求其哈希表。要求将关键字23，53，41，54和57依次存入到下面的哈希表中，并填写相应的探测次数。

答：哈希表如下：

012345678910
哈希表82061017
探测次数11113

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

  1. 请设计一个算法，将有 $n$ 个元素的数组 A 中的元素 A[0]至 A[n-1]循环右移 k 位，并要求只用一个元素大小的附加存储，元素移动或交换次数为 O(n)。要求先给出算法思想，再描述算法，必要时请给予注释和说明。

  2. 设计在二叉排序树上查找节点的值等于 key（int 类型）的节点算法。其中二叉树用二叉链表的形式表示，定义如下：

typedef struct node{ int key; struct node \* lchild,\* lchild; }BinNode,\* bitree;

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