算法大视界知到智慧树章节测试课后答案2024年秋中国海洋大学

算法大视界知到智慧树章节测试课后答案2024年秋中国海洋大学绪论单元测试

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

A:错B:对

答案:对

第一章单元测试

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

A:ListB:QueueC:

LiinkListD:Stack

答案: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:iC:n-i-1D:n-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，6，8

B:2，3，6，5，8C:2，3，5，8，6D:3，2，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:10B:20C:25D:15

答案:10

第四章单元测试

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

A:edcbaB:dceabC:abcdeD:decba

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

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

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

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

答案:通常不会出现栈满的情况栈的插入和删除操作在

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

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

A:SXSSXXXXB:SXXSXSSXC:SXSXXSSX

D:SSSXXSXX

答案:SSSXXSXX对于栈操作数据的原则是（

）

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

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

A:i-jB:j-i+1C:不确定的D:i-j-1

答案:不确定的一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是

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

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

A:push,push,push,pop,pop,popB:push,pop,push,pop,push,popC:push,pop,push,push,pop,popD:push,push,pop,pop,push,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(n)B:时间复杂度O(n)，空间复杂度O(2^n)C:时间复杂度O(n),空间复杂度O(n)D:时间复杂度O(2^n),空间复杂度O(2^n)

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

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

答案:O(n*logn)采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（）

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

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

第六章单元测试

队列是一种（

）的线性表

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

答案:先进先出对于循环队列

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

答案:其他说法都不对一个队列的入队序列是1，2，3，4，则队列的输出序列是

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

答案: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==sq.frontC:sq.(rear+1)%maxsize==sq.frontD:(sq.rear+1%maxsize==sq.front+1

答案:sq.(rear+1)%maxsize==sq.front若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是

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

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

A:rear-front+1B:rear-frontC:

(rear-front+m)%mD:rear-front-1

答案:

(rear-front+m)%m

第七章单元测试

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

)结点

A:

B:C:D:

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

）个叶子结点

A:102B:

99C:100D:101

答案:100下述二叉树中，（

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

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

答案:哈夫曼树下列陈述中正确的是(

)

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

答案:二叉树中最多只有两棵子树，并且有左右之分深度为5的二叉树至多有

个结点

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

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

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

答案:删除90时,需要将150放入其双亲结点中；树中插入85时,结点需要分裂在下列表述中,（）是错误的

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

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

A:AVL树B:

B+/B-树C:红黑树D:哈夫曼树

答案:

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

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

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

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

2m-1

答案:

2m-1

第八章单元测试

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

）根结点的值。

A:

!=B:=C:>D:

<

答案:

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

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

答案:根结点的关键字大于左、右子树中所有结点的关键字一棵二叉排序树是由关键字集合{18，43，27，44，36，39}构建的，其中序遍历序列是

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

答案:18，27，36，39，43，44二叉查找树的查找效率与二叉树的()有关

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

答案:树型二叉查找树在（

）时其查找效率最低

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

答案:呈单枝树一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是

A:ADCFEGB:CABDEFGC:ABCDEFGD:DACEFBG

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

它的前序遍历是

A:decabB:acbedC:deabcD:cedba

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

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

答案:32,2,15,10,28,65下列叙述正确的是

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

答案:在二叉排序树中插入一个新结点，总是插入到最下层，作为新的叶子结点二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是

A:EB:G

C:FD:H

答案:G

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

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

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

答案:②③

第九章单元测试

普里姆算法是用来解决

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

答案:最小生成树设某有向图中有n个顶点，则该有向图对应的邻接表中有（

）个表头结点

A:n-1B:

2n-1C:

nD:

n+1

答案:

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

A:2eB:nC:2nD:e

答案:2e具有6个顶点的无向图至少应该有（

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

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

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

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

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

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

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

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

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

(4)D:仅(1)

(3)

答案:仅(1)求图的最小生成树有两种算法，Kruskal算法适合于求稀疏图的最小生成树

A:错B:对

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

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

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

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

答案:n(n-1)/2

第十章单元测试

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

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

答案:1倍下列哪一种图的邻接矩阵是对称矩阵？

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

答案:无向图设某强连通图中有n个顶点，则该强连通图中至少有（

）条边

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

答案:n求解最短路径的Floyd算法的时间复杂度为