超星数据结构_34期末答案(学习通2023完整答案)

超星数据结构_34期末答案(学习通2023完整答案)

点击查看答案

第1章 绪论 （视频总时长30'，超星共计3个）

1.3 算法和算法分析随堂测验

1、数据算法的结构时间复杂度不受以下哪些因素的影响
A、问题规模
B、期末待处理数据状态
C、答案处理器的学习速度
D、关键步骤的通完重复次数

2、计算机算法指的整答是
A、计算方法
B、超星排序方法
C、数据解决问题的结构步骤序列
D、调度方法

3、期末算法的答案优劣与算法描述语言无关，但与所用计算机有关

第1章 单元测验

1、学习下面说法正确的通完是____。
A、健壮的算法不会因为非法的输入数据而出现莫名其妙的状态
B、算法的优劣与算法的描述语言无关，但与所用计算机环境因素有关
C、数据的逻辑结构依赖于数据的存储结构
D、以上几个都是错误的

2、从逻辑上可以把数据结构分为______两大类。
A、初等结构和构造性结构
B、顺序结构和链式结构
C、线性结构和非线性结构
D、动态结构和静态结构

3、数据结构采用链式存储时，存储单元的地址_______________。
A、一定连续
B、一定不连续
C、不一定连续
D、部分连续，部分不连续

4、算法的时间复杂度取决于______________。
A、问题规模
B、计算机的软硬件配置
C、两者都是
D、两者都不是

5、下面程序段的时间复杂度为________________。 for(i=0;i<n;i++） for(j=0;j<i;j++) x++;
A、
B、
C、
D、

6、下列函数的时间复杂度是（ ） int func（int n）｛ int i=0,sum=0; while(sum<n) sum+=++i; return i; ｝
A、
B、
C、
D、

7、算法的计算量的大小称为计算的__________。
A、效率
B、时间复杂性
C、现实性
D、难度

8、从逻辑上可以把数据结构分为__________两大类
A、动态结构、静态结构
B、顺序结构、链式结构
C、线性结构、非线性结构
D、初等结构、构造型结构

9、程序步越少的算法执行效率越高。

10、数据元素是数据的最小单位。

11、数据的逻辑结构是指数据的各数据项之间的逻辑关系。

12、算法的优劣与算法描述语言无关，但与所用计算机有关。

13、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

14、数据的物理结构是指数据在计算机内的实际存储形式。

15、数据结构的操作的实现与数据的存储表示相关。

16、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

17、求该方法的渐近时间复杂度为__________. (注意填写答案时不要有空格，用x^y的方式表达x的y次方) void aFunc(int n) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { printf("Hello World\n"); } } }

18、求aFunc方法的时间复杂度为____________。（注意答案中不要有空格，用logn表示底数为2的对数，用半角括号表示） void aFunc(int n) { for (int i = 2; i < n; i++) { i *= 2; printf("%i\n", i); } }

19、已知算法关键步骤的执行次数,则算法的渐近时间复杂度为_______。 （请用x^y表示x的y次方，采用半角括号）

20、已知算法关键步骤的执行次数,则算法的渐近时间复杂度为_______。 （logn默认以2为底，答案不要有空格，请注意此题表示问题特征的变量有m和n两个，m和n之间关系未知，乘号省略，采用半角括号）

21、四种基本的逻辑结构包括集合结构、_______结构、图形结构和树形结构

22、四种基本的逻辑结构包括线性结构、_______结构、图形结构和树形结构

23、四种基本的逻辑结构包括集合结构、_______结构、线性结构和树形结构

24、四种基本的逻辑结构包括集合结构、_______结构、线性结构和图形结构

第1章 作业

1、确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。 i=1; k=0; do { k=k+10*i; i++; } while(i<=n)

2、确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。 i=1; x=0; do { x++; i=3*i; } while( i<n);

3、确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。 i=1; x=0; for(i=0;i<n;i++) for( j=0;j<n;j++) a[i][j]=0;

4、确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。 y=0; while(n>=y*y) y++;

第2章 线性表（视频总时长63'3''，共计9个）

2.1 线性表的定义随堂测验

1、线性表就是顺序存储的表

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

2.2 线性表的顺序存储随堂测验

1、已知顺序表中每个元素占2个存储单元，第1个元素存储地址为100，则第6个元素的存储地址是
A、110
B、112
C、114
D、116

2、顺序存储方式只能用于存储线性结构

3、取线性表的第i个元素的时间同i的大小有关

2.3 线性表的链接存储随堂测验

1、线性表采用链式存储结构所具有的特点是
A、所需空间地址必须不连
B、需要事先估计所需存储空间
C、可随机存取
D、插入、删除操作不必移动元素

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

3、对任何数据结构链式存储结构一定优于顺序存储结构

4、为了很方便的插入和删除数据，可以使用双向链表存放数据

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

第2章 单元测验

1、如果线性表最常用的操作是读取第i个元素的值，则采用______存储方式最高效。
A、顺序表
B、有序表
C、单链表
D、双向链表

2、对于线性表，下列说法正确的是_______________。
A、每个元素都有一个直接前驱和一个直接后继
B、线性表中至少要有一个元素
C、表中元素必须有序排列
D、除第一个元素与最后一个元素，其他每个元素都有一个直接前驱和一个直接后继

3、已知顺序表中每个元素占2个存储单元，第一个元素存储地址为100，则表中第6个元素的存储地址是_______。
A、112
B、120
C、110
D、140

4、线性表采用链式存储结构所具有的特点是________。
A、所需空间地址必须连续
B、可随机存取
C、插入、删除操作不必移动元素
D、需要事先估计所需存储空间

5、在带表头结点的单链表中，设指针first指向表头结点，当______时，表示链表为空。
A、first==NULL
B、first->link==NULL
C、first->link==first
D、first!=NULL

6、在循环单链表中，设指针first指向头结点，当_____时表示链表为空。
A、first==NULL
B、first->link==NULL
C、first->link==first
D、first->link->link==first

7、在单链表中添加表头结点的目的是_______。
A、使得单链表至少存在一个结点
B、避免断链现象
C、方便插入和删除操作的实现
D、说明单链表是线性表的链式存储

8、循环链表的主要优点是_______。
A、不再需要头指针
B、访问某个结点时，可以快速访问它的直接前驱
C、进行插入和删除操作时避免断链现象
D、从表中任意结点出发都能扫描整个链表

9、在包含n个结点的单链表上进行元素查找操作，平均时间复杂度是_______。
A、O(1)
B、O(n)
C、O(n/2)
D、O(n^2)

10、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用________最节省时间。
A、单链表
B、单循环链表
C、带尾指针的单循环链表
D、带表头结点的双循环链表

11、在一个以 first为头指针的单循环链表中，p 指针指向尾结点的条件是__________。
A、p->link=first
B、p->link=NULL
C、p->link->link=first
D、p->element=-1

12、在单链表中指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A、p->link=s; s->link=p->link;
B、s->link=p->link; p->link=s;
C、p->link=s; p->link=s->link;
D、p->link=s->link; p->link=s;

13、以下选项__________不是链表结构所具备特征。
A、插入、删除操作不需要移动元素
B、可随机存取任意位置元素
C、不必预先估计和申请连续存储空间
D、所需存储空间与线性表长度呈正比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、线性表，删除需要移动______个元素（提示：答案不唯一，写出一个答案即可）。

29、线性表，在前插入一个元素，需要移动______个元素（提示：答案不唯一，写出一个答案即可）。

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

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

第2章 作业

1、请完成下列算法填空实现对顺序表逆置存储，逆置存储是指将元素线性关系逆置后的顺序存储，例如（a0,a1,a2），关系逆置后为（a2,a1,a0). SeqList的结构体定义如下： typedef struct seqList { int n; int maxLength; ElemType *element; }SeqList; void Invert(SeqList *L) { ElemType temp; int i; for ( i=0; i<________; i++) { temp =____________; L->element[i] = L->element[___________]; L->element[________] = ___________; } } 注意：程序题语法错误不扣分，为了避免程序题在互评时因为语法错误被误伤，请尽量写清楚注释，或简单描述一下算法思想。

2、请完成下列算法填空现对单链表的逆置存储，逆置存储是指将元素线性关系逆置后的链表存储，例如（a0,a1,a2），关系逆置后为（a2,a1,a0). 单链表结点Node和单链表SingleList结构体定义如下： typedef struct node { ElemType element; struct node *link; }Node; typedef struct singlelist { Node *first; int n; }SingleList; void invert(SingleList *L) { Node *p=__________,*q; L->first=NULL; while (_____) { q=p->link; p->link=_______; L->first=_______; p=_______; } } 注意：程序题语法错误不扣分，为了避免程序题在互评时因为语法错误带来理解不当被误伤，请尽量写清楚注释，或简单描述一下算法思想。

3、完成下列算法填空，将两个有序递增的带表头结点的单链表合并为一个有序递增的单链表。 链表结点Node和链表SingleList结构体定义如下： typedef struct node { ElemType element; struct node *link; }Node; typedef struct headerlist { Node *head; int n; }HeaderList; void MergeList1(HeaderList *La,HeaderList *Lb,HeaderList *Lc) { //合并链表La和Lb，合并后的新表使用头指针Lc指向 Node *pa,*pb,*pc,*q; pa=La->head->link; pb=Lb->head->link; pc=Lc->head; while(pa && pb) { if(____________________) { pc->link=pa; pc=pa; pa=pa->link; La->n--; } else if(pa->element>pb->element) { pc->link=___________; pc=________; pb=_________; Lb->n--; } else { pc->link=pa; pc=pa; pa=_________; q=_________; free(pb); pb =q; } Lc->n++; } pc->link=pa?pa:pb; //插入剩余段 Lc->n+=pa?La->n:Lb->n; }

第3章 堆栈和队列（视频总时长70'54''，共计9个）

3.1 堆栈随堂测验

1、若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列1,5,4,6,2,3

2、若元素输入序列为1,2,3,4,5,6，则通过一个栈可以得到输出序列3,2,5,6,4,1

3.2 队列随堂测验

1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是______。
A、2
B、3
C、4
D、5

2、用单链表表示的链式队列的队头和队尾分别在链表的（ ）位置
A、链头和链尾
B、链尾和链头
C、链头和链中
D、链尾和链中

3、堆栈和队列的主要区别是____
A、限定元素插入和删除的位置不同
B、逻辑结构不同
C、存储结构不同
D、名字不同

4、栈和队列的共同点是_____
A、都是先进先出
B、都是线性结构
C、具有相同存储结构
D、没有共同点

3.3 表达式随堂测验

1、中缀表达式为(a+b*c)/d+e*f，则其后缀表达式为_______（答案不要有空格）。

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

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

3.4 递归随堂测验

1、一个递归算法必须包括_____。
A、递归部分
B、终止条件和递归部分
C、迭代部分
D、终止条件和迭代部分

2、任何一个递归过程都可以转换成非递归过程

3、执行完下列语句段后，i值为____。 int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));

第3章 单元测验

1、堆栈和队列的主要区别是_______。
A、逻辑结构不同
B、存储结构不同
C、限定元素插入和删除的位置不同
D、名字不同

2、在移动营业厅通过“取号、叫号”办理业务的服务模式符合______特征。
A、集合
B、堆栈
C、队列
D、线性表

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

4、设数组data[m]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，则执行出队操作时对front执行的操作是______。
A、front=front+1
B、front=(front+1)%(m-1)
C、front=(front-1)%m
D、front=(front+1)%m

5、已知某多项式的中缀表达式为(a+b*c)/d+e*f，则其后缀表达式为_______。
A、abc*+d/ef*+
B、abc*+d/+ef*
C、abc*+def/*+
D、ab+c*d/ef*+

6、在具有m个存储单元的循环队列中，队满时共有个 数据元素。
A、m
B、m-1
C、m-2
D、m+1

7、设有一顺序栈，元素3,2,1依次进栈，进栈后可立即出栈，共可得到________种不同的出栈序列。
A、5
B、6
C、4
D、3

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

9、设数组data[20]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==4，rear==15时，以下说法正确的是_______。
A、data数组中下标从4到15的位置存储的是队列元素
B、data数组中下标从5到14的位置存储的是队列元素
C、该循环队列当前存储的队列元素个数是11个
D、该循环队列当前存储的队列元素个数是10个

10、设数组data[20]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==4，rear==15时，以下说法正确的是_______。
A、队列中还能存放数据元素的空闲位置数量为8个
B、队列中还能存放数据元素的空闲位置数量为7个
C、队列中还能存放数据元素的空闲位置数量为9个
D、队列中还能存放数据元素的空闲位置数量为6个

11、设数组data[m]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，则执行入队操作时对rear执行的操作是______。
A、rear=(rear+1)%m
B、rear=(rear+1)%(m-1)
C、rear=rear+1
D、++rear

12、设数组data[100]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==80，rear==15时，以下说法正确的是_______。
A、data数组中下标从16到79的位置都为空闲位置
B、队列元素个数为36
C、data数组中下标从16到80的位置都为空闲位置
D、队列元素个数为34

13、设计一个判别表达式中左右括号是否配对出现的算法，采用_______实现最佳。
A、线性表的顺序存储结构
B、队列
C、线性表的链式存储结构
D、堆栈

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

15、递归过程或函数调用时，处理参数及返回地址，要用一种称为______的数据结构。
A、堆栈
B、队列
C、数组
D、线性表

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

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

18、用链接方式存储的队列，在进行删除运算时_______。
A、仅修改头指针
B、仅修改尾指针
C、头、尾指针都要修改
D、头、尾指针可能都要修改

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

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

21、栈和队列的共同点是__________。
A、都是先进先出
B、都是先进后出
C、都是线性结构
D、没有共同点

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

23、9 3 1 - 3 * + 10 2 / +（表达式中相邻数字以空格相隔）的计算结果是______。
A、20
B、18
C、22
D、16

24、3 2+5*4-（表达式中相邻数字以空格相隔）的计算结果是______.
A、21
B、20
C、19
D、18

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

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

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

28、设数组data[20]作为循环队列SQ的存储空间,front指向队头，则data[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。

第3章 作业

1、写出下列表达式的后缀形式。 (1) (a+b)/(c+d） (2) b^2-4*a*c (3) a*c-b/c^2 (4) (a+b)*c+d/(e+f） (5) (a+b)*(c*d+e)-a*c

2、设A, B, C, D, E五个元素依次进栈（允许元素进栈后立即出栈），问能否得到下列元素出栈序列。若能得到，则给出相应的push和pop操作序列；若不能，则说明理由。 (1) A，B，C，D，E (2) A，C，E，B，D (3) C，A，B，D，E (4) E，D，C，B，A

3、请完成算法填空，实现带表头结点的单链表形式实现的队列上的元素入队与出队操作，队列和元素结点结构体定义如下： typedef struct node { ElemType element; struct node* link; }Node; typedef struct queue { Node* front; //注意front指向表头结点，非头结点，请对视频中提供的代码进行修改 Node* rear; //指向尾结点 }Queue; void EnQueue(Queue *Q, ElemType x) { Node* p= (Node*)malloc(sizeof(Node)); ____________ = x; p->link = NULL; ____________=p; Q->rear=p; } void DeQueue(Queue *Q) { //若队列为空，直接返回 if(___________ ==NULL) return; Node *p=_____________; Q->front->link=___________; free(p); //若出队后，队列为空，则需重置rear if(______________==NULL) Q->rear=Q->front;//指向表头结点 }

第4章 数组（视频总时长64'46''，共计8个）

4.1 数组的基本概念随堂测验

1、设有8?10二维数组A，数组的每个元素长度为3字节，数组元素行下标i的值为0到7，列下标j的值为0 到9，数组元素从内存地址100开始顺序存放，当用以列优先顺序存储时，元素A[5][8]的存储首地址为_____。
A、241
B、280
C、307
D、325

2、数组是元素值和下标构成的偶对的有穷集合

3、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作

4.2 特殊矩阵随堂测验

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

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

4.3 稀疏矩阵随堂测验

1、对稀疏矩阵进行压缩存储目的是
A、便于进行矩阵运算
B、便于输入和输出
C、节省存储空间
D、降低时间复杂度

2、稀疏矩阵压缩存储后，必会失去随机存取功能

3、一个稀疏矩阵采用三元组表形式表示，若把三元组表中每个三元组的行下标与列下标值互换，并把m和n的值互换，则就完成了的转置运算

第4章 单元测验

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第4章 作业

1、以行优先存储对称矩阵的下三角元素，对称矩阵结构体定义如下： typedef int ElemType; typedef struct smatrix{ ElemType *elements; int m; //阶数 }SMatrix 请完成以下算法填空题： （1）查找运算 ElemType Find(SMatrix *dm, int i, int j) //查找[i][j] ElemType Find(SMatrix *dm, int i, int j) //m行m列 { int temp, k; if (i<0 || i>=_________ || j<0 || j>=___________) return ERROR; if(i<j) { temp = i; ____________; j = temp; } k=_____________; return dm->elements[k]; } （2）赋值运算void SetValue(SMatrix *dm, int i, int j, ElemType x) void SetValue(SMatrix *dm, int i, int j, ElemType x) //设置[i][j]=x { int temp, k; if(i<j){ temp = i;__________; j = temp; } k=____________; dm->elements[_________] = ___________; }

2、稀疏矩阵以行三元组表方式存储，请完成下列程序实现稀疏矩阵元素的查找运算，并给出算法时间复杂度分析。 提示：实现该方法所需结构体定义如下 typedef int ElemType; typedef struct term{ int col, row; /*非零元素在稀疏矩阵中的列下标 col 和行下标 row*/ ElemType value; /*非零元素的值*/ }Term; typedef struct sparsematrix{ int m, n, t; /*m 是矩阵行数， n 是矩阵列数， t 是实际非零元素个数*/ Term table[maxSize]; /*存储非零元素的三元组表*/ }SparseMatrix; ElemType Find(SparseMatrix *M, int i, int j) { if(i>=m||j>=n) return NULL; for(k = 0; k<__________; k++){ if(M->table[k].row==_________ && M->table[k].col==j) return M->table[k].value; } return ZERO; //ZERO为预定义的零元值 }

3、稀疏矩阵如下图所示，请给出 (1) 行三元组表; (2) 快速转置算法所需的num数组; (3) 快速转置算法所需的k数组。

第10章 排序（视频总时长68'16''，共计9个）

第10章 单元测验

1、在下列排序算法中，_______的比较次数与元素的初始排列状态无关。
A、冒泡排序
B、快速排序
C、直接插入排序
D、简单选择排序

2、对序列5,2,6,3,8进行一趟快速排序的结果为_____。
A、3, 2, 5, 6, 8
B、2, 3, 5, 8, 6
C、3, 2, 5, 8, 6
D、2, 3, 6, 5, 8

3、在第一趟排序结束后，不能确定某个元素最终位置的排序算法是________。
A、直接插入排序
B、简单选择排序
C、冒泡排序
D、快速排序

4、序列含有10个元素，快速排序至少需要_____趟。
A、6
B、5
C、4
D、3

5、序列含有10个元素，快速排序最多需要_____趟。
A、9
B、8
C、7
D、6

6、以下哪个算法无论何种情况时间复杂度都无法等于或低于的量级。 n是待排序元素个数。
A、简单选择排序
B、直接插入排序
C、冒泡排序
D、快速排序

7、以下哪些算法，每一趟都可以至少确定一个元素的最终位置。
A、合并排序与堆排序
B、快速排序与合并排序
C、快速排序与简单选择排序
D、直接插入排序与简单选择排序

8、以下哪些算法最坏情况下时间复杂度依然为。 n是待排序元素个数。
A、快速排序与合并排序
B、堆排序与合并排序
C、快速排序与堆排序
D、合并排序与冒泡排序

9、以下哪些算法最坏情况下时间复杂度为。 n是待排序元素个数。
A、快速排序与简单选择排序
B、冒泡排序和堆排序
C、快速排序与合并排序
D、直接插入排序和合并排序

10、以下哪些算法最好情况下时间复杂度可以低至O(n)。 n是待排序元素个数。
A、直接插入排序和冒泡排序
B、简单选择排序和直接插入排序
C、简单选择排序和冒泡排序
D、直接插入排序和快速排序

11、直接插入排序是稳定的

12、直接插入排序在元素已经有序情况下，时间复杂度可低至O(n)

13、合并排序是不稳定的

14、冒泡排序是稳定的

15、快速排序是稳定的

16、堆排序是不稳定的

17、简单选择排序是稳定的

18、对n个有序元素执行快速排序，需要执行n-1趟

19、对n个元素执行冒泡排序需要执行n-1趟

20、对n个元素执行冒泡排序最多执行n-1趟

21、如果一个系统输入的元素序列处于有序状态的概率很大，则不应该选择快速排序算法实现系统的排序功能。

22、如果一个系统输入的元素序列处于有序状态的概率很大，且要求排序结果的稳定性，则冒泡排序算法是实现系统排序功能的一个不错的选择。

23、如果一个系统输入的元素序列处于有序状态的概率很大，且要求排序结果的稳定性，则直接插入排序算法是实现系统排序功能的一个不错的选择。

24、如果一个系统输入的元素序列总是处于非常无序的状态，则快速排序算法是实现系统排序功能的一个不错的选择。

25、对元素序列43, 12, 89, 56, 7, 99, 14, 32按教材中冒泡排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

26、对元素序列43, 12, 89, 56, 7, 99, 14, 32按教材中快速排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

27、对元素序列49, 38, 66, 82, 13, 53, 3按教材中冒泡排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

28、对元素序列49, 38, 66, 82, 13, 53, 3按教材中快速排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

29、对元素序列49, 38, 66, 82, 13, 53, 3按教材中简单选择排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

30、对元素序列49, 38, 66, 82, 13, 53, 3按教材中堆排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

31、对元素序列49, 38, 66, 82, 13, 53, 3按教材中合并序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

32、对元素序列49, 38, 66, 82, 13, 53, 3按教材中直接插入排序算法进行排序，第一趟排序的结果是_____（以半角逗号分隔元素，答案不要有空格）。

33、假定对46, 79, 56, 25, 76, 38, 40, 80进行一趟快速排序后，分割元素右侧元素的个数为__________。

34、假定对46, 79, 56, 25, 76, 38, 40, 80进行一趟快速排序后，分割元素左侧元素的个数为__________。

35、假定对46, 79, 46, 25, 46, 38, 40, 80进行一趟快速排序后，带下划线的46会交换到分割元素的__________侧（填写左或右）。

第10章 作业

1、设待排序数据元素的关键字为：65,78,21,30,80,7,79,57,35,26，请按照下列算法对这组数据元素按关键字升序排序（以教材所给出算法为标准），给出每个算法的前2趟排序结果。 注意：不要写错关键字造成扣分，比如35写成36 A.直接插入排序； B.简单选择排序； C.冒泡排序； D.快速排序； E.两路合并排序； F.堆排序（注意要先给出调整好的最大堆，再写前2趟结果）。

2、请对元素序列27, 6, 32, 48, 26, 17, 63进行排序（注意：不要写错关键字造成扣分）： (1) 请用直接插入排序算法进行排序，写出第一趟排序结果：____________。 (2) 请用冒泡排序算法进行排序，写出第一趟排序结果：____________。 (3) 请用两路合并排序算法进行排序，写出第一趟排序结果：____________。 (4) 请用快速排序算法进行排序，写出第一趟排序结果：____________。

3、已知一组待排序元素关键字为：24,33,12,17,33,15,12 请写出3趟快速排序的结果（注意以下划线区分相同关键字，结果没标明下划线判错）。

4、待排序数据元素以单链表方式存储，完成下列基于单链表的简单选择排序算法。 单链表结点结构体定义如下： typedef struct node{ int key; //简单起见，只定义排序关键字且为整数 struct node* link; //指针域 }Node; void SelectSort(Node *first) { Node * small, p, q; int temp; for (p=first; (1) ; (2) ){ small=p; for (q=p->link; q!=NULL; q=q->link) // 找最小值 if ( (3) ) // small=q; //元素值交换 temp = p->key; (4) ; (5) ; } }

第5章 树和二叉树（视频总时长220'10''，共计22个）

5.1 树随堂测验

1、一个树形结构的关系集合R={ <e,a>,<a,b>,<b,c>,<a,d>,<d,f>}，下面说法正确的是
A、e是根结点
B、a是根结点
C、树的度是2
D、树的度是3

2、关系集合R={ <e,a>,<a,b>,<b,c>,<a,d>,<d,e>} 可以描述成是树形逻辑结构，根结点是e

5.1 树随堂测验

1、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
A、5
B、6
C、7
D、8

2、在一棵度为3的树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数是
A、4
B、5
C、6
D、7

5.2 二叉树随堂测验

1、一个有5个结点的二叉树，以下不可能出现的情况是：
A、度为1的结点个数是0
B、度为1的结点个数是1
C、度为1的结点个数是2
D、度为1的结点个数是3

2、一棵完全二叉树有15个结点，则这棵树的树高是______。

3、一棵2树，有4个叶子，则该树共有____个结点。

4、按照视频里面的编号方式对一棵完全二叉树进行结点编号，已知结点的最大编号是245，则拥有最小编号的叶子结点的编号是________。

5.3 二叉树的遍历随堂测验

1、一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是
A、CABDEFG
B、ABCDEFG
C、DACEFBG
D、ADCFEG

2、请给出下图二叉树的先序遍历序列，答案为小写字母序列，不要有任何分隔符和空格

3、请给出下图二叉树的中序遍历序列，答案为小写字母序列，不要有任何分隔符和空格

4、请给出下图二叉树的后序遍历序列，答案为小写字母序列，不要有任何分隔符和空格

5.4 树和森林随堂测验

1、已知一个有序森林描述如下，它的先序遍历序列为_______________________（给出结点序列，不要有分隔符和空格）。 第1棵树：根结点I I的孩子依次为：J,A J的孩子依次为：C A没有孩子 C的孩子依次为：H H没有孩子 第2棵树：根结点F F没有孩子 第3棵树：根结点G G的孩子依次为：B,E B没有孩子 E没有孩子 第4棵树：根结点D D没有孩子

2、已知一个树描述如下，它的中序遍历序列为_______________________（给出结点序列，不要有分隔符和空格）。 根结点B B的孩子依次为：A,I,J,F A的孩子依次为：C,D I的孩子依次为：G J没有孩子 F没有孩子 C没有孩子 D的孩子：E G的孩子：H E没有孩子 H没有孩子

5.5 堆和优先权队列随堂测验

1、向最大堆92,54,65,18,36,53依次插入元素82,86,88,97,81，最终得到的最大堆是____________（请写出元素序列，用半角逗号相隔，不要有空格）

2、对最大堆序列59,55,57,50,45,22执行3次删除操作（提示：对优先级队列执行删除操作默认删除堆顶元素）后得到最大堆序列____________（请写出元素序列，用半角逗号相隔，不要有空格）。

5.6 哈夫曼树及哈夫曼编码随堂测验

1、有n个叶子的哈夫曼树的结点总数为_____。
A、不确定
B、2n
C、2n+1
D、2n-1

2、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和

3、哈夫曼树的结点个数不能是偶数

第5章 单元测验（二叉树的性质、遍历算法）

1、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为_________。
A、4
B、5
C、6
D、7

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

3、一个高度为3的二叉树上最多有____个叶子结点。
A、1
B、2
C、3
D、4

4、一个高度为9的二叉树上最多有____个叶子结点。
A、64
B、128
C、256
D、512

5、一个高度为5的二叉树上最多有____个叶子结点。
A、8
B、16
C、24
D、32

6、一个高度为9的满二叉树上共有______个分支结点。
A、254
B、255
C、256
D、257

7、一个高度为6的满二叉树上共有______个分支结点。
A、30
B、31
C、32
D、33

8、一个高度为7的满二叉树上共有______个分支结点。
A、61
B、62
C、63
D、64

9、一个高度为4的满二叉树上共有______个分支结点。
A、4
B、5
C、6
D、7

10、高度为6的二叉树上至多有_______个结点。
A、62
B、63
C、64
D、65

11、高度为4的二叉树上至多有_______个结点。
A、15
B、16
C、17
D、18

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

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

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

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

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

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

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

19、高度为9的二叉树上至多有_______个结点。

20、一棵二叉树中，若叶结点的个数为14，度为1的结点个数为12，度为2的结点的个数为_______。

21、一棵二叉树中，若度为1的结点个数为18，度为2的结点的个数为18，则叶结点的个数为_______。

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

23、一棵二叉树中，若叶结点的个数为11，度为1的结点个数为18，度为2的结点的个数为_______。

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

25、包含80个元素的二叉树的高度至少为_________。

26、包含169个元素的二叉树的高度至少为_________。

27、包含300个元素的二叉树的高度至少为_________。

28、包含494个元素的二叉树的高度至少为_________。

29、包含96个元素的完全二叉树的高度是_________。

30、包含314个元素的完全二叉树的高度是_________。

31、包含216个元素的完全二叉树的高度是_________。

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

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

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

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

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

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

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

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

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

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

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

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

第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方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。

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

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

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

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

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

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

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

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

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

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

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

23、已知一个有序森林如下图所示，它的先序遍历序列为_______________________（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。

24、已知一个有序森林如下图所示，它的先序遍历序列为_______________________（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。

25、已知一个有序森林如下图所示，它的先序遍历序列为_______________________（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。

26、已知一个有序森林如下图所示，它的中序遍历序列为_______________________（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。

27、已知一个有序森林如下图所示，它的中序遍历序列为_______________________（答案请表示为结点序列，用半角逗号相隔，答案不要有空格）。

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

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

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

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

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

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

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

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

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

第5章 作业（二叉树的遍历）

1、给定三个结点 A、B 和 C，可分别组成多少个不同的无序树、有序树和二叉树?

2、设二叉树以二叉链表方式存储，试完成下列问题的递归算法。 设二叉树结点和二叉树结构体定义如下： typedef struct btnode { ElemType element; struct btnode* lchild, *rchild; }BTNode; typedef struct binarytree{ BTNode* root; }BinaryTree; （1）求一棵二叉树的高度； int Depth(BTNode *p) { int lh, rh; if (!p) return 0; lh = ______________; rh = _____________; if (lh > rh) return _________; else return ________; } int DepthofBT(BinaryTree Bt) { return ___________; } （2）求一棵二叉树中的结点个数； int Size(BTNode * p) { if (!p) return _____ ; else return Size(p->lchild)+______________+1; } int SizeofBT(BinaryTree Bt) { return ______________); } （3）交换一棵二叉树中每个结点的左、右子树。 void exchange ( BTNode * p) { if(!p) return; if ( p->lchild != NULL || p->rchild != NULL ) { temp = p->lchild; p->lchild = ____________; p->rchild = temp; exchange (___________ ); exchange ( p->rchild ); } } void exchange(BinaryTree *bt) { ____________________; }

3、已知一棵二叉树结点的先序遍历序列为：F,D,E,B,C,A, 中序遍历序列为 D,B,E,F,A,C, 请画出该二叉树。

4、已知一棵二叉树结点的后遍历序列为：A,C,B,D,F,E, 中序遍历序列为 C,A,E,F,B,D, 请画出该二叉树。

第5章 作业（森林、堆、哈夫曼编码）

1、已知一棵二叉树如下所示，请画出这棵二叉树对应的有序森林。

2、已知一个有序森林如下所示，它的先序遍历序列为_______________________。

3、已知一个有序森林如下所示，它的中序遍历序列为_______________________。

4、已知一个有序森林如下所示，请给出它的带右链的先序表示法（填写图下方表格即可）。 下标 0 1 2 3 4 5 6 7 8 9 element ltag sibling

5、请将给定数据元素序列84,23,32,54,16,97调整成最大堆。

6、向最小堆35,75,37,85,93,72依次插入元素1,6，请给出最终得到的最小堆。

7、对最小堆序列14,39,50,79,95,59执行2次删除操作，请给出最终得到的最小堆。

8、已知英文字母集合 { A,B,C,D,E,F,G,H}及其权值集合{ 29,9,26,27,2,23,8,24}，请给出以上英文字母的哈夫曼编码并计算WPL值，要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值。 A:____________ B:____________ C:____________ D:____________ E:____________ F:____________ G:____________ H:____________ WPL=____________

第6章 集合和搜索（视频总时长37'31''，共计4个）

6.2 顺序搜索随堂测验

1、对有序表进行顺序搜索比无序表上进行顺序搜索速度更快

2、在平均情况下，对有序表进行顺序搜索在查找成功的情况下快于对无序表上进行顺序搜索

6.3 二分搜索随堂测验

1、查找相同元素的效率对半搜索总比顺序搜索高

2、在有序表8,17,19,38,47,49,79,80,93,96上查找元素83，若执行对半搜索，需要比较____次查找失败

6.4 平均搜索长度分析随堂测验

1、二叉判定树的树形取决于
A、表中元素的个数
B、表中元素的关键字值
C、表中元素是否有序
D、表中元素的存储方式

2、对有7个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_____（答案请写成X/X的形式）

第6章 单元测验

1、二叉判定树的树形取决于________。
A、表中元素的关键字值
B、表中元素是否有序
C、表中元素的个数
D、表中元素的存储方式

2、适用于对半搜索的集合元素存储方式和排序要求是_________。
A、顺序存储，元素无序
B、顺序存储，元素有序
C、链式存储，元素无序
D、链式存储，元素有序

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

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

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

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

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

8、对有5个元素的有序表进行对半搜索，搜索失败的平均搜索长度为_______。
A、8/3
B、5/2
C、3
D、2

9、对有7个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_______。
A、17/7
B、16/7
C、18/7
D、3

10、对有8个元素的有序表进行对半搜索，搜索失败的平均搜索长度为_______。
A、29/9
B、29/8
C、10/3
D、3

11、对有9个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_______。
A、25/9
B、26/9
C、8/3
D、3

12、对有13个元素的有序表