数据结构与算法基础知到智慧树章节测试课后答案2024年秋潍坊学院

数据结构与算法基础知到智慧树章节测试课后答案2024年秋潍坊学院第一章单元测试

数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。（）

A:错B:对

答案:对数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。（）

A:错B:对

答案:错抽象数据类型与计算机内部表示和实现无关。（）

A:对B:错

答案:对算法分析的两个主要方面是时间复杂度和空间复杂度的分析。（）

A:对B:错

答案:对，

对应的算法时间复杂度相同。（）

A:错B:对

答案:对算法的时间复杂度取决于（）

A:A和BB:待处理数据的初态C:问题的规模

答案:A和B数据逻辑结构可以分为（）。

A:集合结构、线性结构、树结构和图结构B:线性结构和图结构C:集合结构和非线性结构D:顺序结构和链式结构

答案:集合结构、线性结构、树结构和图结构在数据结构中，与所使用的计算机无关的是数据的（）结构。

A:存储B:逻辑和存储C:逻辑D:物理

答案:逻辑在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。

A:数据的处理方法B:数据元素之间的关系C:数据元素的类型D:数据的存储方法

答案:数据元素之间的关系数据结构在计算机中的表示称为数据的（）。

A:逻辑结构B:抽象数据类型C:存储结构D:顺序结构

答案:存储结构

第二章单元测试

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。（）

A:对B:错

答案:对在顺序表中，逻辑上相邻的元素，其物理位置必定相邻。（）

A:错B:对

答案:对线性表的插入、删除总是伴随着大量数据的移动。（）

A:错B:对

答案:错带头结点的循环单链表中，任一结点的后继结点的指针域均不空。（）

A:对B:错

答案:对线性表采用链式存储结构时，各个数据元素的存储单元地址一定是不连续的。（）

A:对B:错

答案:错线性表L=(a1​，a2​，…，an​)，下列说法正确的是（）

A:除第一个和最后一个元素外，其他元素都有且仅有一个直接前驱和一个直接后继B:表中至少有一个元素C:表中元素需有序D:每个元素都有一个直接前驱和一个直接后继

答案:除第一个和最后一个元素外，其他元素都有且仅有一个直接前驱和一个直接后继在n个数据元素的顺序表中，算法时间复杂度为O(1)的操作是（）

(1)访问第i个结点（1≤i≤n）

(2)求第i个结点的直接前驱（2≤i≤n）

(3)求第i个结点的直接后继（1≤i≤n-1）

(4)在第i个结点后插入一个新结点（1≤i≤n）

(5)删除第i个结点（1≤i≤n）

(6)排序

A:(6)B:(1)(2)(3)(4)(5)C:(4)(5)D:(1)(2)(3)

答案:(1)(2)(3)假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是（）

A:head!=NULLB:head->next==headC:head->next==NULLD:head==NULL

答案:head->next==NULL创建一个包括n个结点的单链表的时间复杂度是（）

A:O(n2)B:O(n)C:O(1)D:O(log2​n)

答案:O(n)在单链表中，指针域为next，要将q所指结点链接到p所指结点之后，其语句序列应为（）

A:q->next=p->next;p->next=q;B:q->next=p+1;p->next=q;C:p->next=q;q->next=p;D:p->next=q;q->next=p->next;

答案:q->next=p->next;p->next=q;

第三章单元测试

栈顶元素和栈底元素有可能是冋一个元素。（）

A:错B:对

答案:对链栈和顺序栈相比，比较明显的优点是通常不会出现栈满的情况。（）

A:错B:对

答案:对在用数组表示的循环队列中，front值一定小于等于rear值。（）

A:错B:对

答案:错栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。（）

A:对B:错

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

A:图B:栈C:队列D:树

答案:队列栈在（）中有所应用。

A:递归调用B:前三个选项都有C:函数调用D:表达式求值

答案:前三个选项都有循环队列的引入，目的是为了克服（）。

A:真溢出问题B:假溢出问题C:操作不方便D:空间不够用

答案:假溢出问题若用一个大小为6的数值来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。

A:1和5B:2和4C:5和1D:4和2

答案:2和4若元素1、2、3、4、5依次入栈，则出栈次序不可能为（）。

A:2,1,3,5,4B:3,5,4,2,1C:4,3,2,5,1D:1,5,3,4,2

答案:1,5,3,4,2

第四章单元测试

广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。（）

A:错B:对

答案:对已知二维数组A[0..5][0..7]（行下标为0到5，列下标为0到7），每个元素占用2个字节存储，存储器按字节编址，若A[0][0]的地址为2000，则按行优先存储时元素A[3][4]的地址是2056。（）

A:对B:错

答案:对广义表A=（（a），a）的表头是（）。

A:(a)B:((a))C:()D:a

答案:(a)对广义表，通常采用的存储结构是（）。

A:链表B:数组C:三元组D:Hash表

答案:链表已知二维数组A[0..4][0..5]，则A按行优先存储时元素A[3][5]的地址与A按列优先存储时元素（）的地址相同。

A:A[3][5]B:A[2][4]C:A[3][4]D:A[4][3]

答案:A[3][4]已知二维数组A[0..7][0..9]（行下标为0到7，列下标为0到9），数组的每个元素长度为3字节，数据元素A[0][0]的内存首地址为100，当采用列主序存放时，元素A[4][7]的存储首地址为（）

A:241B:322C:325D:280

答案:280在一个二维数组A中，假设每个数组元素的长度为3个存储单元，行下标为0~8,列下标为0~9，从首地址SA开始连续存放。则按行优先存储时，元素A[8][5]的起始地址为（）

A:SA+141B:SA+222C:SA+144D:SA+255

答案:SA+255广义表((a,b),c,d,e)的表头和表尾分别是

A:(a,b)和eB:

(a,b)和(c,d,e)C:a和eD:a和(c,d,e)

答案:

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

第五章单元测试

在含有n个结点的树中，分支数只能是n-1条。（）

A:对B:错

答案:对一棵有124个结点的完全二叉树，其叶结点个数是确定的。（）

A:对B:错

答案:对在任意一棵二叉树中，分支结点的数目一定少于叶结点的数目。（）

A:对B:错

答案:错哈夫曼树中一定没有度为1的结点。（）

A:错B:对

答案:对一棵非空二叉树，若先序遍历与后序遍历的序列相反，则该二叉树（）。

A:为任意二叉树B:只有一个叶子结点C:所有结点均无左孩子D:所有结点均无右孩子

答案:只有一个叶子结点树最适合用来表示（）。

A:元素之间无联系的数据B:元素之间具有分支层次关系的数据C:无序数据元素D:有序数据元素

答案:元素之间具有分支层次关系的数据深度为5的二叉树至多有（）个节点。

A:31B:32C:16D:10

答案:31设某棵二叉树的中序遍历序列为DBEAC，先序遍历序列为ABDEC，则该二叉树的后序遍历序列是（）。

A:CFDBAB:DBFACC:DBEACD:DEBCA

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

A:30B:60C:90D:69

答案:69

第六章单元测试

有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。（）

A:错B:对

答案:对无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）

A:错B:对

答案:错邻接表法只能用于有向图的存储，邻接矩阵法对于有向图和无向图的存储都适用。（）

A:对B:错

答案:错连通分量是无向图中的极小连通子图。（）

A:错B:对

答案:错对下图进行广度优先遍历，得到的序列不可能为（）。

A:AFEBCDB:CDFBAEC:DCEFBAD:BCFADE

答案:CDFBAE使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：（）

A:5,2,6,3,4,7B:2,3,4,5,6,7C:2,4,3,6,5,7D:2,5,3,4,6,7

答案:2,4,3,6,5,7已知无向图G如下所示，使用克鲁斯卡尔（Kruskal）算法求图G的最小生成树，加入到最小生成树中的边依次是：（）

A:(a,e),(b,e),(c,e),(b,d),(b,f)B:(b,f),(b,d),(a,e),(c,e),(b,e)C:(a,e),(c,e),(b,e),(b,f),(b,d)D:(b,f),(b,d),(b,e),(a,e),(c,e)

答案:(b,f),(b,d),(a,e),(c,e),(b,e)在下图中，自a点开始进行深度优先遍历算法可能得到的结果为

A:a,e,d,f,c,bB:a,c,f,e,b,d

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

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

第七章单元测试

当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。

A:取决于表递增还是递减B:不一定C:必定快D:在大部分情况下要快

答案:在大部分情况下要快在有N个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为：（）

A:O(Nlog2N)B:O(N)C:O(N2)D:O(log2N)

答案:O(log2N)若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

A:n/2B:(n+1)/2C:(n-1)/2D:n

答案:(n+1)/2适用于折半查找的表的存储方式及元素排列要求为（）。

A:顺序方式存储，元素有序B:顺序方式存储，元素无序C:链接方式存储，元素无序D:链接方式存储，元素有序

答案:顺序方式存储，元素有序将{3,8,9,1,2,6}依次插入初始为空的二叉排序树。则该树的后序遍历结果是：（）

A:1,2,8,6,9,3B:2,1,6,9,8,3C:1,2,3,6,9,8D:2,1,3,6,9,8

答案:2,1,6,9,8,3设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18，59}依次存储到散列表中。元素59存放在散列表中的地址是：（）

A:9B:11C:8D:10

答案:11设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为H(key)=key%17，采用线性探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为（）。

A:1.17B:1.25C:1.33D:0.33

答案:1.33设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为H(key)=key%17，采用二次探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为（）。

A:0.33B:1.25C:1.33D:1.17

答案:1.25

第八章单元测试

插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。（）

A:错B:对

答案:错对N个记录进行简单选择排序，比较次数和移动次数分别为O(N2)和O(N)。（）

A:对B:错

答案:对要从50个键值中找出最大的3个值，简单选择排序比堆排序快。（）

A:对B:错

答案:对对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(Nlog2N)。（）

A:对B:错

答案:错基数排序只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（）

A:错B:对

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

A:快速排序B:直接插入排序C:折半插入排序D:归并排序

答案:直接插入排序下述几种排序方法中，（）是稳定的排序方法。

A:希尔排序B:堆排序C:快速排序D:归并排序

答案:归并排序用某种排序