数据结构智慧树知到课后章节答案2023年下广州大学

数据结构智慧树知到课后章节答案2023年下广州大学广州大学

第一章测试

与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A:存储结构B:存储实现C:逻辑结构D:运算实现

答案:逻辑结构

说法正确的是（）。

A:数据结构是带有结构的各数据项的集合B:一些表面上很不相同的数据可以有相同的逻辑结构C:数据项是数据的基本单位D:数据元素是数据的最小单位

答案:一些表面上很不相同的数据可以有相同的逻辑结构

在这些数据结构中，（）是非线性数据结构

A:栈B:队列C:字符串D:树

答案:树

在数据结构中，数据的基本单位是（）。

A:数据变量B:数据元素C:数据类型D:数据项

答案:数据元素

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

A:事后统计的方法B:事前分析估算的方法C:事前统计的方法D:事后分析估算的方法

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

数据元素之间的关系称为（）

A:数据对象B:结构C:操作D:数据集合

答案:结构

在下列算法中，“x=x*2”的执行次数是（）

intsuanfal(intn){

inti,j,x=1;for(i=0;i<n;i++)for(j=i;j<n;j++)x=x*2;

returnx;}

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

答案:n(n+1)/2

求整数n（n≥0）阶乘的算法如下，其时间复杂度是（）

intfact(intn){

if(n<=1)return1;return

n×fact(n-1);}

A:O(n2)B:O(nlog2n)C:O(log2n)D:O(n)

答案:O(n)

数据元素可以由类型互不相同的数据项构成。（）

A:错B:对

答案:对

在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）

A:错B:对

答案:错

算法可以没有输人，但是必须有输出。（）

A:对B:错

答案:对

第二章测试

线性表是一个（）

A:无限序列，可以为空B:有限序列，可以为空C:有限序列，不能为空D:无限序列，不能为空

答案:有限序列，可以为空

能在O(1)时间内访问线性表的第i个元素的结构是（）。

A:顺序表B:单链表C:单向循环链表D:双向链表

答案:顺序表

线性表是具有n（n>0）个（）的有限序列。

A:字符B:数据元素C:表元素D:数据项

答案:数据元素

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

A:顺序表B:单循环链表C:双链表D:带头结点的双循环链表

答案:顺序表

线性表（a1，a2，…，an）以链接方式存储时，访问第i个位置元素的时间复杂性为（）。

A:O(n)B:O(i)C:O(i-1)D:О(1)

答案:O(n)

将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）

A:O(n)B:O(1)C:O(m+n)D:О(m)

答案:О(m)

链表具有的特点是（）。

A:不必事先估计存储空间B:插入、删除不需要移动元素C:所需空间与线性长度成正比D:可随机访问任一元素

答案:不必事先估计存储空间;插入、删除不需要移动元素;所需空间与线性长度成正比

已知L是有头结点的非空单链表，则要在P结点前插入S结点的语句序列是（）

A:S->next=Q->next;B:P->next=Q->next;C:Q=L;D:Q->next=S;E:P=Q;F:while(Q->next!=P)Q=Q->next;G:Q=P;H:P->next=S->next;I:deleteQ;

答案:S->next=Q->next;;Q=L;;Q->next=S;;while(Q->next!=P)Q=Q->next;

下面代码是实现尾插法创建单链表L的过程，请选择合适的语句，将代码补充完整。（）

voidCreatList_R(LinkList&L,intn){

L=newLNode;

L->next=NULL;

①

for(inti=0;i<n;i++){

LNode*p=newLNode;

cin>>p->data;

②

r=p;

}}

A:p->next=NULL;r->next=p;B:LNode*r=L->next;C:LNode*r=L;D:LNode*p=NULL;E:r->next=NULL;p->next=r;

答案:p->next=NULL;r->next=p;;LNode*r=L;

线性表的逻辑顺序与物理顺序总是一致的。（）

A:错B:对

答案:错

线性表的插入和删除操作总是伴随着大量数据的移动。（）

A:对B:错

答案:错

在顺序表中取出第i个元素所花费的时间与i成正比。（）

A:对B:错

答案:错

线性表采用链式存储表示时，所有结点之间的存储单元地址可连续可不连续。（）

A:错B:对

答案:对

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

A:对B:错

答案:错

在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（）

A:错B:对

答案:错

在一个具有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）

A:错B:对

答案:错

第三章测试

数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A:(n+f-r)%nB:r-fC:（n+r-f)%nD:n+r-f

答案:（n+r-f)%n

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

A:线性表B:有序表C:栈D:队列

答案:队列

用链接方式存储的队列，在进行删除运算时（）。

A:仅修改头指针B:头、尾指针都要修改C:头、尾指针可能都要修改D:仅修改尾指针

答案:头、尾指针可能都要修改

同一组不重复输入序列，执行不同的入、出站组合操作，所得结果也可能相同。（）

A:对B:错

答案:对

若某堆栈初始为空，push与pop分别表示对栈进行一次进栈与出栈操作，那么，对于输入序列A、B、C、D、E经过pushpushpoppushpoppushpush以后，输出序列中有元素（）。

A:DB:AC:BD:CE:E

答案:B;C

下面代码实现的是一个顺序栈S的出栈操作，请选择合适的语句将代码补充完整。（）

boolPop(SqStack&S,ElemType&e){

if(

①

)return0;

②

return1;}

A:S.top==NULL;B:

S.top--;e=*S.top;C:e=*S.top;S.top--;D:S.top==S.base;E:S.base==NULL;

答案:

S.top--;e=*S.top;;S.top==S.base;

下面代码实现的是一个循环队列Q的出队操作，请选择合适的语句将代码补充完整。（）boolDeQueue(SqQueue&Q,ElemType&e){

if(

①

)return0;

e=Q.base[②];

③

return

1;}

A:Q.front=(Q.front+1)%MAXSIZE;B:Q.rear=(Q.rear+1)%MAXSIZE;C:Q.front;D:Q.front+1;E:Q.front==Q.rear;

答案:Q.front=(Q.front+1)%MAXSIZE;;Q.front;;Q.front==Q.rear;

第四章测试

由3个结点可以构造出多少种不同的二叉树？（）

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

答案:5

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

A:10至1024之间B:10C:11至1025之间D:11

答案:11至1025之间

利用二叉链表存储树，则根结点的右指针是（）。

A:指向最左孩子B:空C:非空D:指向最右孩子

答案:空

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

A:树中两个权值最小的结点一定是兄弟结点B:该树一定是一棵完全二叉树C:树中一定没有度为1的结点D:树中任一非叶结点的权值一定不小于下一层任一结点的权值

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

下列判断中，（）是正确的。

A:对二叉树遍历是指先序、中序或后序遍历中的一种B:深度为k的二叉树最多有2k-1个结点（k≥1），最少有k个结点C:二叉树中不存在度大于2的结点D:构造线索二叉树是为能方便找到每个结点的双亲

答案:深度为k的二叉树最多有2k-1个结点（k≥1），最少有k个结点;二叉树中不存在度大于2的结点

根据（）可以唯一地确定一棵二叉树。

A:中序遍历和后序遍历B:中序遍历C:先序遍历和后序遍历D:先序遍历和中序次遍历

答案:中序遍历和后序遍历;先序遍历和中序次遍历

下面代码是中序遍历二叉树的非递归算法，请选择合适的语句将代码补充完整。（）

A:q=q->rchild;B:p=p->lchild;C:p=p->rchild;D:q=q->lchild;

答案:q=q->rchild;;p=p->lchild;

二叉树只能采用二叉链表来存储。（）

A:对B:错

答案:错

二叉树是度为2的有序树。（）

A:对B:错

答案:错

对一棵有n个结点的二叉树，从上到下、从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i（2i<n），右儿子是2i+1（2i+1<n）。（）

A:对B:错

答案:错

用二叉树的前序遍历序列和中序遍历序列可以求出二叉树的后序序列序列。（）

A:错B:对

答案:对

哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根结点较近。（）

A:对B:错

答案:对

第五章测试

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

A:1B:1/2C:2D:4

答案:2

下面（）算法适合构造一个稠密图G的最小生成树。

A:Dijkstra算法B:Floyd算法C:Prim算法D:Kruskal算法

答案:Prim算法

广度优先遍历类似于二叉树的（）。

A:后序遍历B:中序遍历C:先序遍历D:层次遍历

答案:层次遍历

已知图的邻接矩阵如图所示，则从顶点v0出发按深度优先遍历的结果是（）。

A:0361542B:0134256C:0243156D:0136542

答案:0134256

下面（）方法可以判断出一个有向图是否有环。

A:拓扑排序B:求关键路径C:求最短路径D:深度优先遍历

答案:拓扑排序

n个结点的无向图，若不允许结点到自身的边，也不允许结点到结点的多重边，且边的总数为n（n-1）/2，则该无向图一定是连通图。（）

A:错B:对

答案:对

n个结点的有向图，若它有n（n-1)条边，则它一定是强连通的。（）

A:对B:错

答案:对

无向图中任何一个边数最少且连通所有顶点的子图都是该无向图的生成树。（）

A:对B:错

答案:对

图g的顶点v的入度等于其邻接矩阵中第v列中的1的个数。（）

A:错B:对

答案:对

用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）

A:错B:对

答案:对

有e条边的无向图在邻接表中有e个结点。（）

A:对B:错

答案:错

任何无向图都存在生成树。（）

A:对B:错

答案:错

不同的求最小生成树的方法最后得到的生成树是相同的。（）

A:错B:对

答案:错

一个带权的无向连通图的最小生成树的权值之和是唯一的。（）

A:对B:错

答案:对

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

A:对B:错

答案:对

对于任意一个图，从它的某个顶点进行一次先深或先广搜索可以访问到该图的每个顶点。（）

A:对B:错

答案:错

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环。（）

A:错B:对

答案:对

如果有向图的拓扑排序序列是唯一的，则图中必定只有一个顶点的入度为0，一个顶点的出度为0。（）

A:错B:对

答案:对

具有n个顶点和e条边的无向图，若用邻接矩阵作为存储结构，则求任意顶点的度数的时间复杂度为O(e)。（）

A:错B:对

答案:错

广度优先搜索遍历图的时间复杂度和深度优先搜索遍历的相同。（）

A:对B:错

答案:对

在拓扑序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。（）

A:错B:对

答案:错

有向图如下图所示，该图的深度优先遍历序列是（）。

A:15432B:12345C:13254D:12543

答案:15432;13254;12543

下列关于最小生成树的叙述中，不正确的是（）。

A:所有权值最小的边一定会出现在最小生成树中B:使用Prim算法从不同顶点开始得到的最小生成树一定相同C:使用Prim算法和Kruskas算法得到的最小生成树总不相同。D:最小生成树的代价唯一

答案:所有权值最小的边一定会出现在最小生成树中;使用Prim算法从不同顶点开始得到的最小生成树一定相同;使用Prim算法和Kruskas算法得到的最小生成树总不相同。

无向图如下图所示，在求该图的最小生成树时，可能是Kruskal算法第二次选中的边，也可能是Prim算法，从4号顶点开始，第二次选中的边是（）。

A:(1,4)B:(2,3)C:(1,3)D:(3,4)

答案:(1,3);(3,4)

下面哪些方法可以用来判断一个有向图中是否有环存在。（）

A:拓扑排序B:求最短路径算法C:深度优先遍历D:广度优先遍历

答案:拓扑排序;深度优先遍历

第六章测试

衡量查找算法效率的主要标准是（）。

A:算法难易程度B:所需的存储量C:平均查找长度D:元素个数

答案:平均查找长度

对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

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

答案:(n+1)/2

已知8个元素为{34,76,45,18,26,54,92,65}，按照依次有序插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（）。

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

答案:2

顺序查找法，表中元素可以任意存放。（）

A:对B:错

答案:对

折半查找法要求待查表的关键字值必须有序。（）

A:错B:对

答案:对

在有序的顺序表和有序的链表上，均可以采用折半查找法来提高查找速度。（）

A:错B:对

答案:错

对一棵二叉排序树，按先序方法进行遍历，得出的结点序列是从小到大的排序序列。（）

A:错B:对

答案:错

在二叉排序树中插入一个新结点总是插入到叶结点的下面。（）

A:对B:错

答案:错

在二叉排序树中，根结点的值都小于孩子结点的值。（）

A:错B:对

答案:错

利用二叉排序树进行查找时，若关键字的值比根结点的值小，则继续在左子树中查找。（）

A:错B:对

答案:对

在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。（）

A:对B:错

答案:错

对于一个堆，按照二叉树的层次遍历，可以得到一个有序序列。（）

A:对B:错

答案:错

下面针对折半查找算法，说法正确的是（）

A:在折半查找算法对应的二叉判定树中，结点的值是查找表中数据元素的关键字。B:当给定的关键字与mid位置处的关键字相等时，说明查找成功。C:折半查找不适用于数据元素经常变动的线性表。D:当给定的关键字与mid位置处的关键字不相等时，说明查找失败。

答案:当给定的关键字与mid位置处的关键字相等时，说明查找成功。;折半查找不适用于数据元素经常变动的线性表。

下列选项中，能构成折半查找中关键字比较序列的是（）。

A:500,450,200.180B:500,200,450,180C:180,500,200,450D:180,200,500,450

答案:500,450,200.180;180,500,200,450;180,200,500,450

对于下列关键字序列，可能构成某二叉排序树中一条查找路径的序列是（）。

A:92,20,91,34,88,35B:21,89,77,29,36,38C:95,22,91,24,94,71D:12,25,71,68,33,34

答案:92,20,91,34,88,35;21,89,77,29,36,38;12,25,71,68,33,34

下面代码是折半查找的递归算法，请为①②位置处选择合适的语句。（）

A:midB:r[mid].key>kC:highD:lowE:r[mid].key<k

答案:mid;r[mid].key>k

第七章测试

评价排序算法好坏的标准主要是（）。

A:执行时间和所需的辅助空间B:执行时间C:辅助空间D:算法本身的复杂度

答案:执行时间和所需的辅助空间

内排序是指在排序的整个过程中，全部数据都在计算机的（）中完成的排序。

A:内存B:寄存器C:外存D:内存和外存

答案:内存

直接插入排序的方法是从第（）个元素开始，插入到前边适当位置的排序方法。

A:nB:1C:3D:2

答案:2

按排序策略分类，冒泡排序属于（）。

A:选择排序B:插入排序C:交换排序D:分配排序

答案:交换排序

用直接插入排序法对下面的4个序列进行由小到大的排序，元素比较次数最少的是（）。

A:21，32，46，40，80，69，90，94B:94，32，40，90，80，46，21，69C:32，40，21，46，69，94，90，80D:90，69，80，46，21，32，94，40

答案:21，32，46，40，80，69，90，94

从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。

A:快速排序B:插入排序C:冒泡排序D:选择排序

答案:插入排序

从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。

A:快速排序B:插入排序C:冒泡排序D:选择排序

答案:选择排序

对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

A:元素基本有序B:从大到小排列好的C:元素无序D:从小到大排列好的

答案:从大到小排列好的

对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。

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

答案:n(n-1)/2

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

A:被排序的数据已基本有序B:被排序的数据中含有多个相同排序码C:被排序的数据中的最大值和最小值相差悬殊D:被排序的数据完全无序

答案:被排序的数据已基本有序

对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

A:O(n2)B:O(n)C:O(nlog2n)D:O(n3)

答案:O(n2)

若一组记录的排序码为{46,79，56，38，40，84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A:40，38，46，79，56，84B:38，40，46，56，79，84C:40，38，46，84，56，79D:40，38，46，56，79，84

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

下列关键字序列中，（）是堆。

A:94，23，31，72，16，53B:16，23，53，31，94，72C:16，72，31，23，94，53D:16，53，23，94，31，72

答案:16，23，53，31，94，72

堆是一种（）排序。

A:交换B:插入C:归并D:选择

答案:选择

堆的形状是一棵（）。

A:平衡二叉树B:满二叉树C:二叉排序树D:完全二叉树

答案:完全二叉树

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

A:84，79，56，46，40，38B:84，79，56，38，40，46C:79，46，56，38，40，84D:84，56，79，40，46，38

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

下述几种排序方法中，（）是稳定的排序方法。

A:冒泡排序B:堆排序C:快速排序D:简单选择排序

答案:冒泡排序

数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（）算法最节省时间。

A:堆排序B:快速排序C:冒泡排序D:简单选择排序

答案:堆