数据结构（A）智慧树知到课后章节答案2023年下山东理工大学

数据结构（A）智慧树知到课后章节答案2023年下山东理工大学山东理工大学

第一章测试

数据结构的抽象操作的定义与具体实现有关。（）

A:对B:错

答案:错

数据的物理结构是指数据在计算机内的实际存储形式。（）

A:错B:对

答案:错

顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）

A:错B:对

答案:错

数据元素是数据的最小单位。（）

A:错B:对

答案:错

逻辑结构是（）关系的整体。（）

A:数据元素之间逻辑

B:数据项之间逻辑

C:存储结构之间

D:数据类型之间

答案:数据元素之间逻辑

数据结构有（）种基本逻辑结构。（）

A:2

B:1

C:3

D:4

答案:4

下列四种基本的逻辑结构中，数据元素之间关系最弱的是（）。

A:图状结构

B:树形结构

C:集合

D:线性结构

答案:集合

从逻辑上可以把数据结构分为（）两大类。（）

A:动态结构、静态结构

B:线性结构、非线性结构

C:顺序结构、链式结构

D:初等结构、构造型结构

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

for（i=0；i＜n；i++）

c[i][i]=i+i算法的时间复杂度是（）。

A:O(n2)

B:O(log2n)

C:O(1)

D:O(n)

答案:O(n)

下列时间复杂度中最好的是（）。

A:O(n)

B:O(1)

C:O(n2)

D:O(log2n)

答案:O(1)

第二章测试

对任何数据结构，链式存储结构一定优于顺序存储结构。（）

A:错B:对

答案:错

循环链表不是线性表。（）

A:错B:对

答案:错

在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存储结构。（）

A:错B:对

答案:错

顺序存储的线性表可以随机存取。（）

A:错B:对

答案:对

带头结点的单链表（以head为头指针）为空判断条件是（）。

A:head!=NULL

B:head==NULL

C:head-＞next==head

D:head-＞next==NULL

答案:head-＞next==NULL

在单链表中，一个结点有（）个指针。（）

A:2

B:4

C:3

D:1

答案:1

对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构为（）。

A:用头指针表示的单循环链表

B:用尾指针表示的单循环链表

C:单链表

D:顺序表

答案:用尾指针表示的单循环链表

在一个以h为头指针的单循环链中，p指针指向链尾的条件是：（）。

A:p-＞next-＞next=h

B:p-＞next=NIL

C:p-＞next=h

D:p-＞data=-1

答案:p-＞next=h

P和q两个指针分别指向双向循环链表L的两个结点，p所指结点是q所指结点后继的条件是（）。

A:q-＞next==p-＞next

B:p==q

C:p-＞next==q

D:q-＞next==p

答案:q-＞next==p

设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。（）

A:单循环链表

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

C:带尾指针的单循环链表

D:单链表

答案:带头结点的双循环链表

第三章测试

若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。（）

A:错B:对

答案:对

两个栈共用静态存储空间，相向增长使用，也存在空间溢出问题。（）

A:对B:错

答案:对

队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（）

A:错B:对

答案:错

任何一个递归过程都可以转换成非递归过程。（）

A:错B:对

答案:对

某栈的输入序列为a,b，c，d，下面的四个序列中，不可能是它的输出序列的是：（）。

A:b,c，d，a

B:a，c，b，d

C:c,d，b,a

D:d,c，a，b

答案:d,c，a，b

一个递归算法必须包括：（）。

A:终止条件和迭代部分

B:迭代部分

C:终止条件和递归部分

D:递归部分

答案:终止条件和递归部分

中缀表达式A-(B+C／D)*E的后缀形式是：（）。

A:ABCD/E*+

B:ABCD／+E*

C:AB-C+D／E*

D:ABC+D/-E*

答案:ABCD／+E*

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

A:1和5

B:4和2

C:5和1

D:2和4

答案:2和4

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

A:栈

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

C:队列

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

答案:栈

经过InitStack（S）；Push（S，a）；Push（S，b）；Pop（S，x）；Pop（S，x）；的运算后EmptyStack（S）的值是（）。

A:1

B:0

C:b

D:a

答案:1

第四章测试

KMP算法的特点是在模式匹配时指示主串的整型指针值不会减小。（）

A:对B:错

答案:对

设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配。（）

A:对B:错

答案:对

INDEX（‘DATASTRUCTURE’，‘STR’）=4。（）

A:错B:对

答案:错

空串是零个字符的串，其长度等于零。（）

A:对B:错

答案:对

已知U=‘xyxyxyxxyxy’；t=‘xxy’；

ASSIGN（S，U）；

ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；

ASSIGN（m，‘ww’）

求REPLACE（S，V，m）=‘xyxyxywwy’。（）

A:错B:对

答案:对

设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度可达到O(n+m)。（）

A:错B:对

答案:对

字符串’ababaaab’的nextval函数值为01010421。（）

A:错B:对

答案:对

串又称字符串，（）。

A:串中可以含有空格字符

B:串中元素只能是字符

C:串中元素只能是字母

D:串长度不为零

答案:串中元素只能是字符

模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（）。

A:01112211123456712

B:01112231123456712

C:01110013101100701

D:01112121123456112

答案:01112231123456712

模式串t=‘abcaabbcabcaabdab’，该模式串的nextval数组的值为（）。

A:01102131011021701

B:01110013101100701

C:01112231123456712

D:01100111011001701

答案:01102131011021701

第五章测试

对于数组的操作，最常见的两种是（）

A:索引和修改

B:查找和修改

C:查找和索引

D:建立和删除

答案:查找和修改

稀疏矩阵一般的压缩存储方法有（）两种。（）

A:三元组和十字链表

B:二维数组和三维数组

C:散列和十字链表

D:三元组和散列

答案:三元组和十字链表

若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1...n(n+1)/2+1]中，则存放到B[k]中的非零元素aij(1≤i,j≤n）的下标i,j与k的对应关系是（)。

A:(j-1)(2n-j+1)/2+i-j

B:(j-1)(2n-j+1)/2+i-j-1

C:(j-1)(2n-j+2)/2+i-j+1

D:(j-1)(2n-j+2)/2+i-j

答案:(j-1)(2n-j+2)/2+i-j+1

有一个n的对称矩阵A，将其下三角部分按行存放在一维数组B中，而A[0][0存放于B[0]中，则第i行的对角元素A[i][i]存放于B中的（）处。（）

A:(2n-i-1)i/2

B:(i+3)i/2

C:(i+1)i/2

D:(2n-i+1)i/2

答案:(i+3)i/2

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

A:240

B:270

C:80

D:100

答案:240

设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j(1＜i≤j≤12)按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是()。

A:66

B:51

C:55

D:50

答案:50

已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()。

A:head(tail(LS))

B:head(tail(tail(head(LS))))

C:tail(head(LS))

D:head(tail(head(tail(LS)))

答案:head(tail(head(tail(LS)))

广义表（（a,b,c,d））的表尾是（）。

A:（）

B:（a,b,c,d）

C:（b,c,d）

D:a

答案:（a,b,c,d）

设广义表L=（（a,b,c）），则L的长度和深度分别为（）。

A:1和1

B:1和2

C:1和3

D:2和3

答案:1和2

下面说法不正确的是()。

A:广义表的表头总是一个广义表

B:广义表的表尾总是一个广义表

C:广义表难以用顺序存储结构

D:广义表可以是一个多层次的结构

答案:广义表的表头总是一个广义表

第六章测试

一棵有n个结点的树的所有结点的度数之和为（）

A:2n

B:n-1

C:n

D:n+1

答案:n-1

对于一棵具有n个结点、度为4的树来说，()

A:至少在某一层上正好有4个结点

B:树的高度至多是n-3

C:第i层上至多有4(i-1)个结点

D:树的高度至多是n-4

答案:树的高度至多是n-3

假定―棵度为3的树中，结点数为50，则其最小高度为（）

A:3

B:4

C:6

D:5

答案:5

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

A:10~1024

B:11

C:11~1025

D:10

答案:11~1025

设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是（）

A:2k

B:2k-1

C:k2

D:2k+1

答案:2k-1

在任何一棵二叉树中，若结点a有左孩子b、右孩子c，则在结点的先序序列、中序序列、

后序序列中，()。

A:结点b一定在结点a的前面

B:结点α一定在结点b的前面

C:结点b一定在结点c的前面

D:结点a一定在结点c的前面

答案:结点b一定在结点c的前面

若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是()。

A:3,2,4,1

B:2,3,4,1

C:1,2,3,4

D:4,3,2,1

答案:3,2,4,1

某二叉树的树形所示，其后序序列为e，a，c，b，d，g，f，树中与结点a同层的结点是（）。

A:f

B:g

C:d

D:c

答案:d

所示的二叉树进行中序线索化，则结点X的左、右线索指向的结点分别是（）。

A:d,c

B:e,a

C:e,c

D:b,a

答案:b,a

先序序列为a,b,c,d的不同二叉树的个数是（）。

A:16

B:13

C:14

D:15

答案:14

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

A:X的左子树中最右叶结点

B:X的右子树中最左的结点

C:X的左子树中最右结点

D:X的双亲

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

设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个

数为n，森林F中第一棵树的结点个数是（）。

A:n+l

B:m-n

C:条件不足，无法确定

D:m-n-1

答案:m-n

将森林F转换为对应的二叉树T，F中叶结点的个数等于()。

A:T中左孩子指针为空的结点个数

B:T中度为1的结点个数

C:T中右孩子指针为空的结点个数

D:T中叶结点的个数

答案:T中左孩子指针为空的结点个数

若森林F有15条边、25个结点，则F包含树的个数是（）。

A:8

B:11

C:9

D:10

答案:10

n(n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中错误的是（）。

A:树中一定没有度为1的结点

B:树中任一非叶结点的权值一定不小于下一层任一结点的权值

C:树中两个权值最小的结点一定是兄弟结点

D:该树一定是一棵完全二叉树

答案:该树一定是一棵完全二叉树

给定整数集合{3,5,6,9,12}，与之对应的哈夫曼树是（）

A:如图B

B:如图A

C:如图C

D:如图D

答案:如图C

对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是（）。

A:60

B:57

C:58

D:56

答案:58

若将一棵树T转化为对应的二叉树BT，则不列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是（）。

A:按层遍历

B:先序遍历

C:后序遍历

D:中序遍历

答案:中序遍历

在森林的二叉树表示中，结点M和结点N是同一父结点的左儿子和右心子，则在该森林中().

A:M和N有同一双亲

B:M和N可能无公共祖先

C:M是N的儿子

D:M是N的左兄弟

答案:M和N可能无公共祖先

某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（）棵树。（）

A:4

B:3

C:2

D:1

答案:3

第七章测试

十字链表是无向图的一种存储结构。（）

A:错B:对

答案:错

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

A:错B:对

答案:对

若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）

A:错B:对

答案:对

给定有权无向图的邻接矩阵如下，其最小生成树的总权重是（）。

A:18

B:23

C:24

D:17

答案:23

图中关于路径的定义是（）。

A:其他定义都不是。

B:由顶点和相邻顶点序偶构成的边所形成的序列。

C:由不同顶点所形成的序列。

D:由不同边所形成的序列。

答案:由顶点和相邻顶点序偶构成的边所形成的序列。

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

A:有向图

B:无向图

C:AOV网

D:AOE网

答案:无向图

在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A:1

B:1/2

C:4

D:2

答案:1

无向图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,d,f,c,b

B:a,e,b,c,f,d

C:a,c,f,e,b,d

D:a,b,e,c,d,f

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

下面关于求关键路径的说法不正确的是（）。

A:关键活动一定位于关键路径上。

B:一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差。

C:求关键路径是以拓扑排序为基础的。

D:一个事件的最早开始时间和以该事件为尾的弧的活动最早开始时间相同。

答案:一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差。

图G有n个顶点，求其最短路径的Dijkstra算法的时间复杂度为（）

A:O（n+e）

B:O（n）

C:O（n2）

D:O（n3）

答案:O（n3）

第八章测试

中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）

A:错B:对

答案:对

哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。（）

A:对B:错

答案:对

二叉排序树的查找和折半查找时间的性能相同。（）

A:对B:错

答案:错

AVL树是一棵二叉树．该树上任一结点的平衡因子的绝对值不大于1。（）

A:对B:错

答案:对

散列法存储的基本思想是由关键码的值决定数据的存储地址。（）

A:对B:错

答案:对

折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。（）

A:错B:对

答案:对

若根据查找表建立长度为m的闭散列表并采用二次探测处理冲突，假定对一个元素第一次计算的散列地址为d，则第4次计算的散列地址为（）

A:(d+4)％m

B:(d+l)％m

C:(d--4)％m

D:(d--1)％m

答案:(d+4)％m

若在线性表中采用折半查找法查找元素，该线性表应该（）

A:采用顺序存储结构

B:元素按值有序，且采用链式存储结构

C:元素按值有序

D:元素按值有序，且采用顺序存储结构

答案:元素按值有序，且采用顺序存储结构

下面关于二叉排序树论述中，错误的是（）

A:当所有结点的权值都相等时，用这些结点构造的二叉排序树除根结点外只有右子树

B:中序遍历二叉排序树的结点就可以得到排好序的结点序列

C:对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列是一样的

D:任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间

答案:任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间

在一棵平衡二叉树中，每个结点的平衡因子取值范围是（）

A:-2～2

B:-1～l

C:0～l

D:1～2

答案:-1～l

设Hash表长m=14，哈希函数H(key)=key％11。表中已有4个结点，地址分别为：addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7，其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点地址是（）。

A:3

B:8

C:5

D:9

答案:9

在顺序表(n足够大)中进行顺序查找，其查找不成功的平均长度是（）

A:+1

B:(n+1)／2

C:n+1

D:n

答案:n+1

在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较（）个结点。

A:n

B:(n-1)/2

C:n／2

D:(n+l)/2

答案:(n+l)/2

第九章测试

有一小根堆，堆中任意结点的关键字均小于它的左、右孩子关键字。则其具有最大值的结点一定是一个叶结点并可能在堆的最后两层中。（）

A:对B:错

答案:对

堆