数据结构知到智慧树章节测试课后答案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:问题的规模和待处理数据的初态

答案:问题的规模和待处理数据的初态

数据元素是数据的最小单位。（）

A:对B:错

答案:错数据结构是带有结构的数据元素的结合。（）

A:对B:错

答案:对算法和程序没有区别，所以在数据结构中二者是通用的。（）

A:对B:错

答案:错数据结构的抽象操作的定义与具体实现有关。（）

A:对B:错

答案:错

第二章单元测试

下述哪一条是顺序存储结构的优点？（）。

A:可方便地用于各种逻辑结构的存储表示

B:插入运算方便

C:存储密度大

D:删除运算方便

答案:存储密度大

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

A:线性表采用顺序存储，必须占用一片连续的存储单元

B:线性表采用链接存储，便于插入和删除操作

C:线性表采用顺序存储，便于进行插入和删除操作

D:线性表采用链接存储，不必占用一片连续的存储单元

答案:线性表采用顺序存储，便于进行插入和删除操作

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

A:数据元素

B:字符

C:数据项

D:表元素

答案:数据元素

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

A:单循环链表

B:带头结点的双循环链表

C:顺序表

D:双链表

答案:顺序表

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

A:单链表

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

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

D:双链表

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

设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。

A:带头结点的双循环链表

B:单链表

C:带尾指针的单循环链表

D:单循环链表

答案:带头结点的双循环链表

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。

A:单链表

B:带头结点的双循环链表

C:单循环链表

D:双链表

答案:带头结点的双循环链表

静态链表中指针表示的是（）。

A:左、右孩子地址

B:数组下标

C:下一元素地址

D:内存地址

答案:下一元素地址

链表不具有的特点是（）。

A:所需空间与线性长度成正比

B:不必事先估计存储空间

C:可随机访问任一元素

D:插入、删除不需要移动元素

答案:可随机访问任一元素

下面的叙述不正确的是（）。

A:线性表在顺序存储时，查找第i个元素的时间同i的值无关

B:线性表在链式存储时，查找第i个元素的时间同i的值无关

C:线性表在链式存储时，查找第i个元素的时间同i的值成正比

D:线性表在顺序存储时，查找第i个元素的时间同i的值成正比

答案:线性表在链式存储时，查找第i个元素的时间同i的值无关

；线性表在顺序存储时，查找第i个元素的时间同i的值成正比

第三章单元测试

设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是()。

A:1

B:4

C:2

D:3

答案:3

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是()。

A:bacde

B:ecbad

C:dbace

D:dbcae

答案:dbcae

若用一个大小为5的数组来实现循环队列，且当前rear和front的值分别为0和2，当从队列中删除2个元素，再加入1个元素后，rear和front的值分别为多少()。

A:1和4

B:4和1

C:2和3

D:3和2

答案:1和4

若用链表来表示队列，则应该选用（）。

A:带头指针的循环链表

B:带头指针的非循环链表

C:带尾指针的循环链表

D:带尾指针的非循环链表

答案:带尾指针的循环链表

向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行()。

A:S-＞next=top;top=S；

B:top-＞next=S

C:S-＞next=top-＞next;top-＞next=S;

D:S-＞next=top;top=top-＞next；

答案:S-＞next=top;top=S；

消除递归不一定需要使用栈。（）

A:对B:错

答案:对若输入序列为1,2,3,4,5,6，则出栈序列不可能是3,2,5,6,4,1。（）

A:错B:对

答案:错循环队列也存在空间溢出问题。（）

A:错B:对

答案:对栈和队列的存储方式都可以采用顺序方式存储。（）

A:对B:错

答案:对在链队列中，即使不设置尾指针也能进行入队操作。（）

A:错B:对

答案:对

第四章单元测试

字符串S="Todayis30July2005"，其长度是()。

A:20

B:21

C:19

D:18

答案:21

下列哪一个不是串的存储方法（）。

A:定长顺序存储

B:十字表存储

C:堆分配存储

D:块链存储

答案:十字表存储

设有两个串p和q，Concat(p,q)操作是（）。

A:连接

B:串赋值

C:求串长

D:求子串

答案:连接

若串str=“Software”，其子串的个数是（）。

A:37

B:8

C:9

D:36

答案:37

串是一种数据对象和操作都特殊的线性表。（）

A:对B:错

答案:对两个串相等就是两个串含有相同字符。（）

A:对B:错

答案:错设SUBSTR（S,i,k）是求S中从第i个字符开始的连续k个字符组成的子串操作，则对于S=‘Beijing&Nanjing’，SUBSTR(S,4,5)=()。

A:‘ijing’

B:‘ingNa’

C:‘jing&’

D:‘ing&N’

答案:‘jing&’

空串与空格串（）。

A:相同

B:不相同

C:无法确定

D:可能相同

答案:不相同

“DT”是“DATA”的子串。（）

A:错B:对

答案:错串中不能含有数字。（）

A:对B:错

答案:错

第五章单元测试

一个一维数组A的长度为500，起始（A[0]）地址为2000，每个元素占4个字节，则A[80]的地址是（）。

A:2004

B:2088

C:2320

D:2080

答案:2320

数组A[0..4,-1..-3,5..7]中含有元素的个数为（）。

A:16

B:55

C:45

D:36

答案:45

对下述矩阵进行压缩存储后，失去随机存取功能是（）。

A:稀疏矩阵

B:三角矩阵

C:对称矩阵

D:三对角矩阵

答案:稀疏矩阵

广义表L=((a,b,c,d))的表尾是（）。

A:(b,c,d)

B:()

C:A

D:(a,b,c,d)

答案:()

一个5*5的对称矩阵采用压缩存储，需要存储（）个元素。

A:20

B:15

C:5

D:10

答案:15

设有一个10阶的对称矩阵A，采用压缩存储，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A:13

B:33

C:18

D:40

答案:33

广义表A=(a,b,(c,d),(e,(f,g)))，则表达式Head(Tail(Head(Tail(Tail(A)))))的值为（）。

A:(d)

B:(g)

C:d

D:c

答案:d

设广义表L=（a,（b,c,d）），则L的长度和深度分别为（）。

A:2和2

B:1和1

C:2和3

D:1和3

答案:2和2

广义表B=（a,(b,c,d)），则它的表尾是(）。

A:(b,c,d)

B:a,(b,c,d)

C:c,d

D:a

答案:(b,c,d)

稀疏矩阵一般的压缩存储方法有（）两种。

A:三元组和十字链表

B:二维数组和三维数组

C:三元组和散列表

D:散列表和十字链表

答案:三元组和十字链表

第六章单元测试

已知一棵完全二叉树的第5层有7个结点，则其有（）个叶子结点。

A:10

B:11

C:12

D:13

答案:11

含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）。

A:4

B:6

C:3

D:5

答案:3

一棵二叉树的广义表表示为a(b(c,d),e(,f(g)))，则得到的层次遍历序列为（）。

A:cdbgfea

B:cbdaegf

C:abecdfg

D:abcdefg

答案:abecdfg

已知完全二叉树有80个结点，则该二叉树有（）个度为1的结点。

A:1

B:0

C:2

D:不确定

答案:1

下列存储形式中，（）是树的存储形式。

A:广义表表示法

B:双亲表示法

C:孩子表示法

D:孩子兄弟表示法

答案:双亲表示法

；孩子表示法

；孩子兄弟表示法

一棵先序序列为1,2,3,4的二叉树，其中序序列可能是（）。

A:3,4,2,1

B:2,4,3,1

C:4,1,2,3

D:4,3,2,1

答案:3,4,2,1

；2,4,3,1

；4,3,2,1

一棵有16个结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的（）。

A:左孩子编号为14

B:左孩子编号为15

C:双亲编号为3

D:双亲编号为4

答案:左孩子编号为14

；双亲编号为3

将一个递归算法改为对应的非递归算法时，通常需要使用队列。（）

A:错B:对

答案:错完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达。（）

A:对B:错

答案:对设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，则森林F中第一棵树的结点个数是m-n。（）

A:错B:对

答案:对

第七章单元测试

在一个无向图中，所有顶点的度数之和等于图的边数的多少倍？（）

A:1/2

B:2

C:1

D:4

答案:2

在十字链表中，既容易找到以顶点i为尾的弧，也容易找到以i为头的弧。（）

A:对B:错

答案:对邻接多重表用两个边结点表示一条边。（）

A:错B:对

答案:错对于下图所示的带权有向图，采用迪杰斯特拉（Dijkstra）算法求从顶点0到其余各顶点的最短路径，则得到的第一条最短路径的目标顶点是1，第二条最短路径的目标顶点是2，后续得到其余各最短路径的目标顶点依次为？（

）

A:3->5->4->6B:3->4->5->6C:4->3->5->6D:3->5->6->4

答案:3->5->4->6在下图表示某工程的AOE网中，关键路径长度是多少？（

）

A:16B:19C:23D:17

答案:23有下图所示的有向图，其拓扑排序序列为？（

）

A:ADBCEB:ABDCEC:ABCDED:ABCED

答案:ABCDE用普里姆(Prim)算法求一个连通图的带权图的最小生成树，在算法执行过程中，已选取的顶点集合U={A，B}，已选取的边的集合TE={（A，B）}，要选取下一条权值最小的边，应当从下列哪组中选取？（

）

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

答案:{（A，C），（A，E），（B，D）}按照深度优先搜索遍历下图，从顶点1出发，可得到顶点访问序列为（

）。

A:1523467B:1273645C:1253467

D:1236745

答案:1273645以下哪项是下面有向图的邻接表？（

）

A:B:C:D:

答案:下面哪项是下图无向图的邻接矩阵？（

）

A:B:C:D:

答案:

第八章单元测试

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

A:n

B:(n-1)/2

C:n/2

D:(n+1)/2

答案:(n+1)/2

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

A:4

B:5

C:6

D:7

答案:5

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

A:21,89,77,29,36,38

B:95,22,91,24,94,71

C:92,20,91,34,88,35

D:12,25,71,68,33,24

答案:95,22,91,24,94,71

用线性探测再散列处理冲突时，可能出现聚集现象。下列选项中，会受聚集现象直接影响的是（）。

A:装填因子

B:散列函数

C:存储效率

D:平均查找长度

答案:平均查找长度

对于二叉排序树，下面的说法错误的是（）。

A:在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2

B:逐点插入构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大

C:对二叉排序树进行层序遍历可得到有序序列

D:二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合

答案:在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2

；对二叉排序树进行层序遍历可得到有序序列

；二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合

在构造哈希表方面，下面的说法正确的是（）。

A:哈希表的装填因子越大，说明空间利用率越好，因此应使装填因子尽量大

B:在哈希表中进行查找也需要关键字的比较

C:哈希函数选的好可减少冲突现象

D:链地址法在处理冲突时会产生聚集

答案:在哈希表中进行查找也需要关键字的比较

；哈希函数选的好可减少冲突现象

在平衡二叉树中插入一个结点后造成了不平衡，需要进行平衡化旋转，调整类型有（）。

A:LL型

B:LR型

C:RR型

D:RL型

答案:LL型

；LR型

；RR型

；RL型

有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。（）

A:对B:错

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

A:对B:错

答案:错AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于1。（）

A:错B:对

答案:对

第九章单元测试

下列排序算法中，稳定的是（）。

A:快速排序，堆排序

B:直接选择排序，归并排序

C:归并排序，冒泡排序

D:堆排序，冒泡排序

答案:归并排序，冒泡排序

为实现快速排序算法，待排序序列采用的存储方式是（）。

A:索引存储

B:链式存储

C:顺序存储

D:散列存储

答案:顺序存储

对给定的关键字序列110,119,007,911,114,120,122进行基数排序，则第2趟分配收集后得到的关键字序列是（）。

A:007,110,119,114,911,120,122

B:007,110,911,114,119,120,122

C:007,110,119,114,911,12