重庆邮电大学

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

科目名称： 数据结构

科目代码： 802

考生注意事项

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

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

  1. 计算机算法指的是解决问题的有限运算序列，它必须具备输入、输出和（ ）等5个特性。

A. 可执行性、可移植性和可扩充性
B. 可行性、确定性和有穷性
C. 确定性、有穷性和稳定性
D. 易读性、稳定性和安全性

  1. 某算法代码段如下，其时间复杂度是（）。
for(i=1; i<=n; ++i)  
    for(j=1; j<=n; ++j)  
    { c[i][j]=0;  
        for(k=1;k<=n; ++k)  
            c[i][j]+=a[i][k]*b[k][j];  
    }

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

B $O(n^{3})$

C. $O(n)$

D. $O(n \log_2 n)$

  1. 和顺序（连续）存储结构相比，线性表的链式存储结构的优点是（ ）。

A. 所有操作/运算的算法都简单

B. 便于随机存取

C 便于插入和删除

D. 便于查找

  1. 在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双向链表

D. 仅有尾指针的单循环链表

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

A. 插入

B. 删除

C. 排序

D. 查找

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

A. 队列

B. 栈

C. 链表

D. 都不是

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

A. 都是先进先出

B. 都是后进先出

C 不会删除中间的元素

D. 完全没有共同点

注：所有答案必须写在答题纸上， $^\text{业}$ 卷卜作答无效！ 第2页（共6页）

  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 中, 每个元素 A 的长度为 3 个字节, 行下标 i 从 1 到 8 , 列下标 j 从 1 到 10 , 从首地址 SA 开始连续存放在存储器内, 该数组按行优先存放时, 元素 A[8][5]的起始地址为 ( )。

A. SA+141

B. SA+222

C. SA+144

D. SA+225

10.二叉树中（树根为第1层）第5层上的结点个数最多为（ ）

A. 8

B. 15

C. 16

D. 32

  1. 高度为3的二叉平衡树（空树高度为0）最少有（）个结点。

A. 4

B. 15

C. 11

D. 7

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

A. 2h

B. $2 \mathrm{h} - 1$

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

D.h+1

  1. 将一棵有 100 个结点的完全二叉树从上到下（根这一层），每一层上从左到右依次对结点进行编号，根结点的编号为 1，则编号为 49 的结点的左孩子编号为（）。

A 98

B. 48

C. 99

D. 50

14.一棵哈夫曼树（Huffman Tree）的4个叶子结点的权值分别为3，9，2，7，该树的带权路径长度为（）。

A 38

B. 37

C. 44

D. 46

15.图的邻接矩阵表示法适用于表示（ ）。

A. 无向图

B. 有向图

C. 稠密图

D. 稀疏图

  1. 设图连通 G 采用邻接表存储，则深度优先遍历算法的时间复杂度是（）。

A. $\mathrm{O}\left( \mathrm{n}\right)$

B. $\mathrm{O}\left( {\mathrm{n} + \mathrm{e}}\right)$

C.O(n²)

D.O(n*e)

  1. 顺序查找算法在查找成功情况下的平均比较次数是（ ）。

A. n

B. $n^{2}$

C. $\log (\mathfrak{n})$

D $(n + 1) / 2$

  1. 散列（哈希，Hash）函数有一个共同性质，即其函数取值在值域里呈现（）。

A. 均匀分布

B. 正态分布

C. 泊松分布

D. 任意分布

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

A. 直接插入排序

B. 快速排序

C 简单选择排序

D. 归并排序

  1. 以比较为基础的排序算法在最坏情况下的计算时间复杂度下界为（）

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

B. $O(\log_2 n)$

C. $O(n)$

D. $O(n \log_2 n)$

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

  1. 求整数 $n (n \geq 0)$ 阶乘函数的递归算法如下，其时间复杂度是（）
longFactorial(longn){ if  $(n = = 0)$  return1; else return  $n^{*}$  Factorial(n-1);   
}

  1. 某算法中的语句频度之和为 $\mathrm{T}(\mathrm{n}) = 2\mathrm{n}^2 + 5\mathrm{n} + 2$ ，则其时间复杂度为（ ）。

  2. 已知栈的输入序列为 1,2,3,4,5,6,7 输出序列为 a1, a2, a3, a4, a5, a6, a7 符合 a2=7 条件的输出序列共有（）个。

  3. 采用特殊字符作为结尾的顺序存储方式存储，则串“MyDataS”最少需要（）个字符的存储空间。

  4. 已知某二叉树的先序序列 ABCDEGF，中序序列 CBEGDFA，那么它的后序遍历序列是（）

  5. 已知完全二叉树的第 4 层（根结点为第 1 层）总共只有 3 个结点，则其叶子结点数是（ ）。

  6. 某表达式二叉树按后序遍历的结果为 $abcd - * + ef / -$ ，令 $a = 2, b = 3, c = 4, d = 5, e = 6, f = 2$ ，则该表达式的值等于（）。

  7. 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是（）。

  8. 高度为 $\mathrm{k}$ (空树高度为 0 ) 的完全二叉树至少有( )个结点。

  9. 含 n 个顶点的无向连通图中至少含有 ( ) 条边。
    11．在具有20个元素的顺序表（查找表）上进行折半查找（二分查找），需比较五次并查找成功的元素个数是（ ）？

  10. 判别下面的序列是否为堆（若是，明确小根堆或大根堆）？(100,86,48,73,35,39,42,57,66,21);

  11. 应用 Dijkstra's 算法 (单源最短路径) 求图 1 顶点 v6 到其他顶点的最短路径, 最先求出的是顶点 v6 到顶点 ( ) 的最短路径。

  12. 有 8 个球队参加的某联赛按单循环方式进行比赛, 其需要进行的比赛场次为( ), 和完全无向图的边数一样多。

  13. 由6个权值构造的哈夫曼树（Huffman Tree）有（ ）个结点。

  14. 在非空 $\mathbf{m}$ 阶 $\mathbf{B}$ 树上，除根结点以外的所有其他内部结点含有（ ）棵子树。

  15. 给出图2的一个拓扑序列（ ）。


图1


图2

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

  1. 在一个长度为 $n$ 的单链表 $\mathbf{L}$ 中, 现需删除链表中 *p 结点的前驱结点, 试简要说明该操作的实现思想, 并分析时间复杂度。
  2. 具有 8 个结点的某森林的孩子一兄弟存储结构刚好构成完全二叉树。请画出原来的森林的结构。
  3. 现有无向图如图 3 所示, 从顶点 F 开始使用 Prim(普里姆)算法求图的最小生成树, 要求必须清楚地表明其生成过程。
  4. 现有无向图如图 3 所示, 完成下面任务: 1) 画出图的邻接矩阵图示; 2) 从顶点 H 开始对图进行广度优先遍历, 写出遍历结果。
  5. 已知一棵二叉排序树结构如图 4 所示, 各结点的数据从小到大依次为 15,25,37,49,51,66,请重建出完整的原二叉树。
  6. 设 Hash 函数为 H(key) = key mod 7，哈希表的地址空间为 $0,1,\ldots,10$ ，开始时哈希表为空，用平方探测法解决冲突。回答下列问题：
    1）请画出依次插入键值9，14，10，30，56后的哈希表？
    2）对表中关键字14，30和56进行查找时，所需进行的比较次数各为多少？
    7．对关键字序列(51，32，66，92，75，16，25，46)按从小到大进行快速排序。设选第一个元素为支点/参考值（pivot)，写出排序过程中第1趟的划分结果；


图3


图4

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

  1. 现有一棵二叉查找（排序）树（Binary Search Tree）BST，以二叉链表形式存储，进行中序遍历可得到从小到大排列的有序序列。试设计一算法，对该二叉查找树进行变换，使得对新的二叉树进行中序遍历可得到从大到小排列的有序序列。要求：

（1）描述算法的基本设计思想。
（2）根据设计思想，描述算法的详细实现步骤，可使用伪代码、C或C++或JAVA语言，关键之处给出简要注释。

有关的数据结构已描述如下：

struct Binary_node {
    // 二叉树结点
    int data;
    Binary_node *left;
    Binary_node *right;
}
  1. 某顺序表中的数据序列为降序序列，试设计一算法将数据序列变换为升序序列。要求：

（1）描述算法的基本设计思想。
（2）根据设计思想，描述算法的详细实现步骤，可使用伪代码、C 或 C++ 或 JAVA 语言，关键之处给出简要注释。
（3）分析算法时间复杂度、空间复杂度。