数据结构智慧树知到课后章节答案2023年下上海海洋大学

数据结构智慧树知到课后章节答案2023年下上海海洋大学上海海洋大学

第一章测试

数据的（）是面向计算机的。

A:数据结构B:物理结构C:线性结构D:逻辑结构

答案:物理结构

（）是组成数据的基本单位。

A:数据元素B:抽象数据类型C:数据类型D:数据项

答案:数据元素

下面程序段的时间复杂度为：（）

A:O（n2）B:O（n）C:O（n!）D:O（1）

答案:O（n）

一个算法的时间复杂度为（5n3+2nlog2n+4n+11）/（5n），其数量级表示为：（）

A:O（n2）B:O（n）C:O（nlog2n）D:O（log2n）

答案:O（n2）

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

A:算法分析的主要目的是评价算法的效率B:算法就是程序C:算法必须在有限次数内完成D:算法应该具有确定性

答案:算法就是程序

第二章测试

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找不成功的情况下，需比较（）个元素结点。

A:nB:n/2C:（n-1）/2D:（n+1）/2

答案:n

设单链表中结点的结构为（data,link），若要删除单链表中指针p指向结点的后一个结点（若存在），则需修改指针的操作为（）。

A:p->Link=p;B:p=p->Link;C:p=p->Link->Link;D:p->Link=p->Link->Link;

答案:p->Link=p->Link->Link;

在等概率情况下，顺序表的插入操作要移动（）表项。

A:四分之一B:一半C:三分之一D:全部

答案:一半

在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（）。

A:p->next=HL->next;HL->next=p;B:p->next=HL;p=HL;C:HL=p;p->next=HL;D:p->next=HL;HL=p;

答案:p->next=HL->next;HL->next=p;

对线性表，在下列哪种情况下应当采用链表表示？（）

A:表中元素需要占据一片连续的存储空间B:经常需要随机地存取元素C:表中元素的个数不变D:经常需要进行插入和删除操作

答案:经常需要进行插入和删除操作

第三章测试

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

A:123B:312C:231D:321

答案:312

栈和队列的共同特点是（）。

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

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

设用链表作为栈的存储结构则退栈操作（）。

A:必须判别栈是否为满B:对栈不作任何判别C:必须判别栈是否为空D:判别栈元素的类型

答案:必须判别栈是否为空

向一个栈顶指针为top的链式栈中插入一个s结点时，应执行（）。

A:s->link=top;top=s;B:s->link=top->link;top->link=s;C:s->link=top;top=top->link;D:top->link=s;

答案:s->link=top;top=s;

在一个链式队列中，假定front和rear分别为队头和队尾指针，则删除一个结点的操作为（）。

A:front=rear->nextB:rear=front->nextC:front=front->nextD:rear=rear->next

答案:front=front->next

第四章测试

在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A:行号B:列号C:元素值D:非零元素个数

答案:列号

设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？（）脚注(10)表示用10进制表示。

A:696B:688C:692D:678

答案:692

广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。

A:(x,(a,B))B:(a,B)C:AD:x

答案:x

一个子串在包含它的主串中的位置是指（）。

A:子串的最后那个字符在主串中的位置B:子串的最后那个字符在主串中首次出现的位置C:子串的第一个字符在主串中首次出现的位置D:子串的第一个字符在主串中的位置

答案:子串的第一个字符在主串中首次出现的位置

两个字符串相等的充要条件是（）。

A:其余选项答案都不对B:同时具备(A)和(B)两个条件C:两个字符串的长度相等D:两个字符串中对应位置上的字符相等

答案:同时具备(A)和(B)两个条件

第五章测试

树最适合用来表示（）。

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

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

设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。

A:N2-1B:N1-1C:N1+N3D:N2+N3

答案:N1-1

设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

A:229B:129C:189D:219

答案:229

10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。

A:2nB:2n+lC:2n-1D:n+l

答案:2n-1

线索二叉树中，结点p没有左子树的充要条件是（）。

A:其余选项都不对B:p->ltag=1且p->LeftChild=NULLC:p->LeftChild=NULLD:p->ltag=1

答案:p->ltag=1

第六章测试

设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。

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

答案:5

对于无向图G=(V,E),下列选项中，正确的是：（）

A:当∣V∣>∣E∣+1时，G一定是不连通的B:当∣V∣=∣E∣−1时，G一定是不连通的C:当∣V∣>∣E∣时，G一定是连通的D:当∣V∣<∣E∣时，G一定是连通的

答案:当∣V∣>∣E∣+1时，G一定是不连通的

若使用AOE网估算工程进度，则下列叙述中正确的是：（）

A:缩短任一关键活动的时间将会缩短工程的工期B:关键路径是从源点到汇点边数最多的一条路径C:关键路径是从源点到汇点路径长度最长的路径D:增加任一关键活动的时间不会延长工程的工期

答案:关键路径是从源点到汇点路径长度最长的路径

已知无向图G如下所示，使用克鲁斯卡尔（Kruskal）算法求图G的最小生成树，加入到最小生成树中的边依次是：（）

A:(b,f),(b,d),(a,e),(c,e),(b,e)B:(b,f),(b,d),(b,e),(a,e),(c,e)C:(a,e),(c,e),(b,e),(b,f),(b,d)D:(a,e),(b,e),(c,e),(b,d),(b,f)

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

对下图从顶点C出发进行深度优先搜索，哪个是错误的搜索序列？（）

A:CBADEFGHB:CDABEHFGC:CBAEFGHDD:CDAEHGFB

答案:CDABEHFG

给定有向图如下。下列哪个选项不是对应的拓扑序列？（）

A:aedfbcB:aedbfcC:abedfcD:abdfce

答案:abdfce

下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是：（）

A:3和7B:12和12C:15和15D:12和14

答案:12和14

第七章测试

对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个，

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

答案:4

已知线性表的关键字集合{21，11，13，25，48，6，39，83，30，96，108}，散列函数为h(key)=key%11，采用分离链接法解决冲突。则成功查找的平均查找长度为（）

A:1.18B:1.27C:1.36D:2.36

答案:1.36

若根据关键码建立长度为m的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为d，则下一次的哈希地址为（）。

A:(d+1)/mB:d+1C:(d+1)%mD:d

答案:(d+1)%m

用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：（）

A:99B:7C:50D:10

答案:7

解决散列法中出现的冲突问题常采用的方法是（）。

A:线性探查法、双散列法、开散列法。B:数字分析法、除留余数法、线性探查法。C:数字分析法、除留余数法、平方取中法。D:数字分析法、线性探查法、双散列法。

答案:线性探查法、双散列法、开散列法。

在一棵平衡二叉搜索树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（）。

A:3B:0C:1D:2

答案:1

第八章测试

平均时间复杂度为O(nlogn)且稳定的排序算法是（）。

A:选择排序B:归并排序C:快速排序D:桶排序

答案:归并排序

使用二路归并排序对含n个元素的数组M进行排序时，二路归并操作的功能是：（）

A:将M划分为n个部分，每个部分中仅含有一个元素B:将两个有序表合并为一个新的有序表C:将M划分为两部分，一部分元素的值均小于另一部分元素的值D:将M划分为两部分，两部分的元素个数大致相等

答案:将两个有序表合并为一个新的有序表

设数组S[]={93,946,372,9,146,151,301,485,236,327,43,892}，采用最低位优先（LSD）基数排序将S排列成升序序列。第1趟分配、收集后，元素372之前、之后紧邻的元素分别是：（）

A:43，892B:301，892C:236，301D:485，301

答案:301，892

将序列{