【答案】《数据结构》(中国人民解放军陆军工程大学)章节期末中国大学慕课答案

第一周数据结构概述（总时长51'48''）概述单元测试1.单选题：算法分析的两个主要方面是____。

选项：

A、空间复杂度和时间复杂度

B、正确性和简明性

C、可读性和文档性

D、数据复杂性和程序复杂性

答案：【空间复杂度和时间复杂度】2.单选题：计算机算法指的是____。

选项：

A、计算方法

B、排序方法

C、解决问题的有限运算序列

D、调度方法

答案：【解决问题的有限运算序列】3.单选题：计算机算法必须具备输入、输出和____等5个特性。

选项：

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.单选题：算法分析的目的是____。

选项：

A、找出数据结构的合理性

B、研究算法中的输入和输出的关系

C、分析算法的效率以求改进

D、分析算法的易懂性和文档性

答案：【分析算法的效率以求改进】9.单选题：在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_____。

选项：

A、数据的处理方法

B、数据元素的类型

C、数据元素之间的关系

D、数据的存储方法

答案：【数据元素之间的关系】10.单选题：通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_____。

选项：

A、数据元素具有同一特点

B、不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致

C、每个数据元素都一样

D、数据元素所包含的数据项的个数要相等

答案：【不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致】11.单选题：以下说法正确的是_____。

选项：

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带结构的各数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构

答案：【一些表面上很不相同的数据可以有相同的逻辑结构】12.单选题：数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的____和运算等的学科。

选项：

A、结构

B、关系

C、运算

D、算法

答案：【关系】概述单元编程作业1.元素逆转

答案：【题目内容：元素逆转输入格式：每一行为输入数据个数n(1＜20)＜20)第二行为对应n个整数，以空格分隔输出格式：输出n个逆转后的数据，以逗号（英文状态）分隔。输入样例：512345输出样例：5,4,3,2,1】第二周顺序表（总时长30'44''）顺序表编程作业1.两个有序序列的中位数

答案：【题目内容：已知有两个等长的非降序序列S1,S2,设计函数求S1与S2并集的中位数。有序序列A[0]，A[1]，...，A[N-1]的中位数指A[(N-1)/2]。输入格式：输入分三行。第一行给出序列的公共长度N（0＜N≤100），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。输出格式：在一行中输出两个输入序列的并集序列的中位数。输入样例：51357923456输出样例：4】2.二分查找

答案：【题目内容：已知数组a中存放的元素为{2,4,6,8,10,12,14,16,18,20}，用二分查找法查找元素x出现的位置及查询次数。输入格式：元素x输出格式：如果元素x在表中，则输出try查找次数,posx所在位置（下标）。如果元素x不在表中，则输出try查找次数,notfound。try和pos后均有一空格。输入样例1：10输出样例1：try1,pos4输入样例2：25输出样例2：try4,notfound】顺序表单元测验1.单选题：有一个长度为12的有序顺序表，按二分找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_____。

选项：

A、35/12

B、37/12

C、39/12

D、43/12

答案：【37/12】2.单选题：若数组M可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素M[8]的起始地址为______。

选项：

A、x+8

B、x+28

C、x+32

D、x+64

答案：【x+32】3.单选题：有序数组a[18]进行二分查找时，查找到a[5]的查找路径（下标序列）为_____。

选项：

A、1，3，5

B、8，2，5

C、8，3，5

D、8，4，5

答案：【8，3，5】4.单选题：用二分法对有序数组a[13]进行查找，若待查元素为x，且a[7]，那么查找路径为____________

选项：

A、6，9，7，8

B、6，9，7

C、7，9，8

D、6，9，8

答案：【6，9，7，8】5.单选题：线性表是____。

选项：

A、一个有限序列，可以为空

B、一个有限序列，不可以为空

C、一个无限序列，可以为空

D、一个无限序列，不可以为空

答案：【一个有限序列，可以为空】6.单选题：对于顺序存储的表长为n的线性表中，在第i个位置插入一个元素需要移动____个元素。其中，0≤i＜n。

选项：

A、n-i

B、n-i+1

C、n-i-1

D、i

答案：【n-i】7.单选题：采用顺序查找法查找一个表长为n的线性表，则查找每个元素的平均比较次数为_____。

选项：

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

答案：【(n+1)/2】8.单选题：对线性表进行二分查找时，要求线性表必须采用_____。

选项：

A、顺序存储

B、链式存储

C、顺序存储，且结点有序排序

D、链式存储，且结点有序排序

答案：【顺序存储，且结点有序排序】9.单选题：对于顺序存储的表长为n的线性表，删除第i个元素需要移动____个元素。其中，0≤i＜n。

选项：

A、n-i

B、n-i+1

C、n-i-1

D、i

答案：【n-i-1】10.单选题：用二分法对有序数组a[13]进行查找，在等概率的情况下，查找不成功的平均查找长度为________。

选项：

A、27/7

B、54/13

C、49/14

D、49/13

答案：【27/7】11.单选题：对有序表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

答案：【1，4，7，9，11】12.单选题：线性表的顺序存储最适合于实现运算。

选项：

A、插入

B、删除

C、查找

D、由下标定位

答案：【由下标定位】13.单选题：对有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]

答案：【A[6]，A[2]，A[4]，A[3]】14.单选题：如果线性表最常用的操作是取第i个结点及其前驱，则采用_____存储方式最节省时间。

选项：

A、单向链表

B、双向链表

C、单向循环链表

D、顺序表

答案：【顺序表】第三周链表（上）(总时长22'57''）链表（上）单元测验1.单选题：就单一的____运算来说，线性表采用顺序存储比采用链式存储好（n是表长）。

选项：

A、存取任意第i（0≤i≤n-1）个结点

B、交换前两个结点的值

C、输出所有结点

D、查找结点x在表中的序号

答案：【存取任意第i（0≤i≤n-1）个结点】2.单选题：就单一的____运算来说，线性表采用链式存储比采用顺序存储好。

选项：

A、删除指定元素

B、输出所有结点

C、查找结点x在表中的序号

D、在表尾处插入一个元素

答案：【删除指定元素】3.单选题：判定以head为头指针的单向简单链表为空的条件是。

选项：

A、head==NULL

B、head->next==NULL

C、head->next==head

D、head!=NULL

答案：【head==NULL】4.单选题：判定以head为头指针的单向加头(加监督元)链表为空的条件是。

选项：

A、head==NULL

B、head->next==NULL

C、head->next==head

D、head!=NULL

答案：【head->next==NULL】5.单选题：已知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;

答案：【s->next=NULL;last->next=s;s=last;】6.单选题：已知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;

答案：【last->next=s;s->next=NULL;last=s;】7.单选题：已知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;

答案：【p->next=h->next;h->next=p;】8.单选题：已知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;

答案：【p=h->next;h->next=p->next;free(p);】9.单选题：链表不具备的特点是_____。

选项：

A、可随机访问任一结点

B、插入删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与其长度成正比

答案：【可随机访问任一结点】10.单选题：对一个具有n个元素的线性表，建立单向链表的时间复杂度至少为__。

选项：

A、O(n)

B、O(1)

C、O(logn)

D、O(n^2)

答案：【O(n)】11.单选题：从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较_个结点。

选项：

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

答案：【(n+1)/2】12.单选题：能够满足快速完成插入和删除运算的线性表存储结构是____。

选项：

A、顺序存储

B、链式存储

C、散列存储

D、有序存储

答案：【链式存储】13.单选题：已知单向链表中指针p指向结点A，表示删除A的后继结点（若存在）的链操作（不考虑回收）。

选项：

A、p->next=p->next->next

B、p=p->next

C、p=p->next->next

D、p->next=p

答案：【p->next=p->next->next】14.单选题：在一个单向链表中，已知结点*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;

答案：【q->next=s;s->next=p;】15.单选题：线性表采用链式存储时，其地址。

选项：

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续与否均可以

答案：【连续与否均可以】链表（上）编程作业1.链表构造

答案：【题目内容：本题实现链表的构造，采用表头插入法构造链表，输出表中所有元素。输入格式：输入n个整数，以空格分隔，当输入值为0时表示输入结束。输出格式：输出链表中的所有元素，以逗号（英文状态）分隔。输入样例：1230输出样例：3,2,1】第三周链表（下）(总时长18'38''）链表（下）单元测验1.单选题：与单向链表相比，双向链表的优点之一是_____。

选项：

A、插入、删除操作更简单

B、顺序访问相邻结点更灵活

C、可以省略表头指针或表尾指针

D、可以进行随机访问

答案：【顺序访问相邻结点更灵活】2.单选题：判定以head为头指针的单向加头(加监督元)循环链表为空的条件是。

选项：

A、head->next==NULL

B、head==NULL

C、head->next==head

D、head!=NULL

答案：【head->next==head】3.单选题：双向循环链表中，在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;

答案：【s->Llink=p;s->Rlink=p->Rlink;p->Rlink->Llink=s;p->Rlink=s;】4.单选题：在双向链表中，删除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;

答案：【p->Llink=p->Rlink,p->Rlink=p->Llink;】5.单选题：一个长度为n（n>1）的单向链表设有头和尾两个指针，执行_____操作所用时间与表长有关。

选项：

A、删除单链表中的第一个元素

B、删除单链表中的最后一个元素

C、在单链表第一个元素前插入一个新元素

D、在单链表最后一个元素后插入一个新元素

答案：【删除单链表中的最后一个元素】6.单选题：如果对非空线性表的运算只有如下4种：（1）删除第一个元素；（2）删除最后一个元素；（3）在第一个元素左边插入新元素；（4）在最后一个元素的右边插入新元素。那么，最合适的存储形式是_____。

选项：

A、仅有表头指针的单向链表

B、仅有表尾指针的单向链表

C、仅有表头指针的双向循环链表

D、仅有表尾指针的单向循环链表

答案：【仅有表头指针的双向循环链表】7.单选题：设有两个长度都为n的单向链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_____。

选项：

A、对于两个链表来说，删除第一个结点的操作，其时间复杂性都是O（1）

B、对于两个链表来说，删除最后一个结点的操作，其时间复杂性都是O（n）

C、循环链表要比非循环链表占用更多的内存空间

D、h1和h2是不同类型的变量

答案：【对于两个链表来说，删除最后一个结点的操作，其时间复杂性都是O（n）】8.单选题：在长度为n的_____上，删除第一个元素，如果不允许移动结点的值，其算法的时间复杂性为O（n）。

选项：

A、只有表头指针的简单循环链表

B、只有表尾指针的简单循环链表

C、只有表尾指针的带表头监督元结点的单向循环链表

D、只有表头指针的带表头监督元结点的单向循环链表

答案：【只有表头指针的简单循环链表】9.单选题：将如图所示的向单向链表中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;

答案：【t=q->next;q->next=r->next;r->next=p->next;p->next=t;】10.单选题：若某线性表中最常用的操作是在最后一个元素之后插入新元素，或删除第一个元素，则采用存储方式最节省时间。

选项：

A、仅有头指针的单链表

B、仅有头指针的单循环链表

C、顺序表

D、仅有尾指针的单循环链表

答案：【仅有尾指针的单循环链表】11.单选题：对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为_____。

选项：

A、O(n)

B、O(1)

C、O(logn)

D、O(n^2)

答案：【O(n^2)】12.单选题：以head为头指针的非空单向循环链表的尾结点（由p所指向）满足_____。

选项：

A、p->next==NULL

B、p==NULL

C、p->next==head

D、p==head

答案：【p->next==head】13.单选题：在长度为n的有序单链表中插入一个结点并保持有序，最坏情况下和平均情况下，时间复杂性分别是_____。

选项：

A、O(n)和O(1)

B、O(n)和O(logn)

C、O(n)和O(n)

D、O(nlogn)和O(n)

答案：【O(n)和O(n)】链表（下）编程作业1.求链表的倒数第m个元素

答案：【题目内容：以表尾插入法构造链表，然后在不改变链表的前提下，求链式存储的线性表的倒数第m（>0）个元素，如果不存在，则输入ERROR。输入格式：第一行输入元素个数n第二行输入n个元素值，以空格分隔第三行输入m值输出格式：第一行输出此链表，元素间以逗号（英文状态）分隔第二行输出链表中倒数第m个元素输入样例：5124563输出样例：1,2,4,5,64】第四周特殊表结构（总时长51'56''）特殊表结构单元测验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

答案：【可能是2】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;

答案：【s->next=hs;hs=s;】4.单选题：数组S[M]存储一个栈，top为栈顶指针。如果条件top==-1表示栈空，在栈不空的情况下，栈顶元素为_____。

选项：

A、S[top-1]

B、S[top]

C、S[top+1]

D、S[++top]

答案：【S[top]】5.单选题：数组S[M]存储一个栈，top为栈顶指针。如果条件top==M表示栈满，那么条件_____表示栈空。

选项：

A、top==1

B、top==-1

C、top==0

D、top!=0

答案：【top==0】6.单选题：数组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

答案：【(last+1)%m==first】7.单选题：数组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;

答案：【last=(last+1)%m,q[last]=x;】8.单选题：数组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

答案：【4和0】9.单选题：对于链队，在进行删除操作时，。

选项：

A、仅修改头指针

B、仅修改尾指针

C、采用简单链表时,仅需修改头指针;采用加监督元单链表时,头尾指针均不需要修改

D、头、尾指针可能都要修改

答案：【头、尾指针可能都要修改】10.单选题：设进栈次序为ABCDE，______是不可能得到的出栈序列。

选项：

A、ABCDE

B、BCDEA

C、EABCD

D、EDCBA

答案：【EABCD】11.单选题：设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p3=1，则p1为_____。

选项：

A、必是2

B、可能是3

C、必定是3

D、不可能是3

答案：【可能是3】12.单选题：_____不是串"abcd321ABCD"的子串。

选项：

A、"abd"

B、"321AB"

C、"ABC"

D、"B"

答案：【"abd"】13.单选题：一个单向简单链表存储的栈，其栈顶指针为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;

答案：【x=top->data;top=top->next;】14.单选题：首尾指针分别是f和r的单向加头链表存储一个队，元素x出队的语句为“f=f->next,x=f->data;”，那么判断队空否的条件是_____。

选项：

A、f==r

B、f==NULL

C、f->next==r

D、f->next=NULL

答案：【f==r】15.单选题：设进栈序列是p1，p2，p3，…，pn，输出序列为1，2，3，…，n。若p3=1，则p1为_____。

选项：

A、可能是2

B、不可能是2

C、必是2

D、必定是3

答案：【不可能是2】16.单选题：数组q[M]存储一个循环队，first和last分别是首尾指针。当前队中元素个数为_____。

选项：

A、(last-first+M)%M

B、last-first+1

C、last-first-1

D、last-first

答案：【(last-first+M)%M】特殊表结构编程作业1.括号匹配判断

答案：【题目内容：本题实现求嵌套括号字符串是否匹配。只需判断括号是否匹配，表达式中可以有其他字符。如果匹配，则输出此嵌套括号字符串和match，否则输出此嵌套括号字符串和notmatch。输入格式：输入一串嵌套括号字符串输出格式：套括号字符串match/notmatch，套括号字符串和match/motmatch间有一个空格分隔。输入样例1：((2*(3+2)-7))/4输出样例1：((2*(3+2)-7))/4match输入样例2：()())(()输出样例1：()())(()notmatch】第四周散列表(总时长30'11"）散列表单元测试1.单选题：以下说法错误的是_____。

选项：

A、散列存储的基本思想是由元素值决定其存储地址

B、散列表的结点中只包含数据元素自身的信息，不包含任何指针

C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度

D、散列表的查找效率主要取决于的散列函数和处理冲突的方法

答案：【散列表的结点中只包含数据元素自身的信息，不包含任何指针】2.单选题：设散列表长m=14，散列函数Hash(x)=xmod11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。若用平方探测法处理冲突，插入元素49时，其地址是_____。

选项：

A、8

B、3

C、5

D、9

答案：【9】3.单选题：顺序查找法最适合用于（）的线性表。

选项：

A、散列存储

B、顺序存储或链式存储

C、压缩存储

D、分段存储

答案：【顺序存储或链式存储】4.单选题：平均情况下，查找速度最快，而且又能适应插入、删除的数据结构是（）。

选项：

A、顺序存储的有序表

B、链式存储的有序表

C、散列表

D、链式存储的无序表

答案：【散列表】5.单选题：数组a[m]存储的散列表，散列函数为：hash(x)=xmodp,一般情况下，p取（）时，散列结果可能比较平均。

选项：

A、小于m的最大奇数

B、小于m的最大素数

C、小于m的最大偶数

D、小于m的最大合数

答案：【小于m的最大素数】散列表编程作业1.散列表构造

答案：【题目内容：设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突hi=(h0+di)%m。冲突时，使用增量序列di=5i。计算输入序列(值>=0)对应的散列地址值。（输入个数不会超过15个）输入格式：第一行为输入个数；第二行为对应的输入值，用空格隔开。输出格式：每行对应一个值及其散列地址，中间用空格隔开（即pos前后均有一个空格）输入样例：5141739511256输出样例：141pos:573pos:1095pos:15112pos:256pos:7】第五周树结构（上）（总时长53'24"）树结构（上）单元测验1.单选题：已知二叉树的扩充先序序列是“ABC空空DE空FG空空空空空”。那么，它的中序序列是__________。

选项：

A、ABCEDGF

B、DBCAEFG

C、CBEGFDA

D、GABFDCE

答案：【CBEGFDA】2.单选题：二叉树按层遍历算法实现时采用了数据结构。

选项：

A、栈

B、数组

C、队

D、文件

答案：【队】3.单选题：下面哪种说法是不正确的。

选项：

A、正则二叉树，可由其先序序列唯一确定。

B、完全二叉树，可由其先序序列唯一确定。

C、完全二叉树，可由其中序序列唯一确定。

D、满二叉树，可由其后序序列唯一确定。

答案：【正则二叉树，可由其先序序列唯一确定。】4.单选题：二叉树的后序序列为DBKHFEGCA，中序序列为DBAKHEFCG，则其先序序列是__________。

选项：

A、ABFHGKCED

B、GDBEFCAHK

C、KHDGBAECF

D、ABDCEHKFG

答案：【ABDCEHKFG】5.单选题：正则二叉树的先序序列为ABCDE，后序序列为BDECA，则其中序序列是__________。

选项：

A、ABCED

B、DBCAE

C、BADCE

D、ABDCE

答案：【BADCE】6.单选题：若需要经常查找结点的父亲，采用树的存储法性能较好。

选项：

A、树的多重链接法

B、树的儿子兄弟链法

C、树的完全存储法

D、树的父亲链域法

答案：【树的父亲链域法】7.单选题：若二叉树中，2度结点数为m，则叶子数为____。

选项：

A、m

B、m+1

C、2m

D、m-1

答案：【m+1】8.单选题：高度为h的正则二叉树至少有_____结点。

选项：

A、2h-1

B、2h+1

C、2^h

D、2^h+1

答案：【2h-1】9.单选题：图中，_____都是完全二叉树。

选项：

A、1、2、4

B、1、2、3

C、2、3、4

D、1、3、4

答案：【1、2、4】10.单选题：若三元树中，度数为1，2，3的结点数分别是2，1，3。叶子数必为____个。

选项：

A、4

B、5

C、6

D、8

答案：【8】11.单选题：含3个结点的普通树的树形共有____种。

选项：

A、5

B、2

C、6

D、7

答案：【2】12.单选题：具有50个结点的三元树，其高度的最小值为____。

选项：

A、3

B、4

C、5

D、6

答案：【5】13.单选题：如图所示：二叉树1的先序序列为_____________，二叉树2的中序序列分别为_____________。

选项：

A、ABDGCEFH，ABDEFCG

B、ABDGCEFH，DFEBAGC

C、DGBAECHF，DFEBAGC

D、GDBEHFCA，ABDEFCG

答案：【ABDGCEFH，DFEBAGC】14.单选题：设二叉树的结点个数为n，采用双链法存储，其递归先序遍历算法如下：voidsuorder(Bptrp){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、不确定

答案：【n+1】15.单选题：通过遍历可以求得二叉树结点的高。

选项：

A、先序

B、中序

C、后序

D、按层

答案：【后序】16.单选题：通过遍历可以删除二叉树中所有的叶子结点。

选项：

A、先序

B、中序

C、后序

D、按层

答案：【先序】17.单选题：具有n片叶子的完全二叉树共有个。

选项：

A、1

B、2

C、n

D、不确定

答案：【2】18.单选题：图中由3棵树组成的森林所转换成的二叉树有片叶子。

选项：

A、3

B、4

C、5

D、6

答案：【5】19.单选题：二叉树的中序序列之中，结点a排在结点b之前的条件是_____。

选项：

A、a在b右方

B、a是b祖先

C、a在b左方

D、a是b子孙

答案：【a在b左方】20.单选题：对普通树先根遍历的规则是：先访问根结点，再依次先根遍历根的各个子树；后根遍历的规则是：先依次后根遍历根的各个子树，再访问根结点。对普通树T先根遍历和后根遍历得到先根序列和后根序列，与将T转换成二叉树B的先序序列、中序序列、后序序列之间的关系是_____。

选项：

A、T的先根序列与B的先序序列相同

B、T的后根序列与B的后序序列相同

C、T的先根序列与B的中序序列相同

D、无简单的对应关系

答案：【T的先根序列与B的先序序列相同】树结构（上）编程作业1.根据后序和中序遍历输出先序遍历

答案：【题目内容：本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。输入格式：第一行给出正整数(N＜=30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。输出格式：在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。输入样例：723157641234567输出样例：Preorder:4132657】第六周树结构（下）（总时长110'13"）树结构（下）单元测验1.单选题：按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LR旋转，则插入前后失衡结点的平衡因子。

选项：

A、由1变为2

B、不变

C、由2变为1

D、由-1变为-2

答案：【由-1变为-2】2.单选题：平衡树插入时，若进行LR旋转，则旋转后原失衡结点的位置被插入前其替换。

选项：

A、左儿子的左儿子

B、左儿子的右儿子

C、右儿子的左儿子

D、右儿子的右儿子

答案：【左儿子的右儿子】3.单选题：依次插入20，8，17，25，30，18来构造开始为空的平衡二叉树，其构造过程中经过的旋转方式依次为。

选项：

A、LL，RR，RL

B、LR，RR，RL

C、LR，RR，RR

D、LR，RR，LL

答案：【LR，RR，RL】4.单选题：若有一个整数序列，把这些整数依次插入开始为空的平衡树，使四种旋转LL，RR，LR，RL各至少一次，则此整数序列至少有个数。

选项：

A、4

B、9

C、12

D、7

答案：【7】5.单选题：在一棵AVL树中，每个结点的平衡因子（整数）的取值范围是。

选项：

A、-l～1

B、-2～2

C、1～2

D、0～1

答案：【-l～1】6.单选题：若树的结点个数相同，则下面是查找效率最高的树。

选项：

A、所有结点的左子树都为空的检索树

B、所有结点的右子树都为空的检索树

C、平衡二叉树

D、检索树

答案：【平衡二叉树】7.单选题：按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LL旋转，则插入前后失衡结点的平衡因子。

选项：

A、由1变为2

B、不变

C、由2变为1

D、由-1变为-2

答案：【由-1变为-2】8.单选题：按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LL旋转，则插入前失衡结点的左儿子的平衡因子是。

选项：

A、0

B、1

C、-1

D、-2

答案：【0】9.单选题：根据哈夫曼编码，字母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

答案：【100，11，10，1，0】10.单选题：学生成绩分布情况如表所示，现有10000个学员成绩数据，利用哈夫曼树，设计最好的比较判断逻辑结构，最少需要次比较分数段0~5960~6970~7980~8990~100比例0.050.150.400.300.10五分制不及格及格中良优

选项：

A、22000

B、21000

C、18050

D、20500

答案：【20500】11.单选题：设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进制编码，使得上述正文的编码最短，其总码长为。

选项：

A、18

B、144

C、31

D、36

答案：【31】12.单选题：依次删除如图所示的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

答案：【LL，RL，RR，LR】13.单选题：下列说法正确的是。

选项：

A、在哈夫曼树中，权值相同的叶子结点都在同一层上。

B、在哈夫曼树中，权值较大的叶子结点一般离根结点较远。

C、哈夫曼树中不存在度为1的结点。

D、以上说法都不正确。

答案：【哈夫曼树中不存在度为1的结点。】14.单选题：以序列2，3，23，9，12，14，6，8，15，17作为叶之权的三元Huffman树，其W(T)=____。

选项：

A、298

B、210

C、219

D、156

答案：【219】15.单选题：设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。

选项：

A、13

B、12

C、26

D、25

答案：【25】16.单选题：已知检索树的后序序列是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

答案：【23，19，12，21，45，67】17.单选题：由输入序列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

答案：【46，25，15，10，28，36，30，32，70，55，78】18.单选题：若检索树中，每个结点，其左子树中所有结点值都比其小或相等，其右子树中所有结点值都比其大，删除结点时，若被删除结点有二个儿子，则真正删除的是。

选项：

A、该结点的父亲结点

B、该结点的中序前驱结点，或中序后继结点

C、该结点的中序后继结点

D、该结点的中序前驱结点

答案：【该结点的中序前驱结点】19.单选题：如图所示的4棵二叉树，是平衡二叉树。

选项：

A、A

B、B

C、C

D、D

答案：【B】20.单选题：含有15个结点的平衡二叉树的最大高度为。

选项：

A、4

B、5

C、6

D、7

答案：【5】21.单选题：若检索树中序序列是从小到大的序列，下列说法正确的是。

选项：

A、检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，比其右子树中所有结点关键字小。

B、检索树中，每个结点的关键字都比其左孩子关键字大或相等，比其右孩子关键字小。

C、检索树中，每个结点的关键字都不比其左孩子关键字大或相等，不比其右孩子关键字小。

D、检索树中，每个结点的关键字都比其右子树中所有结点关键字大或相等，比其左子树中所有结点关键字小。

答案：【检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，比其右子树中所有结点关键字小。】22.单选题：如图所示检索树，其不成功查找的平均查找长度为____。

选项：

A、3

B、4

C、15/6

D、21/6

答案：【3】23.单选题：在关键字随机分布的情况下，用检索树的方法进行查找，其查找长度与数量级相当。

选项：

A、顺序查找

B、折半查找

C、前两者均不正确

D、前两者均正确

答案：【折半查找】24.单选题：由输入序列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

答案：【10，15，36，28，25，55，78，70，46】树结构（下）编程作业1.构造哈夫曼树-有序输入

答案：【题目内容：构造哈夫曼树，然后输出它树的中序序列。从小到大的顺序给出词频（不超过10个），根据词频构造哈夫曼树。为确保构建的哈夫曼树唯一，本题做如下限定：（1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。（2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。输入格式：第一行输入词频个数；第二行按从小到大的顺序输入每个词频输出格式：输出中序序列，中间以一个空格隔开输入样例：3112输出样例：24121】第七周图结构（上）（总时长71'37''）图结构（上）单元测验1.单选题：图的先广搜索是二叉树_____的推广。

选项：

A、先序遍历

B、中序遍历

C、后序遍历

D、按层遍历

答案：【按层遍历】2.单选题：对于无向图的邻接矩阵，说法正确的是_____。

选项：

A、第i行上的非零元素个数和第i列的非零元素个数一定相等

B、矩阵中的非零元素个数等于图中的边数

C、第i行和第i列上非零元素总数等于顶点i的度数

D、矩阵中的非全零行的行数等于图中的顶点数

答案：【第i行上的非零元素个数和第i列的非零元素个数一定相等】3.单选题：对于下图所存储的有向图，从顶点A开始进行先广搜索，不能得到的顶点序列是______。

选项：

A、ABCDE

B、ACBDE

C、ABCED

D、ADCEB

答案：【ADCEB】4.单选题：对于下图所示的无向图，若从顶点A开始进行先深搜索，可得到的顶点序列可能为________。

选项：

A、ABDFCEGH

B、ABCHDEGF

C、ADECHBFG

D、AFBDCEGH

答案：【ABCHDEGF】5.单选题：对于n个顶点，m条边的无向图G，说法正确的是______。

选项：

A、若m>n，则G必连通

B、若m，则G必不连通

C、若m≥n，则G中必含回路

D、若m，则G中必不含回路

答案：【若m≥n，则G中必含回路】6.单选题：在有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

选项：

A、1

B、1/2

C、2

D、4

答案：【1】7.单选题：对于简单无向图而言，一条回路至少含有_____条边。

选项：

A、2

B、3

C、4

D、5

答案：【3】8.多选题：以下说法正确的是____。

选项：

A、对非连通的无向图不能进行先广搜索

B、实现先广搜索通常要用到队

C、实现先深搜索通常要用到栈

D、对有向图也能进行先广搜索

答案：【实现先广搜索通常要用到队;实现先深搜索通常要用到栈;对有向图也能进行先广搜索】9.单选题：通过对无向图进行先深搜索，一定可以判断该图是否是连通图，或找出图的连通分量及先深生成树。

选项：

A、正确

B、错误

答案：【正确】10.单选题：可以采用一维数组对无向图的邻接矩阵进行压缩存储。对于一个包含n个顶点的无向图而言，假设M是其邻接矩阵，A是对M（下三角）进行压缩存储的一维数组。那么M[i][j]=A[i*(i+1)/2+j]，其中0≤j≤i≤n-1。

选项：

A、正确

B、错误

答案：【正确】11.单选题：无向图G的连通分量是G的极大连通子图。

选项：

A、正确

B、错误

答案：【正确】12.单选题：对于无向加权图而言，其最小生成树有可能不存在，但如果存在的话通常是不唯一的。

选项：

A、正确

B、错误

答案：【正确】13.对含有k个连通分量的无向图进行先深搜索时，主控函数中需要调用递归的搜索函数dfs_____次。

答案：【k】14.n个顶点的有向图中，顶点的最大度数等于______。

答案：【2(n-1)】图结构（上）编程作业1.图的先深搜索

答案：【题目内容：输出无向图的给定起点的先深序列。输入格式：输入第一行给出三个正整数，分别表示无向图的节点数N（1随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号。输出格式：输出从S开始的无向图的先深搜索序列，用一个空格隔开；如果为非连通图，仅输出以S开始的连通部分先深序列，再在结尾处另起一行输出一个0，表示此图非连通。由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以表头插入法构造邻接表。输入样例：6821223344556643615输出样例：236451】第八周图结构（下）（总时长86'17''）图结构（下）编程作业1.最小生成树构造

答案：【题目内容：某地对偏远地区实行“村村通”工程，目标是使整个地区任何两个村落间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到拟修建道路的费用，现请你编写程序，计算出全地区畅通需要的最低成本。输入格式：输入的第一行给出村庄数目N(1≤N≤20)和拟修建的道路数M接下来的M行对应修建每条村庄间道路的成本，每行给出3个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本。输出格式：输出需修建的道路，按prim算法从编号1开始得到的顺序，输出每条路，每行输出一条道路，形式如：道路1编号,道路2编号,费用。(编号小的放前面，编号大的放后面，逗号为英文状态下的逗号)输入样例：46121134141233242345输出样例：1,2,11,4,12,3,3】图结构（下）单元测验1.单选题：用Dijkstra算法求下图顶点A到其余各顶点的最短路径时，将按照__________的次序，依次求出A到它们的最短路径。

选项：

A、BEDFC

B、BEDCF

C、BCEDF

D、EDFCB

答案：【BEDCF】2.单选题：下面不正确的说法是_____。（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）

答案：【（1）（4）】3.单选题：下图的拓扑序列不正确的是（）。

选项：

A、v1,v2,v3,v4

B、v2,v1,v3,v4

C、v1,v3,v2,v4

D、v2,v3,v1,v4

E、v2,v4,v1,v3

答案：【v2,v3,v1,v4】4.单选题：用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

答案：【GB4、BC2、AB3、CD5、ED10、EF9】5.多选题：下图中，添加哪一条边可使其拓扑序列变成唯一。

选项：

A、

B、

C、

D、

答案：【;】6.对于下图中的加权图，其最小生成树的边长之和等于______。

答案：【36】第九周排序（上）(总时长51'51"）排序（上）编程作业1.寻找大富翁

答案：【题目内容：胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。输入格式：输入首先给出两个正整数N(＜=18000)和M（＜=10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。输出格式：在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。输入样例：8381273209518输出样例：201812】排序（上）单元测试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)

答案：【O(nlogn)】3.单选题：一组记录的排序码为{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

答案：【38,40,56,46,79,84】4.单选题：下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是。

选项：

A、直接插入排序

B、快速排序

C、简单选择排序

D、堆排序

答案：【快速排序】5.单选题：对n个元素进行快速排序，第一次划分最多需要移动次元素，假定包括基准和临时量之间的移动。

选项：

A、n/2

B、n-1

C、n

D、n+1

答案：【n+1】6.单选题：_____可以满足稳定性要求。

选项：

A、直接插入排序和冒泡排序

B、直接插入排序和快速排序

C、冒泡排序和堆排序

D、快速排序和简单选择排序

答案：【直接插入排序和冒泡排序】7.单选题：在对n个元素进行改进的冒泡排序的过程中，最好情况下的时间复杂度为____。

选项：

A、O(1)

B、O(logn)

C、O(n^2)

D、O(n)

答案：【O(n)】8.单选题：插入排序和选择排序是都不稳定。

选项：

A、正确

B、错误

答案：【错误】9.单选题：插入排序时间复杂度大于选择排序时间复杂度。

选项：

A、正确

B、错误

答案：【错误】10.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较____次。

答案：【3】第十周排序（下）（总时长17'29"）排序（下）单元测试1.单选题：在所有排序方法中，排序方法使数据的组织采用的是完全二叉树的结构。

选项：

A、合并排序

B、快速排序

C、二分插入排序

D、堆排序

答案：【堆排序】2.单选题：若要对1000个元素进行排序，要求又快又稳定，则最好采用方法

选项：

A、插入排序

B、快速排序

C、合并排序

D、堆排序

答案：【合并排序】3.单选题：对n个数据进行堆排序的空间复杂度为。

选项：

A、O(1)

B、O(nlogn)

C、O(n)

D、O(n^2)

答案：【O(1)】4.单选题：对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是。

选项：

A、快速排序

B、基数排序

C、希尔排序

D、堆排序

答案：【希尔排序】5.单选题：下面各种排序方法中，最好情况下时间复杂度为O(n)的是。

选项：

A、快速排序

B、直接插入排序

C、堆排序

D、合并排序

答案：【直接插入排序】6.单选题：对初始状态为递增序列的表按递增顺序排序，最省时间的是算法，最费时间的是算法。

选项：

A、堆排序、简单选择排序

B、直接插入排序、快速排序

C、快速排序、合并排序

D、冒泡排序、堆排序

答案：【直接插入排序、快速排序】7.单选题：下面排序算法占用的辅助空间最小。

选项：

A、堆

B、合并

C、基数

D、快速

答案：【堆】8.单选题：如果想得到1000个元素中前5名最大值，用排序最快。

选项：

A、冒泡

B、快速

C、希尔

D、堆

答案：【堆】9.单选题：需要对任何5个不同的数据进行排序，则至少需要比较次;对5个数据进行排序，如果5个数据已经有序，但我们并不知道，最少比较次可结束排序;

选项：

A、4,4

B、7,4

C、6,7

D、7,7

答案：【7,4】10.单选题：在下面的排序方法中，辅助空间为O（n）的是。

选项：

A、直接插入排序

B、堆排序

C、快速排序

D、合并排序

答案：【合并排序】排序（下）编程作业1.比赛排名

答案：【题目内容：某个计算机编程大赛将在全国举办，会在若干个不同的比赛场点同时举行，产生本赛点的成绩，每个比赛点按总成绩决出前30名。比赛结束后，各个考点的成绩将即刻汇总成一张总的排名表。现在就请你写一个程序自动归并各个考点的成绩生成总排名表。输入格式：输入的第一行给出一个正整数N（≤600），代表比赛场点总数。随后给出N行各30个整数，表示N个比赛场点的前30名成绩（已按成绩从小到大排列），中间用空格分隔。输出格式：输出汇总的排名成绩（由小到大排列），如果N＜=3时，输出所有学生成绩。每10个成绩占一行，中间有一个空格分隔。如果N>3时，总共输出90名学生成绩，前10（下标0~9），后10（30N-10~30N-1)，中间70（30N/2-34~30N/2+35)共90名，每10个成绩占一行，中间有一个空格分隔。输入样例：338281114213232240243729975853771983658855894597251045011797146801592118457205372097621238216552590626285281002888130612318913227832285411532924912995390248275436570563349961114781194212382146041572416827174211846718716191691971819895232812446426500269622814529358323914560624245557596266587167751210705110391265214590148951779517829183161891719650234402419826431281892896129216294842971129813300853036732153输出样例：38414515328129249160611421323224024242437299529973902482754365557570558535962633466587167751277198365885589459725996110450107051103911478117971194212382126521459014604146801489515724159211682717421177951782918316184571846718716189171916919650197181989520537209762123821655232812344024198244642590626285264312650026962281002814528189288812896129216293582948429711298133008530367306123189132153322783228532391】期末考试期末考试1.单选题：以下排序方法中，不需要进行关键字比较的是______。

选项：

A、快速排序

B、归并排序

C、基数排序

D、堆排序

答案：【基数排序】2.单选题：对n个记录的数组元素进行简单选择排序，所需进行的元素间的比较次数为。

选项：

A、n

B、n+1

C、n(n-1)/2

D、n^2

答案：【n(n-1)/2】3.单选题：一个有n个顶点的无向图最多有条边。

选项：

A、n

B、n(n-1)

C、n(n-1)/2

D、2n

答案：【n(n-1)/2】4.单选题：在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。

选项：

A、n-1

B、n+1

C、n

D、n/2

答案：【n-1】5.单选题：在待排序的元素序列基本有序的前提下，效率最高的排序方法是。

选项：

A、插入排序

B、选择排序

C、快速排序

D、归并排序

答案：【选择排序】6.单选题：用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况如下：（1）25，84，21，47，l5，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、堆排序

答案：【堆排序】7.单选题：就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（）。

选项：

A、堆排序＜归并排序＜快速排序

B、快速排序＜堆排序＜归并排序

C、堆排序>归并排序>快速排序

D、堆排序>快速排序>归并排序

答案：【堆排序＜归并排序＜快速排序】8.单选题：稳定的排序方法是。

选项：

A、直接插入排序

B、简单选择排序

C、堆排序

D、快速排序

答案：【直接插入排序】9.单选题：具有n个顶点，m条边的无向图，其邻接表中，共有n个顶点结点和____个边结点。

选项：

A、m/2

B、n+m

C、m

D、2m

答案：【2m】10.单选题：下面叙述正确的是______。

选项：

A、算法的执行效率与数据的存储结构无关

B、算法的空间复杂度是指算法程序中指令（或语句）的条数

C、算法的有穷性是指算法必须能在执行有限个步骤之后终止

D、以上三种描述都不对

答案：【算法的有穷性是指算法必须能在执行有限个步骤之后终止】11.单选题：已知一个图如图所示，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为。

选项：

A、a，c，f，d，e，b

B、a，e，b，c，f，d

C、a，b，c，e，d，f

D、a，b，c，e，f，d

答案：【a，b，c，e，f，d】12.单选题：使用普里姆算法构造出如图所示的图G的一棵最小生成树，从顶点1出发依次得到的最小生成树的序列为。

选项：

A、(1,3)1,(3,6)4,(6,4)2,(3,2)5,(2,5)3

B、(1,3)1,(6,4)2,(2,5)3,(3,6)4,(3,2)5

C、(1,3)1,(3,6)4,(3,2)5,(6,4)2,(2,5)3

D、(1,3)1,(3,2)5,(2,5)3,(3,6)4,(6,4)2

答案：【(1,3)1,(3,6)4,(6,4)2,(3,2)5,(2,5)3】13.单选题：用下图求得的最小生成树中，A到F的路径为：_______。

选项：

A、AC、CF

B、AD、DF

C、AC、CD、DF

D、AC、CE、EF

答案：【AC、CD、DF】14.单选题：在下图中，A到F的最短路径为：_______。

选项：

A、AC、CF

B、AD、DF

C、AC、CD、DF

D、AD、DC、CF

答案：【AD、DF】15.单选题：若数组M可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素M[8]的起始地址为_____。

选项：

A、x+8

B、x+28

C、x+32

D、x+64

答案：【x+32】16.单选题：对于顺序存储的长度为n的线性表，插入、删除一个元素的平均时间复杂度分别是。

选项：

A、O(1)O(n)

B、O(n)O(n)

C、O(1)O(1)

D、O(n)O(1)

答案：【O(n)O(n)】17.单选题：有序数组a[18]进行二分查找时，查找到a[5]的查找路径（下标序列）为_____。

选项：

A、1，3，5

B、8，2，5

C、8，3，5

D、8，4，5

答案：【8，3，5】18.单选题：对a[12]进行二分查找，在等概率情况下，查找成功的平均查找长度为___。

选项：

A、37/12

B、35/12

C、39/12

D、43/12

答案：【37/12】19.单选题：在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r(指向尾结点)，执行操作与链表的长度有关。

选项：

A、删除单链表中的第一个元素

B、删除单链表中的最后一个元素

C、在单链表第一个元素前插入一个新元素

D、在单链表最后一个元素后插入一个新元素

答案：【删除单链表中的最后一个元素】20.单选题：在长度为n的有序链表中插入结点并保持有序，最坏情况下和平均情况下，时间复杂性分别是_____。

选项：

A、O(n)和O(1)

B、O(n)和O(logn)

C、O(n)和O(n)

D、O(logn)和O(n)

答案：【O(n)和O(n)】21.单选题：若某线性表中最常用的操作是在最后一个元素之后插入新元素，或删除第一个元素，则采用存储方式最节省时间。

选项：

A、单链表

B、仅有头指针的单循环链表

C、双链表

D、仅有尾指针的单循环链表

答案：【仅有尾指针的单循环链表】22.单选题：设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p1=3，则p2为_____。

选项：

A、可能是2

B、不可能是2

C、可能是1

D、必是1

答案：【可能是2】23.单选题：链表是线性表的一种存储形式，它与顺序表的存储有所不同，它对存储地址的要求是。

选项：

A、地址必须连续

B、地址连续或不连续均可

C、地址不能连续

D、无需分配地址

答案：【地址连续或不连续均可】24.单选题：已知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;

答案：【p=h->next,h->next=p->next;free(p);】25.单选题：已知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;

答案：【last->next=s,s->next=NULL,last=s;】26.单选题：在长度为n的单向链表中查找值为x的结点，在查找成功的情况下，平均查找长度为_____。

选项：

A、n/2

B、n

C、(n+1)/2

D、(n-1)/2

答案：【(n+1)/2】27.单选题：在长度为n(n>1)的上，删除第一个元素，其算法的时间复杂度为O(n)。

选项：

A、只有首结点指针h的不带头结点的循环单链表

B、只有尾结点指针r的不带头结点的循环单链表

C、只有尾结点指针r的带头结点h的循环单链表

D、只有头结点h的循环单链表

答案：【只有首结点指