数据结构知到智慧树章节测试课后答案2024年秋上海海洋大学

数据结构知到智慧树章节测试课后答案2024年秋上海海洋大学第一章单元测试

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

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

答案:物理结构（）是组成数据的基本单位。

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

答案:数据元素下面程序段的时间复杂度为：（）

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

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

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

答案:O（n2）关于算法的说法错误的是（）

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

答案:算法就是程序

第二章单元测试

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

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

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

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

答案:p->Link=p->Link->Link;在等概率情况下，顺序表的插入操作要移动（）表项。

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

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

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

答案:p->next=HL->next;HL->next=p;对线性表，在下列哪种情况下应当采用链表表示？（）

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

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

第三章单元测试

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

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

答案:312栈和队列的共同特点是（）。

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

答案:只允许在端点处插入和删除元素设用链表作为栈的存储结构则退栈操作（）。

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

答案:必须判别栈是否为空向一个栈顶指针为top的链式栈中插入一个s结点时，应执行（）。

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

答案:s->link=top;top=s;在一个链式队列中，假定front和rear分别为队头和队尾指针，则删除一个结点的操作为（）。

A:front=rear->nextB:rear=rear->nextC:front=front->nextD:rear=front->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:AC:xD:(a,B)

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

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

答案:子串的第一个字符在主串中首次出现的位置两个字符串相等的充要条件是（）。

A:同时具备(A)和(B)两个条件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:129B:229C:219D:189

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

A:2n-1B:2n+lC:n+lD:2n

答案:2n-1线索二叉树中，结点p没有左子树的充要条件是（）。

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

答案:p->ltag=1

第六章单元测试

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

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

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

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

答案:当∣V∣>∣E∣+1时，G一定是不连通的若使用AOE网估算工程进度，则下列叙述中正确的是：（）

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

答案:关键路径是从源点到汇点路径长度最长的路径已知无向图G如下所示，使用克鲁斯卡尔（Kruskal）算法求图G的最小生成树，加入到最小生成树中的边依次是：（）

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

答案:(b,f),(b,d),(a,e),(c,e),(b,e)对下图从顶点C出发进行深度优先搜索，哪个是错误的搜索序列？（）

A:CBADEFGHB:CDABEHFGC:CBAEFGHDD:CDAEHGFB

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

A:abedfcB:abdfceC:aedbfcD:aedfbc

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

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

答案:12和14

第七章单元测试

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

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

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

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

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

A:(d+1)%mB:dC:d+1D:(d+1)/m

答案:(d+1)%m用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：（）

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

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

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

答案:线性探查法、双散列法、开散列法。在一棵平衡二叉搜索树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（）。

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

答案:1

第八章单元测试

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

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

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

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

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

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

答案:301，892将序列{