数据结构智慧树知到课后章节答案2023年下海南师范大学

数据结构智慧树知到课后章节答案2023年下海南师范大学海南师范大学

第一章测试

从一个二维数组b[m][n]中找出最大值元素的时间复杂度为

A:m+nB:m*nC:mD:n

答案:m*n

在以下时间复杂度的数量级中，数量级最大的是

A:B:C:D:

答案:

下面程序段的时间复杂度为____________。for(inti=0;i<m;i++)

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

a[i][j]=i*j;

A:O(m+n)B:O(n2)C:O(m2)D:O(m*n)

答案:O(m*n)

执行下面程序段时，执行S语句的次数为（

）。for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)

S;

A:n2B:n(n+1)/2C:n(n+1)D:n2/2

答案:n(n+1)/2

线性结构是数据元素之间存在一种：（

）。

A:一对一关系B:一对多关系C:多对一关系D:多对多关系

答案:一对一关系

数据结构中，与所使用的计算机无关的是数据的（

）结构。

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

答案:逻辑

算法分析的目的是：（

）。

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

答案:分析算法的效率以求改进

算法分析的两个主要方面是：（

）。

A:空间复杂性和时间复杂性B:数据复杂性和程序复杂性C:可读性和文档性D:正确性和简明性

答案:空间复杂性和时间复杂性

计算机算法指的是：（

）。

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

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

计算机算法必须具备输入、输出和（

）等5个特性。

A:易读性、稳定性和安全性B:可行性、确定性和有穷性C:确定性、有穷性和稳定性D:可行性、可移植性和可扩充性

答案:可行性、确定性和有穷性

一个算法的好坏可以通过复杂性、可读性、健壮性、高效性这四个方面进行评价。

A:错B:对

答案:错

数据结构是一门研究算法的学科。

A:错B:对

答案:错

数据结构中，数据的逻辑结构包括线性结构、图结构、树形结构、集合。

A:对B:错

答案:对

线性表的逻辑顺序与存储顺序总是一致的。

A:对B:错

答案:错

每种数据结构都具备三个基本运算：插入、删除和查找。

A:错B:对

答案:错

线性结构中元素之间只存在多对多关系。

A:错B:对

答案:错

在线性结构中，第一个结点没有前驱结点。

A:错B:对

答案:对

在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

A:对B:错

答案:对

算法分析的目的是分析算法的效率以求改进。

A:对B:错

答案:对

同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。

A:错B:对

答案:对

第二章测试

在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（

）

A:在第i个结点后插入一个新结点（1≤i≤n）B:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C:将n个结点从小到大排序D:删除第i个结点（1≤i≤n）

答案:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（

）个元素。

A:8B:63C:7D:63.5

答案:63.5

线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（

）

A:一定是不连续的B:连续或不连续都可以C:必须是连续的D:部分地址必须是连续的

答案:连续或不连续都可以

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

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

答案:顺序表

在一个以h为头结点的单循环链表中，使指针p指向链尾结点的条件是（

）。

A:p->next->next==hB:p->next==NULL

C:p->next==h->nextD:p->next==h;

答案:p->next==h;

链表是一种采用（

）存储结构存储的线性表

A:顺序B:链式

C:星式D:网状

答案:链式

单链表包括两个域：（

）。

A:数据域和指针域B:数据域和表位C:链式和数字D:数据域和星式

答案:数据域和指针域

单链表可以用（

）来命名。

A:头指针的名字B:LC:KD:结点名

答案:头指针的名字

单链表的插入操作其时间复杂度为（

）。

A:O（1）B:O（n3）C:O（n2）D:O（n）

答案:O（n）

顺序表的插入操作的时间复杂度为（

）。

A:O（1）

B:O（n）C:O（n3）D:O（n2）

答案:O（n）

线性表的逻辑结构特性是一对多的。

A:错B:对

答案:错

顺序表在进行插入和删除操作时不需要移动元素。

A:错B:对

答案:错

对于链表是依靠指针来反映其线性逻辑关系的。

A:对B:错

答案:对

在单链表的第一个结点之前是不允许附设结点的。

A:错B:对

答案:错

在单链表中首元结点就是头结点。

A:对B:错

答案:错

循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素。

A:对B:错

答案:对

线性表采用链式存储，便于插入和删除操作。

A:对B:错

答案:对

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

A:错B:对

答案:对

单链表可以有多个指针域。

A:错B:对

答案:错

顺序表的每个元素所占的存储单元是相等的。

A:错B:对

答案:对

第三章测试

栈的插入和删除操作在（

）

A:任意位置

B:栈顶

C:指定位置

D:栈底

答案:栈顶

五节车厢以编号a，b，c，d，e顺序进入铁路调度站（栈），可以得到（

）的编组

A:b，d，a，c，e

B:c，d，e，a，b

C:a，c，e，b，d

D:c，e，d，b，a

答案:c，e，d，b，a

判定一个顺序栈S（栈空间大小为n）为空的条件是（）

A:S->top==n

B:S->top!=n

C:S->top==0

D:S->top!=0

答案:S->top==0

在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（

）

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

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

C:front=front->next

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

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

一个队列的入队序列是1，2，3，4，则队列的出队序列是（

）

A:1，4，3，2

B:1，2，3，4

C:4，3，2，1

D:3，4，1，2

答案:4，3，2，1

依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）

A:dB:cC:a

D:b

答案:c

栈是一种非线性结构。

A:错B:对

答案:错

队列允许在一端进行插入，另一端进行删除操作。

A:对B:错

答案:对

在程序设计语言中实现递归操作是用到栈实现的。

A:对B:错

答案:对

递归程序在执行时是用队列来保存调用过程中的参数、局部变量和返回参数的。

A:对B:错

答案:错

在表达式求值算法中运用到队列来实现的。

A:对B:错

答案:错

队列假溢出问题的一个解决方法是运用循环队列。

A:错B:对

答案:对

队列Q满的条件是：Q.front==Q.rear。

A:对B:错

答案:错

每当在新队列中插入一个新元素时，尾指针rear增1。

A:对B:错

答案:对

在顺序队列中，头指针始终指向队列的最后一个元素。

A:对B:错

答案:错

在顺序队列中，尾指针始终指向队列尾元素的下一个位置。

A:错B:对

答案:对

第四章测试

串的长度是指（

）

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

答案:串中所含不同字母的个数

设有串t='I

am

a

good

student

'，那么Substr(t,6,6)=（

）

A:agoodB:goodC:a

good

sD:student

答案:agood

串“ababaaababaa”的next数组为（

）

A:012121111212B:0123012322345C:012345678999D:011234223456

答案:011234223456

函数substr(“DATASTRUCTURE”，5，9)的返回值为（

）

A:“DATA”B:“STRUCTURE”C:“DATASTRUCTURE”D:“ASTRUCTUR”

答案:“STRUCTURE”

设有两个串p和q，求q在p中首次出现的位置的运算称作（

）

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

答案:模式匹配

设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（

）

A:BCDEFGB:BCPQRSTC:BCDEFD:BCDEFEF

答案:BCDEFEF

若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（）

A:ABC###G2345

B:ABC###G1234

C:ABC###G0123D:ABCD###2345

答案:ABC###G1234

主串为’abaababaddecab’

,模式串为’abad’。使用KMP算法需要（

）次匹配成功。

A:5B:4

C:12D:10

答案:4

不包含任何字符的串称为空白串。

A:对B:错

答案:错

在串的模式匹配运算中，被匹配的主串称为模式。

A:对B:错

答案:错

组成串的数据元素只能是字符。

A:错B:对

答案:对

串不能采用顺序存储结构进行存储。

A:对B:错

答案:错

模式匹配简单算法时间复杂度是O(m*n)。

A:对B:错

答案:对

空格串与空串的没有区别。

A:错B:对

答案:错

设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为O(m+n)。

A:对B:错

答案:对

两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。

A:对B:错

答案:对

串是一种非线性结构。

A:对B:错

答案:错

串的模式匹配算法只能采用串的链式存储结构来实现。

A:对B:错

答案:错

第五章测试

设二维数组A[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素aij占d个字节，则元素aij的地址为（

）

A:LOC(a00)+((j-1)*n+i-1)*dB:LOC(a00)+(i*n+j)*dC:LOC(a00)+((i-1)*n+j-1)*dD:LOC(a00)+(j*n+i-1)*d

答案:LOC(a00)+(i*n+j)*d

若数组A[0..m-1][0..n-1]按列优先顺序存储，则aij地址为（）

A:LOC(a00)+j*m+iB:LOC(a00)+j*n+IC:LOC(a00)+(j-1)*m+I-1D:LOC(a00)+(j-1)*n+i-1

答案:LOC(a00)+j*m+i

若下三角矩阵An*n，按行顺序压缩存储在数组a[0..(n+1)n/2]中，则非零元素aij的地址为（）（设每个元素占d个字节）

A:LOC(a00)+((i-1)i/2+j-1)*dB:LOC(a00)+((i+1)i/2+j)*dC:LOC(a00)+((i-1)i/2+i-1)*dD:LOC(a00)+((j-1)j/2+i)*d

答案:LOC(a00)+((i-1)i/2+j-1)*d

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

A:三元组和十字链表B:散列和十字链表C:二维数组和三维数组D:三元组和散列

答案:三元组和十字链表

广义表A=((x,(a,b)),((x,(a,b)),y))，则运算head(head(tail(A)))为（

）

A:xB:(x,(a,b))

C:AD:(a,b)

答案:(x,(a,b))

二维数组可以看成是一个线性表。

A:对B:错

答案:对

不做插入删除操作的数组，采用顺序存储结构表示数组比较合适。

A:对B:错

答案:对

二维数组的顺序存储方法只可以行序为主序的存储方式。

A:对B:错

答案:错

对称矩阵在存储时可进行压缩存储。

A:对B:错

答案:对

稀疏矩阵是非零值元素分布有一定规律的矩阵。

A:对B:错

答案:错

第六章测试

一棵具有67个结点的完全二叉树，它的深度为（

）。

A:9B:6C:7D:8

答案:7

给定树如图所示，请列出的中序遍历序列（

）

。

A:ABDCEFB:DABECFC:DBAECFD:DBEFCA

答案:DBAECF

设有树如图所示，则结点g的度为（

）。

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

答案:3

用4个权值{7,2,4,5}构造的哈夫曼（Huffman）树的带权路径长度是（

）。

A:32B:34C:33D:35

答案:35

对于任何一棵具有n个结点的线索二叉树，具有（

）个线索。

A:

0B:

nC:

n+1D:

n-1

答案:

n+1

一棵深度为5的满二叉树有（

）个分支结点。

A:7B:16C:14D:15

答案:15

一棵深度为5的满二叉树有（

）个叶子。

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

答案:16

给定二叉树如图所示，请列出的后序遍历序列（

）

。

A:BACDEB:BDECAC:BADCED:ABCDE

答案:BDECA

设有二叉树如图所示，按其中序遍历次序遍历，对于根a的右子树最先访问的结点是（

）。

A:dB:bC:hD:a

答案:h

若按层序对深度为6的完全二叉树中全部结点从１开始编号，则编号为10的结点其右孩子的编号为（

）。

A:12B:20

C:11

D:21

答案:21

二叉树的子树无左右之分的。

A:对B:错

答案:错

二叉树的度大于2的树。

A:对B:错

答案:错

二叉树是非线性数据结构。

A:对B:错

答案:错

二叉树不能转换为树，树也不能转换为二叉树。

A:错B:对

答案:错

哈夫曼（Huffman）树的带权路径长度是最小的。

A:对B:错

答案:对

满二叉树就是一种特殊的完全二叉树。

A:错B:对

答案:对

假设n(n>0)个结点的树，它有且只有1个根结点。

A:对B:错

答案:对

n个结点的线索二叉树中线索的数目是不确定的。

A:错B:对

答案:错

不含任何结点的空树，它可以是一棵树也是一棵二叉树。

A:错B:对

答案:对

可以采用递归的方法计算二叉树的深度。

A:对B:错

答案:对

第七章测试

无向图的邻接矩阵是一个(

)

A:对角阵B:对称矩阵C:零矩阵D:上三角矩阵

答案:对称矩阵

若图G(V,E)中含有7个顶点，则保证图G在任何情况下都是连通的需要的边数最少是(

)

A:15B:16C:6D:21

答案:16

如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所以顶点，则该图一定是(

)

A:一棵树B:完全图C:有回路D:连通图

答案:连通图

用Prim算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶点集合U={1,2,3},已选取的边的集合TE={(1,2),(2,3)},要选取下一条权值最小的边，应该从(

)组中选取。

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

答案:{(1,4),(3,4),(3,5),(2,5)}

已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则从顶点1出发按深度优先遍历的结点序列是（

）。

A:1234B:1423C:1432

D:2314

答案:1234

已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则从顶点1出发按广度优先遍历的结点序列是（

）。

A:1243B:1342C:1432D:1324

答案:1324

任何一个无向连通图的最小生成树（

）。

A:只有一棵B:一定有多棵C:可能不存在D:一棵或多棵

答案:只有一棵

有8个结点的无向图最多有（

）条边。

A:14B:56C:112D:28

答案:28

有8个结点的无向连通图最少有（

）条边。

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

答案:7

有8个结点的有向完全图有（

）条边。

A:56B:112C:14D:28

答案:56

已知无向图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3),(3,4)}，则顶点3的度是（

）。

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

答案:3

已知有向图的顶点集合U={1,2,3,4},弧的集合TE={<1,2>,<1,3>,<2,3>,<3,4>}，则该有向图的拓扑排序序列是（

）。

A:1234B:4321C:1423D:1324

答案:1234

图的深度优先遍历序列（

）。

A:无B:不存在C:可以有多个D:只有一个

答案:可以有多个

拓扑排序算法是通过重复选择具有（

）个前驱顶点的过程来完成的。

A:2B:1C:3

D:0

答案:0

n个顶点e条边的图采用邻接表存储，该算法的时间复杂度为（

）。

A:O(n)

B:O(n+e)

C:O(n2)D:O(e)

答案:O(n+e)

n个顶点e条边的图采用邻接矩阵存储，该算法的时间复杂度为（

）。

A:O(n)

B:O(n+e)C:O(e)D:O(n2)

答案:O(n2)

第八章测试

在表长为ｎ的链表中进行线性查找，它的平均查找长度为（

）。

A:ＡＳＬ＝ｎB:ＡＳＬ＝（ｎ＋１）／２C:D:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

答案:ＡＳＬ＝（ｎ＋１）／２

有一个有序表（1，3，9，12，32，41，45，62，75，77，82，95，100），当折半查找有序表中值为82的结点时，则它与表元素中比较了（

）次后查找成功。

A:4B:2

C:8D:1

答案:4

采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（

）。

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

答案:O(log2n)

链表适用于以下（

）查找

A:顺序B:二分法C:随机D:顺序，也能二分法

答案:顺序

顺序表查找法适合于以下（

）存储结构的线性表。

A:散列存储B:顺序存储或链接存储C:压缩存储D:索引存储

答案:顺序存储或链接存储

对线性表进行二分查找时，要求线性表必须（

）。

A:以链接方式存储B:以顺序方式存储C:以顺序方式存储，且结点按关键字有序排序D:以链接方式存储，且结点按关键字有序排序

答案:以顺序方式存储，且结点按关键字有序排序

有一个长度为12的有序表，按二分查找对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（

）。

A:43/12B:39/12C:37/12D:35/12

答案:37/12

碰撞（冲突）指的是（

）。

A:不同关键码值对应到相同的存储地址B:负载因子过大C:两个元素具有相同序号D:两个元素的关键码值不同，而非码属性相同

答案:不同关键码值对应到相同的存储地址

在各种查找方法中，平均查找长度与结点个数n无关的查找方法是（

）。

A:分块查找B:顺序查找C:散列查找D:折半查找

答案:散列查找

散列法存储的基本思想是（

）。

A:查找与结点个数n无关B:以顺序方式且结点按关键字有序排序C:由关键字的值决定数据的存储地址D:顺序查找

答案:由关键字的值决定数据的存储地址

在散列函数H(key)=key%p，p应取（

）。

A:偶数B:小数C:素数D:整数

答案:素数

采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（

）个结点最佳。

A:625B:10C:25D:6

答案:25

平衡二叉树上的平衡因子只能取（

）。

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

答案:-1,0,1

以下对二叉排序树的描述不正确的是（

）。

A:二叉排序树右子树上所有结点的值均大于它的根结点的值

B:中序遍历一棵二叉树时可以得到一个结点值递减的序列C:二叉排序树左子树上所有结点的值均小于它的根结点的值D:左、右子树也分别是二叉排序树

答案:中序遍历一棵二叉树时可以得到一个结点值递减的序列

假设在平衡二叉树上插入一个结点后造成了不平衡，其最近不平衡点为A，且已知A的左子树的平衡因子为-1，其右子树的平衡因子为0，应该进行（

）型调整可使二叉树平衡。

A:LLB:LRC:RLD:RR

答案:LR

第九章测试

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

）。

A:选择排序B:冒泡排序C:归并排序D:插入排序

答案:插入排序

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

）。

A:选择排序B:归并排序C:插入排序D:冒泡排序

答案:选择排序

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

）。

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

答案:O(n2)

下列关键字序列中，（

）是堆。

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

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

下述几种排序方法中，（

）是稳定的排序方法。

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

答案:归并排序

在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（

）。

A:起泡排序B:插入排序C:选择排序D:希尔排序

答案:选择排序

在待排序的元素序列基本有序的前提下，效率最高的排序方法是（

）。

A:归并排序B:插入排序C:选择排序D:快速排序

答案:插入排序

在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（

）次。

A:5B