数据结构知到智慧树章节测试课后答案2024年秋临沂大学

数据结构知到智慧树章节测试课后答案2024年秋临沂大学第一章单元测试

下列叙述中正确的是（

）

A:程序可以作为算法的一种描述方法B:算法设计只需考虑得到计算结果C:算法设计可以忽略算法的运算时间D:所谓算法就是计算方法

答案:程序可以作为算法的一种描述方法数据的最小单位是数据项（

）

A:对B:错

答案:对在数据结构中，从逻辑上可以把数据结构分成（

）

A:内部结构和外部结构B:动态结构和静态结构C:线性结构和非线性结构D:紧凑结构和非紧凑结构

答案:线性结构和非线性结构与数据元素本身的形式、内容、相对位置、个数无关的是数据的（

）

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

答案:逻辑结构以下说法正确的是（

）

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

答案:一些表面上很不相同的数据可以有相同的逻辑结构下面代码段的时间复杂度是（）。

s=0;

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

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;

A:O(n)B:O(logn)C:O(1)D:O(

n²

)

答案:O(

n²

)下面代码段的时间复杂度是（）。

x=0;

for(i=1;i<n;i++)

for(j=1;j<=n-i;j++)

x++;

A:O(n)B:O(n³)

C:O(logn)D:O(n²)

答案:O(n²)

NlogN²和NlogN具有相同的增长速度。（

）

A:对B:错

答案:对N²logN²和NlogN²具有相同的增长速度。（

）

A:对B:错

答案:错斐波那契数列FN的定义为：F0=0，F1=1，FN=FN−1+FN−2，N=2,3,...。用递归函数计算FN的时间复杂度是O(N!)。

A:对B:错

答案:错

第二章单元测试

下面关于线性表的叙述中，错误的是哪一个（）

A:线性表采用顺序存储，必须占用一片连续的存储单元B:线性表采用顺序存储，便于进行插入和删除操作C:线性表采用链接存储，便于插入和删除操作D:线性表采用链接存储，不必占用一片连续的存储单元

答案:线性表采用顺序存储，便于进行插入和删除操作在具有n个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(n)？

A:删除开始结点B:在地址为p的结点之后插入一个结点C:删除地址为p的结点的后继结点D:遍历链表和求链表的第i个结点

答案:遍历链表和求链表的第i个结点链表不具有的特点是（）

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

答案:可随机访问任一个元素带头结点的单链表L为空的条件是（）

A:L->next->next==NULL;B:L->next==NULL;C:L->next==L;D:L==NULL;

答案:L->next==NULL;在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）

A:p->next=s->next;

p->next=s;B:p->next=s;

s->next=p->next;C:p->next=s;

p->next=s->next;D:s->next=p->next;

p->next=s;

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

p->next=s;在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）

A:O(

n²

)B:O(

1

)C:O(

logn

)D:O(

n

)

答案:O(

1

)单链表中，增加头结点的目的是为了()

A:说明单链表是线性表的链式存储实现B:标示表结点中首结点的位置C:方便运算的实现D:使单链表至少有一个结点

答案:方便运算的实现线性表的逻辑顺序与物理顺序总是一致的（）

A:对B:错

答案:错取线性表的第i个元素的时间同i的大小有关(

)

A:对B:错

答案:错线性表的长度是线性表所占用的存储空间的大小（）

A:对B:错

答案:错

第三章单元测试

设有六列火车，编号为1，2，3，4，5，6，顺序开进一个栈式结构的站台，问下列输出序列中，哪个是不可能出现的（

）。

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

答案:3,1,2,6,5,4栈和队列都是运算受限的线性表。（

）

A:错B:对

答案:对当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==1。（

）

A:对B:错

答案:错元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（

）。

A:4

B:6C:5

D:3

答案:4

已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（

）。

A:n-1,n-1B:n-1,0C:0,n-1D:0,0

答案:0,n-1数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（

）。

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

答案:(n+r-f)%n若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（

）。

A:V[top]=x;top++;B:top++;V[top]=x;C:top--;V[top]=x;D:V[top]=x;top--;

答案:top--;V[top]=x;设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（

）。

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

答案:3循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（

）。

A:队空：end1==end2；队满：end2==(end1+1)mod(M-1)B:队空：end1==(end2+1)；队满：end2==(end1+1)mod(M-1)C:队空：end2==(end1+1)modM；队满：end1==(end2+1)modMD:队空：end1==end2；队满：end1==(end2+1)modM

答案:队空：end1==end2；队满：end1==(end2+1)modM用链接方式存储的队列，在进行删除运算时（

）。

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

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

第四章单元测试

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

A:4B:2

C:5D:3

答案:2

一棵树高为K的完全二叉树至少有(

)个结点

A:B:C:D:

答案:将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下、从左到右顺序结点编号，那么编号为41的双亲结点编号为（

）

A:20B:40C:42D:21

答案:20对于有n个结点的二叉树,其高度为（）

A:B:C:D:不确定

答案:不确定给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是（）

A:LRNB:RLNC:RNLD:NRL

答案:RNL如果T2是由有序树T转化而来的二叉树，那么T中结点的先序就是T2中结点的（）

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

答案:先序下面几个符号串编码集合中，不是前缀编码的是（）

A:{0,10,110,1111}B:{11,10,001,101,0001}C:{00,010,0110,1000}

D:{b,c,aa,ac,aba,abb,abc}

答案:{11,10,001,101,0001}二叉树先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是（）

A:FB:HC:GD:E

答案:G以下说法错误的是（）

A:若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树B:一般在哈夫曼树中，权值越大的叶子离根结点越近C:若初始森林中共有N棵二叉树，最终求得的哈夫曼树中共有2N-1个结点D:哈夫曼树中没有度数为1的分支结点

答案:若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树（）

A:对B:错

答案:错若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反（）

A:错B:对

答案:对完全二叉树中，若一个结点没有左孩子，则它必是树叶。（

）

A:对B:错

答案:对利用二叉链表存储树，则根结点的右指针是（

）

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

答案:空

第五章单元测试

用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（）

A:对B:错

答案:对有向图的邻接矩阵是对称的。（）

A:对B:错

答案:错设无向图的顶点个数为n，则该图最多有（）条边。

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

答案:n(n-1)/2下列关于无向连通图特征的叙述中，正确的是：（）

1.所有顶点的度之和为偶数

2.边数大于顶点个数减1

3.至少有一个顶点的度为1

A:只有2B:只有1C:1和3D:1和2

答案:只有1对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有顶点邻接表的边结点总数为（）。

A:2eB:e/2C:n+eD:e

答案:2e给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的顶点序列为()。

A:V1,V5,V4,V7,V6,V2,V3B:V1,V5,V4,V7,V6,V3,V2C:V1,V2,V3,V4,V7,V6,V5D:V1,V5,V6,V4,V7,V2,V3

答案:V1,V5,V4,V7,V6,V3,V2在图中自a点开始进行广度优先搜索算法可能得到的结果为（）。

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

答案:a,b,e,c,d,f任何一个带权无向连通图的最小生成树（）。

A:是唯一的B:是不唯一的C:有可能不唯一D:有可能不存在

答案:有可能不唯一对于下列的网，使用克鲁斯卡尔算法求最小生成树，依次得到的边集是（）。

A:{（A，D），（B，C），（E，A），（C，E）}B:{（A，D），（A，B），（A，E），（E，C）}C:{（A，D），（D，E），（B，C），（C，E）}D:{（A，D），（D，E），（E，C），（C，B）}

答案:{（A，D），（D，E），（B，C），（C，E）}使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其它各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。

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

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

第六章单元测试

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。（

）

A:对B:错

答案:错查找相同结点的效率折半查找总比顺序查找高。（

）

A:对B:错

答案:错在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。（

）

A:错B:对

答案:错采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（

）

A:对B:错

答案:对对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（

）

A:错B:对

答案:错已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是（

）。

A:6

B:7C:5

D:4

答案:5

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

）。

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

答案:95,22,91,24,94,71在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（

）。

I.若v是T1的叶结点，则T1与T3不同

II.若v是T1的叶结点，则T1与T3相同

III.若v不是T1的叶结点，则T1与T3不同

IV.若v不是T1的叶结点，则T1与T3相同

A:仅II、IVB:仅I、IVC:仅II、IIID:仅I、III

答案:仅II、III对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则哈希地址为0的元素有（

）个

A:1

B:2

C:4D:3

答案:4适用于折半查找的查找表存储方式及元素排列要求为(

)

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

D:链接方式存储，元素无序

答案:顺序方式存储，元素有序有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，当用折半查找方法查找值82的结点时，（）次比较后查找成功。

A:8B:1

C:4

D:2

答案:4

将{5,2,7,3,4,1,6}依次插入初始为空的二叉排序树。则该树的后序遍历结果是:（）

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

答案:1,4,3,2,6,7,5有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，应选择下列（）的序列输入。

A:30，24，12，37，45，96，53B:37，24，12，30，53，45，96C:45，24，53，12，37，96，30D:12，24，30，37，45，53，96

答案:37，24，12，30，53，45，96下面关于哈希查找的说法，不正确的是（）

A:用链地址法处理冲突，适合表长不确定的情况B:用链地址法处理冲突，不会引起二次聚集现象C:采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的D:采用链地址法处理冲突时，查找每个元素的时间是相同的

答案:采用链地址法处理冲突时，查找每个元素的时间是相同的

第七章单元测试

快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。

A:错B:对

答案:错堆排序是稳定的排序方法。

A:错B:对

答案:错在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。

A:对B:错

答案:错在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。

A:对B:错

答案:对比较次数与排序