2022春季数据结构期中考试总结_对任意给定的含 n (n>2) 个字符的有限集 s,用二叉树表示 s 的哈夫曼编码集和定长

经过考前的三天复习，最终斩获93分的不错成绩，在此进行考后总结。希望以后再接再厉。

---

判断题

1.若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。

解析:可能会超出表容量，插入失败

平方探测的整体流程
平方探测的整体流程和线性探测基本相似，但是线性探测是没有③
①根据哈希函数算出Hashval，i 初始化为零，判断HashTable[Hashval]是否被占用，如果没被占用，则Hashval就是根据哈希函数算出的值，跳出平方探测；如果被占用则向右探测（执行②）；
②判断HashTable[Hashval + i * i]是否被占用，如果没被占用，则Hashval = Hashval + i * i，跳出平方探测；如果被占用则向左探测（执行③）；
③判断HashTable[Hashval - i * i]是否被占用，如果没被占用，则Hashval = Hashval - i * i，跳出平方探测；如果被占用则i++继续向右探测（执行②）；

---

2.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

---

3.在散列中，函数“插入”和“查找”具有同样的时间复杂度。

解析:插入和查找具有同样的时间复杂度O(1)。

---

4.在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。

解析:访问结点的时间复杂度为O(N)

---

5.非空二叉树的形态：一棵非空二叉树，若先序遍历与后序遍历的序列相反，则该二叉树只有一个叶子结点。

解析:因为题中交代了非空二叉树，而如果该二叉树只有根节点时满足所有结点均无左孩子，所有结点均无右孩子。而显然此状态下，三种遍历顺序的结果都相同。先序：根左右 后序：左右根。当该数只有两个节点是，可以省略为 先序：根->孩子 后序：孩子->根，故该二叉树只有一个叶子节点。

---

6.在检索一个单词时，用哈希算法比用搜索树要快。

---

7.循环队列也存在空间溢出的问题。

解析:循环队列解决的是“假溢出”问题，但是仍然出现真正的溢出问题。假溢出指的是下标溢出，真溢出指的是空间溢出。循环队列面临着数组可能溢出的问题。

---

8.二叉搜索树的查找和折半查找的时间复杂度相同。

折半查找：必须要求记录有序，采用顺序存储，利用这个特点，所以折半查找的效率也比顺序查找高，对于数量非常大时，非常快，时间复杂度为$O(logN)$。
二叉搜索树：若它的左子树不为空，则左子树上所有节点的值均小于根节点。若它的右子树不为空，则右子树上所有节点的值均小于根节点，它的左右子树都是二叉查找树。
所以二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系。但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足$O(logN)$的。
例如一棵只有多层左子树的二叉排序树。只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。

---

9.对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。

解释:考察哈弗曼树的构造方法，哈弗曼树的构造思想就是贪心的思想，每次选择权值最小的两个节点来形成新的节点，自底向上建树，因此对于一棵哈弗曼树来说，树中任一非叶节点的权值一定不小于下一层的任意节点的权值。

---

10.在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。

解释:考察二叉搜索树的构造方法。二叉搜索树每次插入一个数时，都需要从句根节点开始比较，小于往左子树比较，大于往右子树比较。而本题中25不能在39的右子树上的。

---

11.算法可以没有输入，但是必须有输出。

解释:考察算法的特性
①有穷性 执行有穷步之后结束
②确定性 算法中每条指令都必须有确切的含义，不能含糊不清。
③算法必须有0个或者0个以上的输入
④算法必须有1个或者1个以上的输出
⑤有效(可行)性 算法的每个步骤都能有效执行并能得到确定的结果。

---

12.将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是$O(logN)$。

解释:二叉查找的平均复杂度是$O(logN)$，但是二叉查找不能用链表存储的，这是由链表的特性决定的。链表是很典型的顺序存取结构，数据在链表中的位置只能通过从头到尾的顺序检索得到，即使是有序的，要操作其中的某个数据也必须从头开始。
这和数组有本质的不同。数组中的元素是通过下标来确定的，只要你知道了下标，就可以直接存储整个元素，比如a[5]是直接的。链表没有这个，所以折半查找只能在数组上进行。

---

13.任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。

解释:二叉 搜索/排序/查找 树的特点：①左孩子小于根 ②右孩子大于根

---

14.《数据结构》是一门研究数值计算的程序设计问题的学科。

解释:数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的关系和运算等的学科。

---

15.所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。

解释:循环队列指的是后者，用数组表示的队列，利用求余数运算使得头尾相接

---

16.哈夫曼树中一定没有度为 1 的结点。

解释:哈夫曼树的构造总是以两棵值最小的树合并，每次合并都是两棵子树，不会存在度为1的节点。

---

单选题

1.若二叉搜索树是有N个结点的完全二叉树，则不正确的说法是：

解释:最大值在右子树上，但不一定是叶子节点

---

2.栈和队列的共同点是（ ）。

解释:不写了吧

---

3.将 26, 13, 44, 51, 98, 37, 66, 73 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？

解释:

---

4.一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。

解释:通过分支可以确定该二叉树边的个数为60，由一颗树的性质：结点等于边+1【n= k+ 1】，那么总结点个数为61，叶子节点的个数为16。

---

5.对于先序遍历与中序遍历结果相同的二叉树为（ ）

解释:某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。因为 前序序列：根左右 中序序列：左根右

---

6. 对一个长度为 10 的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是（ ）。

解释:向下查找方法，查找下标(从1开始)依次为：5，2，1，故最少比较3次

---

7.下列函数中，哪两个函数具有相同的增长速度：

解释:增长速度与相当于时间复杂度，与常数无关

---

8.线性表、堆栈、队列的主要区别是什么？

解释:不写了吧

---

9.一棵二叉树中有7个度为2的结点和5个度为1的结点，其总共有（ ）个结点。

解释:树的边为7 * 2 + 5 * 1 = 19，总共19+1个点

---

10.一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是( )。

解释:树的边为20 * 4 + 10 * 3 + 1 * 2 + 10 * 1 = 122，总共点数为(122 + 1)叶子节点即度为0的结点，那么叶子节点的个数为82个

---

11.若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？

解释:

循环队列入队操作只改变front：front=(front+1)%size; （0+2）%4
出队操作只改变rear：rear=(rear+1)%size; （4+2）%6
出队前判断队空情况：队空—rear=front;
入队前判断队满情况：队满—(rear+1)%size=front;

---

12.已知普通表达式c/(e-f)*(a+b)，对应的后缀表达式是（ ）

解释:考察栈的应用。
①数字直接输出 ②符号入栈 ③’(‘符号入栈 ④’)‘是右括号，匹配左括号，所以栈顶符号依次出栈，直到’(’ ⑤符号入栈时，如果栈顶符号优先级大于当前需要入栈的符号，那么需要出栈直到栈顶元素的优先级大于(不包含等于)入栈的符号的优先级。

---

13.将 1, 2, 3, 6, 5, 4 顺序一个个插入一棵初始为空的AVL树，会经历下列哪些旋转？

解释:

---

函数题

两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

List Merge( List L1, List L2 );
1

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
1
2
3
4
5
6

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

输入样例：

3
1 3 5
5
2 4 6 8 10
1
2
3
4

输出样例：

1 2 3 4 5 6 8 10 
NULL
NULL
1
2
3

---

答案

List Merge( List L1, List L2 )
{
	List L = (List)malloc(sizeof(struct Node));
	List L3 = L;
	List P = L1 -> Next;
	List Q = L2 -> Next;
	while(P && Q){
		if(P -> Data < Q -> Data){
			L3 -> Next = P;
			P = P -> Next;
		}else{
			L3 -> Next = Q;
			Q = Q -> Next;
		}
		L3 = L3 -> Next;
	}
	L3 -> Next = NULL;
	if(P){
		L3 -> Next = P;
		P = P -> Next;
	}
	if(Q){
		L3 -> Next = Q;
		Q = Q -> Next;
	}
	//L3 -> Next = NULL;
	L1 -> Next = NULL;
	L2 -> Next = NULL;
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

---

先序输出叶结点

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义：

void PreorderPrintLeaves( BinTree BT );
1

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
1
2
3
4
5
6
7

函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void PreorderPrintLeaves( BinTree BT );

int main()
{
    BinTree BT = CreatBinTree();
    printf("Leaf nodes are:");
    PreorderPrintLeaves(BT);
    printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

输出样例（对于图中给出的树）：

Leaf nodes are: D E H I
1

---

答案

void PreorderPrintLeaves( BinTree BT )
{
	if(BT != NULL)
	{
		if(BT->Left == NULL && BT->Right == NULL)
		{
			printf(" %c",BT->Data);
		}
		PreorderPrintLeaves(BT->Left);
		PreorderPrintLeaves(BT->Right);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

---

知识点

1. %[^,]是scanf的正则表达式之一。
   一般我们是scanf("%s", xxxx)，有时我们希望空格也输入进去，可以用scanf("%[^\n]", xxxx)
%[^\n]的意思就是以'\n'作为输入的结束标志。
   同理%[^,]就是以','做输入的结束标志。
   其它的如
   %[a-z] 表示匹配a到z中任意字符
   %[aB'] 匹配a、B、'中一员
   %[^a] 匹配非a的任意字符
   fscanf的用法基本一样。
2. 数据的逻辑结构说明数据元素之间的顺序关系，其逻辑结构可用不同的存储结构实现。
3. 抽象数据类型与计算机内部表示和实现无关。
4. 算法独立于具体的程序设计语言，与具体的计算机无关。
5. 算法的优劣只考虑时间和空间，与其它的没有必然关系。
6. 数据结构在计算机内存中的表示是指 数据的存储结构
7. 在数据结构中，从逻辑上可以把数据结构分为线性结构和非线性结构
8. 线性结构：
   顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
   链式存储结构的特点是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。
9. 算法的时间复杂度取决于 问题的规模，待处理数据的初态。
10. logN的增长速度 小于 N的0.5次方。
11. 斐波那契数列Fn用递归函数计算的时间复杂度为O(Fn).
12. 任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。
13. 由一颗树的性质：结点等于边+1【n= k+ 1】。
    那么森林是由多个树构成，由N个结点、K条边的森林。故共有 n - k 棵树。
14. AVL树是平衡二叉查找树。特点：
    1.本身首先是一颗二叉搜索树
    2.带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为1.
    也就是说，AVL树，本质上是带了平衡功能的二叉查找树。
15. 循环顺序队列中是否可以插入下一个元素与队头指针和队尾指针的值有关。
16. 前缀编码满足任意一个字符的编码都不是另一个字符的编码的前缀。
17. LOC[行坐标，列坐标]表示当前元素起始存储地址
18. 平衡二叉树需要遵循二叉查找树和平衡度的问题。那么完全二叉树不一定是平衡二叉树。
19. 二叉排序树删除一个结点后，仍是二叉排序树。
20. 由三个结点可以构造多少个不同的二叉树？
    三个结点可以构成5种形态的二叉树：根左左、根左右、左根右、根右右、根右左。
21. 一颗n个结点的m叉树的高度为$lo{g}_{m}n\sim n$。
22. 大根堆
    1.可以将堆看成一颗完全二叉树
    2.可以采用顺序存储方式保存堆
    3.堆种的次大值一定在根的下一层
23. 实现两个多项式的乘法，需要让一个多项式的每一项乘以另外一个多项式的每一项，因此实现两个多项式相乘的时间复杂度只跟非零项的个数有关。
24. 当二叉树使用顺序存储结构存储时，为了保证任意性，其每个层次的所有结点（包括空结点）全部都要被存储起来。即考虑成一个满二叉树。
25. 给定一个森林的遍历序列让你计算存在几颗树。
    首先通过遍历序列构造一个唯一的二叉树，再将二叉树转换成对应的森林。
    通过孩子兄弟表示法。将根节点和左子树作为一个单独的树，右子树作为一个单独的树。
26. n个结点的二叉树二叉链表中有n+1个空链域，三叉链表中有n个（多了一个根结点中的空链域）
27. 构造哈夫曼树
    每次选择权值最小的两个点，保证左子结点小于右子结点。
    那么哈夫曼树中每一个父结点的键值都等于其子结点之和(不是子树结点)。
    哈夫曼树的带权路径长度为每个叶子节点的带权路径长度。路径×叶子节点权值
28. 哈夫曼编码问题
    左节点为0，右节点为1
    哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，哈夫曼字符的频率相同时每个字符的码长不是确定的。
29. 哈夫曼编码集和定长编码集
    对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。
    定长编码集：如 ASCII表 就是这样。
    哈夫曼编码集：1.不存在多义性 2.编码长度最小(哈夫曼树的特性,叶子结点的权重 X 路径长度之和最小)。
    出现频次不同的字符在T2中处于相同的层。
30. KMP 算法求$next$数组的值