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

数据结构知到章节测试答案智慧树2023年最新上海海洋大学第一章测试

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

参考答案:

物理结构

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

参考答案:

数据元素

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

参考答案:

O（n）

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

参考答案:

O（n2）

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

参考答案:

算法就是程序

第二章测试

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

参考答案:

n

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

参考答案:

p->Link=p->Link->Link;

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

参考答案:

一半

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

参考答案:

p->next=HL->next;HL->next=p;

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

参考答案:

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

第三章测试

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

参考答案:

312

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

参考答案:

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

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

参考答案:

必须判别栈是否为空

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

参考答案:

s->link=top;top=s;

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

参考答案:

front=front->next

第四章测试

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

参考答案:

列号

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

参考答案:

692

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

参考答案:

x

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

参考答案:

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

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

参考答案:

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

第五章测试

树最适合用来表示（）。

参考答案:

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

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

参考答案:

N1-1

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

参考答案:

229

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

参考答案:

2n-1

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

参考答案:

p->ltag=1

第六章测试

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

参考答案:

5

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

参考答案:

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

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

参考答案:

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

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

参考答案:

(b,f),(b,d),(a,e),(c,e),(b,e)

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

参考答案:

CDABEHFG

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

参考答案:

abdfce

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

参考答案:

12和14

第七章测试

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

参考答案:

4

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

参考答案:

1.36

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

参考答案:

(d+1)%m

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

参考答案:

7

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

参考答案:

线性探查法、双散列法、开散列法。

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

参考答案:

1

第八章测试

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

参考答案:

归并排序

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

参考答案:

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

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

参考答案:

301，892

将序列{2,12,16,88,5,10,34}排序。若前2趟排序的结果如下：

第1趟排