算法与数据结构智慧树知到课后章节答案2023年下浙江理工大学

算法与数据结构智慧树知到课后章节答案2023年下浙江理工大学浙江理工大学

绪论单元测试

学好算法与数据结构的关键在于多多实践。

A:错B:对

答案:对

第一章测试

数据结构是（）

A:一种数据类型B:相互之间存在一种或多种特定关系的数据元素的集合C:数据的存储结构D:一组性质相同的数据元素的集合

答案:相互之间存在一种或多种特定关系的数据元素的集合

下列说法错误的是（）

A:数据处理方式总是与数据的表示形式相联系B:数据是指描述客观事物的特征及活动所采用的符号形式C:数据在计算机存储器内的存在形式称为机外表示D:数据元素是数据的基本单位

答案:数据在计算机存储器内的存在形式称为机外表示

算法的描述方法只有语言方式。

A:错B:对

答案:错

下列关于算法说法错误的是（）

A:算法是指令的有限序列B:算法就是数学中的计算方法C:算法是在存储结构上的操作实现方法D:算法是对特定问题求解步骤的一种描述

答案:算法就是数学中的计算方法

有哪几种存储结构？

A:索引存储方式B:散列存储方式C:顺序存储方式D:链式存储方式

答案:索引存储方式;散列存储方式;顺序存储方式;链式存储方式

算法的效率主要是指（）

A:算法的空间效率和时间效率B:算法的时间效率C:算法的空间效率D:其他选项都不对

答案:算法的空间效率和时间效率

在数据结构的讨论中把数据结构从逻辑上分为（）

A:线性结构与非线性结构

B:内部结构与外部结构C:

静态结构与动态结构D:紧凑结构与非紧凑结构

答案:线性结构与非线性结构

指出下列程序段的时间复杂度（）

sum=1；

for(i=0;sum<n;i++)

sum+=1;

A:O(n*n)B:O(0)C:O(n)D:O(1)

答案:O(n)

树形结构中元素之间存在（）关系

A:一对多B:没有关系C:多对多D:一对一

答案:一对多

图形结构中元素之间存在（）关系

A:一对一B:多对多C:没有关系D:一对多

答案:多对多

第二章测试

带头结点的单链表head为空的判定条件是（）

A:head->next==NULLB:head->next==headC:head!=NULLD:head==NULL

答案:head->next==NULL

循环链表的主要优点是（）。

A:在表中任一结点出发都能扫描整个链表B:不再需要头指针C:在进行插入、删除运算时能保证链表不断开D:已知某结点位置后能容易找到其直接前驱

答案:在表中任一结点出发都能扫描整个链表

线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）

A:必须是连续的B:部分地址必须是连续的C:连续或不连续都可以D:一定是不连续的

答案:连续或不连续都可以

若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

A:循环单链表B:单链表C:双链表D:顺序表

答案:顺序表

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

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

答案:n-i+1

线性表的顺序存储结构是一种（）存储结构。

A:索引存取B:顺序存取C:散列存取D:随机存取

答案:随机存取

在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。

A:q->next=p->next;q->prior=p;p->next=q;p->next=q;B:p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C:p->next=q;q->prior=p;p->next->prior=q;q->next=q;D:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

答案:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。（答案中的i均为合法输入）

A:对顺序表中元素进行排序B:删除第i个元素C:在第i个元素之后插入一个新元素D:访问第i个元素的前驱

答案:访问第i个元素的前驱

已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。

A:p->next=s->next；s->next=q；B:q->next=s->next；s->next=p；C:s->next=q；p->next=s->next；D:s->next=p；q->next=s->next；

答案:q->next=s->next；s->next=p；

在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。

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

答案:(n-1)/2

第三章测试

栈和队列的共同点是()

A:没有共同点B:都是先进先出C:都是先进后出D:只允许在端点处插入和删除元素

答案:只允许在端点处插入和删除元素

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

A:edcbaB:abcdeC:decbaD:dceab

答案:dceab

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

A:顺序表B:队列C:栈D:链表

答案:栈

若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。

A:5和1B:2和4C:1和5D:4和2

答案:2和4

循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是()

A:rear-frontB:rear-front+1C:(rear-front+m)%mD:rear-front-1

答案:(rear-front+m)%m

一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（）。（注：top指向待插入位置）

A:*S->top=e;S->top++;B:S->top++;*S->top=e;C:*S->top=eD:S->top=e;

答案:*S->top=e;S->top++;

在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（）结构。

A:队列B:线性表C:堆栈D:数组

答案:队列

当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（）。

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

答案:N-1

依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）。

A:bB:cC:aD:d

答案:c

向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行(

)。(不带空的头结点)

A:s->next=HS->next;

HS->next=s;B:s->next=HS;

HS=HS->next;C:HS->next=s;D:s->next=HS;

HS=s;

答案:s->next=HS;

HS=s;

第四章测试

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，则a[8][5]的地址为（）。

A:33B:40C:18D:13

答案:33

设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()

A:BA+222B:BA+180C:BA+141D:BA+225

答案:BA+180

将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A[66][65]（即该元素下标i=66，j=65），在B数组中的位置K为（）。

A:198B:193C:195D:197

答案:195

二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节

A:3B:8C:10D:5

答案:5

设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为()

A:（i-1）*n+jB:（i-1）*n+j-1C:i*（j-1）D:j*m+i-1

答案:（i-1）*n+j

有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）

A:18000B:60C:66D:33

答案:66

设有两个串p和q，求q在p中首次出现的位置的运算称作（）。

A:模式匹配B:求子串C:求串长D:连接

答案:模式匹配

常对数组进行的两种基本操作是（）。

A:对数据元素的存取和修改B:查找与索引C:索引和修改D:建立与删除

答案:对数据元素的存取和修改

二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。

A:240B:100C:270D:80

答案:240

二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（）。

A:SA+222B:SA+225C:SA+180D:SA+141

答案:SA+180

第五章测试

引入二叉线索树的目的是（）。

A:使二叉树的遍历结果唯一B:为了能在二叉树中方便的进行插入与删除C:加快查找结点的前驱或后继的速度D:为了能方便的找到双亲

答案:加快查找结点的前驱或后继的速度

n个结点的线索二叉树上含有的线索数为（）。

A:n－lB:nC:n＋lD:2n

答案:n＋l

由3个结点可以构造出多少种不同的二叉树（）。

A:2B:5C:3D:4

答案:5

已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()。

A:-A+B*C/DEB:-+A*BC/DEC:-A+B*CD/ED:-+*ABC/DE

答案:-+A*BC/DE

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

A:9B:不确定C:11D:15

答案:11

有关二叉树下列说法正确的是（）。

A:二叉树中至少有一个结点的度为2B:二叉树的度为2C:二叉树中任何一个结点的度都为2D:一棵二叉树的度可以小于2

答案:一棵二叉树的度可以小于2

一个具有1025个结点的二叉树的高h为（）。

A:10B:11至1025之间C:10至1024之间D:11

答案:11至1025之间

若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。

A:中序B:按层次C:后序D:前序

答案:后序

若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()

A:X的右子树中最左的结点B:X的左子树中最右结点C:X的双亲D:X的右子树的根

答案:X的左子树中最右结点

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

A:HB:EC:FD:G

答案:G

第六章测试

无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A:a,e,b,c,f,dB:a,c,f,e,b,dC:a,e,d,f,c,bD:a,b,e,c,d,f

答案:a,e,d,f,c,b

已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，

E={,,,,,,,,},G的拓扑序列是（）。

A:V1,V3,V2,V6,V4,V5,V7B:V1,V2,V5,V3,V4,V6,V7C:V1,V3,V4,V6,V2,V5,V7D:V1,V3,V4,V5,V2,V6,V7

答案:V1,V3,V4,V6,V2,V5,V7

要连通具有n个顶点的有向图，至少需要（）条边。

A:n-lB:2nC:n+1D:n

答案:n

在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）

A:对B:错

答案:错

邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）

A:错B:对

答案:错

设无向图的顶点个数为n，则该图最多有（）条边。

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

答案:n(n-1)/2

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

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

答案:无向图

下面哪一方法可以判断出一个有向图是否有环（回路）：（）。

A:拓扑排序B:求最短路径C:求关键路径D:深度优先遍历

答案:拓扑排序

对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为

A:k2B:k1C:k1-k2D:k1+k2

答案:k1

下列说法不正确的是（）。

A:图的深度遍历不适用于有向图B:图的遍历是从给定的源点出发每一个顶点仅被访问一次C:图的深度遍历是一个递归过程D:遍历的基本算法有两种：深度遍历和广度遍历

答案:图的深度遍历不适用于有向图

第七章测试

一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32时，查找成功需要的比较次数是（）。

A:4B:2C:3D:8

答案:3

设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址为空，如用二次探测法处理冲突，关键字为49的结点地址是（

）。

A:5B:8C:3D:9

答案:9

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。

A:RRB:LLC:LRD:RL

答案:RL

当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。

A:取决于表递增还是递减B:不一定C:在大部分情况下要快D:必定快

答案:在大部分情况下要快

如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则应采用的查找方法是（）

A:二分法查找B:分块查找C:都不行D:顺序查找

答案:分块查找

在长度为n的顺序表中进行顺序查找，查找失败时需与键值比较次数是（）

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

答案:n+1

在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的键值（）

A:不一定是同义词B:无任何关系C:一定都是同义词D:一定都不是同义词

答案:不一定是同义词

对一棵二叉排序树进行()遍历，可以得到一个键值从小到大次序排列的有序序列。

A:中序B:层序C:先序D:后序

答案:中序

分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。

A:（100，80，60，90，120，130，110）B:（100，80，90，60，120，110，130）C:（100，120，110，130，80，60，90）D:（100，60，80，90，120，110，130）

答案:（100，60，80，90，120，110，130）

在查找过程中，若同时还要做插入、删除操作，这种查找称为

A:静态查找B:动态查找C:内部查找D:外部查找

答案:动态查找

第八章测试

对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

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

答案:从大到小排列好的

下列关键字序列中，（）是堆。

A:16，53，23，94，31，7