中国大学数据结构_32期末答案(慕课2023课后作业答案)
86 min read中国大学数据结构_32期末答案(慕课2023课后作业答案)
（一）为什么要学习数据结构(6'33")随堂测验
1、中国作业计算机资源管理器中，大学答案答案对文件（夹）的数据组织用的什么数据结构？
A、表结构
B、结构树结构
C、期末图结构
D、慕课散结构
2、课后数据结构的中国作业研究对象包括
A、数据元素的大学答案答案集合
B、元素之间的数据关系
C、对数据集合进行的结构运算
D、算法及算法评价
3、期末数据结构主要研究非数值计算的慕课问题
（二）数据结构的概念(5'42")随堂测验
1、一个数据结点集合，课后以及集合中____，中国作业组成一个数据结构。
A、结构
B、各结点之间的关系
C、运算
D、算法
2、下面关于数据的逻辑结构与存储结构说法正确的是_____
A、逻辑结构要体现出存储结构
B、存储结构要体现出逻辑结构
C、二者含义是一样的
D、二者毫无关系
3、_____表示结点之间的先后次序关系
A、表结构
B、树结构
C、图结构
D、散结构
4、_____表示结点之间的层次关系
A、表结构
B、树结构
C、图结构
D、散结构
5、物理结构指的是_____
A、数据的物理特征
B、数据的物理类型
C、数据结构的存储表示
D、数据的存储表示
6、基本数据结构包括
A、表结构
B、树结构
C、图结构
D、散结构
（三）算法的概念和描述(7'48")随堂测验
1、《The?Art?of?Computer?Programming》的作者是_____
A、Dijkstra
B、Knuth
C、Turing
D、Huffman
2、算法的描述形式包括
A、自然语言
B、流程图
C、类程序设计语言
D、维恩图（Venn）
3、算法的特征包括有穷性、确定性、可行性和输入输出。
4、对算法的描述包括程序形式和描述形式。
5、描述形式是算法的最终形式。
6、流程图是一种程序形式。
（四）算法的评价随堂测验
1、算法的有效性指的是_____
A、时间复杂性和空间复杂性
B、最坏情况和平均情况
C、制作周期与使用时效的关系
D、制作费用与实用价值的关系
2、下列说法不正确的是_____
A、算法的正确性通常需要人工证明
B、只有对所有合法输入数据都正确的算法才是正确的算法
C、经反复调试、长期运行，也不一定能够发现算法中的错误
D、只有经长期运行，从不出错的算法，才是正确的算法
3、算法复杂性记号T(n)、TW(n)和TE(n)分别代表_____
A、准确的、上界和下界
B、常数阶、多项式阶和指数阶
C、有效的、无效的和最优的
D、一般情况、最坏情况和平均情况
4、算法的空间复杂性是算法对存储空间的需求。
5、低价算法一定比高价算法快。
概述单元测试
1、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的____和运算等的学科。
A、结构
B、关系
C、运算
D、算法
2、在数据结构中，从逻辑上可以把数据结构分成_____。
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
3、数据结构在计算机内存中的表示是指_____。
A、数据的存储结构
B、数据关系
C、数据的逻辑结构
D、数据元素之间的关系
4、在数据结构中，与所使用的计算机无关的是数据的_____结构。
A、逻辑
B、存储
C、逻辑和存储
D、物理
5、算法分析的目的是____。
A、找出数据结构的合理性
B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进
D、分析算法的易懂性和文档性
6、算法分析的两个主要方面是____。
A、空间复杂度和时间复杂度
B、正确性和简明性
C、可读性和文档性
D、数据复杂性和程序复杂性
7、计算机算法指的是____。
A、计算方法
B、排序方法
C、解决问题的有限运算序列
D、调度方法
8、计算机算法必须具备输入、输出和____等5个特性。
A、可行性、可移植性和可扩充性
B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性
D、易读性、稳定性和安全性
9、在决定选取何种存储结构时，一般不考虑_____。
A、各结点的值如何
B、结点个数的多少
C、对数据有哪些运算
D、所用编程语言实现这种结构是否方便
10、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_____。
A、数据的处理方法
B、数据元素的类型
C、数据元素之间的关系
D、数据的存储方法
11、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_____。
A、数据元素具有同一特点
B、不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C、每个数据元素都一样
D、数据元素所包含的数据项的个数要相等
12、以下说法正确的是_____。
A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带结构的各数据项的集合
D、一些表面上很不相同的数据可以有相同的逻辑结构
第二周 顺序表（总时长30'44''）
（一）表结构的基本概念（5'52''）随堂测验
1、线性表是 。
A、一个有限序列，可以为空
B、一个有限序列，不可以为空
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
2、若数组M可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素M[8]的起始地址为_____。
A、x+8
B、x+28
C、x+32
D、x+64
（二）顺序表的插入和删除（5'45''）随堂测验
1、对于顺序存储的长度为n的线性表，在第i个位置插入一个元素需要移动____个元素。其中，0≤i＜n。
A、n-i
B、n-i+1
C、n-i-1
D、i
2、对于顺序存储的长度为n的线性表，删除第i个元素需要移动____个元素。其中，0≤i＜n。
A、n-i
B、n-i+1
C、n-i-1
D、i
3、对于顺序存储的长度为n的线性表，插入、删除一个元素的平均时间复杂度分别是 。
A、O(1) O(n)
B、O(n) O(n)
C、O(1) O(1)
D、O(n) O(1)
（三）顺序表的查找（14'28''）随堂测验
1、顺序查找长度为n的线性表的平均查找长度为_____。
A、n
B、n/2
C、(n+1)/2
D、(n-1)/2
2、对a[12]进行二分查找，在等概率情况下，查找成功的平均查找长度为_____。
A、37/12
B、35/12
C、39/12
D、43/12
3、用二分法对数组a[13]进行查找，若待查元素为x，且a[7]<x<a[8]，那么查找路径为（1）____________（用下标序列表示）
A、6，9，7，8
B、6，9，8
C、6，7，8
D、6，10，7，8
顺序表单元测验
1、线性表的顺序存储最适合于实现 运算。
A、插入
B、删除
C、查找
D、由下标定位
2、对有14个元素的有序表A[14]作二分查找，查找元素A[3]时，将会与 元素依次比较。
A、A[0]，A[1]，A[2]，A[3]
B、A[0]，A[13]，A[6]，A[3]
C、A[6]，A[2]，A[4]，A[3]
D、A[6]，A[4]，A[2]，A[3]
3、如果线性表最常用的操作是取第i个结点及其前驱，则采用_____存储方式最节省时间。
A、单向链表
B、双向链表
C、单向循环链表
D、顺序表
4、线性表是____。
A、一个有限序列，可以为空
B、一个有限序列，不可以为空
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
5、对于顺序存储的长度为n的线性表，在第i个位置插入一个元素需要移动____个元素。其中，0≤i＜n。
A、n-i
B、n-i+1
C、n-i-1
D、i
6、采用顺序查找法查找一个长度为n 的线性表，则查找每个元素的平均比较次数为_____。
A、n/2
B、n
C、(n+1)/2
D、(n-1)/2
7、对线性表进行二分查找时，要求线性表必须采用 _____。
A、顺序存储
B、链式存储
C、顺序存储，且结点有序排序
D、链式存储，且结点有序排序
8、有一个长度为12的有序表，按二分找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_____。
A、35/12
B、37/12
C、39/12
D、43/12
9、若数组M可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素M[8]的起始地址为_____。
A、x+8
B、x+28
C、x+32
D、x+64
10、有序数组a[18]进行二分查找时，查找到a[5]的查找路径（下标序列）为_____。
A、1，3，5
B、8，2，5
C、8，3，5
D、8，4，5
11、用二分法对数组a[13]进行查找，若待查元素为x，且a[7]<x<a[8]，那么查找路径为____________
A、6，9，7，8
B、6，9，7
C、7，9，8
D、6，9，8
12、对于顺序存储的长度为n的线性表，删除第i个元素需要移动____个元素。其中，0≤i＜n。
A、n-i
B、n-i+1
C、n-i-1
D、i
13、用二分法对数组a[13]进行查找，在等概率的情况下，查找不成功的平均查找长度为________。
A、27/7
B、54/13
C、49/14
D、49/13
14、对a[12]进行二分查找，查找下标为_____的元素时，查找长度最大。
A、1，4，7，9，11
B、0，3，6，9，11
C、1，3，6，9，11
D、0，4，8，9，10
第三周 链表（上）(总时长22'57''）
（一）基本概念（11'19''）随堂测验
1、在单向链表中，将结点q插入p所指结点之后的链操作为____。
A、q->next=p->next;p->next=q;
B、p->next=q; q->next=p->next;
C、q->next=p; p->next=q;
D、p->next=q; q->next=p;
2、在单向链表中，删除p所指结点的后继结点的链操作为____（不考虑回收结点）。
A、p->next=p->next->next;
B、p=p->next;
C、p=p->next->next;
D、p->next=p;
3、已知h是指向单向加头链表的头指针，删除首元结点的操作是_____。
A、p=h,h=p->next;free(p);
B、p=h->next;free(p);h=h->next;
C、p=h->next,h->next=p->next;free(p);
D、free(h->next);h=h->next;
（二）单向链表的构造（8'25''）随堂测验
1、已知h是指向单向加头链表的头指针，p指向一个新结点，将p所指结点插在表头的操作是_____。
A、p->next=h,h->next=p;
B、p->next=h->next,h->next=p;
C、p->next=h,h=p;
D、h->next=p,p->next=h->next;
2、已知last指向单向简单链表的尾结点，将s所指结点插入在表尾，正确的操作是____。
A、s->next=s,last=s,last->next=NULL;
B、last->next=s,s->next=NULL,last=s;
C、s->next=NULL, last->next=s, s=last;
D、s->next=last, last->next=NULL,last=s;
（三）单向链表的输出和查找（3'13"）随堂测验
1、在长度为n的单向链表中查找值为x的结点，在查找成功的情况下，平均查找长度为_____。
A、n/2
B、n
C、(n+1)/2
D、(n-1)/2
2、在单链表中，可以从首元结点开始输出任何一个结点元素值。
链表（上）单元测验
1、线性表采用链式存储时，其地址 。
A、必须是连续的
B、部分地址必须是连续的
C、一定是不连续的
D、连续与否均可以
2、从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较_ 个结点。
A、n/2
B、n
C、(n+1)/2
D、(n-1)/2
3、能够满足快速完成插入和删除运算的线性表存储结构是____。
A、顺序存储
B、链式存储
C、散列存储
D、有序存储
4、已知单向链表中指针p指向结点A， 表示删除A的后继结点（若存在）的链操作（不考虑回收）。
A、p—>next=p—>next—>next
B、p=p—>next
C、p=p—>next—>next
D、p—>next=p
5、在一个单向链表中，已知结点*q是*p的前趋结点，若在*q和*p之间插入*s结点，则须执行_____。
A、s—>next= p—>next；p—>next=s；
B、q—>next=s； s—>next= p；
C、p—>next= s—>next；s—>next= p；
D、p—>next=s； s—>next=q；
6、已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是____。
A、last->next=s,last=s,last->next=NULL;
B、last->next=s,s->next=NULL,last=s;
C、s->next=NULL, last->next=s, s=last;
D、s->next=NULL, last->next=s,last=s;
7、已知last指向单向简单链表的尾结点，将s所指结点加在表尾，正确的操作是____。
A、s->next=s,last=s,last->next=NULL;
B、last->next=s,s->next=NULL,last=s;
C、s->next=NULL, last->next=s, s=last;
D、s->next=last, last->next=NULL,last=s;
8、已知h是指向单向加头链表的头指针，p指向一个新结点，将p所指结点插在表头（p指向第一个实际结点）的操作是_____。
A、p->next=h,h->next=p;
B、p->next=h->next,h->next=p;
C、p->next=h,h=p;
D、h->next=p,p->next=h->next;
9、已知h是指向单向加头链表的头指针，删除首元结点（第1个实际元素）的操作是_____。
A、p=h,h=p->next;free(p);
B、p=h->next;free(p);h=h->next;
C、p=h->next,h->next=p->next;free(p);
D、free(h->next);h=h->next;
10、就单一的____运算来说，线性表采用顺序存储比采用链式存储好（n是表长）。
A、存取任意第i（0≤i≤n-1）个结点
B、交换前两个结点的值
C、输出所有结点
D、查找结点x在表中的序号
11、就单一的____运算来说，线性表采用链式存储比采用顺序存储好。
A、删除指定元素
B、输出所有结点
C、查找结点x在表中的序号
D、在表尾处插入一个元素
12、判定以head为头指针的单向简单链表为空的条件是 。
A、head= =NULL
B、head->next= =NULL
C、head->next= =head
D、head!=NULL
13、判定以head为头指针的单向加头链表为空的条件是 。
A、head= =NULL
B、head->next= =NULL
C、head->next= =head
D、head!=NULL
14、链表不具备的特点是_____。
A、可随机访问任一结点
B、插入删除不需要移动元素
C、不必事先估计存储空间
D、所需空间与其长度成正比
15、对一个具有n个元素的线性表，建立单向链表的时间复杂度至少为__ 。
A、O(n)
B、O(1)
C、O(logn)
D、O(n^2)
第三周 链表（下）(总时长18'38''）
（一）链表的种类（4'02''）随堂测验
1、判定以head为头指针的单向加头链表为空的条件是 。
A、head= =NULL
B、head->next= =NULL
C、head->next= =head
D、head!=NULL
2、在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。
（二）复杂链表的基本操作（4'30''）随堂测验
1、在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r(指向尾结点)，执行 操作与链表的长度有关。
A、删除单链表中的第一个元素
B、删除单链表中的最后一个元素
C、在单链表第一个元素前插入一个新元素
D、在单链表最后一个元素后插入一个新元素
2、双向循环链表中，在p所指结点的右侧插入指针s所指结点，其操作是____。
A、p->Rlink=s; s->Llink=p; (p->Rlink)->Llink=s; s->Rlink=p->Rlink;
B、s->Llink=p; s->Rlink=p->Rlink; p->Rlink=s; p->Rlink->Llink=s;
C、p->Rlink=s; p->Rlink->Llink=s; s->Llink=p; s->Rlink=p->Rlink;
D、s->Llink=p; s->Rlink=p->Rlink; p->Rlink->Llink=s; p->Rlink=s;
（三）有序链表的构造（4'28''）随堂测验
1、在长度为n的有序链表中插入结点并保持有序，最坏情况下和平均情况下，时间复杂性分别是_____。
A、O(n)和O(1)
B、O(n)和O(log n)
C、O(n)和O(n)
D、O(logn)和O(n)
链表（下）单元测验
1、在长度为n的有序链表中插入一个结点并保持有序，最坏情况下和平均情况下，时间复杂性分别是_____。
A、O(n)和O(1)
B、O(n)和O(log n)
C、O(n)和O(n)
D、O(nlogn)和O(n)
2、将如图所示的向单向链表中A段和B段交换位置（将B段调到A段的前面，其余结点次序不变），正确的程序段为_______。
A、p->next= q->next；q->next=r->next; r->next=p->next;
B、q->next=r->next; r->next=p->next; p->next=q->next；
C、t=q->next; q->next=r->next; r->next=p->next; p->next=t；
D、t=q->next; q->next=r->next; r->next=q; p->next=t；
3、若某线性表中最常用的操作是在最后一个元素之后插入新元素，或删除第一个元素，则采用 存储方式最节省时间。
A、单链表
B、仅有头指针的单循环链表
C、双链表
D、仅有尾指针的单循环链表
4、对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为_____。
A、O (n)
B、O (1)
C、O (logn)
D、O(n^2)
5、以head为头指针的非空单向循环链表的尾结点（由p所指向）满足_____。
A、p—>next==NULL
B、p==NULL
C、p—>next==head
D、p==head
6、一个长度为n（n>1）的单向链表设有头和尾两个指针，执行_____操作所用时间与表长有关。
A、删除单链表中的第一个元素
B、删除单链表中的最后一个元素
C、在单链表第一个元素前插入一个新元素
D、在单链表最后一个元素后插入一个新元素
7、如果对非空线性表的运算只有如下4种： （1）删除第一个元素；（2）删除最后一个元素；（3）在第一个元素左边插入新元素；（4）在最后一个元素的右边插入新元素。那么，最合适的存储形式是_____。
A、仅有表头指针的单向链表
B、仅有表尾指针的单向链表
C、仅有表头指针的双向循环链表
D、仅有表尾指针的单向循环链表
8、设有两个长度都为n的单向链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_____。
A、对于两个链表来说，删除第一个结点的操作，其时间复杂性都是O（1）
B、对于两个链表来说，删除最后一个结点的操作，其时间复杂性都是O（n）
C、循环链表要比非循环链表占用更多的内存空间
D、h1和h2是不同类型的变量
9、在长度为n的_____上，删除第一个元素，如果不允许移动结点的值，其算法的时间复杂性为O（n）。
A、只有表头指针的不带表头监督元结点的单向循环链表
B、只有表尾指针的不带表头监督元结点的单向循环链表
C、只有表尾指针的带表头监督元结点的单向循环链表
D、只有表头指针的带表头监督元结点的单向循环链表
10、与单向链表相比，双向链表的优点之一是_____。
A、插入、删除操作更简单
B、顺序访问相邻结点更灵活
C、可以省略表头指针或表尾指针
D、可以进行随机访问
11、判定以head为头指针的单向加头循环链表为空的条件是 。
A、head->next= =NULL
B、head= =NULL
C、head->next= =head
D、head!=NULL
12、双向循环链表中，在p所指结点的右侧插入指针s所指结点，其操作是____。
A、p->Rlink=s; s->Llink=p; (p->Rlink)->Llink=s; s->Rlink=p->Rlink;
B、s->Llink=p; s->Rlink=p->Rlink; p->Rlink=s; p->Rlink->Llink=s;
C、p->Rlink=s; p->Rlink->Llink=s; s->Llink=p; s->Rlink=p->Rlink;
D、s->Llink=p; s->Rlink=p->Rlink; p->Rlink->Llink=s; p->Rlink=s;
13、在双向链表中，删除p所指结点（不考虑回收结点）不正确的操作是_____。
A、p->Llink->Rlink=p->Rlink, p->Rlink->Llink=p->Llink;
B、p->Llink= p->Rlink, p->Rlink=p->Llink;
C、p=p->Llink,p->Rlink= p->Rlink->Rlink, p->Rlink->Llink=p;
D、p=p->Rlink,p->Llink= p->Llink->Llink, p->Llink->Rlink=p;
第七周 图结构（上）（总时长48'07''）
（一）图的定义和有关术语(14'57")随堂测验
1、在有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。
A、1
B、1/2
C、2
D、4
2、n个顶点的无向图至多有_____条边。
A、n*n
B、n*n/2
C、n(n+1)/2
D、n(n-1)/2
3、对于简单无向图而言，一条回路至少含有_____条边。
A、2
B、3
C、4
D、5
4、对于n个顶点，m条边的无向图G，说法正确的是______。
A、若m>n，则G必连通
B、若m<n，则G必不连通
C、若m≥n，则G中必含回路
D、若m<n，则G中必不含回路
5、对于有向加权图而言，加权边的权通常满足三角不等式（即：两边之和大于第三边）。
6、无向图G的连通分量是G的极大连通子图。
7、有向图和无向图都具有强连通分量。
8、对于无向加权图而言，其最小生成树有可能不存在，但如果存在的话通常是唯一的。
9、n个顶点的有向图中，顶点的最大度数等于______。
10、如果顶点v到顶点w之间存在一条路径，则称v和w是______。
（二）图的存储方法(8'08")随堂测验
1、具有n个顶点，m条边的无向图，其邻接矩阵共有_____个元素。
A、n
B、(n-1)*(n-1)
C、n-1
D、n*n
2、对于无向图的邻接矩阵，说法正确的是_____。
A、第i行上的非零元素个数和第i列的非零元素个数一定相等
B、矩阵中的非零元素个数等于图中的边数
C、第i行和第i列上非零元素总数等于顶点i的度数
D、矩阵中的非全零行的行数等于图中的顶点数
3、可以采用一维数组对无向图的邻接矩阵进行压缩存储。对于一个包含n个顶点的无向图而言，假设M是其邻接矩阵，A是对M（下三角）进行压缩存储的一维数组。那么M[i][j]=A[i*(i-1)/2+j]，其中0≤j≤i≤n-1。
（三）图的遍历(15'50")随堂测验
1、对于下图所存储的有向图，从顶点A开始进行先广搜索，不能得到的顶点序列是______。
A、ABCDE
B、ACBDE
C、ABCED
D、ADCEB
2、图的先广搜索是二叉树_____的推广。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
3、对含有k个连通分量的无向图进行先深搜索时，主控函数中需要调用递归的搜索函数dfs_____次。
A、k
B、1
C、k-1
D、k+1
4、以下说法不正确的是____。
A、对非连通的无向图不能进行先广搜索
B、实现先广搜索通常要用到队
C、实现先深搜索通常要用到栈
D、对有向图也能进行先广搜索
5、对于下图所示的无向图，若从顶点A开始进行先深搜索，可得到的顶点序列可能为________。
A、ABDFCEGH
B、ABCHDEGF
C、ADECHBFG
D、AFBDCEGH
6、通过对无向图进行先深搜索，可以判断该图是否是连通图，或找出图的连通分量及先深生成树。
图结构（上）单元测验
1、在有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。
A、1
B、1/2
C、2
D、4
2、对于简单无向图而言，一条回路至少含有_____条边。
A、2
B、3
C、4
D、5
3、对于n个顶点，m条边的无向图G，说法正确的是______。
A、若m>n，则G必连通
B、若m<n，则G必不连通
C、若m≥n，则G中必含回路
D、若m<n，则G中必不含回路
4、对于无向图的邻接矩阵，说法正确的是_____。
A、第i行上的非零元素个数和第i列的非零元素个数一定相等
B、矩阵中的非零元素个数等于图中的边数
C、第i行和第i列上非零元素总数等于顶点i的度数
D、矩阵中的非全零行的行数等于图中的顶点数
5、对于下图所存储的有向图，从顶点A开始进行先广搜索，不能得到的顶点序列是______。
A、ABCDE
B、ACBDE
C、ABCED
D、ADCEB
6、对于下图所示的无向图，若从顶点A开始进行先深搜索，可得到的顶点序列可能为________。
A、ABDFCEGH
B、ABCHDEGF
C、ADECHBFG
D、AFBDCEGH
7、图的先广搜索是二叉树_____的推广。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
8、以下说法正确的是____。
A、对非连通的无向图不能进行先广搜索
B、实现先广搜索通常要用到队
C、实现先深搜索通常要用到栈
D、对有向图也能进行先广搜索
9、无向图G的连通分量是G的极大连通子图。
10、对于无向加权图而言，其最小生成树有可能不存在，但如果存在的话通常是不唯一的。
11、可以采用一维数组对无向图的邻接矩阵进行压缩存储。对于一个包含n个顶点的无向图而言，假设M是其邻接矩阵，A是对M（下三角）进行压缩存储的一维数组。那么M[i][j]=A[i*(i+1)/2+j]，其中0≤j≤i≤n-1。
12、通过对无向图进行先深搜索，一定可以判断该图是否是连通图，或找出图的连通分量及先深生成树。
13、n个顶点的有向图中，顶点的最大度数等于______。
14、对含有k个连通分量的无向图进行先深搜索时，主控函数中需要调用递归的搜索函数dfs_____次。
第四周 栈和队（总时长24'53''）
（一）栈（15'24''）随堂测验
1、栈是一种对进栈、出栈操作总次数作了限制的线性表。
2、栈是后进先出的线性表，因此对序列1，2，3依次执行进栈操作，则出栈序列只能得到321。
（二）队（9'29''）随堂测验
1、数组q[M]存储一个循环队，first和last分别是首尾指针。当前队中元素个数为_____。
A、(last- first+M)%M
B、last-first+1
C、last-first-1
D、last-first
2、队是先进先出的线性表，元素1，2，3按顺序进队，其出队顺序只能是1，2，3。
栈和队单元测验
1、链栈与顺序栈相比有一个明显的优点，即 。
A、插入操作更方便
B、通常不会出现栈满的情况
C、不会出现栈空的情况
D、删除操作更加方便
2、设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p1=3，则p2为_____。
A、可能是2
B、不可能是2
C、可能是1
D、必是1
3、已知hs为首指针的简单单向链表存储一个栈，使指针s所指结点进栈的操作是____。
A、hs->next=s;
B、s->next=hs;hs=s;
C、s->next=hs->next; hs->next=s;
D、s->next=hs;hs=hs->next;
4、数组q[M]（M等于6）存储一个循环队，first和last分别是首尾指针。已知first和last的当前值分别等于2和5，且q[5]存放的是队尾元素。当从队列中删除两个元素，再插入一个元素后，first和last的值分别等于_____。
A、3和6
B、4和0
C、1和3
D、5和1
5、对于链队，在进行删除操作时， 。
A、仅修改头指针
B、仅修改尾指针
C、头、尾指针都要修改
D、头、尾指针可能都要修改
6、设进栈次序为ABCDE，______是不可能得到的出栈序列。
A、ABCDE
B、BCDEA
C、EABCD
D、EDCBA
7、设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p3=1，则p1为_____。
A、必是2
B、可能是3
C、必定是3
D、不可能是3
8、数组S[M]存储一个栈，top为栈顶指针。如果条件top= =-1表示栈空，在栈不空的情况下，栈顶元素为_____。
A、S[top-1]
B、S[top]
C、S[top+1]
D、S[++top]
9、数组S[M]存储一个栈，top为栈顶指针。如果条件top= =M表示栈满，那么条件_____表示栈空。
A、top= =1
B、top= =-1
C、top= =0
D、top!=0
10、数组q[M]存储一个循环队，first和last分别是首尾指针，如果使元素x进队操作的语句为“q[last]=x,last=(last+1)%m;”那么判断队满的条件是_____。
A、last= =first
B、last= =M-1
C、(last+1)%m= =first
D、last+1= =first
11、数组q[M]存储一个循环队，first和last分别是首尾指针。如果使元素x出队操作的语句为“first=(first+1)%m, x=q[first];”。那么元素x进队的语句是_____。
A、last=(last+1)%m,q[last]=x;
B、x=q[last], last =(last+1)%m;
C、q[last+1]=x;
D、q[(last+1)%m]=x;
12、一个单向简单链表存储的栈，其栈顶指针为top。执行操作______可将原栈顶元素退栈，并存放在变量x中（不考虑回收结点）。
A、x=top; top=top->next;
B、x=top->data;
C、top=top->next; x= top->data;
D、x=top->data; top=top->next;
13、首尾指针分别是f和r的单向加头链表存储一个队，元素x出队的语句为“f=f->next, x=f->data;”，那么判断队空否的条件是_____。
A、f= =r
B、f= =NULL
C、f->next= =r
D、f->next=NULL
14、设进栈序列是p1，p2，p3，…，pn，输出序列为1，2，3，…，n。若p3=1，则p1为_____。
A、可能是2
B、不可能是2
C、必是2
D、必定是3
15、数组q[M]存储一个循环队，first和last分别是首尾指针。当前队中元素个数为_____。
A、(last- first+M)%M
B、last-first+1
C、last-first-1
D、last-first
第四周 散列表(总时长30'11'')
（一）散列函数(7'08'')随堂测验
1、散列表需要体现结点之间原有的先后次序。
2、散列函数必须保证一一映射关系。
（二）散列表的处理算法(23'03'')随堂测验
1、假定有k个元素的散列函数值相等（称为同义词），若用线性探测法把这k个元素逐一插入散列表中，至少要进行_____次探测。
A、k-1
B、k
C、k+1
D、k (k+1)/2
2、已知散列表a[14]中，a[4]~a[7]已有元素占用，其余为空。散列函数为 hash(k) = k mod 11,用开放地址法和平方探测法解决冲突，当插入元素49时，得到的散列地址为（）。
散列表单元测试
1、顺序查找法最适合用于（）的线性表。
A、散列存储
B、顺序存储或链式存储
C、压缩存储
D、分段存储
2、平均情况下，查找速度最快，而且又能适应插入、删除的数据结构是（）。
A、顺序存储的有序表
B、链式存储的有序表
C、散列表
D、链式存储的无序表
3、数组a[m]存储的散列表，散列函数为：hash(x)=x mod p,一般情况下，p取（）时，散列结果可能比较平均。
A、小于m的最大奇数
B、小于m的最大素数
C、小于m的最大偶数
D、小于m的最大合数
4、以下说法错误的是_____。
A、散列存储的基本思想是由元素值决定其存储地址
B、散列表的结点中只包含数据元素自身的信息，不包含任何指针
C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度
D、散列表的查找效率主要取决于的散列函数和处理冲突的方法
5、设散列表长m=14，散列函数Hash(x)=x mod 11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。若用平方探测法处理冲突，插入元素49时，其地址是_____。
A、8
B、3
C、5
D、9
第五周 树结构（上）（总时长53'24"）
（一）树的基本概念和存储方法（24'00"）随堂测验
1、已知(L,N)，(G,K)，(G,L)，(G,M)，(B,E)，(B,F)，(D,G)，(D,H)，(D,I)，(D,J)，(A,B)，(A,C)，(A,D)是表示一棵树中具有父子关系的边，那么： 是树的根，树的高度为 ，结点G的度数是 ，叶结点数为 。
A、C，5，2，8
B、A，5，3，9
C、A，6，3，8
D、A，5，2，8
（一）树的基本概念和存储方法（24'00"）随堂测验
1、树的多重链接存储法中每个结点需要存储的指针链域个数为 。
A、树的结点数
B、树的结点度数的最大值
C、树的元数
D、树的边数
（一）树的基本概念和存储方法（24'00"）随堂测验
1、含3个结点的二叉树的树形共有____种。
A、2
B、5
C、6
D、7
（一）树的基本概念和存储方法（24'00"）随堂测验
1、图中所示的二叉树是由某森林转换而来的，那么原森林中，共有_____棵树。
A、3
B、4
C、5
D、6
（二）二叉树的遍历（15'54"）随堂测验
1、二叉树的中序序列之中，根结点r的右边_____。
A、只有r所有的右子孙
B、只有r的一部分右子孙
C、只有r的一部分左子孙
D、只有r所有的左子孙
（二）二叉树的遍历（15'54"）随堂测验
1、具有相同先序序列的n个不同结点的二叉树共有 棵。
A、n！
B、C(2n,n)/(n＋1)
C、2^n
D、不确定
（二）二叉树的遍历（15'54"）随堂测验
1、通过 遍历可以求得二叉树结点的层数。
A、先序
B、中序
C、后序
D、按层
（三）二叉树的构造（13'30"）随堂测验
1、下面哪种说法是正确的 。
A、不同的二叉树，其先序序列不同。
B、中序序列相同的二叉树不一定相同。
C、二叉树的先序、中序、后序中任何二个序列都可唯一确定二叉树。
D、二叉树的先序、中序、后序序列不能确定二叉树。
（三）二叉树的构造（13'30"）随堂测验
1、二叉树的先序序列为ABDGCEF，中序序列为DGBAECF，则其后序序列是___________。
A、ABDGCEF
B、GDBEFCA
C、DGBAECF
D、FGEBDCA
（三）二叉树的构造（13'30"）随堂测验
1、已知二叉树的先序序列是15，5，3，10，8，11，18，24，而后序序列是3，8，11，10，5，24，18，15，除结点18只有右儿子而无左儿子之外，其余每个非叶结点均有两个儿子。那么，它的中序序列是____________。
A、3，5，8，10，11，15，18，24
B、3，15，18，10，11，5，8，24
C、5，15，3，10，8，11，18，24
D、3，8，10，11，5，24，18，15
树结构（上）单元测验
1、若三元树中，度数为1，2，3的结点数分别是2，1，3。叶子数必为____个。
A、4
B、5
C、6
D、8
2、含3个结点的普通树的树形共有___ _种。
A、5
B、2
C、6
D、7
3、具有50个结点的三元树，其高度的最小值为____。
A、3
B、4
C、5
D、6
4、若需要经常查找结点的父亲，采用树的 存储法性能较好。
A、树的多重链接法
B、树的儿子兄弟链法
C、树的完全存储法
D、树的父亲链域法
5、若二叉树中，2度结点数为m，则叶子数为____。
A、m
B、m+1
C、2m
D、m-1
6、高度为h的正则二叉树至少有_____结点。
A、2h-1
B、2h+1
C、2^h
D、2^h+1
7、图中，_____都是完全二叉树。
A、1、2、4
B、1、2、3
C、2、3、4
D、1、3、4
8、具有n片叶子的完全二叉树共有 个。
A、1
B、2
C、n
D、不确定
9、图中由3棵树组成的森林所转换成的二叉树有 片叶子。
A、3
B、4
C、5
D、6
10、二叉树的中序序列之中，结点a排在结点b之前的条件是_____。
A、a在b右方
B、a是b祖先
C、a在b左方
D、a是b子孙
11、对普通树先根遍历的规则是：先访问根结点，再依次先根遍历根的各个子树；后根遍历的规则是：先依次后根遍历根的各个子树，再访问根结点。对普通树T先根遍历和后根遍历得到先根序列和后根序列，与将T转换成二叉树B的先序序列、中序序列、后序序列之间的关系是_____。
A、T的先根序列与B的先序序列相同
B、T的后根序列与B的后序序列相同
C、T的先根序列与B的中序序列相同
D、无简单的对应关系
12、如图所示：二叉树1的先序序列为_____________，二叉树2的中序序列分别为_____________。
A、ABDGCEFH，ABDEFCG
B、ABDGCEFH，DFEBAGC
C、DGBAECHF，DFEBAGC
D、GDBEHFCA，ABDEFCG
13、设二叉树的结点个数为n，采用双链法存储，其递归先序遍历算法如下： void suorder(Bptr p) { 0. if(!p)return; 1. visit(p); 2. suorder(p->Lson); 3. suorder(p->Rson); 4.} 主调语句为：suorder(root); 递归遍历算法执行时，要进行 次空调用。
A、n-1
B、n
C、n+1
D、不确定
14、通过 遍历可以求得二叉树结点的高。
A、先序
B、中序
C、后序
D、按层
15、通过 遍历可以删除二叉树中所有的叶子结点。
A、先序
B、中序
C、后序
D、按层
16、二叉树按层遍历算法实现时采用了数据结构 。
A、栈
B、数组
C、队
D、文件
17、下面哪种说法是不正确的 。
A、正则二叉树，可由其先序序列唯一确定。
B、完全二叉树，可由其先序序列唯一确定。
C、完全二叉树，可由其中序序列唯一确定。
D、满二叉树，可由其后序序列唯一确定。
18、二叉树的后序序列为DBKHFEGCA，中序序列为DBAKHEFCG，则其先序序列是__________。
A、ABFHGKCED
B、GDBEFCAHK
C、KHDGBAECF
D、ABDCEHKFG
19、正则二叉树的先序序列为ABCDE，后序序列为BDECA，则其中序序列是__________。
A、ABCED
B、DBCAE
C、BADCE
D、ABDCE
20、已知二叉树的扩充先序序列是“ABC空空DE空FG空空空空空”。那么，它的中序序列是__________。
A、ABCEDGF
B、DBCAEFG
C、CBEGFDA
D、GABFDCE
第六周 树结构（下）（总时长57'13"）
（一）检索树（17'32"）随堂测验
1、已知检索树的先序序列是18，16，8，29，21，27，38，那么，它的后序序列是________________。
A、18，16，8，29，21，27，38
B、18，29，21，27，38，16，8
C、8，16，27，21，38，29，18
D、8，16，18，21，27，29，38
（一）检索树（17'32"）随堂测验
1、如图所示检索树，其成功平均查找长度为__ __。
A、2.5
B、3.2
C、2.9
D、2.7
（一）检索树（17'32"）随堂测验
1、由输入序列46，70，25，15，28，10，36，78，55所构造的检索树，其先序序列是_____________。
A、46，25，15，10，28，36，70，55，78
B、36，15，25，10，28，46，78，55，70
C、78，55，15，70，28，36，10，25，46
D、55，15，10，46，25，36，78，58，70
（一）检索树（17'32"）随堂测验
1、由输入序列46，70，25，15，28，10，36，78，55，30，32所构造的检索树，删除结点46，它的后序序列是__________。
A、10，15，32，30，28，25，55，78，70，36
B、10，15，36，28，25，55，78，70，30，32
C、25，15，10，28，36，30，32，70，55，78
D、30，32，55，15，10，25，36，78，58，70
（二）平衡树（26'43"）随堂测验
1、具有5层结点的AVL树至少有 个结点。
A、17
B、15
C、10
D、12
（二）平衡树（26'43"）随堂测验
1、平衡树插入时，若进行LL旋转，则插入点是失衡结点的 。
A、左儿子的右子孙
B、右儿子的左子孙
C、左儿子的左子孙
D、右儿子的左子孙
（二）平衡树（26'43"）随堂测验
1、平衡树插入时，若进行LR旋转，则插入点是失衡结点的 。
A、左儿子的右子孙
B、右儿子的左子孙
C、左儿子的左子孙
D、右儿子的左子孙
（二）平衡树（26'43"）随堂测验
1、将结点13，24，37，90，53插入开始为空的平衡树，其先序遍历序列为 。
A、13，24，37，90，53
B、24，13，37，90，53
C、24，13，53，37，90
D、13，37，24，90，53
（二）平衡树（26'43"）随堂测验
1、根据视频授课中所给出的“平衡树插入算法”，对于插入序列：13、24、37、90、53，算法执行过程中结点24的平衡因子的变化过程为 。
A、1、0、1、0
B、0、1、0
C、0、1、0、1
D、0、1、0、1、2、1
2、根据视频授课中所给出的“平衡树插入算法”，下面说法正确的是 。
A、若结点和其左儿子的平衡因子都为1时，进行LL旋转
B、若结点平衡因子为1，其左儿子的平衡因子为1时，进行LR旋转
C、若结点和其左儿子的平衡因子都为-1时，进行LL旋转
D、若结点平衡因子为0，其左儿子的平衡因子为1时，进行LR旋转
（二）平衡树（26'43"）随堂测验
1、下面说法 是正确的。
A、平衡树插入一个结点最多只进行一次旋转即平衡。
B、平衡树删除一个结点最多只进行一次旋转即平衡。
C、平衡树插入一个结点要进行多次旋转才平衡。
D、平衡树删除一个结点最多进行二次旋转即平衡。
（三）哈夫曼树（12'58"）随堂测验
1、在哈夫曼树中，权值较大的叶子结点一般离根结点较远。
（三）哈夫曼树（12'58"）随堂测验
1、用权：2，12，4，14，3，16，构造Huffman树，则W(T)=___ _。
A、123
B、110
C、102
D、116
（三）哈夫曼树（12'58"）随堂测验
1、已知字符集{ A，B，C，D，E，F}各字符的Huffman编码依次是011，010，10，001，11，000，那么，对编码序列“01011011000111011001”的译码结果是___________。
A、ABCDEFED
B、BEAFECED
C、BEAEFCFD
D、BFAEFCFD
（三）哈夫曼树（12'58"）随堂测验
1、试完成编码表生成算法coding。根结点指针root指向的是具有n片叶子的哈夫曼树（若p指向结点，则p->Lson、p->Rson分别指向该结点的左、右儿子）。其中，pcode函数完成一个字符编码的输出（不必关心该函数的实现方式），变量top和数组hfcdstr是整体量。 函数调用的方法是：top=-1; coding(root); void coding(ptr p) { if （p!=NULL） if ( ___________________ ) pcode(p,top) ; else { top=_________; ____ _; coding(p->Lson); hfcdstr[top]='1'; _______ __; ___ ______; } } ①p->Lson==NULL&&p->Rson==NULL ②p->Lson &&p->Rson ③top-1 ④top+1 ⑤top=top+1 ⑥top=top-1 ⑦hfcdstr[top]='0' ⑧coding(p->Lson) ⑨hfcdstr[top]='1' ⑩coding(p->Rson) 函数中，下划线位置依次填入 。
A、①⑤⑦⑧⑥
B、②④⑨⑧⑥
C、②④⑦⑧③
D、①④⑦⑩⑥
树结构（下）单元测验
1、已知检索树的后序序列是12，21，19，67，45，23，那么，它的先序序列是________________。
A、21，12，19，23，45，67
B、23，19，12，21，45，67
C、23，19，21，12，67，45
D、23，45，12，67，19，2
2、若检索树中序序列是从小到大的序列，下列说法正确的是 。
A、检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，比其右子树中所有结点关键字小。
B、检索树中，每个结点的关键字都比其左孩子关键字大或相等，比其右孩子关键字小。
C、检索树中，每个结点的关键字都不比其左孩子关键字大或相等，不比其右孩子关键字小。
D、检索树中，每个结点的关键字都比其右子树中所有结点关键字大或相等，比其左子树中所有结点关键字小。
3、如图所示检索树，其不成功查找的平均查找长度为_ ___。
A、3
B、4
C、15/6
D、21/6
4、在关键字随机分布的情况下，用检索树的方法进行查找，其查找长度与 数量级相当。
A、顺序查找
B、折半查找
C、前两者均不正确
D、前两者均正确
5、由输入序列46，70，25，15，28，10，36，78，55所构造的检索树，其后序序列是___________。
A、36，15，25，10，28，46，78，55，70
B、10，15，36，28，25，55，78，70，46
C、46，25，15，10，28，36，70，55，78
D、55，15，10，46，25，36，78，58，70
6、由输入序列46，70，25，15，28，10，36，78，55所构造的检索树，在此树上插入结点30和32后，它的先序序列是___________。
A、36，30，15，25，10，28，32，46，78，55，70
B、10，15，36，28，25，55，78，70，46，30，32
C、46，25，15，10，28，36，30，32，70，55，78
D、46，32，55，15，10，30，25，36，78，58，70
7、若检索树中，每个结点，其左子树中所有结点值都比其小或相等，其右子树中所有结点值都比其大，删除结点时，若被删除结点有二个儿子，则真正删除的是 。
A、该结点的父亲结点
B、该结点的中序前驱结点，或中序后继结点
C、该结点的中序后继结点
D、该结点的中序前驱结点
8、如图所示的4棵二叉树， 是平衡二叉树。
A、A
B、B
C、C
D、D
9、含有15个结点的平衡二叉树的最大高度为 。
A、4
B、5
C、6
D、7
10、在一棵AVL树中，每个结点的平衡因子（整数）的取值范围是 。
A、-l～1
B、-2～2
C、1～2
D、0～1
11、若树的结点个数相同，则下面 是查找效率最高的树。
A、所有结点的左子树都为空的检索树
B、所有结点的右子树都为空的检索树
C、平衡二叉树
D、检索树
12、按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LL旋转，则插入前后失衡结点的平衡因子 。
A、由1变为2
B、不变
C、由2变为1
D、由-1变为-2
13、按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LL旋转，则插入前失衡结点的左儿子的平衡因子是 。
A、0
B、1
C、-1
D、-2
14、按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LR旋转，则插入前后失衡结点的平衡因子 。
A、由1变为2
B、不变
C、由2变为1
D、由-1变为-2
15、平衡树插入时，若进行LR旋转，则旋转后原失衡结点的位置被插入前其 替换。
A、左儿子的左儿子
B、左儿子的右儿子
C、右儿子的左儿子
D、右儿子的右儿子
16、依次插入20，8，17，25，30，18来构造开始为空的平衡二叉树，其构造过程中经过的旋转方式依次为 。
A、LL，RR，RL
B、LR，RR，RL
C、LR，RR，RR
D、LR，RR，LL
17、若有一个整数序列，把这些整数依次插入开始为空的平衡树，使四种旋转LL，RR，LR，RL各至少一次，则此整数序列至少有 个数。
A、4
B、9
C、12
D、7
18、依次删除如图所示的AVL树中的结点47、17、22、9、39，则删除过程进行的旋转方式依次为 。
A、LL，RR，RL，LR
B、LR，RR，RL，LL
C、LL，RL，RR，LR
D、RL，LR，RR，LL
19、下列说法正确的是 。
A、在哈夫曼树中，权值相同的叶子结点都在同一层上。
B、在哈夫曼树中，权值较大的叶子结点一般离根结点较远。
C、哈夫曼树中不存在度为1的结点。
D、以上说法都不正确。
20、以序列2，3，23，9，12，14，6，8，15，17作为叶之权的三元Huffman树，其W(T)=___ _。
A、298
B、210
C、219
D、156
21、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有 个结点。
A、13
B、12
C、26
D、25
22、根据哈夫曼编码，字母ABCDE的不等长编码不可能是_____。
A、111，110，10，01，00
B、000，001，010，011，1
C、100，11，10，1，0
D、001，000，01，11，10
23、学生成绩分布情况如表所示，现有10000个学员成绩数据，利用哈夫曼树，设计最好的比较判断逻辑结构，最少需要 次比较 分数段 0~59 60~69 70~79 80~89 90~100 比例 0.05 0.15 0.40 0.30 0.10 五分制 不及格 及格 中 良 优
A、22000
B、21000
C、18050
D、20500
24、设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短，其总码长为 。
A、18
B、144
C、31
D、36
第八周 图结构（下）（总时长40'56''）
（一）最小生成树（27'11"）随堂测验
1、用Prim算法，以G为初始生长点，求下图的最小生成树时，依次得到的树边为：_____。
A、GB4、BC2、AB3、CD5、ED10、EF9
B、BC2、AB3、GB4、CD5、EF9、ED10
C、GB4、BC2、CD5、ED10、EF9、AB3
D、AB3、BC2、GB4、CD5、ED10、EF9
2、对于下图中的加权图，其最小生成树的边长之和等于______。
（二）最短路径（13'45"）随堂测验
1、下面不正确的说法是_____。 （1）边的权不能为负的主要原因是无实际意义。 （2）Dijkstra算法经修改后可以用于含负长度的边（但不含负回路）的加权图。 （3）用Dijkstra算法求每一对顶点之间最短路径的时间复杂性为O(n*n*n)。 （4）用Kruskal算法与用Prim算法求同一个无向连通加权图的最小生成树，所得结果必然是一样的。
A、（1）（2）（3）
B、（1）（3）
C、（1）（4）
D、（2）（4）
2、用Dijkstra算法求下图顶点A到其余各顶点的最短路径时，将按照__________的次序，依次求出A到它们的最短路径。
A、BEDFC
B、BEDCF
C、BCEDF
D、EDFCB
图结构（下）单元测验
1、用Prim算法，以G为初始生长点，求下图的最小生成树时，依次得到的树边为：_____。
A、GB4、BC2、AB3、CD5、ED10、EF9
B、BC2、AB3、GB4、CD5、EF9、ED10
C、GB4、BC2、CD5、ED10、EF9、AB3
D、AB3、BC2、GB4、CD5、ED10、EF9
2、用Dijkstra算法求下图顶点A到其余各顶点的最短路径时，将按照__________的次序，依次求出A到它们的最短路径。
A、BEDFC
B、BEDCF
C、BCEDF
D、EDFCB
3、下面不正确的说法是_____。 （1）边的权不能为负的主要原因是无实际意义。 （2）Dijkstra算法经修改后可以用于含负长度的边（但不含负回路）的加权图。 （3）用Dijkstra算法求每一对顶点之间最短路径的时间复杂性为O(n*n*n)。 （4）用Kruskal算法与用Prim算法求同一个无向连通加权图的最小生成树，所得结果必然是一样的。
A、（1）（2）（3）
B、（1）（3）
C、（1）（4）
D、（2）（4）
4、对于下图中的加权图，其最小生成树的边长之和等于______。
第九周 排序（上）(总时长51'51"）
（一）排序的基本概念(4'41'')随堂测验
1、如果某种排序方法能够使任何数值相等的元素，排序以后相对次序不变，那么这种排序方法就是_____的排序方法。
A、原地
B、稳定
C、快速
D、自然
2、外排序是指_____的排序方法。
A、在计算机系统外进行
B、在外存上进行
C、对外存上的数据进行排序，排序时将一部分数据调入内存
D、数据很大，需要人工干预
（二）插入排序(14'14'')随堂测验
1、排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方 法，称为 。
A、希尔排序
B、归并排序
C、插入排序
D、选择排序
2、从未排序的序列中顺次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序。
A、选择
B、希尔
C、直接插入
D、二分插入
3、在对n个元素进行直接插入排序的过程中，算法的空间复杂度（ ）。
A、O(1)
B、O(logn)
C、O(n^2)
D、O(nlogn)
4、希尔排序的关键字比较的次数与记录的初始排列次序无关。
5、因为二分插入排序对直接插入排序进行了改进，使得查找插入位置的时间效率由n改进为log2n,因此二分插入排序算法时间复杂度比直接插入排序更低。
6、设有一无序序列{ 32，45，41，12，1，9}，进行从小到大的希尔排序，首次分组增量d=3，则一趟希尔排序后的序列为__ 。
（三）交换排序(18'11'')随堂测验
1、设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，且从后往前进行比较，则第一趟冒泡排序的结果为（ ）。
A、2，5，3，6， 8
B、2，5，6，3，8
C、2，3，5，6， 8
D、2，3，6，5，8
2、对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。
A、1, 3, 5, 7, 9
B、9, 7, 5, 3, 1
C、5, 1, 3, 7, 9
D、5, 7, 9, 3, 1
3、直接插入排序和冒泡排序在初始数据基本有序的情况下，时间复杂性均为____。
A、O(n)
B、O(logn)
C、O(nlogn)
D、O(n^2)
4、当要排序的数据_____的情况下，快速排序方法最不利于发挥其长处。
A、元素太多
B、数值太大
C、基本有序
D、次序太乱
（四）选择排序(14'45'')随堂测验
1、元素比较次数与初始排列次序无关的是_____排序。
A、直接插入
B、冒泡
C、二分插入
D、简单选择
2、用简单选择排序方法对 n 个元素进行排序时，最坏情况下，比较的次数与移动次数分别是_____。
A、O(n)和 O(log n)
B、O(logn)和 O(n^2)
C、O(n^2)和 O(n^2)
D、O(nlogn)和 O(n)
3、一组记录的排序码为{ 46，79，56，38，40，84}，则利用堆排序（建立大根堆）的方法建立的初始堆为_____。
A、79，46，56，38，40，80
B、84，79，56，38，40，46
C、84，79，56，46，40，38
D、84，56，79，40，46，38
4、从 10000 个无序元素中选出前 10 个最大元素，最好采用_____排序方法。
A、冒泡
B、快速
C、堆
D、插入
5、如果原始数据已有序，那么，使用_____排序算法最快。
A、冒泡
B、直接插入
C、简单选择
D、堆
排序（上）单元测试
1、如果排序过程中，序列的变化情况依次是： （1）25，84，21，47，15，27，68，35，20（原始排列） （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 那么，所用的排序方法是_____排序。
A、选择
B、冒泡
C、插入
D、快速
2、在对n个元素进行快速排序的过程中，若每次划分得到的两个数据段的长度相等或只差一个元素，则排序的时间复杂度为 。
A、O(1)
B、O(nlogn)
C、O(n^2)
D、O(n)
3、_____可以满足稳定性要求。
A、直接插入排序和冒泡排序
B、直接插入排序和快速排序
C、冒泡排序和堆排序
D、快速排序和简单选择排序
4、在对n个元素进行改进的冒泡排序的过程中，最好情况下的时间复杂度为 ____ 。
A、O(1)
B、O(logn)
C、O(n^2)
D、O(n)
5、一组记录的排序码为{ 79，46，84，38，40，56}，则利用堆排序（建立小根堆）的方法建立的初始堆为 ____。
A、38，79，56，46，40，84
B、38，46，40，56，79，84
C、38,40,56,46,79,84
D、84，56，79，40，46，38
6、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是 。
A、直接插入排序
B、快速排序
C、简单选择排序
D、堆排序
7、对n个元素进行快速排序，第一次划分最多需要移动 次元素，假定包括基准和临时量之间的移动。
A、n/2
B、n-1
C、n
D、n+1
8、插入排序和选择排序是都不稳定。
9、插入排序时间复杂度大于选择排序时间复杂度。
10、在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较____ 次。
第十周 排序（下）（总时长17'29"）
（一）合并排序(7'45'')随堂测验
1、下述几种排序方法中，要求内存最大的是 。
A、插入排序
B、快速排序
C、合并排序
D、选择排序
2、若对n个元素进行合并排序，则进行每一趟合并的时间复杂性为___。
A、O(1)
B、O(logn)
C、O(n)
D、O(n^2)
3、将两个各有n个元素的有序表合并成一个有序表，最少比较___次。
4、对20个记录进行合并排序时，共需要进行________趟归并。
（二）基数排序(9'44'')随堂测验
1、若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选 排序为宜。
A、直接插入
B、简单选择
C、堆
D、基数
排序（下）单元测试
1、在下面的排序方法中，辅助空间为O（n）的是 。
A、直接插入排序
B、选择排序
C、快速排序
D、合并排序
2、对初始状态为递增序列的表按递增顺序排序，最省时间的是 算法，最费时间的是 算法。
A、堆排序、简单选择排序
B、直接插入排序、快速排序
C、快速排序、合并排序
D、冒泡排序、堆排序
3、就平均性能而言，目前最好的内排序方法是 排序法。
A、冒泡
B、交换
C、希尔
D、快速
4、如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用 排序最快。
A、冒泡
B、快速
C、希尔
D、基数
5、需要对5个不同的数据进行排序，则至少需要比较 次;对5个数据进行排序，如果5个数据已经有序，但我们并不知道，最少比较 次可结束排序;
A、4,4
B、7,4
C、6,7
D、7，7
6、若要对1000个元素进行排序，要求又快又稳定，则最好采用（）方法
A、插入排序
B、快速排序
C、合并排序
D、堆排序
7、对n个数据进行堆排序的空间复杂度为 。
A、O(1)
B、O(nlogn)
C、O(n)
D、O(n^2)
8、对记录的关键码{ 50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为： 50,26,38,80,70,90 ,8,30,40,20 50,8,30,40,20,90,26,38,80,70 26,8,30,40,20,80,50,38,90,70 8,20,26,30,38,40,50,70,80,90 其使用的排序方法是 。
A、快速排序
B、基数排序
C、希尔排序
D、堆排序
9、下面各种排序方法中，最好情况下时间复杂度为O(n)的是 。
A、快速排序
B、直接插入排序
C、堆排序
D、合并排序
10、在所有排序方法中，________排序方法使数据的组织采用的是完全二叉树的结构。
A、合并排序
B、快速排序
C、二分插入排序
D、堆排序
中国大学数据结构_32
数据结构是计算机科学中一门非常重要的课程，是计算机科学的基础。在中国的大学中，数据结构是计算机科学专业的重要课程之一。通过学习数据结构，学生们可以了解计算机内存如何管理，数据如何存储和如何处理数据，这对于未来的计算机科学家至关重要。
课程概述
在中国大学的数据结构课程中，学生们将学习以下内容：
- 基本数据结构：数组、链表、栈和队列等
- 树和二叉树：二叉搜索树、AVL树、B树等
- 图的表示和遍历：深度优先搜索、广度优先搜索等
- 高级数据结构：散列表、红黑树、堆等
- 算法分析：时间复杂度和空间复杂度
- 算法设计：贪心算法、动态规划、分治法等
- 并查集和图论算法
- 应用场景：哈夫曼编码、最短路径、最小生成树等
学习方法
在学习数据结构的过程中，学生们需要掌握一些基本的学习方法：
- 理论学习：认真阅读教材，掌握数据结构的基本概念和原理。
- 实践练习：通过编写代码实现不同数据结构的功能，加深对数据结构的理解。
- 做题总结：做完每个章节的练习题和习题集后，总结其中的经验和教训。
- 与他人讨论：与同学和老师一起讨论不同的数据结构和算法，加深对知识的理解。
考试形式
在中国大学的数据结构课程中，考试形式通常是笔试和上机实验两种形式的结合。笔试的内容包括选择题、填空和简答题，而上机实验则需要学生通过计算机编程实现不同的数据结构和算法。
就业方向
学习数据结构的学生可以选择不同的就业方向。以下是一些常见的就业方向：
- 软件工程师：负责开发、测试和维护软件系统。
- 数据分析师：利用数据结构和算法分析数据，为企业提供数据支持。
- 网络工程师：负责设计、搭建和维护企业网络系统。
- 人工智能工程师：利用数据结构和算法开发人工智能系统。
结语
数据结构是计算机科学中非常重要的一门课程，通过学习数据结构，学生们可以掌握计算机内存管理、数据存储和处理、算法设计等基本知识。在中国的大学中，数据结构是计算机科学专业的重要课程之一，学生们需要通过实践和总结，掌握基本的学习方法。学习数据结构的学生可以选择不同的就业方向，包括软件工程师、数据分析师、网络工程师和人工智能工程师等。
