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

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

A:m+n

B:m*n

C:m

D:n

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

A:

B:

C:

D:

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

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

a[i][j]=ij;

A:O(mn)

B:O(n2)

C:O(m+n)

D:O(m2)

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

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

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

S;

A:n(n+1)/2

B:n2/2

C:n2

D:n(n+1)

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

）。

A:一对多关系

B:多对一关系

C:一对一关系

D:多对多关系

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

）结构。

A:存储

B:物理

C:逻辑

D:物理和存储

答案:C算法分析的目的是：（

）。

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

B:研究算法中的输入和输出的关系

C:找出数据结构的合理性

D:分析算法的易懂性和文档性

答案:A算法分析的两个主要方面是：（

）。

A:数据复杂性和程序复杂性

B:正确性和简明性

C:可读性和文档性

D:空间复杂性和时间复杂性

答案:D计算机算法指的是：（

）。

A:计算方法

B:调度方法

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

D:排序方法

答案:C计算机算法必须具备输入、输出和（

）等5个特性。

A:确定性、有穷性和稳定性

B:可行性、确定性和有穷性

C:易读性、稳定性和安全性

D:可行性、可移植性和可扩充性

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

A:错

B:对

答案:A数据结构是一门研究算法的学科。

A:对

B:错

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

A:对

B:错

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

A:对

B:错

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

A:错

B:对

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

A:错

B:对

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

A:对

B:错

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

A:错

B:对

答案:B算法分析的目的是分析算法的效率以求改进。

A:错

B:对

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

A:错

B:对

答案:B第二章测试在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（

）

A:删除第i个结点（1≤i≤n）

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

C:在第i个结点后插入一个新结点（1≤i≤n）

D:将n个结点从小到大排序

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

）个元素。

A:7

B:8

C:63

D:63.5

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

）

A:必须是连续的

B:部分地址必须是连续的

C:连续或不连续都可以

D:一定是不连续的

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

A:顺序表

B:双链表

C:带头节点的双循环链表

D:单循环链表

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

）。

A:p->next==NULL

B:p->next==h;

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

D:p->next->next==h

答案:B链表是一种采用（

）存储结构存储的线性表

A:顺序

B:星式

C:链式

D:网状

答案:C单链表包括两个域：（

）。

A:数据域和星式

B:数据域和表位

C:链式和数字

D:数据域和指针域

答案:D单链表可以用（

）来命名。

A:K

B:头指针的名字

C:结点名

D:L

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

）。

A:O（1）

B:O（n2）

C:O（n）

D:O（n3）

答案:C

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

）。

A:O（1）

B:O（n）

C:O（n3）

D:O（n2）

答案:B线性表的逻辑结构特性是一对多的。

A:对

B:错

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

A:错

B:对

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

A:错

B:对

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

A:错

B:对

答案:A在单链表中首元结点就是头结点。

A:对

B:错

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

A:错

B:对

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

A:错

B:对

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

A:错

B:对

答案:B单链表可以有多个指针域。

A:错

B:对

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

A:错

B:对

答案:B第三章测试栈的插入和删除操作在（

）

A:任意位置

B:栈底

C:栈顶

D:指定位置

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

）的编组

A:c，d，e，a，b

B:a，c，e，b，d

C:b，d，a，c，e

D:c，e，d，b，a

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

A:S->top==0

B:S->top!=n

C:S->top==n

D:S->top!=0

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

）

A:front=front->next

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

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

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

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

）

A:1，4，3，2

B:1，2，3，4

C:4，3，2，1

D:3，4，1，2

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

A:b

B:a

C:d

D:c

答案:D栈是一种非线性结构。

A:对

B:错

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

A:错

B:对

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

A:错

B:对

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

A:错

B:对

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

A:错

B:对

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

A:对

B:错

答案:A队列Q满的条件是：Q.front==Q.rear。

A:对

B:错

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

A:对

B:错

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

A:错

B:对

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

A:错

B:对

答案:B第四章测试串的长度是指（

）

A:串中所含非空格字符的个数

B:串中所含不同字符的个数

C:串中所含字符的个数

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

答案:D设有串t=‘I

am

a

good

student

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

）

A:agood

B:good

C:student

D:a

good

s

答案:A串“ababaaababaa”的next数组为（

）

A:012345678999

B:011234223456

C:0123012322345

D:012121111212

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

）

A:“STRUCTURE”

B:“DATA”

C:“DATASTRUCTURE”

D:“ASTRUCTUR”

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

）

A:模式匹配

B:连接

C:求串长

D:求子串

答案:A设串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:BCPQRST

B:BCDEFG

C:BCDEF

D:BCDEFEF

答案:D若串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:ABCD###2345

B:ABC###G0123

C:ABC###G2345

D:ABC###G1234

答案:D主串为’abaababaddecab’

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

）次匹配成功。

A:4

B:5

C:10

D:12

答案:A不包含任何字符的串称为空白串。

A:对

B:错

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

A:对

B:错

答案:B组成串的数据元素只能是字符。

A:错

B:对

答案:B串不能采用顺序存储结构进行存储。

A:错

B:对

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

A:错

B:对

答案:B空格串与空串的没有区别。

A:对

B:错

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

A:对

B:错

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

A:错

B:对

答案:B串是一种非线性结构。

A:对

B:错

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

A:错

B:对

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

）

A:LOC(a00)+(jn+i-1)d

B:LOC(a00)+(in+j)d

C:LOC(a00)+((j-1)n+i-1)d

D:LOC(a00)+((i-1)n+j-1)d

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

A:LOC(a00)+(j-1)m+I-1

B:LOC(a00)+(j-1)n+i-1

C:LOC(a00)+jn+I

D:LOC(a00)+jm+i

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

A:LOC(a00)+((i-1)i/2+i-1)d

B:LOC(a00)+((i-1)i/2+j-1)d

C:LOC(a00)+((j-1)j/2+i)d

D:LOC(a00)+((i+1)i/2+j)*d

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

A:三元组和十字链表

B:散列和十字链表

C:二维数组和三维数组

D:三元组和散列

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

）

A:A

B:x

C:(a,b)

D:(x,(a,b))

答案:D二维数组可以看成是一个线性表。

A:错

B:对

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

A:错

B:对

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

A:错

B:对

答案:A对称矩阵在存储时可进行压缩存储。

A:错

B:对

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

A:错

B:对

答案:A第六章测试一棵具有67个结点的完全二叉树，它的深度为（

）。

A:9

B:8

C:6

D:7

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

）

。

A:ABDCEF

B:DABECF

C:DBEFCA

D:DBAECF

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

）。

A:1

B:4

C:3

D:2

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

）。

A:35

B:33

C:34

D:32

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

）个线索。

A:

n

B:

n+1

C:

0

D:

n-1

答案:B一棵深度为5的满二叉树有（

）个分支结点。

A:16

B:15

C:7

D:14

答案:B一棵深度为5的满二叉树有（

）个叶子。

A:16

B:32

C:31

D:17

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

）

。

A:BDECA

B:BACDE

C:ABCDE

D:BADCE

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

）。

A:a

B:b

C:h

D:d

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

）。

A:12

B:11

C:20

D:21

答案:D二叉树的子树无左右之分的。

A:对

B:错

答案:B二叉树的度大于2的树。

A:错

B:对

答案:A二叉树是非线性数据结构。

A:对

B:错

答案:B二叉树不能转换为树，树也不能转换为二叉树。

A:对

B:错

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

A:错

B:对

答案:B满二叉树就是一种特殊的完全二叉树。

A:错

B:对

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

A:错

B:对

答案:Bn个结点的线索二叉树中线索的数目是不确定的。

A:对

B:错

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

A:错

B:对

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

A:对

B:错

答案:A第七章测试无向图的邻接矩阵是一个(

)

A:对称矩阵

B:零矩阵

C:对角阵

D:上三角矩阵

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

)

A:15

B:6

C:21

D:16

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

)

A:完全图

B:连通图

C:有回路

D:一棵树

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

)组中选取。

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

B:{(3,4),(3,5),(4,5),(1,4)}

C:{(1,2),(2,3),(3,5)}

D:{(4,5),(1,3),(3,5)}

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

）。

A:2314

B:1432

C:1234

D:1423

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

）。

A:1324

B:1432

C:1243

D:1342

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

）。

A:可能不存在

B:一棵或多棵

C:只有一棵

D:一定有多棵

答案:C有8个结点的无向图最多有（

）条边。

A:56

B:28

C:14

D:112

答案:B有8个结点的无向连通图最少有（

）条边。

A:7

B:8

C:6

D:5

答案:A有8个结点的有向完全图有（

）条边。

A:28

B:56

C:112

D:14

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

）。

A:2

B:0

C:1

D:3

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

）。

A:4321

B:1324

C:1423

D:1234

答案:D图的深度优先遍历序列（

）。

A:无

B:只有一个

C:不存在

D:可以有多个

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

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

A:2

B:3

C:0

D:1

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

）。

A:O(e)

B:O(n+e)

C:O(n)

D:O(n2)

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

）。

A:O(n2)

B:O(n)

C:O(n+e)

D:O(e)

答案:A第八章测试在表长为ｎ的链表中进行线性查找，它的平均查找长度为（

）。

A:ＡＳＬ＝ｎ

B:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

C:

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

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

）次后查找成功。

A:1

B:2

C:8

D:4

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

）。

A:O(n2)

B:O(log2n)

C:O(n)

D:O(nlog2n)

答案:B链表适用于以下（

）查找

A:顺序

B:随机

C:二分法

D:顺序，也能二分法

答案:A

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

）存储结构的线性表。

A:散列存储

B:顺序存储或链接存储

C:压缩存储

D:索引存储

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

）。

A:以链接方式存储

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

C:以顺序方式存储

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

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

）。

A:35/12

B:43/12

C:39/12

D:37/12

答案:D碰撞（冲突）指的是（

）。

A:负载因子过大

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

C:两个元素的关键码值不同，而非码属性相同

D:两个元素具有相同序号

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

）。

A:分块查找

B:折半查找

C:散列查找

D:顺序查找

答案:C散列法存储的基本思想是（

）。

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

B:查找与结点个数n无关

C:顺序查找

D:以顺序方式且结点按关键字有序排序

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

）。

A:偶数

B:整数

C:小数

D:素数

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

）个结点最佳。

A:10

B:25

C:625

D:6

答案:B平衡二叉树上的平衡因子只能取（

）。

A:-1

B:0

C:1

D:-1,0,1

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

）。

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

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

C:左、右子树也分别是二叉排序树

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

答案:B

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

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

A:RR

B:LL

C:RL

D:LR

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

）。

A:选择排序

B:插入排序

C:冒泡排序

D:归并排序

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

）。

A:选择排序

B:冒泡排序

C:插入排序

D:归并排序

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

）。

A:O(n)

B:O(n3)

C:O(nlog2n)

D:O(n2)

答案:D下列关键字序列中，（

）是堆。

A:16，23，53，31，94，72

B:94，23，31，72，16，53

C:16，72，31，23，94，53

D:16，53，23，94，31，72

答案:A下述几种排序方法中，（

）是稳定的排序方法。

A:快速排序

B:堆排序

C:希尔排序

D:归并排序

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

）。

A:起泡排序

B:选择排序

C:希尔排序

D:插入排序

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

）。

A:选择排序

B:快速排序

C:归并排序

D:插入排序

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

）次。

A:5

B:3

C:6

D:4