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

数据结构（A）知到章节测试答案智慧树2023年最新山东理工大学第一章测试

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

参考答案:

错

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

参考答案:

错

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

参考答案:

错

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

参考答案:

错

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

参考答案:

数据元素之间逻辑

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

参考答案:

4

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

参考答案:

集合

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

参考答案:

线性结构、非线性结构

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

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

参考答案:

O(n)

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

参考答案:

O(1)

第二章测试

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

参考答案:

错

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

参考答案:

错

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

参考答案:

错

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

参考答案:

对

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

参考答案:

head-＞next==NULL

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

参考答案:

1

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

参考答案:

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

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

参考答案:

p-＞next=h

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

参考答案:

q-＞next==p

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

参考答案:

带头结点的双循环链表

第三章测试

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

参考答案:

对

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

参考答案:

对

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

参考答案:

错

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

参考答案:

对

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

参考答案:

d,c，a，b

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

参考答案:

终止条件和递归部分

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

参考答案:

ABCD／+E*

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

参考答案:

2和4

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

参考答案:

栈

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

参考答案:

1

第四章测试

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

参考答案:

对

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

参考答案:

对

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

参考答案:

错

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

参考答案:

对

已知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’。（）

参考答案:

对

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

参考答案:

对

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

参考答案:

对

串又称字符串，（）。

参考答案:

串中元素只能是字符

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

参考答案:

01112231123456712

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

参考答案:

01102131011021701

第五章测试

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

参考答案:

查找和修改

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

参考答案:

三元组和十字链表

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

参考答案:

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

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

参考答案:

(i+3)i/2

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

参考答案:

240

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

参考答案:

50

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

参考答案:

head(tail(head(tail(LS)))

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

参考答案:

（a,b,c,d）

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

参考答案:

1和2

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

参考答案:

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

第六章测试

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

参考答案:

n-1

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

参考答案:

树的高度至多是n-3

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

参考答案:

5

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

参考答案:

11~1025

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

参考答案:

2k-1

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

后序序列中，()。

参考答案:

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

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

参考答案:

3,2,4,1

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

参考答案:

d

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

参考答案:

b,a

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

参考答案:

14

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

参考答案:

X的左子树中最右叶结点

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

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

参考答案:

m-n

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

参考答案:

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

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

参考答案:

10

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

参考答案:

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

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

参考答案:

如图C

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

参考答案:

58

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

参考答案:

中序遍历

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

参考答案:

M和N可能无公共祖先

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

参考答案:

3

第七章测试

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

参考答案:

错

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

参考答案:

对

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

参考答案:

对

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

参考答案:

23

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

参考答案:

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

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

参考答案:

无向图

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

参考答案:

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,e,d,f,c,b

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

参考答案:

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

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

参考答案:

O（n3）

第八章测试

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

参考答案:

对

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

参考答案:

对

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

参考答案:

错

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

参考答案:

对

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

参考答案:

对

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

参考答案:

对

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

参考答案:

(d+4)％m

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

参考答案:

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

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

参考答案:

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

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

参考答案:

-1～l

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

参考答案:

9

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

参考答案:

n+1

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

参考答案:

(n+l)/2

第九章测试

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

参考答案:

对

堆排序所需时间与待排序记录的个数无关。（）

参考答案:

对

排序算法中的比较次数与初始元素序列的排列无关。（）

参考答案:

错

当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（）

参考答案:

错

堆排序是稳定的排序方法。（）

参考答案:

错

对于n个记录的集合进行快速排序，所需要的附加空间数是。（）

参考答案:

错

下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。

参考答案:

快速排序

下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。（）

参考答案:

插入排序

在下列排序算法中,哪一