数据结构知到智慧树章节测试课后答案2024年秋武汉纺织大学

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

在数据结构中，从逻辑上可以把数据结构分成（）。

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++的时间是单位时间，则以下语句的时间复杂度为（）。

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

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

x++;

A:O(

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

)

答案:O(

)数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。

A:低B:相同C:不好说D:高

答案:高算法分析的目的是（）。

A:分析算法的易懂性和文档性B:找出数据结构的合理性C:研究算法中的输入和输出关系D:分析算法的效率以求改进

答案:分析算法的效率以求改进计算机算法指的是（）。

A:排序方法B:解决问题的有限运算序列C:调度方法D:计算方法

答案:解决问题的有限运算序列

第二章单元测试

线性结构中的一个结点代表一个（）

A:数据结构B:数据元素C:数据D:数据项

答案:数据元素若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。

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

答案:O(n)若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。

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

答案:顺序表在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。

A:n-i-1B:iC:n-iD:n-i+1

答案:n-i+1⾮空的循环单链表head的尾结点p满⾜（）。

A:p->next==headB:p==NULLC:p->next==NULLD:p==head

答案:p->next==head链表不具有的特点是（）。

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

答案:可随机访问任⼀元素在⼀个单链表中，若删除p所指向结点的后续结点，则执⾏（）。

A:p=p->next;p->next=p->next->next;B:p->next=p->next->next;C:p=p->next;D:p=p->next->next;

答案:p->next=p->next->next;单链表不是⼀种随机存储结构。（）

A:对B:错

答案:对顺序存储⽅式只能⽤于存储线性结构。（）

A:对B:错

答案:错在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不⼀定是相邻的。（）

A:对B:错

答案:错

第三章单元测试

若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

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

答案:4，3，1，2，5设有一个递归算法如下：

intfact(intn){//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);}

则计算fact(n)需要调用该函数的次数为（）。

A:n+1B:n+2C:nD:n-1

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

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

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

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

答案:3最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A:(rear+1)%n==frontB:rear+1==frontC:rear==frontD:(rear-l)%n==front

答案:rear==front栈和队列的共同点是（）。

A:都是先进后出B:只允许在端点处插入和删除元素C:没有共同点D:都是先进先出

答案:只允许在端点处插入和删除元素栈和队列都是限制存取端的。（）

A:错B:对

答案:对对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。（）

A:对B:错

答案:对若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A:n-iB:n-i+1C:iD:n-i-1

答案:n-i+1循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A:rear=(rear+1)%(m+1)B:rear=(rear+1)%(m-1)C:rear=(rear+1)%mD:rear=rear+1

答案:rear=(rear+1)%(m+1)

第四章单元测试

空串与空格串是相同的。（）

A:错B:对

答案:错设有两个串p和q，求q在p中首次出现的位置的运算称作____。（）

A:求子串B:模式匹配C:连接D:求串长

答案:模式匹配设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存人C语言的一维数组N中，元素m6,6在N中的下标是（）。

A:66B:51C:55D:50

答案:55将一个10*10对称矩阵M的上三角部分的元素mi,j（1≤i≤j≤10）按列优先存入C语言的一维数组N中，元素m7,2在N中的下标是____。（）

A:33B:16C:22D:15

答案:22下面关于串的的叙述中，哪一个是不正确的？（）

A:串既可以采用顺序存储，也可以采用链式存储B:模式匹配是串的一种重要运算C:空串是由空格构成的串D:串是字符的有限序列

答案:空串是由空格构成的串串的长度是指（）

A:串中所含不同字符的个数B:串中所含非空格字符的个数C:串中所含字符的个数D:串中所含不同字母的个数

答案:串中所含字符的个数若串S=“software”，其子串的个数是（）。

A:8B:37C:36D:9

答案:36常对数组进行的两种基本操作是____。（）

A:建立与删除B:索引和修改C:查找与索引D:查找和修改

答案:查找和修改有一个三维数组A[-2…2][-4…5][2…6],其元素个数是____。（）

A:396B:144C:60D:250

答案:250设二维数组A[1..5][1..8]，若按行优先的顺序存放数组的元素，则A[4][6]元素的前面有____个元素。（）

A:29B:6C:28D:40

答案:29

第五章单元测试

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

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

答案:5一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A:254B:500C:501D:250

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

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

答案:11至1025之间深度为h的满m叉树的第k层有（）个结点。(1=<k=<h)

A:mk-1B:mh-1C:mk-1D:mh-1

答案:mk-1一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。

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

答案:只有一个叶子结点设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A:100B:101C:99D:102

答案:100若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

A:X的右子树中最左的结点B:X的双亲C:X的左子树中最右叶结点D:X的左子树中最右结点

答案:X的左子树中最右结点引入二叉线索树的目的是（）。

A:为了能方便的找到双亲B:使二叉树的遍历结果唯一C:加快查找结点的前驱或后继的速度D:为了能在二叉树中方便的进行插入与删除

答案:加快查找结点的前驱或后继的速度n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。

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

答案:该树一定是一棵完全二叉树设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。

A:nB:n+2C:n−1D:n+1

答案:n+1

第六章单元测试

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

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

答案:2具有n个顶点的有向图最多有（）条边

A:n(n+1)B:2nC:nD:n(n-1)

答案:n(n-1)n个顶点的联通图用邻接矩阵表示时，该矩阵至少有（）个非零元素

A:2(n-1)B:nC:n2D:n/2

答案:2(n-1)若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图

A:联通B:弱连通C:强连通D:非连通

答案:联通用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法

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

答案:队列下面（）算法适合构造一个稠密图G的最小生成树

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

答案:Prim算法下面（）方法可以判断出一个有向图是否有环

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

答案:深度优先遍历使用Dijkstra算法求下图中从顶点到其他各顶点的最短路径，依次得到的各最短路径的目标点是（）

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

答案:5,2,3,6,4下图所示的AOE表示一项包含8个活动的工程，活动d的最早开始时间和最迟开始时间分别是（）

A:15和15B:12和14C:3和7D:12和12

答案:12和14已知无向图G如下所示，使用Kruskal算法求图G的最小生成树，加入到最小生成树中的边依次是（）

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

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

第七章单元测试

静态查找表和动态查找表的区别是？（）

A:所包含的数据元素的类型不同B:施加其上的操作不同C:它们的逻辑结构不同D:其他三个选项都不对

答案:施加其上的操作不同采用顺序查找方法查找长度为n的顺序表时，在等概率时成功查找的平均查找长度为（）。

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

答案:(n+1)/2适合于折半查找的数据组织方式是（）。

A:以顺序表存储的线性表B:以顺序表存储的有序线性表C:以链表存储的有序线性表D:以链表存储的线性表

答案:以顺序表存储的有序线性表已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个存在的元素，则比较的次数最多是（）。

A:4B:6C:7D:5

答案:5‌对有3600个记录的索引顺序表（分块表）进行分块查找，最理想的块长是（）。

A:60B:120C:180D:600

答案:60有一棵含有8个节点的二叉排序树，其节点值为A～H，以下（）是其后序遍历结果。

A:ADBCEGFHB:BCAEFDHGC:BDACEFHGD:BCAGEHFD

答案:BCAEFDHG具有5层节点的AVL树至少有（）个节点。

A:12B:17C:10D:15

答案:12‎以下关于m阶B-树的叙述中正确的是（）。

A:当插入一个关键字引起B-树节点分裂时，树增高一层B:树中每个节点至多有ém/2ù-1个关键字C:所有叶子节点均在同一层上D:每个节点至少有两棵非空子树

答案:所有叶子节点均在同一层上‏以下关于哈希查找的叙述中正确的是（）。

A:哈希查找中不需要任何关键字的比较B:采用拉链法解决冲突时，查找一个元素的时间是相同的C:哈希表在查找成功时的平均查找长度仅仅与表长有关D:哈希表的装填因子等于表中填入的记录数除以哈希表的长度

答案:哈希表的装填因子等于表中填入的记录数除以哈希表的长度

第八章单元测试

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

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

答案:n(n-1)/2对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

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

答案:O(n2)若一组记录的排序码为（46,79，56，38，40，84），则利