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

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

A:对

B:错

答案:A第一章测试以下那个数据结构是适用于”数据必须以相反的顺序存储然后检索”?

A:

LiinkList

B:Stack

C:Queue

D:List

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

A:错

B:对

答案:B关系数据模型的基本数据结构是：

A:索引

B:关系

C:树

D:图

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

A:关联算法

B:回归分析

C:聚类分析

D:决策树算法

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

A:对

B:错

答案:B以下数据结构中哪一个是非线性结构？

A:队列

B:二叉树

C:栈

D:线性表

答案:B树最适合用来表示

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

B:无序数据元素

C:元素之间无联系的数据

D:有序数据元素

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

A:数据元素的类型

B:数据的存储方法

C:数据的处理方法

D:数据元素之间的关系

答案:D计算机算法指的是：

A:调度方法

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

C:排序方法

D:计算方法

答案:B研究数据结构就是研究

A:数据的逻辑结构

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

C:数据的存储结构

D:数据的逻辑结构和存储结构

答案:B第二章测试下面关于线性表的叙述错误的是（

）。

A:线性表采用链式存储便于插入和删除操作的实现

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

C:线性表采用顺序存储必须占用一片连续的存储空间

D:线性表采用链式存储不必占用一片连续的存储空间

答案:B链表不具备的特点是

A:可随机访问任一结点

B:所需空间与其长度成正比

C:插入删除不需要移动元素

D:不必事先估计存储空间

答案:A线性表是具有n个（）的有限序列

A:表元素

B:字符

C:数据元素

D:数据项

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

）个元素。

A:n-i

B:n-i-1

C:n-i+1

D:i

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

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

B:以顺序方式存储

C:以链接方式存储

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

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

A:插入运算方便

B:删除运算方便

C:存储密度大

D:可方便地用于各种逻辑结构的存储表示

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

）存储方式最节省时间。

A:单循环链表

B:带头结点的双循环链表

C:双链表

D:顺序表

答案:D静态链表中指针表示的是（

）

A:数组下标

B:内存地址

C:左、右孩子地址

D:下一元素地址

答案:D指针的全部作用就是（

）

A:存储某数据

B:指向某结点

C:指向某常量

D:指向某变量

答案:B单链表的一个存储结点包含（）

A:指针域或链域

B:数据域或指针域

C:指针域和链域

D:数据域和链域

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

A:2，3，5，8，6

B:2，3，6，5，8

C:3，2，5，8，6

D:3，2，5，6，8

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

A:选择排序

B:希尔排序

C:起泡排序

D:插入排序

答案:D快速排序方法在（

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

A:要排序的数据已基本有序

B:要排序的数据个数为奇数

C:要排序的数据中含有多个相同值

D:要排序的数据量太大

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

A:数据基本有序

B:从大到小排列好的

C:数据无序

D:从小到大排列好的

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

A:直接选择排序

B:希尔排序

C:直接插入排序

D:冒泡排序

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

A:归并排序的最坏时间复杂度是O(nlog(n))

B:快速排序的最坏时间复杂度是O(nlog(n))

C:插入排序的最坏时间复杂度是O(n2)

D:堆排序的平均时间复杂度是O(n*log(n))

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

A:归并排序

B:堆排序

C:插入排序

D:快速排序

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

A:冒泡排序

B:插入排序

C:归并排序

D:选择排序

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

A:归并排序

B:堆排序

C:希尔排序

D:冒泡排序

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

A:15

B:10

C:25

D:20

答案:B第四章测试一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是

A:abcde

B:decba

C:dceab

D:edcba

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

A:栈

B:线性表的顺序存储结构

C:线性表的链式存储结构

D:队列

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

A:插入操作更容易实现

B:删除操作更容易实现

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

D:通常不会出现栈空的情况

答案:C栈的插入和删除操作在

A:栈顶

B:任意位置

C:指定位置

D:栈底

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

A:SXXSXSSX

B:SSSXXSXX

C:SXSXXSSX

D:SXSSXXXX

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

）

A:不分顺序

B:后进先出

C:先进先出

D:后进后出

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

A:i-j-1

B:i-j

C:j-i+1

D:不确定的

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

A:23145

B:23415

C:15432

D:54132

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

A:push,push,push,pop,pop,pop

B:push,pop,push,pop,push,pop

C:push,pop,push,push,pop,pop

D:push,push,pop,pop,push,pop

答案:A栈在（

）中应用

A:表达式求值

B:其他都是

C:递归调用

D:子程序调用

答案:ABCD第五章测试将递归算法转换成对应的非递归算法时，通常需要使用（

）来保存中间结果

A:栈

B:树

C:链表

D:队列

答案:A一个对象如果（

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

A:全部的

B:部分的

C:不能

D:完全

答案:B下面哪种情况不能用递归来实现

A:汉诺塔

B:直接插入排序

C:八皇后

D:阶乘函数

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

A:有递归出口

B:有循环结构

C:有分支结构

D:有输入

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

A:逐渐变小的

B:不变的

C:逐渐变大的

D:有时大有时小

答案:A一个递归算法必须包括

A:终止条件和递归部分

B:终止条件和迭代部分

C:递归部分

D:迭代部分

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

A:栈

B:双向链表

C:队列

D:二叉树

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

A:时间复杂度O(n),空间复杂度O(n)

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

C:时间复杂度O(n)，空间复杂度O(2^n)

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

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

A:O(n)

B:O(nlogn)

C:O(n^2)

D:O(logn)

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

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

B:每次划分后，先处理较长的分区可以减少递归次数

C:每次划分后，先处理较短的分区可以减少递归次数

D:递归次数与初始数据的排列次序无关

答案:A第六章测试队列是一种（

）的线性表

A:只能删除

B:先进后出

C:只能插入

D:先进先出

答案:D对于循环队列

A:队列不可能满

B:其他说法都不对

C:无法判断队列是否为满

D:无法判断队列是否为空

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

A:1，4，3，2

B:3，2，4，1

C:1，2，3，4

D:4，3，2，1

答案:C允许对队列进行的操作有

A:在队头元素之前插入元素

B:取出最近进队的元素

C:删除队头元素

D:对队列中的元素排序

答案:C队列的“先进先出”特性是指

A:最早插入队列中的元素总是最后被删除

B:每当有删除操作时，总是要先做一次插入操作

C:当同时进行插入、删除操作时，总是插入操作优先

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

答案:D队列的结构属于

A:链式存储的非线性结构

B:顺序存储的线性结构

C:限制存取点的非线性结构

D:限制存取点的线性结构

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

A:仅修改头指针

B:仅修改尾指针

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

D:头、尾指针都要修改

答案:C循环队列的队满条件为

A:(sq.rear+1%maxsize==sq.front+1

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

C:sq.rear==sq.front

D:(sq.rear+1)%mazsize==(sq.front+1)%maxsize;

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

A:1234

B:4132

C:4231

D:4213

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

A:rear-front

B:rear-front-1

C:

(rear-front+m)%m

D:rear-front+1

答案:C第七章测试在二叉树的第i层上至多有(

)结点

A:

B:

C:

D:

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

）个叶子结点

A:101

B:102

C:

99

D:100

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

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

A:二叉排序树

B:AVL树

C:哈夫曼树

D:堆

答案:C下列陈述中正确的是(

)

A:二叉树中必有度为2的结点

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

C:二叉树中结点只有一个孩子时无左右之分

D:二叉树是度为2的有序树

答案:B深度为5的二叉树至多有

个结点

A:16

B:10

C:32

D:31

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

A:删除90时,需要将150放入其双亲结点中

B:树中插入85时,结点需要分裂

C:删除200时,需要将150放入其双亲结点中

D:树中插入80时,结点需要分裂

答案:AB在下列表述中,（）是错误的

A:对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树

B:平衡二叉树的左右子树的结点数之差的绝对值不超过1

C:含有一个或多个空格字符的串称为空串

D:选择排序算法是不稳定的

答案:ABC以下不是平衡二叉查找树的是

A:

B+/B-树

B:哈夫曼树

C:AVL树

D:红黑树

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

A:

B+树能够支持顺序查找

B:B+树的插入、删除可以保证其平衡性

C:与二叉树相比，B+树更利于降低高度

D:B+树空间复杂度低于B树

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

A:

2m-1

B:2m-2

C:2m+1

D:m+1

答案:A第八章测试二叉排序树中左子树上所有结点的值均（

）根结点的值。

A:

!=

B:=

C:>

D:

<

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

A:关键字插入的顺序影响二叉排序树的形态

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

C:右子树中所有结点的关键字大于根节点的关键字

D:左子树中所有结点的关键字小于根结点的关键字

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

A:树形未定，无法确定

B:18，43，27，44，36，39

C:18，27，36，39，43，44

D:44，43，39，36，27，18

答案:C二叉查找树的查找效率与二叉树的()有关

A:结点的位置

B:树型

C:结点的多少

D:高度

答案:B二叉查找树在（

）时其查找效率最低

A:结点太多

B:完全二叉树

C:结点太复杂

D:呈单枝树

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

A:ADCFEG

B:ABCDEFG

C:CABDEFG

D:DACEFBG

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

它的前序遍历是

A:cedba

B:decab

C:acbed

D:deabc

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

A:2,10,15,28,32,65

B:32,2,10,15,28,6

C:10,28,15,2,65,32

D:32,2,15,10,28,65

答案:D下列叙述正确的是

A:在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同

B:虽然给出关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的

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

D:二叉树中除叶结点外,任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值，则此二叉树一定是二叉排序树

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

A:F

B:H

C:E

D:G

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

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

A:②③

B:③

C:②③④

D:①②③

答案:A第九章测试普里姆算法是用来解决

A:最小生成树

B:关键路径

C:最短路径

D:拓扑结构

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

）个表头结点

A:

2n-1

B:

n

C:n-1

D:

n+1

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

A:2e

B:e

C:2n

D:n

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

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

A:6

B:5

C:7

D:8

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

A:n×(n+1)

B:(n-1)×(n-1)

C:n×n

D:(n-1)×n

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

A:队列

B:栈

C:二叉树

D:单向链表

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

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

A:仅(2)

(4)

B:仅(2)

C:仅(1)

D:仅(1)

(3)

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

A:错

B:对

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

A:5

B:6

C:4

D:7

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

A:(n-1)/2

B:n(n-1)/2

C:n(n+1)/2

D:n(n-1)

答案:B第十章测试在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的

A:2倍

B:1倍

C:1/2

D:4倍

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

A:无向图

B:AOV网

C:AOE网

D:有向图

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

）条边

A:n

B:n+1

C:n(n+1)

D:n(n-1)

答案:A求解最短路径的Floyd算法的时间