数据结构与算法知到智慧树章节测试课后答案2024年秋长安大学

数据结构与算法知到智慧树章节测试课后答案2024年秋长安大学第一章单元测试

以下可以用于定义一个完整的数据结构的是（）。

A:数据元素

B:数据关系

C:抽象数据类型

D:数据对象

答案:抽象数据类型

以下关于数据结构的说法中，正确的是（）。

A:数据的逻辑结构唯一决定了其存储结构

B:数据结构仅由其逻辑结构和存储结构决定

C:数据的逻辑结构独立于其存储结构

D:数据的存储结构独立于其逻辑结构

答案:数据的逻辑结构独立于其存储结构

计算算法的时间复杂度是属于一种（）。

A:事前分析估算的方法

B:事后统计的方法

C:事后分析估算的方法

D:事前统计的方法

答案:事前分析估算的方法

算法的时间复杂度主要取决于（）。

A:数据的类型

B:待处理数据的值

C:问题的规模

D:计算的环境

答案:问题的规模

intsuanfa(intn){

inti=1,s=1;

while(s＜n)s+=++I;

returni;

}

上面算法的时间复杂度是O()。（）

A:对B:错

答案:对

第二章单元测试

线性表L=(a1,a2,……,an)，下列说法正确的是（）。

A:每个元素都有一个直接前驱和一个直接后继

B:表中诸元素的排列顺序必须是由小到大或由大到小

C:线性表中至少要有一个元素

D:除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

答案:除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继

在长度为n的顺序表中删除第i(1≤i≤n)个元素时，需向前移动（）个元素。

A:n-i+1

B:n

C:n-i

D:i-1

答案:n-i

如果线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A:仅有尾指针的单循环链表

B:仅有头指针的单循环链表

C:单链表

D:双链表

答案:仅有尾指针的单循环链表

在一个单链表中，若删除p所指向结点的后续结点，则所需修改指针的操作为（）。

A:p=p-＞next;

B:p-＞next=p-＞next-＞next;

C:p=p-＞next-＞next;

D:p=p-＞next;p-＞next=p-＞next-＞next;

答案:p-＞next=p-＞next-＞next;

设线性表有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的（）。

A:顺序输出前k个元素

B:交换第i个元素和第2n-i-1个元素(i=,1,…,n-1)

C:在最后一个元素的后面插入一个新元素

D:删除指定元素

答案:删除指定元素

第三章单元测试

栈是（）。

A:链式存储的线性结构

B:限制存取点的线性结构

C:顺序存储的线性结构

D:限制存取点的非线性结构

答案:限制存取点的线性结构

一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（）。

A:d,e,c,b,a

B:a,b,c,d,e

C:d,c,e,a,b

D:e,d,c,b,a

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

判断一个循环队列Q（最多n个元素）为满的条件是（）。

A:Q-＞rear==Q-＞front

B:Q-＞front==(Q-＞rear-1)%n

C:Q-＞front==(Q-＞rear+1)%n

D:Q-＞rear==Q-＞front+1

答案:Q-＞front==(Q-＞rear+1)%n

在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（）。

A:s-＞next=front;front=s;

B:s-＞next=rear;rear=s;

C:rear-＞next=s;rear=s;

D:front=front-＞next;

答案:rear-＞next=s;rear=s;

在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（）结构。

A:堆栈

B:队列

C:线性表

D:数组

答案:队列

第四章单元测试

与线性表相比，串的插入和删除操作的特点是（）。

A:算法的时间复杂度较高

B:需要更多的辅助空间

C:涉及移动的元素更多

D:通常以串整体作为操作对象

答案:通常以串整体作为操作对象

设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。

A:O(n)

B:O(m*n)

C:O(nlog2m)

D:O(m)

答案:O(m)

数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（）。

A:1205

B:1175

C:1210

D:1180

答案:1175

对一些特殊矩阵采用压缩存储的目的主要是为了（）。

A:对矩阵元素的存取变得简单

B:去掉矩阵中的多余元素

C:减少不必要的存储空间的开销

D:表达变得简单

答案:减少不必要的存储空间的开销

稀疏矩阵的三元组存储方法（）。

A:实现转置运算很简单，只需将每个三元组的行标和列标交换

B:矩阵的非零元个数和位置在操作过程中变化不大时较有效

C:是一种链式存储方法

D:比十字链表法更高效

答案:矩阵的非零元个数和位置在操作过程中变化不大时较有效

第五章单元测试

设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。

A:decab

B:abcde

C:debac

D:adbce

答案:abcde

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序不发生改变。（）。

A:错B:对

答案:对在下列情况中，可称为二叉树的是（）。

A:哈夫曼树

B:每个结点至多有两棵子树的树

C:每个结点只有一棵子树

D:每个结点至多有两棵子树的有序树

答案:哈夫曼树

树的先根序列等同于与该树对应的二叉树的（）。

A:层序序列

B:中序序列

C:先序序列

D:后序序列

答案:先序序列

由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A:51

B:53

C:74

D:23

答案:51

第六章单元测试

已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。

A:将邻接矩阵的第i行删除

B:将邻接矩阵的第i列删除

C:将邻接矩阵的第i列元素全部置为0

D:将邻接矩阵的第i行元素全部置为0

答案:将邻接矩阵的第i行元素全部置为0

为便于判别有向图中是否存在回路，可借助于（）。

A:最小生成树算法

B:最短路径算法

C:拓扑排序算法

D:广度优先搜索算法

答案:拓扑排序算法

已知一个有向图的邻接表存储结构如图所示，根据深度优先遍历算法，从顶点v1出发，所得到的顶点序列是：v1,v3,v4,v5,v2。（）

A:对B:错

答案:对任何一个无向连通网的最小生成树（）。

A:只有一棵

B:一定有多棵

C:有一棵或多棵

D:可能不存在

答案:有一棵或多棵

使用迪杰斯特拉算法求下图中从顶点1到其他各顶点的最短路径，依次得到最短路径的目标顶点是2,3,5,6,4。（）

A:对B:错

答案:对

第七章单元测试

折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A:30，88，50

B:20，70，30，50

C:20，50

D:30，88，70，50

答案:20，70，30，50

链表适用于（）查找

A:顺序

B:随机

C:二分法

D:顺序，也能二分法

答案:顺序

在上图所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字38所在的结点左、右子结点中保存的关键字分别是24,48。（）

A:对B:错

答案:对分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

A:(100,80,60,90,120,130,110)

B:(100,120,110,130,80,60,90)

C:(100,80,90,60,120,110,130)

D:(100,60,80,90,120,110,130)

答案:(100,60,80,90,120,110,130)

哈希表构建时采用线性探测法处理冲突，在某关键字查找成功的情况下，所探测的多个位置上的关键字（）。

A:一定都不是同义词

B:必然有序

C:一定是同义词

D:不一定都是同义词

答案:不一定都是同义词

第八章单元测试

快速排序在下列哪种情况下最易发挥其长处（）。

A:被排序的数据中含有多个相同排序码

B:被排序的数据已基本有序

C:被排序的数据完全无序

D:被排序的数据中的最大值和最小值相差悬殊

答案:被排序的数据完全无序

若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（）。

A:84,56,79,40,46,38

B:84,79,56,46,40,38

C:84,79,56,38,40,46

D:79,46,56,38,40,84

答案:84,79,56,38,40,46

希尔排序的组内排序采用的是（）。

A:折半插入排序

B:直接插入排序

C:归并排序

D:快速排序

答案