2006年试题
# 重庆邮电学院
# 2006年硕士学位研究生入学考试试题
考试科目：数据结构
试题编号：41026
招生专业：计算机应用技术、计算机软件与理论、软件工程硕士
考试科目：数据结构 试题编号：418(450)
注：答题（包括填空题、选择题）必须答在专用答题纸上，否则无效
# 一、单项选择题（每小题1分，共15分）
1. 两个各有 $n$ 个元素的有序列表并成一个有序表，其最少的比较次数是
A. n
B. ${2n} - 1$
C. $2 \\mathbf{n}$
D. $n - 1$
2. 设循环队列中数组的下标范围是 $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$
3. 一个5行6列的二维数组s,采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s\[3\]\[3\]在a中的下标是
A. 7
B. 8
C. 9
D. 10
4. 设只含根结点的二叉树的高度为 1, 则高度为 $n$ 的二叉树中所含叶子结点的个数最多为\_\_\_\_\_\_个。
A. $2 \\mathrm{n}$
B. n
C. $2^{n - 1}$
D. ${2}^{n} - 1$
5. 设高度为 $h$ 的二叉树上只有度为 0 和度为 2 的结点，则此二叉树中所包含的结点数至少为个（设只含根结点的二叉树的高度为 1）。
A. 2h
B 2h-1
C. $2 h + 1$
D.h+1
6. 对一棵二叉检索树进行 \_\_\_\_\_\_ 得到的结点序列是一个有序序列。
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
8. 下列编码中\_\_\_\_不是前缀码。
A. ${00, 01, 10, 11}$
B. ${0, 1, 00, 11}$
C. ${0, 10, 110, 111}$ D. ${10, 110, 1110, 1111}$
9. 在含 $n$ 个顶点和 $e$ 条边的有向图的邻接矩阵中，零元素的个数为\_\_\_\_.
A.e B.2e C.n²-e D.n²-2e
10. 具有 $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. 归并排序
14. 在理想情况下，散列表中查找元素所需的比较次数为
A. n B. 0 C. n/2 D. 1
15. 在一棵 $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.任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。 （ ）
10. 快速排序在最差情况下的时间复杂度是 $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. 证明若二叉排序树中的一个结点存在两个孩子，则
①它的中序后继结点没有左孩子。
②它的中序前趋结点没有右孩子。
3. 对下面的带权无向图采用 prim 算法从顶点①开始构造最小生成树。写出
4. 已知一组关键字序列为：（17，31，13，11，20，35，25，8，4，11，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。（10分）
5. 设散列函数为 $H(k) = k % 13$ ，散列表的地址空间为 0 到 12，用线性探查法解觉冲突，将关键字（18，22，78，205，40，16，35，104，61）依次存入该散列表中，试构造散列表，并计算在等概率下的搜索成功的平均搜索长度 ASL（搜索成功的平均搜索长度 ASLsucc 是指搜索到表中己有表项的平均探查次数。它是找到表中各个己有表项的探查次数的平均值） （10 分）
6. 给出一组关键字 $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分）
3. 定义二叉树中两个结点之间的最小距离为：这两个结点的最近公共祖先结点分别到这两个结点的路径长度之和。请设计一个算法，找出给定二叉树中任意两个结点之间的最小距离。（15分）
4. 设有 $n$ 个待排序元素存放在一个不带表头结点的单链表中，每个链表结点只存放一个元素，头指针为 head。试设计一个算法，对其进行自然归并排序（按照下面的提示进行）。要求不移动个结点中的元素，只修改结点中的指针。排序完成后，head 仍指示结果链表的第一个结点。（15 分）
提示：先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，然后反复进行二路归并，直到将所有子链表归并为一个有序链表为止。
| S: | 顶点号 | Edge: | (顶点, 顶点, 权值) | |
| ①° | ( , , , ) | |||
| ① | ( , , , ) | |||
| ①· | ( , , , ) | |||
| ① | ( , , , ) | |||
| ①· | ( , , , ) | |||
| ① | ( , , , ) |
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
