智慧树知到答案数据结构（海南联盟）最新答案

第三章 单元测试

1、单选题：
栈的插入和删除操作在（ ）

选项：
A:栈顶

B:任意位置

C:栈底

D:指定位置

答案:

2、单选题：
五节车厢以编号a，b，c，d，e顺序进入铁路调度站（栈），可以得到（  ）的编组

选项：
A:b，d，a，c，e

B:c，e，d，b，a

C:c，d，e，a，b

D:a，c，e，b，d

答案:

3、单选题：
判定一个顺序栈S（栈空间大小为n）为空的条件是（ ）

选项：
A:S->top!=n

B:S->top==0

C:S->top==n

D:S->top!=0

答案:

4、单选题：
在一个链队列中，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;

答案:

5、单选题：
一个队列的入队序列是1，2，3，4，则队列的出队序列是（  ）

选项：
A:3，4，1，2

B:4，3，2，1

C:1，4，3，2

D:1，2，3，4

答案:

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

选项：
A:d
B:b
C:a

D:c
答案:

7、判断题：
栈是一种非线性结构。

选项：
A:对
B:错
答案:

8、判断题：
队列允许在一端进行插入，另一端进行删除操作。

选项：
A:对
B:错
答案:

9、判断题：
在程序设计语言中实现递归操作是用到栈实现的。

选项：
A:错
B:对
答案:

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

选项：
A:错
B:对
答案:

11、判断题：
在表达式求值算法中运用到队列来实现的。

选项：
A:错
B:对
答案:

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

选项：
A:错
B:对
答案:

13、判断题：
队列Q满的条件是：Q.front==Q.rear。

选项：
A:对
B:错
答案:

14、判断题：
每当在新队列中插入一个新元素时，尾指针rear增1。

选项：
A:对
B:错
答案:

15、判断题：
在顺序队列中，头指针始终指向队列的最后一个元素。

选项：
A:错
B:对
答案:

16、判断题：
在顺序队列中，尾指针始终指向队列尾元素的下一个位置。

选项：
A:错
B:对
答案:

第四章 单元测试

1、单选题：
串的长度是指（   ）
选项：
A:串中所含不同字母的个数
B:串中所含非空格字符的个数
C:串中所含不同字符的个数
D:串中所含字符的个数
答案:

2、单选题：
设有串t=’I am a good student ‘，那么Substr(t,6,6)=（  ）
选项：
A:good
B:student
C:a good
D:a good s
答案:

3、单选题：
串“ababaaababaa”的next数组为（ ）
选项：
A:012121111212
B:0123012322345
C:012345678999
D:011234223456
答案:

4、单选题：
函数substr(“DATASTRUCTURE”，5，9)的返回值为（    ）
选项：
A:“DATA”
B:“DATASTRUCTURE”
C:“STRUCTURE”
D:“ASTRUCTUR”
答案:

5、单选题：
设有两个串p和q，求q在p中首次出现的位置的运算称作（   ）
选项：
A:求子串
B:模式匹配
C:连接
D:求串长
答案:

6、单选题：
设串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:BCDEF
B:BCDEFG
C:BCPQRST
D:BCDEFEF
答案:

7、单选题：

若串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###G1234

C:ABC###G0123
D:ABC###G2345

答案:

8、单选题：
主串为’abaababaddecab’ ,模式串为’abad’。使用KMP算法需要（  ）次匹配成功。
选项：
A:5
B:12
C:4
D:10
答案:

9、判断题：
不包含任何字符的串称为空白串。
选项：
A:错
B:对
答案:

10、判断题：
在串的模式匹配运算中，被匹配的主串称为模式。
选项：
A:错
B:对
答案:

11、判断题：
组成串的数据元素只能是字符。
选项：
A:对
B:错
答案:

12、判断题：
串不能采用顺序存储结构进行存储。
选项：
A:错
B:对
答案:

13、判断题：
模式匹配简单算法时间复杂度是O(m*n)。
选项：
A:对
B:错
答案:

14、判断题：
空格串与空串的没有区别。
选项：
A:对
B:错
答案:

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

选项：
A:错
B:对
答案:

16、判断题：
两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。
选项：
A:对
B:错
答案:

17、判断题：
串是一种非线性结构。
选项：
A:错
B:对
答案:

18、判断题：
串的模式匹配算法只能采用串的链式存储结构来实现。
选项：
A:错
B:对
答案:

第五章 单元测试

1、单选题：
设二维数组A[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素a_ij占d个字节，则元素a_ij的地址为（  ）
选项：
A:LOC(a₀₀)+((j-1)*n+i-1)*d
B:LOC(a₀₀)+(i*n+j)*d
C:LOC(a₀₀)+((i-1)*n+j-1)*d
D:LOC(a₀₀)+(j*n+i-1)*d
答案:

2、单选题：
若数组A[0..m-1][0..n-1]按列优先顺序存储，则a_ij地址为（）
选项：
A:LOC(a₀₀)+j*n+I
B:LOC(a₀₀)+(j-1)*n+i-1
C:LOC(a₀₀)+j*m+i
D:LOC(a₀₀)+(j-1)*m+I-1
答案:

3、单选题：
若下三角矩阵A_n*n，按行顺序压缩存储在数组a[0..(n+1)n/2]中，则非零元素a_ij的地址为（）（设每个元素占d个字节）
选项：
A:LOC(a₀₀)+((i-1)i/2+j-1)*d
B:LOC(a₀₀)+((i+1)i/2+j)*d
C:LOC(a₀₀)+((j-1)j/2+i)*d
D:LOC(a₀₀)+((i-1)i/2+i-1)*d
答案:

4、单选题：
稀疏矩阵一般的压缩存储方法有两种，即（）
选项：
A:三元组和十字链表
B:散列和十字链表
C:二维数组和三维数组
D:三元组和散列
答案:

5、单选题：
广义表A=((x,(a,b)),((x,(a,b)),y))，则运算head(head(tail(A)))为（   ）
选项：
A:(x,(a,b))
B:A
C:x
D:(a,b)
答案:

6、判断题：
二维数组可以看成是一个线性表。
选项：
A:错
B:对
答案:

7、判断题：
不做插入删除操作的数组，采用顺序存储结构表示数组比较合适。
选项：
A:对
B:错
答案:

8、判断题：
二维数组的顺序存储方法只可以行序为主序的存储方式。
选项：
A:错
B:对
答案:

9、判断题：
对称矩阵在存储时可进行压缩存储。
选项：
A:对
B:错
答案:

10、判断题：
稀疏矩阵是非零值元素分布有一定规律的矩阵。
选项：
A:错
B:对
答案:

第六章 单元测试

1、单选题：
一棵具有67个结点的完全二叉树，它的深度为（      ）。
选项：
A:9
B:8
C:6
D:7
答案:

2、单选题：
给定树如图所示，请列出的中序遍历序列（    ） 。

选项：
A:DABECF
B:ABDCEF
C:DBEFCA
D:DBAECF
答案:

3、单选题：
设有树如图所示，则结点g的度为（     ）。 

选项：
A:4
B:1

C:3
D:2
答案:

4、单选题：
用4个权值{7, 2, 4, 5}构造的哈夫曼（Huffman）树的带权路径长度是（     ）。
选项：
A:35
B:32
C:34
D:33
答案:

5、单选题：
对于任何一棵具有n个结点的线索二叉树，具有（    ）个线索。
选项：
A: n+1
B: n
C: n-1
D: 0
答案:

6、单选题：
一棵深度为5的满二叉树有（     ）个分支结点。
选项：
A:16
B:14
C:7
D:15
答案:

7、单选题：
一棵深度为5的满二叉树有（    ）个叶子。
选项：
A:17
B:32
C:16
D:31
答案:

8、单选题：
给定二叉树如图所示，请列出的后序遍历序列（     ） 。
选项：
A:BDECA
B:ABCDE
C:BACDE
D:BADCE
答案:

9、单选题：
设有二叉树如图所示，按其中序遍历次序遍历，对于根a的右子树最先访问的结点是（     ）。
选项：
A:b
B:d
C:h
D:a

答案:

10、单选题：
若按层序对深度为6的完全二叉树中全部结点从１开始编号，则编号为10的结点其右孩子的编号为（    ）。
选项：
A:12
B:11

C:20

D:21
答案:

11、判断题：
二叉树的子树无左右之分的。
选项：
A:错
B:对
答案:

12、判断题：
二叉树的度大于2的树。
选项：
A:对
B:错
答案:

13、判断题：
二叉树是非线性数据结构。
选项：
A:对
B:错
答案:

14、判断题：
二叉树不能转换为树，树也不能转换为二叉树。
选项：
A:对
B:错
答案:

15、判断题：
哈夫曼（Huffman）树的带权路径长度是最小的。
选项：
A:错
B:对
答案:

16、判断题：
满二叉树就是一种特殊的完全二叉树。
选项：
A:对
B:错
答案:

17、判断题：
假设n(n>0)个结点的树，它有且只有1个根结点。
选项：
A:对
B:错
答案:

18、判断题：
n个结点的线索二叉树中线索的数目是不确定的。
选项：
A:对
B:错
答案:

19、判断题：
不含任何结点的空树，它可以是一棵树也是一棵二叉树。
选项：
A:错
B:对
答案:

20、判断题：
可以采用递归的方法计算二叉树的深度。
选项：
A:错
B:对
答案:

第七章 单元测试

1、单选题：
无向图的邻接矩阵是一个(    )
选项：
A:对角阵
B:对称矩阵
C:零矩阵
D:上三角矩阵
答案:

2、单选题：
若图G(V,E)中含有7个顶点，则保证图G在任何情况下都是连通的需要的边数最少是(   )
选项：
A:15
B:21
C:16
D:6
答案:

3、单选题：
如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所以顶点，则该图一定是(  )
选项：
A:连通图
B:有回路
C:完全图
D:一棵树
答案:

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

5、单选题：
已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3), (3,4)}，则从顶点1出发按深度优先遍历的结点序列是（    ）。
选项：
A:2 3 1 4
B:1 4 3 2
C:1 4 2 3
D:1 2 3 4
答案:

6、单选题：
已知图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3), (3,4)}，则从顶点1出发按广度优先遍历的结点序列是（     ）。
选项：
A:1 3 4 2
B:1 3 2 4
C:1 4 3 2
D:1 2 4 3
答案:

7、单选题：
任何一个无向连通图的最小生成树（     ）。
选项：
A:只有一棵
B:一棵或多棵
C:可能不存在
D:一定有多棵
答案:

8、单选题：
有8个结点的无向图最多有（    ）条边。
选项：
A:56
B:28
C:14
D:112
答案:

9、单选题：
有8个结点的无向连通图最少有（     ）条边。
选项：
A:5
B:6
C:7
D:8
答案:

10、单选题：
有8个结点的有向完全图有（    ）条边。
选项：
A:14
B:28
C:112
D:56
答案:

11、单选题：
已知无向图的顶点集合U={1,2,3,4},边的集合TE={(1,2),(1,3),(2,3), (3,4)}，则顶点3的度是（     ）。
选项：
A:3
B:0
C:1
D:2
答案:

12、单选题：
已知有向图的顶点集合U={1,2,3,4},弧的集合TE={<1,2>,<1,3>,<2,3>,<3,4>}，则该有向图的拓扑排序序列是（     ）。
选项：
A:1 2 3 4
B:4 3 2 1
C:1 4 2 3
D:1 3 2 4
答案:

13、单选题：
图的深度优先遍历序列（  ）。
选项：
A:只有一个
B:不存在
C:可以有多个
D:无
答案:

14、单选题：
拓扑排序算法是通过重复选择具有（    ）个前驱顶点的过程来完成的。
选项：
A:3
B:0
C:2
D:1
答案:

15、单选题：
n个顶点e条边的图采用邻接表存储，该算法的时间复杂度为（     ）。
选项：
A:O(e)
B:O(n+e)
C:O(n2)
D:O(n)
答案:

16、单选题：
n个顶点e条边的图采用邻接矩阵存储，该算法的时间复杂度为（    ）。
选项：
A:O(n+e)
B:O(n)
C:O(n2)
D:O(e)
答案:

第八章 单元测试

1、单选题：
在表长为ｎ的链表中进行线性查找，它的平均查找长度为（      ）。
选项：
A:ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
B:ＡＳＬ＝ｎ
C:ＡＳＬ＝（ｎ＋１）／２
D:
答案:

2、单选题：
有一个有序表（1，3，9，12，32，41，45，62，75，77，82，95，100），当折半查找有序表中值为82的结点时，则它与表元素中比较了（    ）次后查找成功。
选项：
A:8
B:4
C:1
D:2
答案:

3、单选题：
采用折半查找方法查找长度为n的 线性表时，每个元素的平均查找长度为（    ）。
选项：
A:O(n²)
B:O(nlog₂n)
C:O(n)
D:O(log₂n)
答案:

4、单选题：
链表适用于以下（     ）查找
选项：
A:随机
B:顺序，也能二分法
C:二分法
D:顺序
答案:

5、单选题：
顺序表查找法适合于以下（     ）存储结构的线性表。
选项：
A:索引存储
B:压缩存储
C:散列存储
D:顺序存储或链接存储
答案:

6、单选题：
对线性表进行二分查找时，要求线性表必须（    ）。
选项：
A:以顺序方式存储
B:以链接方式存储
C:以顺序方式存储，且结点按关键字有序排序
D:以链接方式存储，且结点按关键字有序排序
答案:

7、单选题：
有一个长度为12的有序表，按二分查找对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（    ）。
选项：
A:39/12
B:35/12
C:43/12
D:37/12
答案:

8、单选题：
碰撞（冲突）指的是（     ）。
选项：
A:两个元素具有相同序号
B:不同关键码值对应到相同的存储地址
C:负载因子过大
D:两个元素的关键码值不同，而非码属性相同
答案:

9、单选题：
在各种查找方法中，平均查找长度与结点个数n无关的查找方法是（     ）。
选项：
A:分块查找
B:折半查找
C:顺序查找
D:散列查找
答案:

10、单选题：
散列法存储的基本思想是（     ）。
选项：
A:以顺序方式且结点按关键字有序排序
B:由关键字的值决定数据的存储地址
C:顺序查找
D:查找与结点个数n无关
答案:

11、单选题：
在散列函数H(key)=key%p，p应取（     ）。
选项：
A:小数
B:整数
C:偶数
D:素数
答案:

12、单选题：
采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（     ）个结点最佳。
选项：
A:6
B:10
C:25
D:625
答案:

13、单选题：
平衡二叉树上的平衡因子只能取（     ）。
选项：
A:1
B:0
C:-1,0,1
D:-1
答案:

14、单选题：
以下对二叉排序树的描述不正确的是（    ）。
选项：
A:左、右子树也分别是二叉排序树
B:二叉排序树左子树上所有结点的值均小于它的根结点的值
C:二叉排序树右子树上所有结点的值均大于它的根结点的值
D:中序遍历一棵二叉树时可以得到一个结点值递减的序列
答案:

15、单选题：
假设在平衡二叉树上插入一个结点后造成了不平衡，其最近不平衡点为A，且已知A的左子树的平衡因子为-1，其右子树的平衡因子为0，应该进行（    ）型调整可使二叉树平衡。
选项：
A:LL
B:RL
C:LR
D:RR
答案:

第九章 单元测试

1、单选题：
从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（   ）。
选项：
A:选择排序
B:归并排序
C:冒泡排序
D:插入排序
答案:

2、单选题：
从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（   ）。
选项：
A:冒泡排序
B:选择排序
C:插入排序
D:归并排序
答案:

3、单选题：
对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（   ）。
选项：
A:O(n)
B:O(nlog₂n)
C:O(n³)
D:O(n²)
答案:

4、单选题：
下列关键字序列中，（   ）是堆。
选项：
A:16，53，23，94，31，72
B:94，23，31，72，16，53
C:16，23，53，31，94，72
D:16，72，31，23，94，53
答案:

5、单选题：
下述几种排序方法中，（   ）是稳定的排序方法。
选项：
A:希尔排序
B:快速排序
C:归并排序
D:堆排序
答案:

6、单选题：
在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（    ）。
选项：
A:希尔排序
B:插入排序
C:选择排序
D:起泡排序
答案:

7、单选题：
在待排序的元素序列基本有序的前提下，效率最高的排序方法是（     ）。
选项：
A:选择排序
B:快速排序
C:插入排序
D:归并排序
答案:

8、单选题：
在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（    ）次。
选项：
A:4
B:6
C:3
D:5
答案:

9、单选题：
大多数排序算法都有两个基本的操作：（    ）和（    ）。
选项：
A:插入和比较
B:插入和删除
C:比较和移动
D:移动和删除
答案:

10、单选题：
对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（    ）。
选项：
A:n-1
B:n(n-1)/2
C: n
D:n+1
答案:

11、单选题：
下列关于堆的描述不正确的是（    ）。
选项：
A:堆是利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大的或最小的记录
B:堆的形状是一棵完全二叉树
C:堆是一种选择排序
D:堆是一种插入排序
答案:

12、单选题：
若对n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是（    ）。
选项：
A:O(n²)
B:O(n³)
C:O(n)
D:O(nlog₂n)
答案:

13、单选题：
假设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则初始步长为4的希尔（shell）排序一趟的结果是（     ）。
选项：
A:F H C D P A M Q R S Y X
B:A D C R F Q M S Y P H X
C:P A C S Q H F X R D M Y
D:H C Q P A M S R D F X Y
答案:

14、单选题：
用某种排序方法对线性表（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排列时，元素序列的变化情况如下：(1) 25, 84, 21, 47, 15, 27, 68, 35, 20(2) 20, 15, 21,25, 47, 27, 68, 35, 84(3) 15, 20, 21, 25, 35, 27, 47, 68,84(4) 15, 20, 21, 25, 27, 35, 47, 68, 84则所有的排序方法是（     ）。
选项：
A:选择排序
B:快速排序
C:归并排序
D:插入排序
答案:

15、单选题：
有一组记录的排序码为（25, 48, 16, 35, 79, 82, 23, 40, 36, 72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并的结果是（     ）。
选项：
A:16 25 35 48 79 23 36 40 72 82
B:16 25 48 35 79 82 23 36 40 72
C:16 25 35 48 23 40 79 82 36 72
D:16 25 35 48 79 82 23 36 40 72
答案: