算法大视界智慧树知到课后章节答案2023年下中国海洋大学

算法大视界智慧树知到课后章节答案2023年下中国海洋大学中国海洋大学

绪论单元测试

本课程是面向非计算机专业学生开放，要求学生了解计算机解决现实问题的方式和策略，学习数据结构的基本知识，着重培养学生的计算思维能力

A:对B:错

答案:对

第一章测试

以下那个数据结构是适用于"数据必须以相反的顺序存储然后检索"?

A:StackB:

LiinkListC:ListD:Queue

答案:Stack

判断下列说法是否正确：数据结构中数据元素之间的逻辑关系称为数据的逻辑结构。

A:对B:错

答案:对

关系数据模型的基本数据结构是：

A:树B:索引C:关系D:图

答案:图

数据挖掘算法主要有聚类算法、关联算法、决策树算法和回归分析等，各种算法用于解决不同的实际问题，某分行拟通过对县域机构数量与存款市场竞争力的相关性分析，进而建立两者之间的函数表达式，用新思维拓展县域市场，提升县域存款的市场竞争力。则可以采用的是（）

A:关联算法B:回归分析C:决策树算法D:聚类分析

答案:回归分析

算法一般用类C语言之类的伪码来描述，如果用C语言等高级语言来描述，则算法实际上就是程序了。

A:对B:错

答案:错

以下数据结构中哪一个是非线性结构？

A:二叉树B:线性表C:栈D:队列

答案:二叉树

树最适合用来表示

A:无序数据元素B:元素之间无联系的数据C:元素之间具有分支层次关系的数据D:有序数据元素

答案:元素之间具有分支层次关系的数据

在存储数据时，通常不仅要存储各数据元素的值，而且还要存储

A:数据元素之间的关系B:数据的处理方法C:数据元素的类型D:数据的存储方法

答案:数据元素之间的关系

计算机算法指的是：

A:解决问题的有限运算序列B:计算方法C:排序方法D:调度方法

答案:解决问题的有限运算序列

研究数据结构就是研究

A:数据的逻辑结构B:数据的逻辑结构、存储结构及其基本操作C:数据的逻辑结构和存储结构D:数据的存储结构

答案:数据的逻辑结构、存储结构及其基本操作

第二章测试

下面关于线性表的叙述错误的是（

）。

A:线性表采用顺序存储便于插入和删除操作的实现B:线性表采用链式存储不必占用一片连续的存储空间C:线性表采用顺序存储必须占用一片连续的存储空间D:线性表采用链式存储便于插入和删除操作的实现

答案:线性表采用顺序存储便于插入和删除操作的实现

链表不具备的特点是

A:插入删除不需要移动元素B:所需空间与其长度成正比C:可随机访问任一结点D:不必事先估计存储空间

答案:可随机访问任一结点

线性表是具有n个（）的有限序列

A:字符B:数据元素C:数据项D:表元素

答案:数据元素

在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（

）个元素。

A:n-i-1B:n-iC:n-i+1D:i

答案:n-i+1

对线性表进行二分查找时,要求线性表必须

A:以链接方式存储,且结点按关键字有序排序B:以顺序方式存储C:以顺序方式存储,且结点按关键字有序排序D:以链接方式存储

答案:以顺序方式存储,且结点按关键字有序排序

下述哪一条是顺序存储结构的优点？

A:可方便地用于各种逻辑结构的存储表示B:存储密度大C:插入运算方便D:删除运算方便

答案:存储密度大

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（

）存储方式最节省时间。

A:顺序表B:双链表C:单循环链表D:带头结点的双循环链表

答案:顺序表

静态链表中指针表示的是（

）

A:下一元素地址B:内存地址C:左、右孩子地址D:数组下标

答案:下一元素地址

指针的全部作用就是（

）

A:指向某常量B:指向某变量C:存储某数据D:指向某结点

答案:指向某结点

单链表的一个存储结点包含（）

A:指针域和链域B:数据域和链域C:指针域或链域D:数据域或指针域

答案:数据域和链域

第三章测试

设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为

A:3，2，5，8，6B:3，2，5，6，8

C:2，3，6，5，8D:2，3，5，8，6

答案:3，2，5，6，8

排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法称为

A:起泡排序B:插入排序C:选择排序D:希尔排序

答案:插入排序

快速排序方法在（

）情况下最不利于发挥其长处

A:要排序的数据中含有多个相同值B:要排序的数据量太大C:要排序的数据已基本有序D:要排序的数据个数为奇数

答案:要排序的数据已基本有序

对n个不同的数据进行冒泡排序，实现从小到大排序，在下列哪种情况下比较的次数最多（）

A:数据基本有序B:从小到大排列好的C:从大到小排列好的D:数据无序

答案:从大到小排列好的

在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是

A:冒泡排序B:直接插入排序C:希尔排序D:直接选择排序

答案:直接选择排序

关于排序算法，下列说法错误的是:

A:归并排序的最坏时间复杂度是O(n*log(n))B:快速排序的最坏时间复杂度是O(n*log(n))C:堆排序的平均时间复杂度是O(n*log(n))D:插入排序的最坏时间复杂度是O(n2)

答案:快速排序的最坏时间复杂度是O(n*log(n))

下列排序算法中存储消耗最大的是？（）

A:堆排序B:插入排序C:快速排序D:归并排序

答案:归并排序

以下哪种排序算法在最坏情况下的时间复杂度最小？

A:选择排序B:冒泡排序C:插入排序D:归并排序

答案:归并排序

待排序元素规模较小时，宜选取哪种排序算法效率最高（）

A:冒泡排序B:堆排序C:希尔排序

D:归并排序

答案:冒泡排序

若用冒泡排序对关键字序列{10,8,6,4,2},进行从小到大的排序，所需进行的关键字比较总次数是

A:15B:25C:20D:10

答案:10

第四章测试

一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是

A:edcbaB:dceabC:decbaD:abcde

答案:dceab

设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳

A:队列B:线性表的顺序存储结构C:线性表的链式存储结构D:栈

答案:栈

和顺序栈相比，链栈有一个比较明显的优势是

A:删除操作更容易实现B:插入操作更容易实现C:通常不会出现栈满的情况D:通常不会出现栈空的情况

答案:通常不会出现栈满的情况

栈的插入和删除操作在

A:栈底B:栈顶C:指定位置D:任意位置

答案:栈顶

若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是

A:SXSXXSSX

B:SXXSXSSXC:SSSXXSXXD:SXSSXXXX

答案:SSSXXSXX

对于栈操作数据的原则是（

）

A:先进先出B:后进先出C:后进后出D:不分顺序

答案:后进先出

若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是

A:i-j-1B:i-jC:j-i+1D:不确定的

答案:不确定的

一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是

A:15432B:23415C:23145D:54132

答案:54132

输入序列为ABC，可以变为CBA时，经过的栈操作为

A:push,pop,push,push,pop,popB:push,pop,push,pop,push,popC:push,push,pop,pop,push,popD:push,push,push,pop,pop,pop

答案:push,push,push,pop,pop,pop

栈在（

）中应用

A:子程序调用B:其他都是C:递归调用D:表达式求值

答案:子程序调用;其他都是;递归调用;表达式求值

第五章测试

将递归算法转换成对应的非递归算法时，通常需要使用（

）来保存中间结果

A:队列B:栈C:树D:链表

答案:栈

一个对象如果（

）由它自身来定义（或描述），则称其为递归。

A:全部的B:部分的C:不能D:完全

答案:部分的

下面哪种情况不能用递归来实现

A:直接插入排序

B:汉诺塔C:八皇后D:阶乘函数

答案:直接插入排序

一个递归函数能够正确运行的必要条件是

A:有分支结构B:有循环结构C:有输入D:有递归出口

答案:有递归出口

在递归函数的递归调用过程中问题的规模是

A:有时大有时小B:逐渐变大的C:不变的D:逐渐变小的

答案:逐渐变小的

一个递归算法必须包括

A:终止条件和递归部分B:迭代部分C:递归部分D:终止条件和迭代部分

答案:终止条件和递归部分

在将一个函数的实现从递归实现改为非递归实现时，一般需要用到下列哪个数据结构？

A:栈B:双向链表C:二叉树D:队列

答案:栈

若实现一个未加入任何优化的递归版本的斐波那契序列实现，该递归版本实现的时间复杂度和空间复杂度是怎样的?(不考虑整数溢出和机器的内存限制）

A:时间复杂度O(2^n),空间复杂度O(2^n)B:时间复杂度O(n)，空间复杂度O(2^n)C:时间复杂度O(n),空间复杂度O(n)D:时间复杂度O(2^n),空间复杂度O(n)

答案:时间复杂度O(2^n),空间复杂度O(n)

某递归算法的递归关系式为T(n)=2*T(n/2)+O(n)，那么它所对应的时间复杂度为

A:O(n^2)B:O(logn)C:O(n*logn)D:O(n)

答案:O(n*logn)

采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（）

A:每次划分后，先处理较长的分区可以减少递归次数B:递归次数与每次划分后得到的分区的处理顺序无关C:递归次数与初始数据的排列次序无关D:每次划分后，先处理较短的分区可以减少递归次数

答案:递归次数与每次划分后得到的分区的处理顺序无关

第六章测试

队列是一种（

）的线性表

A:只能插入B:只能删除C:先进先出D:先进后出

答案:先进先出

对于循环队列

A:无法判断队列是否为空B:队列不可能满C:无法判断队列是否为满D:其他说法都不对

答案:其他说法都不对

一个队列的入队序列是1，2，3，4，则队列的输出序列是

A:3，2，4，1B:1，2，3，4C:4，3，2，1D:1，4，3，2

答案:1，2，3，4

允许对队列进行的操作有

A:取出最近进队的元素B:对队列中的元素排序C:在队头元素之前插入元素D:删除队头元素

答案:删除队头元素

队列的“先进先出”特性是指

A:当同时进行插入、删除操作时，总是插入操作优先B:每当有删除操作时，总是要先做一次插入操作C:最早插入队列中的元素总是最后被删除D:每次从队列中删除的总是最早插入的元素

答案:每次从队列中删除的总是最早插入的元素

队列的结构属于

A:顺序存储的线性结构B:限制存取点的线性结构C:限制存取点的非线性结构D:链式存储的非线性结构

答案:限制存取点的线性结构

用链接方式存储的队列，在进行删除运算时

A:头、尾指针可能都要修改B:仅修改尾指针C:头、尾指针都要修改D:仅修改头指针

答案:头、尾指针可能都要修改

循环队列的队满条件为

A:(sq.rear+1)%mazsize==(sq.front+1)%maxsize;B:(sq.rear+1%maxsize==sq.front+1C:sq.rear==sq.frontD:sq.(rear+1)%maxsize==sq.front

答案:sq.(rear+1)%maxsize==sq.front

若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是

A:4132B:4231C:1234D:4213

答案:4231

循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是

A:

(rear-front+m)%mB:rear-frontC:rear-front-1D:rear-front+1

答案:

(rear-front+m)%m

第七章测试

在二叉树的第i层上至多有(

)结点

A:

B:

C:D:

答案:

设某哈夫曼树中有199个结点，则该哈夫曼树中有（

）个叶子结点

A:102B:101C:

99D:100

答案:100

下述二叉树中，（

）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序

A:二叉排序树B:哈夫曼树C:堆D:AVL树

答案:哈夫曼树

下列陈述中正确的是(

)

A:二叉树中必有度为2的结点B:二叉树中结点只有一个孩子时无左右之分C:二叉树中最多只有两棵子树，并且有左右之分D:二叉树是度为2的有序树

答案:二叉树中最多只有两棵子树，并且有左右之分

深度为5的二叉树至多有

个结点

A:16B:10C:32D:31

答案:31

如果初始时B-树为空树，通过逐个向3阶B-树中插入新结点(8,28,40,80,50,90,85,150,120,200)，以下说法正确的是

A:删除90时,需要将150放入其双亲结点中B:树中插入80时,结点需要分裂C:删除200时,需要将150放入其双亲结点中D:树中插入85时,结点需要分裂

答案:删除90时,需要将150放入其双亲结点中;树中插入85时,结点需要分裂

在下列表述中,（）是错误的

A:选择排序算法是不稳定的B:对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树C:平衡二叉树的左右子树的结点数之差的绝对值不超过1D:含有一个或多个空格字符的串称为空串

答案:对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树;平衡二叉树的左右子树的结点数之差的绝对值不超过1;含有一个或多个空格字符的串称为空串

以下不是平衡二叉查找树的是

A:AVL树B:哈夫曼树C:

B+/B-树D:红黑树

答案:哈夫曼树;

B+/B-树

数据库索引经常使用B+树。以下关于B+树的描述，错误的是哪一项？

A:B+树能够支持顺序查找B:B+树的插入、删除可以保证其平衡性C:B+树空间复杂度低于B树D:与二叉树相比，B+树更利于降低高度

答案:B+树空间复杂度低于B树

二叉树是每个结点最多有两个子树的树结构,假设一棵二叉树的高度为m，所有结点的度为0，或为2，则关于此树拥有的最少节点个数，下列选项正确的是

A:

2m-1B:2m+1C:2m-2D:m+1

答案:

2m-1

第八章测试

二叉排序树中左子树上所有结点的值均（

）根结点的值。

A:

!=B:=C:>D:

<

答案:

<

下列描述中不符合二叉排序树特点的是

A:根结点的关键字大于左、右子树中所有结点的关键字B:关键字插入的顺序影响二叉排序树的形态C:右子树中所有结点的关键字大于根节点的关键字D:左子树中所有结点的关键字小于根结点的关键字

答案:根结点的关键字大于左、右子树中所有结点的关键字

一棵二叉排序树是由关键字集合{18，43，27，44，36，39}构建的，其中序遍历序列是

A:18，43，27，44，36，39B:树形未定，无法确定C:44，43，39，36，27，18D:18，27，36，39，43，44

答案:18，27，36，39，43，44

二叉查找树的查找效率与二叉树的()有关

A:高度B:结点的多少C:结点的位置D:树型

答案:树型

二叉查找树在（

）时其查找效率最低

A:呈单枝树B:结点太复杂C:结点太多D:完全二叉树

答案:呈单枝树

一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是

A:ABCDEFGB:ADCFEGC:CABDEFGD:DACEFBG

答案:ABCDEFG

已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,

它的前序遍历是

A:cedbaB:decabC:acbedD:deabc

答案:cedba

将{32,2,15,65,28,10}依次插入初始为空的二叉排序树。则该树的前序遍历结果是

A:2,10,15,28,32,65B:32,2,15,10,28,65C:32,2,10,15,28,6D:10,28,15,2,65,32

答案:32,2,15,10,28,65

下列叙述正确的是

A:二叉树中除叶结点外,任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值，则此二叉树一定是二叉排序树B:在二叉排序树中插入一个新结点，总是插入到最下层，作为新的叶子结点C:在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同D:虽然给出关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的

答案:在二叉排序树中插入一个新结点，总是插入到最下层，作为新的叶子结点

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是

A:FB:EC:G

D:H

答案:G

下面关于m阶B-树说法正确的是(

)①每个结点至少有两棵非空子树②树中每个结点至多有m-1个关键字③所有叶子在同一层上④当插入一个数据项引起B-树结点分裂后,树长高一层

A:②③B:②③④C:①②③D:③

答案:②③

第九章测试

普里姆算法是用来解决

A:最小生成树B:最短路径C:拓扑结构D:关键路径

答案:最小生成树

设某有向图中有n个顶点，则该有向图对应的邻接表中有（

）个表头结点

A:

2n-1B:

n+1

C:n-1D:

n

答案:

n

设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为

A:2nB:nC:eD:2e

答案:2e

具有6个顶点的无向图至少应该有（

）条边才能确保是一个连通图

A:6B:7C:5D:8

答案:5

对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为

A:(n-1)×(n-1)B:(n-1)×nC:n×nD:n×(n+1)

答案:n×n

在对图进行深度优先搜索时，一般需要用到下列哪个数据结构？

A:栈B:单向链表C:二叉树D:队列

答案:栈

下列关于最小生成树的说法中，正确的是(

)。(1)最小生成树的代价唯一(2)权值最小的边一定会出现在所有的最小生成树中(3)用Prim算法从不同顶点开始得到的最小生成树的形态一定相同(4)Prim算法和Kruskal算法得到的最小生成树的形态总不相同

A:仅(1)B:仅(2)

(4)C:仅(2)D:仅(1)

(3)

答案:仅(1)

求图的最小生成树有两种算法，Kruskal算法适合于求稀疏图的最小生成树

A:错B:对

答案:对

6个顶点的连通图的最小生成树，其边数为（）

A:6B:7C:4D:5

答案:5

设完全无向图中有n个顶点，则该完全无向图中有多少条边

A:n(n-1)B:n(n-1)/2C:n(n+1)/2D:(n-1)/2

答案:n(n-1)/2

第十章测试

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的

A:1倍B:1/2C:2倍D:4倍

答案:1倍

下列哪一种图的邻接矩阵是对称矩阵？

A:无向图B:有向图C:AOE网D:AOV网

答案:无向图

设某强连通图中有n个顶点，则该强连通图中至少有（

）条边

A:n+1B:n(n-1)C:n(n+1)D:n

答案:n

求解最短路径的Floyd算法的时间