23春数据结构与算法-03

关注公众号【国开搜题】，回复【试题】获取试题答案

一 、单选题

1. 线性表采用链式存储时，结点的存储地址（ ）。

必须是不连续的

和头结点的存储地址相连续

必须是连续的

连续与否均可

答案：D
- 关注公众号【国开搜题】，对话框内发送试题，获得答案。

2. 若入栈序列为a, b, c，则可能得到的a, b, c的不同的出栈序列个数为（ ）。

4

5

6

7

答案：B
- 关注公众号【国开搜题】，对话框内发送试题，获得答案。

3. 1234按顺序入栈，可能的出栈序列为（ ）。

4312

3124

2341

4132

答案：C
- 关注公众号【国开搜题】，对话框内发送试题，获得答案。

4. 下面有关回溯法的描述，错误的是（ )。

一种组织得井井有条的，能避免不必要搜索的穷举式搜索法

大多回溯法解决的问题会用到栈这种数据结构

问题的解空间由满足隐式约束条件的所有解向量构成

一个所有孩子已经产生的结点称作死结点

答案：C
- 关注公众号【国开搜题】，对话框内发送试题，获得答案。

5. 下面问题不适合用分治法来求解的是（ )。

N后问题

归并排序

折半查找

循环赛日程安排

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

6. 设一组初始记录关键字序列为(25，36，48，51，64，76，89，93,108),则利用折半查找关键字93需要比较的关键字个数为 ( )。

1

2

3

4

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

7. 设一组初始记录关键字序列为(5，9，17，26，32，43，58，67)，则利用顺序查找方法查找关键字32需要比较的关键字个数为 ( )。

1

5

9

10

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

8. 高度为4的二叉树，树中最少有（ ）个结点。

4

8

16

15

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

9. 高度为3的二叉树，树中最多有（ ）个结点。

5

6

7

8

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

10. 下列不是前缀码的是（ ）。

110，10，01，00

000，001，010，10

001，010，000，01

001，01，11，10

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

11. 串S1=“mn56”，S2=“mn56hk”，则S1 （ ） S2。

>

<

=

不确定

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

12. 广义表G=(a,(b,c),(a,(b,c),d))的长度为（ ）。

1

2渝粤题库

3

4

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

13. 下列哪项不是稀疏矩阵的链式存储方式？( ）。

三元组顺序表

三元组行（列）链表

十字链表

三元组单链表

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

14. 对序列{45 35 62 12 20 90}进行简单选择排序，第一趟扫描排序结果为( )。

12 45 35 20 62 90

12 20 62 45 35 90

12 20 35 45 62 90

12 35 62 45 20 90

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

15. 对序列{30 85 15 78 06 33 45}进行快速排序，第一趟扫描排序结果为（ )。

06 85 15 78 30 33 45

06 15 30 78 85 33 45

30 85 15 78 06 33 45

30 15 78 06 33 45 85

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

16. 有如下语句： for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) y=y-1; 该语句的时间复杂度为（ ）。

O(n)

O(n2)

O(1)

O(n3)国开一网一平台渝粤题库，我们的目标是要做全覆盖、全正确的答案搜索服务。

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

17. 有如下语句： for(i=1;i<=n*n;i++) sum=sum+i; 该语句的时间复杂度为（ ）。

O(n)

O(n2)

O(1)

O(n3)

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

18. 对于下面的图，从结点3开始进行深度优先搜索，不可能的搜索结果是（ )。

3,1,4,2,5,0

3,2,1,4,0,5

3,5,2,1,4,0渝粤搜题

3,5,2,4,1,0

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

19. 对于下面的图，从结点5开始进行广度优先搜索，可能的搜索结果是（ )。

5,0,1,2,3,4

5,2,4,3,1,0

5,2,1,0,4,3

5,3,2,1,4,0

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

20. 对于下面的图，从结点4开始进行深度优先搜索，不可能的搜索结果是（ )。

4,1,2,3,5,0

4,3,2,1,0,5

4,1,2,5,3,0

4,0,1,2,3,5

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

二 、判断题

1. 除空树外，树一定有一个根结点。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

2. 线索二叉树线索化的过程就是给原二叉树加上前驱后继线索的过程。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

3. 先序序列和后序序列可以构造出一棵唯一的二叉树。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

4. 数据结构从存储结构上可以分为顺序存储结构和链式存储结构。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

5. 度量算法的效率时，经常使用的方法是事后统计法。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

6. 顺序查找中待查元素为第一个元素时查找速度最快。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。渝粤搜题

7. 平衡二叉树的左子树和右子树都是平衡二叉树。

√国开搜题

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

8. 广义表可以被其他广义表共享。国开搜题

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

9. 单字符链表每个结点只存储一个字符。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

10. 回溯法常用来求解一些组合数较大的问题。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。渝粤搜题

11. 汽车加油问题是用贪心算法来解决的。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

12. 图的遍历过程中，有些顶点可以多次访问。

√国开一网一平台

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。渝粤教育

13. 6个顶点的无向图，可以有10条边。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

14. 图的遍历把所有顶点排成了一个线性序列。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

15. 快速排序中，进行比较和交换是从两端向中间进行，相对应冒泡排序来说，记录移动的距离较远，移动次数较少。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

16. 堆排序是利用堆顶元素的关键字最小（或最大）这个特点实现排序。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

17. 归并排序是稳定的排序算法。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

18. 已知入队的序列是ABCD，则出队序列可以是DCBA。

√

×渝粤题库，我们的目标是要做全覆盖、全正确的答案搜索服务。

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

19. 打印机作业排队队列具备后进先出的性质。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

20. 线性表中除最后一个元素之外的每个元素均有唯一的“直接后继”。

√

×

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

三 、选择填空题

1. ①

O(1)

O(n)

O(log2n)

O(n)

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

2. ①

1渝粤搜题

n-2

n-1渝粤题库

n渝粤题库，我们的目标是要做全覆盖、全正确的答案搜索服务。

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

3. ①

push

pop

peek

set

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

4. ①

O(n)

O(n2)渝粤教育

O(nlog2n)

O(nn)

答案：关注公众号【国开搜题】，对话框内发送试题，获得答案。

关注公众号【国开搜题】，回复【试题】获取试题答案