数据结构（南京邮电大学）中国大学MOOC答案2024版100分完整版

答案: first->link==NULL

6、 在循环单链表中，设指针first指向头结点，当_____时表示链表为空。

答案: first==NULL

7、 在单链表中添加表头结点的目的是_。

答案: 方便插入和删除操作的实现

8、 循环链表的主要优点是_。

答案: 从表中任意结点出发都能扫描整个链表

9、 在包含n个结点的单链表上进行元素查找操作，平均时间复杂度是_。

答案: O(n)

10、 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用__最节省时间。

答案: 带表头结点的双循环链表

11、 在一个以 first为头指针的单循环链表中，p 指针指向尾结点的条件是____。

答案: p->link=first

12、 在单链表中指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。

答案: s->link=p->link; p->link=s;

13、 以下选项____不是链表结构所具备特征。

答案: 可随机存取任意位置元素

14、 线性表就是顺序存储的表。

答案: 错误
分析：顺序表只是线性表的一种实现

15、 线性表采用链表存储时，结点的存储空间可以是不连续的。

答案: 正确

16、 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

答案: 错误
分析：判断一种存储结构是否比另外一种存储结构好，应根据具体解决的问题来看。两种存储方式各有优点各有缺点，不存在一个比另外一个好的论断。

17、 线性表的特点是每个元素都有一个直接前驱和一个直接后继。

答案: 错误

18、 取线性表的第i个元素的时间与i值的大小有关.

答案: 错误
分析：主要是和存储结构有关，如果链接存储实现的线性表，取第i个元素的时间是和i有关，但是顺序存储时无论i等于多少，取元素的时间都是一样的，和i值本身无关。

19、 取顺序表的第i个元素的时间与i值的大小有关.

答案: 错误
分析：无关，不管i等于多少，取第i个元素所花费的时间代价就是进行一次地址计算即可。

20、 取单链表的第i个元素的时间与i值的大小有关.

答案: 正确
分析：i越大，在单链表上需要访问的元素就越多

21、 在顺序表上进行查找操作，最好情况的时间复杂度为O(n)。

答案: 错误

22、 在单链表上进行查找操作，最好情况的时间复杂度为O(1)。

答案: 正确

23、 在顺序表上，逻辑上相邻的两个数据元素 ，在物理存储位置上不一定相邻

答案: 错误

24、 在顺序表上，物理上相邻的两个数据元素之间存在逻辑关系。

答案: 正确

25、 链表方式实现的线性表中，存在逻辑关系的两个数据元素不一定存储在相邻的地址上。

答案: 正确

26、 顺序存储实现的线性表上，元素的插入操作需要移动的元素个数，与元素插入位置有关。

答案: 正确

27、 链表存储实现的线性表上，元素的插入操作需要移动的元素个数，与元素插入位置有关。

答案: 错误
分析：链表结构上进行元素插入删除，不需要移动元素

28、 线性表，删除需要移动______个元素（提示：答案不唯一，写出一个答案即可）。
答案: (以下答案任选其一都对)50;
0
分析：如果是链表结构的线性表，不需要移动元素，答案为0。如果是顺序实现的线性表，需要移动50个。

29、 线性表，在前插入一个元素，需要移动______个元素（提示：答案不唯一，写出一个答案即可）。
答案: (以下答案任选其一都对)51;
0
分析：线性表存储结构不同，对应不同的答案

30、 指针r的指向如上图所示，现在需要在r后插入一个由指针p指向的新结点，请完成如下算法填空（答案中请不要包含空格和分号）：p->llink=r;p-rlink=r->rlink;r->rlink=p;_____;
答案: p->rlink->llink=p

31、 指针r的指向如上图所示，现在需要在r后插入一个由指针p指向的新结点，请完成如下算法填空（答案中请不要包含空格和分号）：p->llink=r;p-rlink=r->rlink;r->rlink->llink=p;______;
答案: r->rlink=p

第3章 堆栈和队列（视频总时长70’54”，共计9个） 第3章 单元测验

1、 堆栈和队列的主要区别是_。

答案: 限定元素插入和删除的位置不同

2、 在移动营业厅通过“取号、叫号”办理业务的服务模式符合______特征。

答案: 队列

3、 若元素入栈序列为a, b, c, d，则不可能得到的出栈序列为___（提示：元素可以入栈后立刻出栈）。

答案: ?d, b, c, a

4、 设数组data[m]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，则执行出队操作时对front执行的操作是______。

答案: front=(front+1)%m?

5、 已知某多项式的中缀表达式为(a+bc)/d+ef，则其后缀表达式为_。

答案: abc+d/ef+?

6、 在具有m个存储单元的循环队列中，队满时共有个 数据元素。

答案: m-1

7、 设有一顺序栈，元素3,2,1依次进栈，进栈后可立即出栈，共可得到__种不同的出栈序列。

答案: 5

8、 算术表达式的后缀形式为264－×2/，每个操作数均为一位数，此表达式的值为_____。

答案: 2

9、 设数组data[20]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==4，rear==15时，以下说法正确的是_。

答案: 该循环队列当前存储的队列元素个数是11个

10、 设数组data[20]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==4，rear==15时，以下说法正确的是_。

答案: 队列中还能存放数据元素的空闲位置数量为8个

11、 设数组data[m]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，则执行入队操作时对rear执行的操作是______。

答案: rear=(rear+1)%m

12、 设数组data[100]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==80，rear==15时，以下说法正确的是_。

答案: data数组中下标从16到79的位置都为空闲位置

13、 设计一个判别表达式中左右括号是否配对出现的算法，采用_实现最佳。

答案: 堆栈

14、 设a,b,c,d,e,f依次进栈，允许入栈后立刻出栈，则下面得不到的出栈序列为______。

答案: c,a,b,d,e,f

15、 递归过程或函数调用时，处理参数及返回地址，要用一种称为______的数据结构。

答案: 堆栈

16、 最多可存储n个数据元素的循环队列，front为队头标识，rear为队尾标识, 则队空的条件是 ( )

答案: rear==front

17、 最多可存储n个数据元素的循环队列，front为队头标识，rear为队尾标识, 则队满的条件是 ( )

答案: (rear+1)%(n+1)==front

18、 用链接方式存储的队列，在进行删除运算时_。

答案: 头、尾指针可能都要修改

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

答案: 2和4?

20、 假设以数组A[m] 存放循环队列的元素，front为队头标识，rear为队尾标识，则当前队列中的元素个数为______。

答案: (rear- front)%m

21、 栈和队列的共同点是____。

答案: 都是线性结构

22、 设栈S初始状态为空，元素e1, e2，e3，e4,e5和e6依次进入栈S，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是____。

答案: 3

23、 9 3 1 – 3 * + 10 2 / +（表达式中相邻数字以空格相隔）的计算结果是______。

答案: 20

24、 3 2+5*4-（表达式中相邻数字以空格相隔）的计算结果是______.

答案: 21

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

答案: 队列

26、 已知某长度为maxSize的循环队列,front为队头标识，rear为队尾标识，则rear==front时表示该队列为满队列。

答案: 错误
分析：表示为空队列

27、 a^2的后缀表达式是aa*

答案: 错误
分析：a2^

28、 设数组data[20]作为循环队列SQ的存储空间,front指向队头，则data[front]为队头元素

答案: 错误
分析：front指向空间不可用

29、 设数组data[20]作为循环队列SQ的存储空间,front指向队头，则data[front+1]为队头元素

答案: 错误

30、 设数组data[30]作为循环队列SQ的存储空间,front指向队头，则data[(front+1)%30]为队头元素

答案: 正确

31、 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

答案: 正确

32、 队是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

答案: 错误

33、 栈和队列的存储方式既可是顺序方式，也可是链接方式。

答案: 正确

34、 一个栈的输入序列是1,2,3,4,5，则栈的输出序列不可能是1,2,3,4,5。

答案: 错误

第4章 数组（视频总时长64’46”，共计8个） 第4章 单元测验

1、 设有10×5的数组A，其每个元素占2个字节，已知A[3][2]在内存中的地址是134，按行优先顺序存储，A[0][1]的地址是___ 。
答案: 102

2、 设有10×5的数组A，其每个元素占2个字节，已知A[7][3]在内存中的地址是176，按行优先顺序存储，A[6][0]的地址是___ 。
答案: 160

3、 设有10×5的数组A，其每个元素占2个字节，已知A[0][2]在内存中的地址是104，按行优先顺序存储，A[8][2]的地址是___ 。
答案: 184

4、 设有10×5的数组A，其每个元素占2个字节，已知A[6][3]在内存中的地址是166，按行优先顺序存储，A[2][0]的地址是___ 。
答案: 120

5、 设有5×8的数组A，其每个元素占4个字节，已知A[2][5]在内存中的地址是124，按行优先顺序存储，A[1][3]的地址是___ 。
答案: 84

6、 设有5×8的数组A，其每个元素占4个字节，已知A[3][4]在内存中的地址是152，按行优先顺序存储，A[2][0]的地址是___ 。
答案: 104

7、 设有5×8的数组A，其每个元素占4个字节，已知A[0][3]在内存中的地址是52，按行优先顺序存储，A[4][4]的地址是___ 。
答案: 184

8、 设有5×8的数组A，其每个元素占4个字节，已知A[3][3]在内存中的地址是148，按行优先顺序存储，A[4][5]的地址是___ 。
答案: 188

9、 将4×6的二维数组A按照行优先顺序存储到一维数组B中，则B[6]中存储的二维数组元素是A[1][__]。
答案: 0

10、 将4×6的二维数组A按照行优先顺序存储到一维数组B中，则B[19]中存储的二维数组元素是A[3][__]。
答案: 1

11、 将4×6的二维数组A按照行优先顺序存储到一维数组B中，则B[3]中存储的二维数组元素是A[0][__]。
答案: 3

12、 将4×6的二维数组A按照行优先顺序存储到一维数组B中，则B[0]中存储的二维数组元素是A[0][__]。
答案: 0

13、 将4×6的二维数组A按照行优先顺序存储到一维数组B中，则B[23]中存储的二维数组元素是A[3][__]。
答案: 5

14、 设有5×8的数组A，其每个元素占2个字节，已知A[3][6]在内存中的地址是146，按列优先顺序存储，A[1][4]的地址是___ 。
答案: 122

15、 设有5×8的数组A，其每个元素占2个字节，已知A[0][5]在内存中的地址是130，按列优先顺序存储，A[2][1]的地址是___ 。
答案: 94

16、 设有5×8的数组A，其每个元素占2个字节，已知A[1][3]在内存中的地址是112，按列优先顺序存储，A[0][5]的地址是___ 。
答案: 130

17、 设有5×8的数组A，其每个元素占2个字节，已知A[0][4]在内存中的地址是120，按列优先顺序存储，A[2][6]的地址是___ 。
答案: 144

18、 设有6阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,5，j为列下标，j=0,1,…,5，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，设每个矩阵元素占2个字节，已知数组B的首地址为100，则，a(1,3)的地址是___ 。
答案: 114

19、 设有6阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,5，j为列下标，j=0,1,…,5，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，设每个矩阵元素占2个字节，已知数组B的首地址为100，则，a(2,3)的地址是___ 。
答案: 116

20、 设有6阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,5，j为列下标，j=0,1,…,5，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，设每个矩阵元素占2个字节，已知数组B的首地址为100，则，a(5,5)的地址是___ 。
答案: 140

21、 设有6阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,5，j为列下标，j=0,1,…,5，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，设每个矩阵元素占2个字节，已知数组B的首地址为100，则，a(0,5)的地址是___ 。
答案: 130

22、 设有6阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,5，j为列下标，j=0,1,…,5，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，设每个矩阵元素占2个字节，已知数组B的首地址为100，则，a(3,3)的地址是___ 。
答案: 118

23、 设有10阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,9，j为列下标，j=0,1,…,9，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，则数组B[34]中存储的矩阵元素是a(,)。（请直接填写i和j的值，用一个空格隔开，注意答案不唯一，写一个即可）
答案: (以下答案任选其一都对)6 7;
7 6

24、 设有10阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,9，j为列下标，j=0,1,…,9，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，则数组B[11]中存储的矩阵元素是a(,)。（请直接填写i和j的值，用一个空格隔开，注意答案不唯一，写一个即可）
答案: (以下答案任选其一都对)1 4;
4 1

25、 设有10阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,9，j为列下标，j=0,1,…,9，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，则数组B[6]中存储的矩阵元素是a(,)。（请直接填写i和j的值，用一个空格隔开，注意答案不唯一，写一个即可）
答案: (以下答案任选其一都对)3 0;
0 3

26、 设有10阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,9，j为列下标，j=0,1,…,9，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，则数组B[8]中存储的矩阵元素是a(,)。（请直接填写i和j的值，用一个空格隔开，注意答案不唯一，写一个即可）
答案: (以下答案任选其一都对)2 3;
3 2

27、 设有10阶对称矩阵A，其中矩阵元素用a(i,j)表示，i为行下标，i=0,1,…,9，j为列下标，j=0,1,…,9，将A按照行优先顺序存储下三角元素的方式存储至一维数组B，则数组B[7]中存储的矩阵元素是a(,)。（请直接填写i和j的值，用一个空格隔开，注意答案不唯一，写一个即可）
答案: (以下答案任选其一都对)1 3;
3 1

第5章 树和二叉树（视频总时长220’10”，共计22个） 第5章 单元测验（二叉树的性质、遍历算法）

1、 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为___。

答案: 6

2、 假设一棵含有15个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0到14编号，则编号为6的结点的左孩子编号为______。

答案: 13

3、 一个高度为3的二叉树上最多有____个叶子结点。

答案: 4

4、 一个高度为9的二叉树上最多有____个叶子结点。

答案: 256

5、 一个高度为5的二叉树上最多有____个叶子结点。

答案: 16

6、 一个高度为9的满二叉树上共有______个分支结点。

答案: 255

7、 一个高度为6的满二叉树上共有______个分支结点。

答案: 31

8、 一个高度为7的满二叉树上共有______个分支结点。

答案: 63

9、 一个高度为4的满二叉树上共有______个分支结点。

答案: 7

10、 高度为6的二叉树上至多有_个结点。

答案: 63

11、 高度为4的二叉树上至多有_个结点。

答案: 15

12、 一棵有n个结点的二叉树采用二叉链表方式存储，有__个空指针域（答案不要有空格）。
答案: n+1

13、 已知某二叉树的高度为6，则该树上最多有_个结点。
答案: 63

14、 假设一棵含有16个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为6的结点的左孩子编号为_（如果孩子不存在，则填写NULL）。
答案: 13

15、 假设一棵含有18个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为14的结点的左孩子编号为_（如果孩子不存在，则填写NULL）。
答案: NULL

16、 假设一棵含有16个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为12的结点的右孩子编号为_（如果孩子不存在，则填写NULL）。
答案: NULL

17、 假设一棵含有13个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为4的结点的右孩子编号为_（如果孩子不存在，则填写NULL）。
答案: 10

18、 假设一棵含有19个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为7的结点的左孩子编号为_（如果孩子不存在，则填写NULL）。
答案: 15

19、 高度为9的二叉树上至多有_个结点。
答案: 511

20、 一棵二叉树中，若叶结点的个数为14，度为1的结点个数为12，度为2的结点的个数为_。
答案: 13

21、 一棵二叉树中，若度为1的结点个数为18，度为2的结点的个数为18，则叶结点的个数为_。
答案: 19

22、 一棵二叉树中，若度为1的结点个数为17，度为2的结点的个数为8，则叶结点的个数为_。
答案: 9

23、 一棵二叉树中，若叶结点的个数为11，度为1的结点个数为18，度为2的结点的个数为_。
答案: 10

24、 一棵二叉树中，若度为1的结点个数为19，度为2的结点的个数为15，则叶结点的个数为_。
答案: 16

25、 包含80个元素的二叉树的高度至少为___。
答案: 7

26、 包含169个元素的二叉树的高度至少为___。
答案: 8

27、 包含300个元素的二叉树的高度至少为___。
答案: 9

28、 包含494个元素的二叉树的高度至少为___。
答案: 9

29、 包含96个元素的完全二叉树的高度是___。
答案: 7

30、 包含314个元素的完全二叉树的高度是___。
答案: 9

31、 包含216个元素的完全二叉树的高度是___。
答案: 8

32、 已知一棵二叉树结点的先序遍历序列为：C,F,E,A,D,B, 中序遍历序列为 E,A,F,B,D,C, 则结点B的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: NULL

33、 已知一棵二叉树结点的先序遍历序列为：D,F,A,E,C,B, 中序遍历序列为 A,F,E,C,D,B, 则结点D的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: F

34、 已知一棵二叉树结点的先序遍历序列为：A,D,B,C,E,F, 中序遍历序列为 D,A,E,C,F,B, 则结点C的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: E

35、 已知一棵二叉树结点的先序遍历序列为：F,B,D,C,E,A, 中序遍历序列为 D,C,B,F,E,A, 则结点D的右孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: C

36、 已知一棵二叉树结点的先序遍历序列为：E,B,F,C,A,D, 中序遍历序列为 B,F,C,E,A,D, 则结点B的右孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: F

37、 已知一棵二叉树结点的先序遍历序列为：A,B,F,E,C,D, 中序遍历序列为 B,E,F,A,C,D, 则结点F的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: E

38、 已知一棵二叉树结点的先序遍历序列为：F,C,B,D,E,A, 中序遍历序列为 C,F,D,B,E,A, 则结点B的右孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: E

39、 已知一棵二叉树结点的先序遍历序列为：C,A,D,E,B,F, 中序遍历序列为 A,C,B,F,E,D, 则结点B的右孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: F

40、 已知一棵二叉树结点的先序遍历序列为：F,D,A,E,C,B, 中序遍历序列为 D,E,A,F,C,B, 则结点D的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: NULL

41、 已知一棵二叉树结点的先序遍历序列为：E,C,B,D,F,A, 中序遍历序列为 B,D,C,E,A,F, 则结点C的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: B

42、 已知一棵二叉树结点的先序遍历序列为：C,A,D,B,E,F, 中序遍历序列为 C,D,A,E,B,F, 则结点B的左孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: E

43、 已知一棵二叉树结点的先序遍历序列为：F,A,C,B,D,E, 中序遍历序列为 A,F,D,B,C,E, 则结点B的右孩子为：_。（请用NULL表示空，答案里不要有空格）
答案: NULL

第5章 树和二叉树（视频总时长220’10”，共计22个） 第5章 单元测验（森林转换二叉树、堆、哈夫曼编码）

1、 序列33,27,95,19,45,17不是最小堆

答案: 正确

2、 序列56,42,24,12,30,11不是最大堆

答案: 错误

3、 序列61,19,17,36,33,71不是最小堆

答案: 正确

4、 序列63,73,29,28,14,71是最大堆

答案: 错误

5、 序列37,82,81,56,48,42不是最大堆

答案: 正确

6、 序列11,42,58,80,46,67不是最小堆

答案: 错误

7、 序列58,40,72,99,9,10是最大堆

答案: 错误

8、 序列95,78,33,17,41,23是最大堆

答案: 正确

9、 序列86,84,74,7,71,68是最大堆

答案: 正确

10、 序列53,23,62,70,42,15不是最大堆

答案: 正确

11、 请将给定数据元素序列71,28,21,72,92,73调整成最小堆：______（提示：调整过程需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 21,28,71,72,92,73

12、 请将给定数据元素序列87,32,15,22,56,43调整成最小堆：______（提示：调整过程需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 15,22,43,32,56,87

13、 请将给定数据元素序列36,65,42,54,98,76调整成最小堆：______（提示：调整过程需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 36,54,42,65,98,76

14、 请将给定数据元素序列72,46,24,44,91,96调整成最大堆：______（提示：调整过程需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 96,91,72,44,46,24

15、 向最大堆71,69,32,25,33,15依次插入元素84，最终得到的最大堆是______（提示：堆的元素插入操作需调用AdjustUp方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 84,69,71,25,33,15,32

16、 向最大堆92,54,65,18,36,53依次插入元素82,86,88,97,81，最终得到的最大堆是______（提示：堆的元素插入操作需调用AdjustUp方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 97,92,82,86,88,53,65,18,54,36,81

17、 向最大堆84,49,82,26,29,46依次插入元素94,99,89,80,94，最终得到的最大堆是______（提示：堆的元素插入操作需调用AdjustUp方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 99,94,84,89,94,46,82,26,49,29,80

18、 向最大堆99,72,76,7,30,41依次插入元素86,91,91,94,97，最终得到的最大堆是______（提示：堆的元素插入操作需调用AdjustUp方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 99,97,86,91,94,41,76,7,72,30,91

19、 对最大堆序列95,61,66,9,19,27执行1次删除操作（提示：对优先级队列执行删除操作默认删除堆顶元素）后得到最大堆序列_______（提示：堆元素删除操作需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 66,61,27,9,19

20、 对最小堆序列10,21,70,27,31,83执行2次删除操作（提示：对优先级队列执行删除操作默认删除堆顶元素）后得到最小堆序列_______（提示：堆元素删除操作需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 27,31,70,83

21、 对最大堆序列59,55,57,50,45,22执行3次删除操作（提示：对优先级队列执行删除操作默认删除堆顶元素）后得到最大堆序列_______（提示：堆元素删除操作需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 50,45,22

22、 对最大堆序列61,56,48,23,53,19执行1次删除操作（提示：对优先级队列执行删除操作默认删除堆顶元素）后得到最大堆序列_______（提示：堆元素删除操作需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。
答案: 56,53,48,23,19

23、 已知一个有序森林如下图所示，它的先序遍历序列为_____（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。
答案: A,D,H,B,F,E,G,C

24、 已知一个有序森林如下图所示，它的先序遍历序列为_____（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。
答案: D,H,E,F,B,C,A,G

25、 已知一个有序森林如下图所示，它的先序遍历序列为_____（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。
答案: G,A,H,D,C,E,F,B

26、 已知一个有序森林如下图所示，它的中序遍历序列为_____（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。
答案: D,H,A,B,F,C,G,E

27、 已知一个有序森林如下图所示，它的中序遍历序列为_____（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。
答案: D,A,H,G,E,C,F,B

28、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母A的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 111

29、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母B的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 101

30、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母C的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 01

31、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母D的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 0011

32、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母E的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 0010

33、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母F的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 000

34、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母G的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 100

35、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，英文字母H的哈夫曼编码为___（提示：要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 110

36、 已知英文字母集合 {A,B,C,D,E,F,G,H}及其权值集合{24,19,29,9,6,13,17,21}，对字母进行哈夫曼编码，得到的哈夫曼树的WPL值为___（提示：要求对应的哈夫曼树上任意结点的左孩子权值不大于右孩子权值，答案中不要有空格）
答案: 400

第6章 集合和搜索（视频总时长37’31”，共计4个） 第6章 单元测验

1、 二叉判定树的树形取决于__。

答案: 表中元素的个数

2、 适用于对半搜索的集合元素存储方式和排序要求是___。

答案: 顺序存储，元素有序

3、 在有序表1,4,18,32,33,37,66,87,90,91上查找元素66，若执行对半搜索算法，需要依次与__进行比较，最终搜索成功。

答案: 33,87,37,66

4、 在有序表10,19,37,39,48,64,66,71,73,75上查找元素64，若执行对半搜索算法，需要依次与__进行比较，最终搜索成功。

答案: 48,71,64

5、 在有序表0,14,24,34,40,43,45,56,89,96上查找元素25，若执行对半搜索算法，需要依次与__进行比较，最终搜索失败。

答案: 40,14,24,34

6、 在有序表12,41,53,54,59,64,69,70,86,99上查找元素65，若执行对半搜索算法，需要依次与__进行比较，最终搜索失败。

答案: 59,70,64,69

7、 在有序表3,8,16,23,37,49,55,62,87,92上查找元素37，若执行对半搜索算法，需要依次与__进行比较，最终搜索成功。

答案: 37

8、 对有5个元素的有序表进行对半搜索，搜索失败的平均搜索长度为_。

答案: 8/3

9、 对有7个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_。

答案: 17/7

10、 对有8个元素的有序表进行对半搜索，搜索失败的平均搜索长度为_。

答案: 29/9

11、 对有9个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_。

答案: 25/9

12、 对有13个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_。

答案: 41/13

13、 在有序表0,8,16,22,24,34,46,48,67,76上查找元素19，若执行顺序搜索需要至少比较__次查找失败；若执行对半搜索，需要比较___次查找失败（答案请用半角逗号相隔，不要有空格）。
答案: 4,4

14、 在有序表8,17,19,38,47,49,79,80,93,96上查找元素83，若执行顺序搜索需要至少比较__次查找失败；若执行对半搜索，需要比较___次查找失败（答案请用半角逗号相隔，不要有空格）。
答案: 9,3

15、 在有序表0,21,23,45,55,78,82,86,91,98上查找元素5，若执行顺序搜索需要至少比较__次查找失败；若执行对半搜索，需要比较___次查找失败（答案请用半角逗号相隔，不要有空格）。
答案: 2,3