第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
a、
b、
c、
d、
6、下列函数的时间复杂度是（ ） int func（int n）｛ int i=0,sum=0; while(sum 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
3、确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。 i=1; x=0; for(i=0;i
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)0]为队头元素
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(ielements[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(ielements[_________] = ___________; }
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={,,,,}，下面说法正确的是
a、e是根结点
b、a是根结点
c、树的度是2
d、树的度是3
2、关系集合r={,,,,} 可以描述成是树形逻辑结构，根结点是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个元素的有序表进行对半搜索，搜索成功的平均搜索长度为_______。
a、41/13
b、40/13
c、42/13
d、43/13
13、在有序表0,8,16,22,24,34,46,48,67,76上查找元素19，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
14、在有序表8,17,19,38,47,49,79,80,93,96上查找元素83，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
15、在有序表0,21,23,45,55,78,82,86,91,98上查找元素5，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
16、在有序表18,22,46,53,59,61,64,69,71,98上查找元素60，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
17、在有序表18,22,46,53,59,61,64,69,71,98上查找元素60，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
18、在有序表2,18,48,49,56,71,72,79,82,95上查找元素71，若执行顺序搜索需要至少比较______次查找成功；若执行对半搜索，需要比较_____次查找成功（答案请用半角逗号相隔，不要有空格）。
19、在有序表3,8,10,19,22,31,41,58,77,88上查找元素41，若执行顺序搜索需要至少比较______次查找成功；若执行对半搜索，需要比较_____次查找成功（答案请用半角逗号相隔，不要有空格）。
20、在有序表24,26,31,40,44,60,61,62,88,91上查找元素42，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
21、在有序表6,9,17,19,23,24,39,71,79,90上查找元素11，若执行顺序搜索需要至少比较______次查找失败；若执行对半搜索，需要比较_____次查找失败（答案请用半角逗号相隔，不要有空格）。
22、在有序表12,20,26,29,39,66,74,88,90,98上查找元素66，若执行顺序搜索需要至少比较______次查找成功；若执行对半搜索，需要比较_____次查找成功（答案请用半角逗号相隔，不要有空格）。
第6章 作业
1、假定对下标从0开始标记、长度为 11 的有序表 (6, 17, 21, 27, 30, 36, 44, 55, 60, 67, 71) 进行对半搜索： （1）请画出描述对半搜索的二叉判定树； （2）求对半搜索该有序表时，搜索成功的平均查找长度； （3）求对半搜索该有序表时，搜索失败的平均查找长度。
2、设有序表用单链表表示，该单链表结点与单链表结构体定义如下 typedef struct snode{ keytype key; datatype data; struct snode* link; }snode; typedef struct linkedlist{ snode * first; }linkedlist; 请设计一个方法seqsearch，实现对有序表的顺序搜索，若搜索成功则seqsearch返回true，否则seqsearch返回false。 bool seqsearch(linkedlist* list, keytype key) { …… }
第7章 搜索树（视频总时长81'41''，共计11个）
7.1 二叉搜索树随堂测验
1、在非空二叉搜索树中插入一个新结点，总是插入到某个叶结点下面
2、n个结点的二叉搜索树有多种，其中树高最小的二叉搜索树是最佳的
3、在任意一棵非空二叉搜索树中，删除某结点后又将其插入，则所得二叉搜索树与原二叉搜索树相同
4、在任意一棵非空二叉搜索树中，删除某叶子结点后又将其插入，则所得二叉搜索树与原二叉搜索树可能不相同
5、二叉搜索树删除一个结点后，仍是二叉搜索树
7.2 二叉平衡树随堂测验
1、以下说法错误的是
a、具有完全二叉树树形的二叉搜索树，一定是二叉平衡树
b、在二叉平衡树中插入一个新结点，新结点成为叶子结点
c、具有n个结点的二叉搜索树，树高越矮搜索效率越高
d、向二叉平衡树中插入一个新元素，新元素有可能被调整到根结点中
2、完全二叉树肯定是平衡二叉树
3、将线性表中的数据元素组织成avl树，其优点之一是总能保证平均搜索长度均为logn量级（n为线形表中的元素个数）
4、在平衡二叉树中，向某个平衡因子不为零的结点的子树中插入一新结点，必引起平衡旋转
7.3 b-树随堂测验
1、下面关于m阶b树说法正确的是
a、每个结点至少有两棵非空子树
b、树中每个结点至多有m-1个关键字
c、所有叶子在同一层上;
d、当插入一个数据元素引起b树结点分裂后，树长高一层
2、高度为4的3阶b树，至少包含___个关键字
第7章 单元测验
1、对空树的二叉平衡树，依次输入a，z，b，t，c，p 所构造的二叉平衡树的根结点为 _______（字母根据在字母表的编号比较大小，a~z的编号为1~26）。
a、a
b、b
c、c
d、z
2、设二叉平衡树中任一结点的子树为t1和t2，则t1和t2的高度不可能为________。
a、0和2
b、1和2
c、3和4
d、11和10
3、下面关于m阶b树说法正确的是_________。
a、每个结点至少有2个非空子树
b、树中每个结点最多有m-1个关键字
c、失败结点都在同一层上，b树的高度等于失败结点所在层数
d、当插入一个元素引起b树结点上溢后，经过调整，b树的高度会发生增长
4、对二叉搜索树进行先序遍历，得到遍历序列为28, 21, 25, 36, 33, 43，则结点28的右孩子为_______。
a、36
b、33
c、43
d、没有右孩子
5、以下哪棵树不是二叉平衡树_________。
a、
b、
c、
d、
6、给定二叉搜索树如下图所示，从二叉搜索树中依次删除33,9,11，最后得到的二叉搜索树中17的双亲是___________。 假设：在进行删除操作时，如果删除的是有两个孩子的结点，选择其中序遍历序列下直接后继结点为替代者。
a、41
b、33
c、11
d、62
7、向空二叉平衡树依次插入关键字为65,35,25,39,38的元素，最后得到的二叉平衡树的根结点是_______。
a、65
b、35
c、39
d、38
8、以下说法错误的是__________。
a、具有完全二叉树树形的二叉搜索树，一定是二叉平衡树
b、具有n个结点的二叉搜索树，树高越矮搜索效率越高
c、在二叉平衡树中插入一个新结点，新结点成为叶子结点
d、在b树中插入一个新元素，新元素有可能被调整到根结点中
9、向空的3阶b树依次插入关键字为65,35,25,39,38的元素，则最后得到的b树中，根结点包含元素的关键字为_______。
a、35,39
b、35,38
c、25,35
d、38,39
10、向空的3阶b树依次插入关键字为76,58,0,99,7的元素，则最后得到的b树中，根结点包含元素的关键字为_______。
a、58
b、76
c、58,76
d、7,58
11、以下哪棵树不是二叉平衡树。
a、
b、
c、
d、
12、二叉平衡树中每一个结点的________的绝对值不超过1。
13、给定二叉搜索树如下图所示，向二叉搜索树依次插入27,65,35，最后得到的二叉搜索树中65的双亲是_____。
14、给定二叉搜索树如下图所示，向二叉搜索树依次插入27,65,35，最后得到的二叉搜索树中35的双亲是_____。
15、给定二叉搜索树如下图所示，从二叉搜索树中依次删除15,5,24，最后得到的二叉搜索树中17的双亲是___________。 假设：在进行删除操作时，如果删除的是有两个孩子的结点，选择其中序遍历序列下直接后继结点为替代者。
16、给定二叉搜索树如下图所示，从二叉搜索树中依次删除33,9,11，最后得到的二叉搜索树中42的双亲是___________。 假设：在进行删除操作时，如果删除的是有两个孩子的结点，选择其中序遍历序列下直接后继结点为替代者。
17、向空二叉平衡树依次插入关键字为76,58,0,99,7的元素，最后得到的二叉平衡树的根结点是_______。
18、高度为3的4阶b树，至少有______个结点。
19、高度为3的4阶b树，最多包含_______个结点。
20、高度为4的3阶b树，最多包含_______个结点。
21、高度为4的3阶b树，至少包含_______个结点。
22、高度为4的3阶b树，至少包含_______个关键字。
23、高度为3的4阶b树，至少包含_______个关键字。
24、高度为3的5阶b树，至少包含_______个关键字。
25、高度为3的4阶b树，最多包含_______个关键字。
26、高度为3的5阶b树，至少包含_______个关键字。
第7章 作业
1、依次向空二叉搜索树插入关键字为37,45,91,25,14,76,56,65的元素： (1) 请画出插入完成后的二叉搜索树树形(a)； (2) 在刚才生成的二叉搜索树上删除76，画出树形(b)； (3) 继续删除37，画出树形(c)
2、从空树开始，使用关键字序列：a,g,f,b,k,d,h,m,j,e,s,i,r,x 建立 (1) 4阶b-树，请画出最终得到的树形； (2) 5阶b-树，请画出最终得到的树形。 提示：建立b-树过程是按照关键字序列从空b树开始依次插入的过程；关键字大小由字母在字母表的次序决定，例如a
3、在下面的4阶b-树上依次删除a,e,f,h，请画出删除完成后的树形。 提示：在删除过程中，如果遇到左右兄弟都可以“借”的情况下，优先向“左”兄弟借。不按照“先左后右”规则的答案，不予给分。
4、向空二叉平衡树依次插入关键字为5,2,4,8,6,7的元素，请画出插入完成后得到的二叉平衡树形。
5、向空二叉平衡树依次插入关键字为0,92,85,26,10,22的元素，请画出二叉平衡树的构造过程。 注意：要求画出5个构造步骤所得到的树形，每个步骤分别计分，如果只给出最终的树形，最多只能得8分。
第8章 散列表（视频总时长56'45''，共计7个）
8.1 散列技术简介随堂测验
1、将10个元素散列到100000个单元的散列表中，则不会产生冲突
2、在散列检索中，“比较”操作一般也是不可避免的
8.2 常见散列函数随堂测验
1、好的散列函数所应该具备的共同特性之一是散列值应当以_______概率取其值域（散列值取值范围）内的每个值。
a、最大
b、最小
c、平均
d、同等
2、散列表实现集合元素快速搜索的思想是一种牺牲空间换取时间的思想
3、散列函数越复杂越好，因为这样冲突概率小
8.3 冲突处理技术随堂测验
1、设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用拉链法构造散列表，散列函数为h(key) = key mod 13，散列地址为1的链中有_____个记录
a、1
b、2
c、3
d、4
2、散列查找中k个关键字具有同一散列值，若用线性探查法将这k个关键字对应的记录存入散列表中，至少要进行___次探查
a、k
b、k 1
c、k(k 1)/2
d、k(k-1)/2
3、散列表的平均查找长度与处理冲突的方法无关
第8章 单元测验
1、散列表的冲突解决方法中__________不是开地址法。
a、线性探查法
b、二次探查法
c、除留余数法
d、双散列法
2、有长度为11的空散列表ht，依次插入23, 89, 55, 46, 12, 7, 48, 66，请采用双散列法解决冲突，散列函数为h1(key)=key, h2(key)=key%9 1，89在散列表中存储位置是____________。
a、7
b、8
c、9
d、10
3、有长度为11的散列表ht，依次插入23, 89, 55, 46, 12, 7, 48, 66，请采用双散列法解决冲突，散列函数为h1(key)=key, h2(key)=key%9 1，23在散列表中存储位置是______。
a、0
b、1
c、2
d、3
4、给定一个长度为11的空散列表，采用线性探查法解决冲突，散列函数为h(key)=key，请向散列表依次插入关键字为27,19,54,48,63的集合元素，插入完成后63在散列表中存储位置是__________。
a、9
b、10
c、11
d、8
5、给定一个长度为7的空散列表ht，采用二次探查法解决冲突，散列函数为h(key)=key%7，请向散列表依次插入关键字为20,11,55的集合元素，插入完成后55在散列表中存储地址为_______。
a、0
b、4
c、6
d、10
6、给定一个长度为7的空散列表ht，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key%7 h2(key)=key%5 1 请向散列表依次插入关键字为9,16,30的集合元素，插入完成后30在散列表中存储地址为_______。
a、2
b、3
c、4
d、5
7、给定一个长度为7的空散列表ht，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key%7 h2(key)=key%5 1 请向散列表依次插入关键字为30,58,65的集合元素，插入完成后65在散列表中存储地址为_______。
a、2
b、3
c、5
d、6
8、给定一个长度为7的空散列表ht，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key%7 h2(key)=key%5 1 请向散列表依次插入关键字为29,64,15的集合元素，插入完成后15在散列表中存储地址为_______。
a、1
b、2
c、3
d、4
9、给定一个长度为7的空散列表ht，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key%7 h2(key)=key%5 1 请向散列表依次插入关键字为35,63,21的集合元素，插入完成后21在散列表中存储地址为_______。
a、1
b、2
c、3
d、4
10、散列表采用线性探查法解决冲突，集合元素在表中存储位置容易连成一片，搜索效率降低，这种现象称为_______（本章测试中考核的术语以视频和修订版电子教材为准，系统判题不支持语义识别功能，请认真观看视频）。
11、散列表中关键字不相同，但是给定散列函数求得的散列值相同的数据元素互称为______（本章测试中考核的术语以视频和修订版电子教材为准，系统判题不支持语义识别功能，请认真观看视频）。
12、对于给定的一个散列函数，有两个数据元素具有相同的散列值的现象称为_____（本章测试中考核的术语以视频和修订版电子教材为准，系统判题不支持语义识别功能，请认真观看视频）。
13、散列表采用二次探查法解决冲突，基地址相同的集合元素拥有相同的探查序列，也会造成搜索效率的下降，这种现象称为___________（本章测试中考核的术语以视频和修订版电子教材为准，系统判题不支持语义识别功能，请认真观看视频）。
14、给定一个长度为7的空散列表ht，采用线性探查法解决冲突，散列函数为h(key)=key%7，请向散列表依次插入关键字为92,29,16,17,25的集合元素，插入完成后25的存储地址是_______（给出散列表位置下标）。
15、给定一个长度为7的空散列表ht，采用线性探查法解决冲突，散列函数为h(key)=key%7，请向散列表依次插入关键字为92,52,7,3,59的集合元素，插入完成后59的存储地址是_______（给出散列表位置下标）。
16、给定一个长度为7的空散列表ht，采用二次探查法解决冲突，散列函数为h(key)=key%7，请向散列表依次插入关键字为62,72,80的集合元素，插入完成后80在散列表中存储地址为_______（给出散列表位置下标）。
17、给定一个长度为7的空散列表ht，采用二次探查法解决冲突，散列函数为h(key)=key%7，请向散列表依次插入关键字为18,32,46的集合元素，插入完成后46在散列表中存储地址为_______（给出散列表位置下标）。
18、给定一个长度为7的空散列表ht，采用二次探查法解决冲突，散列函数为h(key)=key%7，请向散列表依次插入关键字为35,21,7的集合元素，插入完成后7在散列表中存储地址为_______（给出散列表位置下标）。
19、给定一个长度为7的空散列表ht，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key%7 h2(key)=key%5 1 请向散列表依次插入关键字为3,17,45的集合元素，插入完成后45在散列表中存储地址为_______（给出散列表位置下标）。
20、给定一个长度为7的空散列表ht，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key%7 h2(key)=key%5 1 请向散列表依次插入关键字为95,25,67的集合元素，插入完成后67在散列表中存储地址为_______。
第8章 散列表作业
1、给定一个长度为13的散列表ht如下所示，采用线性探查法解决冲突，散列函数为h(key)=key，请向散列表依次插入关键字为55,35,88,98,26的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 51 90 85 9 64
2、给定一个长度为13的散列表ht如下所示，采用二次探查法解决冲突，散列函数为h(key)=key，请向散列表依次插入关键字为78,96,18,2,40的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 91 45 84 32 97
3、给定一个长度为13的散列表ht如下所示，采用二次探查法解决冲突，散列函数为h(key)=key，请向散列表依次插入关键字为42,91,33,73,34的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 3 95 21 60 22
4、给定一个长度为13的散列表ht如下所示，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key h2(key)=key 1 请向散列表依次插入关键字为61,35,59,93,78的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 91 13 98 20 90
5、给定一个长度为13的散列表ht如下所示，采用双散列法解决冲突，两个散列函数分别为： h1(key)=key h2(key)=key 1 请向散列表依次插入关键字为30,22,87,57,82的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 61 74 35 23 100
第9章 图（视频总时长111'36''，共计14个）
9.1 图的基本概念随堂测验
1、有5个顶点的无向完全图，有_____条边。
2、有10个顶点的有向图，最多有_____条边。
3、22个顶点的无向图是连通图，则至少要有______条边
4、15个顶点的有向图是强连通图，则至少有______条边。
9.2 图的存储结构随堂测验
1、在有向图的邻接矩阵中，i行值之和就是顶点i的度。
2、图用邻接表存储，可以很方便的判断两个顶点之间是否存在边。
3、有10个顶点的无向连通图，其邻接矩阵中至少有______个1。
4、给定有向图的关系集合{<1,0>,<2,3>,<3,0>,<1,2>,<3,1>}，则顶点0的入度为_______。
5、给定有向图的关系集合{<1,0>,<2,3>,<3,0>,<1,2>,<3,1>}，则在该图的邻接表中顶点3对应的单链表上有_____个边结点。
9.3 图的遍历随堂测验
1、有n个顶点的深度优先遍历算法的时间复杂度为o(n e)
2、宽度优先遍历算法比深度优先遍历算法计算更快
3、对无向图进行深度优先遍历算法，遍历趟数等于该无向图包含的连通分量个数
9.4 拓扑排序随堂测验
1、拓扑排序算法可以用于判断给定无向图是否有环。
2、拓扑排序算法的输入必须是有向无环图。
9.5 关键路径随堂测验
1、aoe网络中从源点到汇点的最短路径长度是这个工程的最短工期
2、关键活动发生延迟，一定会影响整个工期
3、减少任意一个关键活动的持续时间，可以缩短工期
9.6 最小代价生成树随堂测验
1、给定一个带权无向图，用克鲁斯卡尔算法和普里姆算法得到的最小代价生成树相同。
2、稀疏图（边很少的图）的最小代价生成树用普里姆算法比用克鲁斯卡算法好。
3、稠密图（边很多的图）用普里姆算法求最小代价生成树效率较高。
第9章 单元测验
1、设某强连通图中有n个顶点，则该强连通图最多有 边。
a、n
b、n*(n-1)
c、n*(n-1)/2
d、n*(n 1)
2、已知图的边集合: 则序列_______是该图的拓扑序列之一。
a、6, 3, 4, 5, 1, 2
b、6, 1, 2, 3, 4, 5
c、4, 5, 6, 1, 2, 3
d、4, 3, 5, 2, 1, 6
3、设无向图g中有n个顶点和e条边，则其对应的邻接表中的顶点结点和边结点的个数分别为______。
a、n和e
b、e和n
c、2n和e
d、n和2e
4、aov图中存在两个顶点 i 和 j, 若 i 领先 j, 以下情况绝对不会发生的是________。
a、不存在一条j到i的路径
b、存在一条i到j的边
c、存在一条j到i的路径
d、存在一条i到j的路径
5、关于关键路径，以下说法正确的是_______。
a、是aoe网中从源点到汇点的最短路径
b、是aoe网中从源点到汇点的最长路径
c、可用于评估一个项目的最长工期
d、通过缩短关键路径上的活动时长，一定可以缩短整个项目工期
6、一个有n个顶点的有向图(n>1)，至少要存在______条边，才能成为强连通图。
a、n-1
b、n
c、n(n-1)
d、n(n-1)/2
7、一个有n个顶点的无向图，包含2个连通分量，则它至少有______条边。
a、n-2
b、n-1
c、n
d、n 1
8、一个有n个顶点 (n>2) 的有向图，包含2个强连通分量，则它至少有________条边。
a、n-2
b、n-1
c、n
d、n 1
9、一个有n个顶点的无向图，包含4个连通分量，则它至少有______条边。
a、n-4
b、n-3
c、n-2
d、n-1
10、一个有n个(n>3) 顶点的有向图，包含3个强连通分量，则它至少有______条边。
a、n-3
b、n-2
c、n-1
d、n
11、关于拓扑排序算法，以下说法错误的是_______。
a、只有输入dag图才能获得正确拓扑序列
b、顶点的入度值越大，说明它的先决条件越多，它在拓扑序列中的位置肯定越靠后
c、如果输入非dag图，则算法报错
d、给定dag图的拓扑序列可能不唯一
12、给定一个有向图的边集合为： 则下列序列不是该图拓扑序列的是______。
a、0,1,2,3,4,5,6
b、0,1,2,3,4,6,5
c、0,2,4,1,6,5,3
d、0,2,4,1,6,3,5
13、以下选项_____不是下图的深度优先遍历序列。
a、a,b,c,e,f,d,j,h,i,g,k,o,l,m,n
b、a,b,c,e,f,d,k,g,i,h,j,l,m,n,o
c、a,b,c,e,d,k,g,i,h,j,f,o,m,n,l
d、a,b,c,e,j,h,i,g,k,d,f,o,m,n,l
14、以下选项_____是下图的深度优先遍历序列。
a、k,d,a,b,e,c,f,g,j,h,i
b、k,d,a,b,e,c,f,j,h,i,g
c、j,h,i,g,e,c,f,k,d,a,b
d、j,h,i,g,e,f,c,k,d,a,b
15、以下选项_____是下图的宽度优先遍历序列。
a、k,d,g,a,e,b,c,f,j,h,i
b、k,d,g,a,e,c,b,f,j,h,i
c、k,d,a,e,b,c,f,j,h,i,g
d、k,d,g,a,b,c,f,j,e,h,i
16、用普里姆算法构造下图的最小代价生成树，从a开始构造，第3条被加入生成树中的边是_____。
a、(d,e)
b、(a,b)
c、(d,k)
d、(e,c)
17、用普里姆算法构造下图的最小代价生成树，从b开始构造，第3条被加入生成树中的边是_____。
a、(e,j)
b、(c,f)
c、(e,c)
d、(d,e)
18、给定一个有n个顶点的有向图，如果其边的条数达到，则该图一定是强连通图。
19、给定一个有n个顶点的有向图，如果其边的个数达到，则该图一定是连通图。
20、给定一个有n个顶点的有向图，如果其边的个数达到，则该图一定是完全图。
21、邻接表上边结点的个数就是图中边的条数
22、对无向图进行一趟深度优先遍历，可以得到该图的一棵生成树。
23、无向图由n个连通分量组成，则需要执行n次宽度优先遍历才能遍历完所有顶点。
24、强连通图可以通过1趟深度优先遍历得到完整的遍历序列。
25、给定拓扑序列为0, 1, 3, 4, 5, 2, 6，则一定存在一条3到6的路径
26、给定拓扑序列为0, 1, 3, 4, 5, 2, 6，3到6之间不一定存在路径
27、给定拓扑序列为0, 1, 3, 4, 5, 2, 6，则一定不存在一条6到5的路径
28、已知dag图中，顶点i与j之间不存在先决关系，如果交换拓扑序列中i和j的位置后得到的序列一定也是拓扑序列
29、给定带权无向图，用普里姆和克鲁斯卡尔算法得到的最小代价生成树不一定是同一棵。
30、给定带权无向图，用普里姆和克鲁斯卡尔算法得到的最小代价生成树相同
31、给定带权无向图，用普里姆和克鲁斯卡尔算法得到的最小代价生成树的代价相同
32、给定带权无向图，如果图中各边权值互不相同，用普里姆和克鲁斯卡尔算法得到的最小代价生成树一定相同
33、用普里姆算法构造下图的最小代价生成树，从e开始构造，则边(j,h)一定是第5条被加入到生成树上的边。
34、用克鲁斯卡尔算法构造下图的最小代价生成树，第一条被加入生成树上的边一定是(e,c)。
35、用克鲁斯卡尔算法构造下图的最小代价生成树，最后一条被加入生成树上的边一定是(a,b)。
36、用克鲁斯卡尔算法构造下图的最小代价生成树，最后一条被加入生成树上的边一定是(d,k)。
37、单源最短路径算法可用于求得图中任意两个顶点间的最短路径
38、在aoe网络中，完成工程所需最短时间是从开始顶点到完成顶点的最长路径的长度，这条路径被称作 路径。
39、已知有向图g的边集合： 则顶点0的入度为_________。
40、图的基本存储结构包括_____和邻接表表示法（请按照教材定义术语填写）。
41、已知有向图g的边集合： 则顶点2入度为_________。
42、已知图的边集合: 若采用邻接表存储，则顶点4对应的边结点链表中共有_________个边结点。
43、已知图的边集合: 若采用邻接表存储，则顶点5对应的边结点链表中共有_________个边结点。
44、已知图的边集合: 若采用邻接表存储，则顶点2对应的边结点链表中共有_________个边结点。
45、已知图的边集合 若采用邻接表存储，则邻接到4的顶点共有_________个。
46、在aoe网络中，完成工程所需最____时间是从源点到汇点的最长路径的长度，这条路径称为关键路径。
47、在aoe网络中，完成工程所需最短时间是从源点到汇点的最_____路径的长度，这条路径称为关键路径。
第9章 作业
1、对于图中的有向图： （1）请给出每个顶点的入度； （2）请给出邻接矩阵（以教材为准）； （3）请画出所有强连通分量。
2、画出图中的无向图的邻接矩阵。
3、给定一个只有7个顶点（顶点从0开始编号）没有边的有向图，该图以邻接表方式存储，现在使用教材上的insert 函数依次插入以下边： <0,1>,<0,2>,<1,6>,<2,4>,<3,5>,<4,6>,<4,1>，请画出所构建的邻接表。 注意：边结点在链表上出现的次序是重要的！
4、已知图g的邻接表表示如图所示 在此邻接表上进行深度优先搜索遍历，给出遍历序列； 请画出来该遍历过程得到的深度优先搜索生成森林； 在此邻接表上进行宽度优先搜索遍历，给出遍历序列； 请画出来该遍历过程得到的宽度优先搜索生成森林。 注意（请仔细阅读以免答案不满足要求造成扣分） 此题未指定起点，请模拟教材程序给出遍历序列，答案唯一。
5、如图所示有向图，请给出该有向图的拓扑排序序列。
6、用prim 算法构造下图所示连通图的最小代价生成树，以a为起点。 请画出最小代价生成树的构造过程。 提示：构造过程分为5步骤，每个步骤4分。
7、用kruskal 算法构造下图所示的连通图的最小代价生成树。 请画出最小代价生成树的构造过程。 提示：构造过程分为5步骤，每个步骤4分。
期末考试
在线期末试卷客观卷
1、以下哪种逻辑结构描述了数据元素之间多对多的关系_______。
a、树形结构
b、图形结构
c、集合结构
d、线性结构
2、顺序表插入操作的最好时间复杂度是___________,最坏时间复杂度是____________，平均时间复杂度是__________。
a、o(1)，o(n)，o(n)
b、o(1)，o(n)，o(1)
c、o(1)，o(n)，o(n/2)
d、o(n)，o(n)，o(n)
3、后缀表达式12 15 3 / 4 2 ^ 的计算结果是_______。
a、21
b、23
c、25
d、27
4、已知一个二叉树的树形如下图所示，对该二叉树进行中序遍历得到序列为：3,2,4,1,5,7,6，则二叉树中打？号的结点是_________。
a、4
b、5
c、6
d、7
5、给定dag图如下图所示，以下哪个选项不是该图的拓扑序列______。
a、adbcefgh
b、abdefcgh
c、adefgbch
d、abcdefgh
6、关于关键路径，以下说法正确的是_______。 ① 关键路径是从源点到汇点的最长路径 ② 某个关键活动发生延迟，则工程工期一定会延期 ③ 关键路径长度表示一个工程的最长工期 ④ 只要保证了关键活动的按期完成，则工程一定不会发生延期 ⑤ 非关键活动如果提前完成，对工程工期没有影响 ⑥ 关键活动如果可以提前完成，则工程工期必然缩短 ⑦ 非关键活动如果发生延期，可能不会对工程工期造成影响
a、①②⑤⑦
b、①②④⑦
c、②⑤⑥⑦
d、①③⑤⑥
7、设有8×8的数组a按列优先顺序存储，其每个元素占3个字节，已知a[3][6]在内存中的地址是273，a[2][7]的地址是_________ 。
a、294
b、291
c、288
d、297
8、关于对半搜索算法，以下说法错误的是_______。
a、只要是有序表，都可以用对半搜索进行查找
b、元素必须顺序存储，元素必须有序
c、二次判定树的高度取决于元素个数
d、二叉判定树的树形取决于元素个数
9、对具有7个元素的有序表进行对半搜索，搜索成功的平均搜索长度为______。
a、18/7
b、21/8
c、17/7
d、3
10、采用某种排序算法对序列(4,7,5,3,2,9)进行排序，对其进行第二趟排序后得到的序列为(4,5,7,3,2,9)，则该算法最可能是______。
a、冒泡排序
b、堆排序
c、合并排序
d、直接插入排序
11、对有序序列3,5,7,11,19,22,29,48,97执行对半搜索算法，查询元素97需要比较3次。
12、一棵完全二叉树具有100个结点，则该树叶子结点个数是50。
13、冒泡排序、直接插入排序、两路合并排序和堆排序都是稳定的排序算法。
14、序列91,76,67,39,11,31是最大堆
15、双向链表的优点之一是从链表任意位置都可以访问到链表中所有结点
16、含有20个顶点和10条边的无向图用邻接矩阵存储，矩阵中零元素的数量是__________。
17、设有10×5的数组a按行优先顺序存储，其每个元素占2个字节，已知a[0][2]在内存中的地址是104，a[8][2]的地址是_______。
18、用拉链法实现的散列表上，位于相同链表上的关键字互称为_______。
19、已知完全二叉树有100个叶子结点，则完全二叉树树高为______。
20、高度为4的3阶b树，至少包含_______个关键字。
在线期末考试主观卷
1、请对序列 (4,5,10,2,3,1,3,6,7) 进行快速排序，写出前5趟的排序过程，按照如下答题格式进行答题，答题时注意不要漏掉下划线，下划线标错扣分。 答题格式： 第1趟：____________________________ 第2趟：____________________________ 第3趟：____________________________ 第4趟：____________________________ 第5趟：____________________________
2、已知英文字母集合 {a,b,c,d,e,f}及其权值集合{15,10,8,26,22,12}，请给出以上英文字母的哈夫曼编码，要求该编码对应的哈夫曼树上左分支编码为0，右分支编码为1，且任意结点的左孩子权值不大于右孩子权值。 答题格式： a:____________ b:____________ c:____________ d:____________ e:____________ f:____________ wpl=____________
3、请用克鲁斯卡尔算法画出下图的最小代价生成树，注意按照给定的答题格式进行答题，给出最小代价生成树的生成过程。 答题格式：
4、给定一个长度为13的散列表ht如下所示，采用二次探查法解决冲突，散列函数为h(key)=key，请向散列表依次插入关键字为89,15,22,100的集合元素，给出插入完成后的散列表。 i 0 1 2 3 4 5 6 7 8 9 10 11 12 ht[i] 58 84 72 45 24
5、想空avl树依次插入关键字为39,74,15,67,64,59,81,56,52,60的元素，请画出二叉平衡树的构造过程。 注意：要给出10个元素的插入过程，答案应该包含10个逐渐变大的avl树 （数据结构c和数据结构b考生可跳过本题）
6、向4阶b树依次插入1，2，3，4，5，6，7，8，9，10 请画出插入过程，注意答案应该包含10个逐渐变大的b树
7、请画出具有14个元素的有序表对应的二叉判定树
8、请设计算法实现二叉树的复制。相关结构体定义如下： typedef struct btnode { elemtype element; struct btnode *lchild; struct btnode *rchild; } btnode; 给定创建新结点的方法供调用: btnode newnode(elemtype element) 实现递归函数：btnode* copy(btnode *p)
9、设计一个算法计算邻接表表示的图中任意顶点v的出度。边结点和邻接表的结构如下： typedef struct enode { int adjvex; struct enode* nextarc; }enode; typedef struct graph { int n; int e; enode **a; }graph 要求实现方法： int degree(graph g, int v)
10、请完成冒泡排序算法： typedef int bool; void bubblesort(list *list) { int i, j; // i标识每趟排序范围最后一个元素下标，每趟排序元素下标范围是0 ~ i for( （1） ; i>0; i--) { bool isswap = false; //标记一趟排序中是否发生了元素交换 for(j=0; (2) ; j ) { if(list->d[j].key > (3) ) { swap(list->d, j, j 1); (4) ; } } if(!isswap) break; //如果本趟排序没有发生元素交换，排序完成 } }