重庆邮电大学（重邮）802数据结构：2022年（答案&试题）

重邮802数据结构：2022年（答案&试题）

注：本套试卷由强连通计算机考研完成解析，但难免有疏漏，如果发现错误请及时与我们反馈。

勘误：对微信公众号“强连通计算机考研”回复“重邮802勘误”。

2022年答案

一、 选择题（本大题共 15小题，每小题 2分，共 30分）

二、填空题（本大题共10小题，每小题3分，共30分）

三、综合应用题（本大题共7小题，共60分）

四、算法分析与设计题（本大题共2小题，共30分）

2022年试题

一、 选择题（本大题共 15小题，每小题 2分，共 30分）

1、当输入非法错误时一个“好”的算法会进行适当处理而不会产生难以理解的输出结果。这称为算法的（）。
A可读性    B.健壮性    C.正确性   D.有穷性

2、当字符序列F4_作为一个栈的输入时，输出长度为3的且可用作C语言标识符的序列有（）个。
A.4   B.5   C.3   D.6

3、若用一个大小为7的数组来实现循环队列，且当前rear和front的值分别为0和4，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。
A.2和6    B.6和2    C.5和2    D.2和5

4、用一个栈求下列后缀表达式的值8 2 3 ^ / 2 3 * + 5 1 * -，其中：+、-、*、/、^分别是加、减、乘、除、幂运算符，当扫描到第一个*时，栈顶部2个元素是（）。
A. 6, 1    B. 5, 7   C. 3, 2    D. 1, 5

5、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A.空或只有一个节点   B.高度等于其节点数
C.任一节点无左孩子   D.任一节点无右孩子

6、一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是（）。
A.不确定   B.0   C.1   D.2

7、( )占用的额外空间的空间复杂性为O(1)。
A.堆排序算法    B.归并排序算法
C.快速排序算法   D.以上答案都不对

8、在Huffman编码中，若编码长度只允许小于等于3，则除了已对两个字符编码为0和10外，还可以最多对（）个字符编码。
A.2   B.3   C.4   D.5

9、设一个稀疏矩阵有1000行850列，其中有800个非0元素。设每个整数占2B，数据值占4B，则用三元组表存储该矩阵时所需字节数是（ ）。
A.1600   B.3200    C.6400   D.9600

10、用于求无向图的所有连通分量的算法是（）。
A.广度优先遍历    B.拓扑排序   C.求最短路径   D.求关键路径

11、若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序   B.堆排序   C.归并排序    D.直接插入排序

12、下列（）的邻接矩阵是对称矩阵。
A.AOV网   B.AOE网    C.有向图   D.无向图

13、将元素71、65、84、69、67、83逐个插入空的二叉排序树(BST)中，最低层的元素为（）。
A.65   B.67    C.69    D.83

14、具有12个关键字的有序表，折半查找的平均查找长度为（）。
A.3.1    B.4   C.2.5   D.5

15、若在一棵m阶B树的结点中插入新关键码后该结点必须分裂为两个结点，那么在插入前结点的关键码数应为（）。
A.m    B.m-1    C.m+1   D.m-2

二、填空题（本大题共10小题，每小题3分，共30分）

16、对于具有144个记录的文件，若采用分块查找法，且每块长度为8，采用顺序查找确定所在的块，则平均查找长度为（）。
17、The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue. Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ( ).
18、有n个字符的字符串的非空子串个数最多有（ ）个。
19、用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为（ ）。
20、由3个结点可以构造出（ ）种不同的二叉树。
21、若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有（ ）棵树。
22、对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为（ ）。
23、（ ）是哈希表的一个重要参数，它反映哈希表的装满程度。
24、硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂度为的算法，若用ABC公司的计算机能在1小时内解输入规模为n的问题，那么用XYZ公司的计算机在1小时内能解输入规模为（ ）的问题。
25、表达式A/B+D$E+F/H中，运算符的优先级由高到低依次为+，/，$，均右结合，则相应的后缀式是（ ）。

三、综合应用题（本大题共7小题，共60分）

26、(5分）阅读代码，函数print()接收二叉查找树/二叉排序树(BST)的根和一个正整数k作为参数。请：

// a BST node
struct node {
	int data;
	struct node *left, *right;
};

int count = 0;
void print(struct node *root, int k)
{
	if (root != NULL && count <= k)
	{
		print(root->right, k);
		count++;
		if (count == k)
			printf("%d ", root->data);
		print(root->left, k);
	}
}

(1) 简述该代码的功能
(2) print(root, 3)的输出是什么?其中root表示下图BST树的根。

27、(5分)有一段代码：

int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] >= a[k]) count++;

假设 N = 1000 时，执行这段代码需要 1秒时间。现在对这段代码的运行时间（秒）进行预估，请用一个关于 N的函数来表示。

28、(10分）设A,B,C,D,E五个字符的编码分别为1,2,3,4,5，并设标识符按以下次序出现：AA, BB, BD, BE, AB, AD, CD, BC, AE, DD。要求用哈希（Hash）方法将它们存入具有10个位置的表中。
(1) 将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
(2) 采用线性探测再散列法解决冲突，写出上述各关键字在表中的位置，并给出比较次数；即：填写完整下表。

29、（10分）已知一棵二叉查找树/二叉排序树(BST)的先序遍历序列为30, 20, 10, 15, 25, 23, 39, 35, 42。
（1）请画出此二叉树的形态。
（2）请给出这棵树的后序遍历序列。
（3）画出此二叉树的中序线索二叉树。
（4）画出与此二叉树对应的森林。

30、（12分）已知图G如右边所示：

31、（8分）考虑序列: ‘mississippi’，请：
（1）采用赫夫曼（Huffman）编码算法对上述序列编码，给出相应的Huffman树，以及每个字符的Huffman码。
（2）一共需要多少bit位？

32、（10分）下表32-1中第0行是待排序序列的原始输入(Eagle Ant Dog Frog Cat Horse Bee Goat);其他各行是5种排序算法得到的某个中间步骤的内容。

表32-2列出了6种排序算法。请按行序直接给出每行对应排序算法的编号。每个编号只使用一次。

表32-1：

表32-2:

四、算法分析与设计题（本大题共2小题，共30分）

33、（15分）设计一个算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。要求：
（1）描述算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释；
（3）说明所设计算法的时间复杂度和空间复杂度。
提示：其中稀疏多项式采用的循环链表存储结构LinkedPoly定义为

typedef struct PolyNode {
	float coef; //单项式的系数
	int exp; 	//单项式的指数
	struct PolyNode *next;
} PolyNode;
typedef PolyNode* LinkedPoly;

算法描述，只需要给出如何将循环链表L分成满足要求的两个循环链表的操作，即完善下述函数：

void Divide (LinkedPoly L){
    ……
}

34、从根到叶子的最大距离称为树的半径。给定一个无向连通图，写一个算法找出半径最小的生成树。要求：
（1）描述算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释；
（3）说明所设计算法的时间复杂度和空间复杂度。