【答案】《数据结构与算法》(国防科技大学)章节作业中国大学慕课答案

第一章绪论第一章测验1.单选题：数据的最小单位是（）。

选项：

A、数据对象

B、数据元素

C、数据项

D、数据表

答案：【数据项】2.单选题：数据结构的研究内容是（）。

选项：

A、数值计算问题中的数据对象以及它们之间的关系

B、数值计算问题中的数据对象以及它们之间的关系和操作

C、非数值计算问题中的数据对象以及它们之间的关系

D、非数值计算问题中的数据对象以及它们之间的关系和操作

答案：【非数值计算问题中的数据对象以及它们之间的关系和操作】3.单选题：下列不属于算法三要素的是()。

选项：

A、数据

B、存储

C、控制

D、计算

答案：【存储】4.单选题：下面程序段的时间复杂度是（）。Calc(intn,int**a){for(i=0;ifor(j=i;ja[i][j]=0;}

选项：

A、O(1)

B、O(n)

C、O(n*n)

D、O(n*n*n)

答案：【O(n*n)】5.单选题：下面程序段的时间复杂度是（）。Calc(intn,intm){n=90;m=100;while(m>0){if(n>100){n=n-10;m--;}elsen++;}}

选项：

A、O(1)

B、O(n)

C、O(m)

D、O(n*m)

答案：【O(1)】第二章线性表第二章测验1.单选题：在一个以L为头指针的单循环链表中，p指针指向链尾的条件是（）。

选项：

A、p->next==L

B、p->next==NULL

C、p->next->next==L

D、p->data==-1

答案：【p->next==L】2.单选题：线性表采用顺序存储时，插入和删除操作的平均时间复杂度为（）。

选项：

A、O(1)

B、O(logn)

C、O(n)

D、O(n*n)

答案：【O(n)】3.单选题：线性表采用顺序存储时，第一个元素的存储地址是1000，每个元素长度为2，则第5个元素的地址是（）。

选项：

A、1004

B、1005

C、1008

D、1010

答案：【1008】4.单选题：线性表采用链式存储时，取值操作的平均时间复杂度为（）。

选项：

A、O(1)

B、O(logn)

C、O(n)

D、O(n*n)

答案：【O(n)】5.单选题：在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。

选项：

A、s->next=p+1;p->next=s;

B、(*p).next=s;(*s).next=(*p).next

C、s->next=p->next;p->next=s->next;

D、s->next=p->next;p->next=s;

答案：【s->next=p->next;p->next=s;】第三章栈和队列第三章测验1.单选题：若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）。

选项：

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

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

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

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

答案：【a,f,e,d,c,b】2.单选题：一个栈的入栈序列为1,2,3…n，其出栈序列是p1,p2,p3…pn。若p2=3,则p3可能取值的个数是（）。

选项：

A、n-3

B、n-2

C、n-1

D、无法确定

答案：【n-1】3.单选题：执行完下列语句段后，i的值为（）。intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));

选项：

A、1

B、2

C、4

D、8

答案：【4】4.单选题：在循环队列Q中，Q中现有数据元素的个数计算表达式为（）。

选项：

A、(Q.rear-Q.front)%MAXSIZE

B、(Q.front-Q.rear)%MAXSIZE

C、(Q.rear-Q.front+MAXSIZE)%MAXSIZE

D、(Q.front-Q.rear+MAXSIZE)%MAXSIZE

答案：【(Q.rear-Q.front+MAXSIZE)%MAXSIZE】5.单选题：为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区，按照先来先打印的策略提供服务。则该缓冲区采用的数据结构应该是（）。

选项：

A、栈

B、队列

C、线性表

D、集合

答案：【队列】第四章串第四章测验1.单选题：关于串的模式匹配算法，下列说法错误的是（）。

选项：

A、BF算法和KMP算法在进行字符比较时都采用从左至右的顺序

B、BF算法的时间复杂度高于KMP算法的时间复杂度

C、KMP算法的主要思想是当S[i]≠T[j]时，主串S的指针i不回退，模式T的指针移动到j=next[j]的位置

D、采用KMP算法进行模式匹配时，next数组值的计算与串S密切相关

答案：【采用KMP算法进行模式匹配时，next数组值的计算与串S密切相关】2.单选题：已知串S和模式T，采用BF算法出现“失配”（S[i]≠T[j]）时，i回退的位置是（）。

选项：

A、i-j

B、i-j+1

C、i-j+2

D、i-j-1

答案：【i-j+2】3.单选题：已知串S的长度为n，模式T的长度为m，采用KMP算法计算next数组的时间复杂度是（）。

选项：

A、O(mn)

B、O(n)

C、O(m)

D、O(n+m)

答案：【O(m)】4.单选题：已知串S为“anythingispossible”，模式T为“thing”，采用KMP算法时，next数组值为（）。

选项：

A、01111

B、01234

C、01212

D、01112

答案：【01111】5.单选题：串的长度是指（）。

选项：

A、串中所含不同字母的个数

B、串中所含字符的个数

C、串中所含不同字符的个数

D、串中所含非空格字符个数

答案：【串中所含字符的个数】6.单选题：已知串S为“nothingisimpossible”，模式T为“abcaab”，采用KMP算法时，改进next数组的值为（）。

选项：

A、011122

B、011021

C、011121

D、011001

答案：【011021】第五章树和二叉树第五章测验1.单选题：使用二叉链表存储二叉树结构时，若有n个结点，则有（）个空指针域。

选项：

A、n-1

B、n

C、n+1

D、n+2

答案：【n+1】2.单选题：已知一棵完全二叉树的第7层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最少是（）。

选项：

A、39

B、71

C、111

D、127

答案：【71】3.单选题：若一棵二叉树的前序遍历序列和后序遍历序列分别为1、2、3、4和4、3、2、1。则该二叉树的中序遍历序列不会是（）。

选项：

A、1、2、3、4

B、2、3、4、1

C、3、2、4、1

D、4、3、2、1

答案：【3、2、4、1】4.单选题：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，则这棵二叉树的所有叶子结点是（）。

选项：

A、E、F、G

B、D、E、H

C、C、E、H

D、D、E、G、H

答案：【D、E、H】5.单选题：n(n≥2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是（）。

选项：

A、树中一定没有度为1的结点

B、树中两个权值最小的结点一定是兄弟结点

C、该树一定是一棵完全二叉树

D、树中任一非叶结点的权值一定不小于下一层任一结点的权值

答案：【该树一定是一棵完全二叉树】第六章图第六章测验1.单选题：已知图的邻接表如下，从顶点3出发，深度优先搜索的遍历序列是（）。

选项：

A、3→6→5→1→2→4

B、3→6→2→5→1→4

C、3→6→2→5→4→1

D、3→6→5→2→4→1

答案：【3→6→5→1→2→4】2.单选题：下列关于图的描述，错误的是（）。

选项：

A、关于图的存储结构，十字链表用于表示有向图，而多重邻接表用于表示无向图

B、图的深度优先搜索可以类比二叉树的先序遍历过程

C、图的广度优先搜索可以类比二叉树的中序遍历过程

D、稀疏图适合于用邻接表进行图的遍历，时间复杂度为O(m+n)

答案：【图的广度优先搜索可以类比二叉树的中序遍历过程】3.单选题：设有向图的邻接矩阵A如下所示，各顶点的度依次是（）。

选项：

A、1，2，1，2

B、2，2，1，1

C、3，4，2，3

D、4，4，2，2

答案：【3，4，2，3】4.单选题：使用Dijkstra算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。

选项：

A、5,2,3,4,6

B、5,2,3,6,4

C、5,2,4,3,6

D、5,2,6,3,4

答案：【5,2,3,6,4】5.单选题：对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。

选项：

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

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

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

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

答案：【3,1,4,2,6,5】第七章查找第七章测验1.单选题：若将关键字1、2、3、4、5、6、7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是（）。

选项：

A、0

B、1

C、2

D、3

答案：【3】2.单选题：现有一棵无重复关键字的平衡二叉树（AVL树）,对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（）。

选项：

A、根结点的度一定为2

B、树中最小元素一定是叶结点

C、最后插入的元素一定是叶结点

D、树中最大元素一定无左子树

答案：【树中最大元素一定无左子树】3.单选题：在一棵高度为2的5阶B树中，所含关键字的个数最少是（）。

选项：

A、5

B、7

C、8

D、14

答案：【5】4.单选题：关于AVL树和B树，下列描述错误的是（）。

选项：

A、都是平衡查找树

B、查找时间效率都是对数级的

C、叶子结点都在同一层上

D、查找过程主要基于比较操作

答案：【叶子结点都在同一层上】5.单选题：如果要求一个线性表既能较快地查找，又能适应动态变化的要求，最好采用（）法。

选项：

A、顺序查找

B、分块查找

C、折半查找

D、散列查找

答案：【分块查找】6.单选题：给定一个长度为m的散列表，现采用开放定址法中的线性探测法处理冲突问题，设现在要查找的关键字Key计算得出的散列地址是d，但此时散列表的d号地址单元不为空且关键字不为Key，则下一个要检查的散列地址是（）。

选项：

A、d-1

B、d+1

C、(d-1)%m

D、(d+1)%m

答案：【(d+1)%m】第八章排序第八章测验1.单选题：关于查找和排序的描述，下列说法错误的是（）。

选项：

A、时间复杂度为O(n2)的排序算法有直接插入排序、冒泡排序和简单选择排序

B、针对无序元素执行单个元素查找操作，先排序再查找可以提高整体时间效率

C、归并排序和基数排序所需辅助空间较多，其空间复杂度为O(n)

D、为了提高数据库中数据检索效率，可以使用B+树或Hash方式对多个数据项构建索引

答案：【针对无序元素执行单个元素查找操作，先排序再查找可以提高整体时间效率】2.单选题：下列排序算法中，平均时间复杂度达不到O(nlogn)的是（）。

选项：

A、堆排序

B、归并排序

C、快速排序

D、折半插入排序

答案：【折半插入排序】3.单选题：若数据元素序列[11，12，13，7，8，9，23，4，5]是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。

选项：

A、冒泡排序

B、直接插入排序

C、简单选择排序

D、2-路归并排序

答案：【直接插入排序】4.单选题：排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

选项：

A、希尔排序

B、快速排序

C、基数排序

D、2-路归并排序

答案：【快速排序】5.单选题：下列排序算法中元素的比较次数和关键字的初始排列次序无关的是（）。

选项：

A、直接插入排序

B、冒泡排序

C、快速排序

D、简单选择排序

答案：【简单选择排序】6.单选题：对10TB的数据文件进行排序，应使用的方法是（）。

选项：

A、堆排序

B、归并排序

C、快速排序

D、基数排序

答案：【归并排序】第九章典型算法策略第九章测验1.单选题：8皇后问题使用回溯法求解，最后可以求得（）种摆法。

选项：

A、76

B、91

C、92

D、108

答案：【92】2.单选题：Dijkstra算法的贪心策略主要体现在（）。

选项：

A、每次选择不在树中距离树最近的顶点加入树

B、每次选择不构成回路的权重最小的边加入集合

C、每次选择不在树中距离源点最近的顶点加入树

D、每次选择权重最小的两棵子树合并成树

答案：【每次选择不在树中距离源点最近的顶点加入树】3.单选题：下列关于贪心法与动态规划法，描述正确的是（）。

选项：

A、能用贪心法求解的问题，一定可以使用动态规划法求解

B、能用动态规划求解的问题，也可以使用贪心法求解

C、0/1背包问题可以用贪心法求精确解

D、贪心法与动态规划法适用的问题场景不同，需要根据具体问题选择

答案：【贪心法与动态规划法适用的问题场景不同，需要根据具体问题选择】4.单选题：关于回溯法和分支限界法，下列描述正确的是（）。

选项：

A、