重庆邮电大学

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

科目名称： 数据结构A

科目代码： 802

考生注意事项

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

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

1.（ ）是数据的最小单位。

A. 数据元素

B. 数据项

C. 数据对象

D. 数据结构

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

A. $n - i + 1$

B.i

C. 1

D. n-i

  1. 单链表的存储密度（ ）。

A. 大于 1

B. 等于 1

C. 小于 1

D. 不能确定

  1. 将长度为 $n$ 的单链表链接在长度为 $m$ 的单链表之后的算法的时间复杂度为（ ）。

A. $0(1)$

B. $O(n)$

C. $O(m)$

D. $O(m + n)$

  1. 设计一个把十进制数转换为八进制数的算法，采用（）数据结构最佳。

三栈

B. 队列

C. 顺序结构线性表

D. 链式结构线性表

  1. 一个栈的输入序列为 a, b, c, d, 下面哪一个序列不可能是这个栈的输出序列? ( )

A. b, c, d, a

B.d，c，a，b

C.a.c.b.d

D. c, d, b, a

  1. 若用一个大小为 6 的数组来实现循环队列, 且当前 rear 和 front 的值分别为 0 和 3。当从队列删除两个元素, 再加入一个元素后, rear 和 front 的值分别为 ( )。

A. 1 和 5

B. 2 和 4

C. 4 和 2

D. 5 和 1

  1. 若串 $S =$ “database”，其非空子串数目为（ ）。

A. 8

B. 37

C. 36

D. 9

  1. 数组 a 中，每个元素 a[i, j] 的长度为 4 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址连续存放在存储器内，该数组按行优先存放时，元素 a[7][4] 的起始地址为（）。

A. $a + {192}$

B. $a + 188$

C. a+300

D. a+296

  1. 若广义表 $\mathbf{L}$ 满足 $\operatorname{Head}(\mathbf{L}) = \operatorname{Tail}(\mathbf{L})$ ，则 $\mathbf{L}$ 为（ ）。

A. ()

B. $((\quad))$

C. $((\cdot), (\cdot))$

D. $((\cdot), (\cdot), (\cdot))$

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

A.2h

B.2h-1

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

D.h+1

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

  1. 对二叉树所有结点进行编号(从 1 开始), 要求每个结点的编号大于其左右孩子的编号, 同一结点的左右孩子中, 其左孩子的编号小于其右孩子的编号, 则可采用 ( ) 次序的遍历实现编号。

A. 先序

B. 中序

C. 后序

D. 从根开始的层次遍历

  1. G 是一个连通图，共有 28 条边，则该图至少有（）个顶点。

A. 6

B. 7

C. 8

D. 9

  1. 若一个具有 $n$ 个顶点， $k$ 条边的无向图是一个森林 $(N > K)$ ，则该森林中必有（）颗树。

A. 1

B. k

C. n

D. n-k

  1. 在二叉排序树中，关键值最大的结点（ ）。

A. 左指针一定为空

B. 右指针一定为空

C. 左右指针均为空

D. 左右指针均不为空

  1. 含有 12 个结点的平衡二叉树的最大深度是（ ）。

A. 3

B. 4

C. 5

D. 6

  1. 在非空 $\mathrm{m}$ 阶 $\mathrm{B}$ -树上,除根结点以外的所有其他非终端结点 ( )。

A.至少含有「m/2」棵子树

B.至多含有「m/2」棵子树

C.至少含有 $\lfloor m / 2\rfloor$ 棵子树

D.至多含有 $\lfloor m / 2\rfloor$ 棵子树

  1. 下列序列中，（）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。

A. [da,ax,eb,de,bb] fp [hq,gv]

B. [cd,eb,ax,da] fp [hq,gv,bb]

C. [gv,ax,eb.ed,bb] fp [da,hq]

D. [ax,bb,cd.da] fp [eb,gv,hq]

  1. 在文件“局部有序”的情况下，最佳内部排序是（ ）。

A. 直接插入排序

B. 快速排序

C. 简单选择排序

D. 归并排序

  1. 时间复杂度不受待排序序列初始状态的影响，总是 $O(n^{2})$ 的是（ ）。

A. 直接插入排序

B. 快速排序

C. 简单选择排序

D. 归并排序

二、填空题（本大题共16小题，每小题2分，共32分）

  1. 若一个算法的语句频度之和是 $T(n) = 15n + 10\mathrm{logn}$ ，则算法的时间复杂度为
  2. 表长为 $n$ 的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素需移动元素的平均个数为
  3. 设栈 S 和队列 Q 的初始状态皆为空，元素 a、b、c、d、e 和 f 依次通过一个节点，注：所有答案必须写在答题纸上。试卷上作答无效！ 第 3 页（共 6 页）

栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是c、e、d、f、b、a则栈S至少应该容纳 个元素。

  1. 用数组 Q(其下标在 0...n-1，共有 n 个元素)表示一个循环队列，f 为当前对头元素的前一位置，r 为队尾元素位置，假定队列中元素个数总小于 n，求队列中元素个数的公式是

  2. 采用特殊字符作为串的结束，串 $S =$ “Windows”需要至少长度为 ______ 的字符数组存放。

  3. 已知数组 A[1..10, 1..10]为对称矩阵，其中每个元素占 4 个单元。现将其下三角部分按行优先次序存储在起始地址为 1000 的连续内存单元中，则元素 A[5, 6]对应的地址为 ________。

  4. 将一个 A[0..99, 0..99] 的三对角矩阵，按行优先存入一维数组 B[0..297] 中，A 中元素 A[65][65] 在 B 中的位置 k 为 ________。

  5. 有 $n$ 个结点的二叉树，已知叶子结点个数为 $n_0$ ，则度为 1 的结点的个数 $n_1 =$ ________。

9.一棵有124个叶子结点的完全二叉树，最多有 个结点。

10.具有 $\pmb{n}$ 个结点的满二叉树，其叶子结点有 个。

  1. 在序列(3,6,10,12,15,18,22,24,27,42,5c)中采用折半查找(二分查找)方法查找元素50，需要进行 次元素之间的比较。

  2. 有 $n$ 个顶点的连通图用邻接矩阵表示时，该矩阵至少有 ______ 个非零元素。

13.下图的拓扑排序序列是

  1. 若对序列(45, 38, 65, 97, 76, 12, 28, 56)采用直接选择排序法排序，则第二趟结束后序列的状态是

  2. 高度为 4 的二叉平衡树最少有 _______ 个结点。

  3. 对于键值序列 ${11, 13, 10, 18, 50, 15, 7, 20, 25, 90}$ ，建立初始堆，必须从键值为 ______ 的结点开始对每个结点进行一次堆调整。

三、问答题（本大题共6小题，每小题8分，共48分）

  1. 在双循环链表中，写出在指针 $\mathfrak{p}$ 所指结点之后插入指针s所指结点的执行语句序列。结点定义如下：
struct Node{ char data; Node \*next; Node \*prior; };
  1. 已知二叉树的先序序列和中序序列分别为ABDGCEFH和DGBAECHF：

（1）画出该二叉树；
（2）写出此二叉树的后序序列；
（3）画出与此二叉树对应的森林。

  1. 已知由 12 个关键字构成的序列 18、31、13、11、20、35、25、8、4、24、40、27:

（1）请画出该序列的二叉排序树；
（2）给出删除结点18后的二叉排序树。

  1. 已知初始序列（50, 80, 63, 45, 48, 92），写出直接插入排序的各趟排序的结果。
  2. 设 Hash 函数为 $\mathrm{H}(\mathrm{K}) = \mathrm{Kmod}7$ ，哈希表的地址空间为 0, 1, 2, 3, 4, 5, 6，开始时哈希表为空，用二次探测再散列法解决冲突，请画出依次插入键值 16、21、23、6、30、12、18 后的哈希表。
  3. 已知序列 45、15、20、35、25、60，请画出依次插入该序列的 AVL 树（平衡二叉树）。

四、算法应用、分析题（本大题共2小题，第1小题12分，第2小题8分，共20分）

  1. 设一个无向网 $G$ 如下：

（1）请写出图G的邻接矩阵A；

（2）如果对某个顶点的邻接点的访问顺序按序号从小到大排列，请写出从顶部开始，注：所有答案必须写在答题纸上，试卷上作答无效！ 第5页（共6页）

点v1出发，按“深度优先”和“广度优先”搜索方法遍历网G所得到的顶点序列：

（3）从顶点v1出发，按照最小生成树的Prim算法，画出网G的一棵最小生成树。

  1. 已知某字符串 S 中共有 A、B、C、D、E、F、G 和 H 共 8 种字符，各种字符分别出现 2 次、1 次、4 次、5 次、7 次、3 次、4 次和 10 次，对该字符串用 ${0,1}$ 进行前缀编码：

（1）请画出对应的Huffman树，并给出各字符的前缀编码：
（2）该字符串S的编码有多少位？

五、算法设计题（本大题共1小题，共10分）

  1. 有一个单链表 L（至少有一个结点），其头结点指针为 L，编写一个过程将 L置逆，要求逆转在原链表上进行。单链表中的结点定义如下：
struct Node {
    char data;
    Node *next;
};