重庆邮电学院

2006年硕士学位研究生入学考试试题

考试科目：数据结构

试题编号：41026

招生专业：计算机应用技术、计算机软件与理论、软件工程硕士

考试科目：数据结构 试题编号：418(450)

注：答题（包括填空题、选择题）必须答在专用答题纸上，否则无效

一、单项选择题（每小题1分，共15分）

  1. 两个各有 $n$ 个元素的有序列表并成一个有序表，其最少的比较次数是

A. n

B. ${2n} - 1$

C. $2 \mathbf{n}$

D. $n - 1$

  1. 设循环队列中数组的下标范围是 $0 \sim n - 1$ , f 表示队首元素的前驱位置, r 表示队尾元素的位置, 则队列中元素个数为____。

A. $r - f$

B. $r - f + 1$

C. $(r - f + 1)$ mod n

D. $(r - f + n) \bmod n$

  1. 一个5行6列的二维数组s,采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是

A. 7

B. 8

C. 9

D. 10

  1. 设只含根结点的二叉树的高度为 1, 则高度为 $n$ 的二叉树中所含叶子结点的个数最多为______个。

A. $2 \mathrm{n}$

B. n

C. $2^{n - 1}$

D. ${2}^{n} - 1$

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

A. 2h

B 2h-1

C. $2 h + 1$

D.h+1

  1. 对一棵二叉检索树进行 ______ 得到的结点序列是一个有序序列。

A. 前序周游 B. 中序周游 C. 后序周游 D. 层次周游

7.一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是

A. 4,1,2,3

B. 4, 3, 2, 1

C. 2, 4, 3, 1

D. 3, 4, 2, 1

  1. 下列编码中____不是前缀码。

A. ${00, 01, 10, 11}$

B. ${0, 1, 00, 11}$

C. ${0, 10, 110, 111}$ D. ${10, 110, 1110, 1111}$

  1. 在含 $n$ 个顶点和 $e$ 条边的有向图的邻接矩阵中，零元素的个数为____.

A.e B.2e C.n²-e D.n²-2e

  1. 具有 $n$ 个顶点和 $e$ 条边的图的深度优先搜索算法的时间复杂度为

A. $0(n)$ B: $0(n^{3})$ C. $0(n^{2})$ D. $0(n + e)$

11.如果具有 $\pmb{n}$ 个顶点的图是一个环，则它有 棵生成树。

A. n B. $n + 1$ C. $n - 1$ D. 2n

12 堆排序算法在平均情况下的时间复杂度为

A. $0(n)$ B. $0(\mathrm{n1}\log \mathrm{n})$ C. $0\left(\mathrm{n}^{2}\right)$ D. $0(\log n)$

13.在待排序数据已基本有序的前提下，下述排序方法中效率最高的是

A. 直接插入排序 B. 直接选择排序 C. 快速排序 D. 归并排序

  1. 在理想情况下，散列表中查找元素所需的比较次数为

A. n B. 0 C. n/2 D. 1

  1. 在一棵 $m$ 阶 $B$ 树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是

A.m B. $\mathfrak{m} + 1$ C.m-1 D.m/2

二、判断题（判断下列各题是否正确，若正确，在括号内打“√”，否则打“×”；每小题1分，共10分）

  1. 已知指针 curr 指向链表中的某结点，执行语句 curr=curr->next；不会删除该链表中的结点。 （）

  2. 若二叉树的叶结点数为 1, 则其高度等于结点数 (仅含根结点的二叉树高度为 1)。

  3. 按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问的结点。 （）

  4. 完全二叉树的某结点若无左孩子，则它必是叶结点。 （）

  5. 向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高度。 （）

  6. 对一个堆按层次周游，一定能得到一个有序序列。 （）

7.一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。（）

8.将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树. （ ）

9.任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。 （ ）

  1. 快速排序在最差情况下的时间复杂度是 $O(n^{2})$ ，此时它的性能并不比冒泡排序更好。 （ ）

三、填空题（每空2分，共20分）

  1. 具有 100 个结点的完全二叉树的叶子结点树为

  2. 由权值分别为3，9，6，2，8的叶子结点生成一棵哈夫曼树，它的外部带权路径长度为

  3. 对含 $n$ 个结点的完全二叉树按自上而下，从左到右的顺序结点编号（从0开始），则编号最小的叶子结点的编号是

  4. n个顶点的连通无向图的邻接矩阵至少有 个非零元素。

  5. 在有序表 A[1..20] 中，若需查找的元素位于 A[12]，则采用折半查找算法所比较的元素的下标依次为

  6. 要将序列 ${60, 10, 8, 40, 90, 70, 100}$ 建成堆，只需把 8 与 ______ 相交换。

  7. 从一维数组 $a[n]$ 中顺序查找出一个最大值元素的时间复杂度为 ______。

  8. 已知广义表 $\mathrm{L} = \left( {\left( {\mathrm{a},\mathrm{b},\mathrm{c}}\right) ,\left( {\mathrm{d},\mathrm{e},\mathrm{f}}\right) }\right)$ ,则运算 head(tail(head(head(tail(L)) 的结果是_____

  9. 模式串 $\mathsf{P} =$ “abaa”的 next 函数值序列为

  10. 一个两层100阶的B+树，最多可以有 条记录

四、解析题（共55分）

  1. 对二叉树中结点进行按层次顺序（每一层从左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHJ，中序序列为DBGEHJACIF，请画出该二叉树。

  2. 证明若二叉排序树中的一个结点存在两个孩子，则

①它的中序后继结点没有左孩子。

②它的中序前趋结点没有右孩子。

  1. 对下面的带权无向图采用 prim 算法从顶点①开始构造最小生成树。写出

S:顶点号Edge:(顶点, 顶点, 权值)
①°( , , , )
①( , , , )
①·( , , , )
①( , , , )
①·( , , , )
①( , , , )

  1. 已知一组关键字序列为：（17，31，13，11，20，35，25，8，4，11，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。（10分）

  2. 设散列函数为 $H(k) = k % 13$ ，散列表的地址空间为 0 到 12，用线性探查法解觉冲突，将关键字（18，22，78，205，40，16，35，104，61）依次存入该散列表中，试构造散列表，并计算在等概率下的搜索成功的平均搜索长度 ASL（搜索成功的平均搜索长度 ASLsucc 是指搜索到表中己有表项的平均探查次数。它是找到表中各个己有表项的探查次数的平均值） （10 分）

  3. 给出一组关键字 $T = {20, 3, 18, 40, 9, 30, 5, 11, 32, 7, 28}$ ，设内存工作区可容纳 4 个记录，写出用置换-选择排序得到的全部初始归并段。若某文件经内排序后得到 50 个初始归并段（初始顺串），若使用多路归并排序算法算法，并要求三趟归并完成排序，归并路数最少为多少？（10 分）

五、算法设计题（共50分）

  1. 请写一算法，在顺序表中查找指定的数据，查找成功则将该记录放到顺序表的最前面，而把其他记录后退到有个位置。（10分）

  2. 有一个由自然数构成的序列采用单链表存储，试编写算法判断该序列是否

是fibonacci序列（fibonacci序列是1，1，2，3，5，8，13，21，34，…）. （10分）

  1. 定义二叉树中两个结点之间的最小距离为：这两个结点的最近公共祖先结点分别到这两个结点的路径长度之和。请设计一个算法，找出给定二叉树中任意两个结点之间的最小距离。（15分）

  2. 设有 $n$ 个待排序元素存放在一个不带表头结点的单链表中，每个链表结点只存放一个元素，头指针为 head。试设计一个算法，对其进行自然归并排序（按照下面的提示进行）。要求不移动个结点中的元素，只修改结点中的指针。排序完成后，head 仍指示结果链表的第一个结点。（15 分）

提示：先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，然后反复进行二路归并，直到将所有子链表归并为一个有序链表为止。