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

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

A:抽象数据类型

B:数据对象

C:数据元素

D:数据关系

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

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

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

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

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

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

A:事后统计的方法

B:事前统计的方法

C:事前分析估算的方法

D:事后分析估算的方法

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

A:计算的环境

B:问题的规模

C:数据的类型

D:待处理数据的值

答案:Bintsuanfa(intn){inti=1,s=1;while(s＜n)s+=++I;returni;}上面算法的时间复杂度是O()。（）

A:对

B:错

答案:A第二章测试线性表L=(a1,a2,……,an)，下列说法正确的是（）。

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

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

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

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

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

A:n-i

B:n-i+1

C:n

D:i-1

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

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

B:单链表

C:双链表

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

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

A:p=p-＞next-＞next;

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

C:p=p-＞next;

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

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

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

B:顺序输出前k个元素

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

D:删除指定元素

答案:D第三章测试栈是（）。

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

B:顺序存储的线性结构

C:链式存储的线性结构

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

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

A:d,e,c,b,a

B:a,b,c,d,e

C:e,d,c,b,a

D:d,c,e,a,b

答案:D判断一个循环队列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

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

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

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

C:front=front-＞next;

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

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

A:队列

B:堆栈

C:数组

D:线性表

答案:A第四章测试与线性表相比，串的插入和删除操作的特点是（）。

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

B:涉及移动的元素更多

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

D:需要更多的辅助空间

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

A:O(m*n)

B:O(nlog2m)

C:O(n)

D:O(m)

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

A:1180

B:1210

C:1175

D:1205

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

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

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

C:表达变得简单

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

答案:B稀疏矩阵的三元组存储方法（）。

A:比十字链表法更高效

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

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

D:是一种链式存储方法

答案:B第五章测试设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。

A:adbce

B:abcde

C:debac

D:decab

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

A:对

B:错

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

A:哈夫曼树

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

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

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

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

A:层序序列

B:先序序列

C:后序序列

D:中序序列

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

A:51

B:74

C:53

D:23

答案:A第六章测试已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。

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

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

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

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

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

A:拓扑排序算法

B:最小生成树算法

C:广度优先搜索算法

D:最短路径算法

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

A:对

B:错

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

A:只有一棵

B:可能不存在

C:有一棵或多棵

D:一定有多棵

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

A:错

B:对

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

A:20，50

B:20，70，30，50

C:30，88，70，50

D:30，88，50

答案:B链表适用于（）查找

A:随机

B:顺序

C:顺序，也能二分法

D:二分法

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

A:对

B:错

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

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

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

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

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

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

A:一定都不是同义词

B:不一定都是同义词

C:必然有序

D:一定是同义词

答案:B第八章测试快速排序在下列哪种情况下最易发挥其长处（）。

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

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

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

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

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

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

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

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

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

答案:C希尔排序的组内排序采用的是（）。

A:快速排序

B:折半插入排序

C:归并排序

D:直接插入排序

答案:D