《数据结构与算法》二

您的姓名： [填空题] *

_________________________________

一、单选题

1. 深度优先搜索遍历类似于二叉树的（）. [单选题] * A. 先序遍历(正确答案) B. 中序遍历 C. 后序遍历 D. 按层次遍历

2. 无向图顶点v的度是关联于该顶点（）的数目. [单选题] * A. 顶点 B. 边(正确答案) C. 序号 D. 下标

3. 有n个顶点的无向图的邻接矩阵是用（）数组存储。. [单选题] * A. 一维

B. n行n列(正确答案) C. 任意行n列 D. n行任意列

4.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）. [单选题] *

A. n-1 B. n+1 C. n(正确答案) D. n+e

5. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）. [单选题] * A. k1

B. k2(正确答案) C. k1-k2 D. k1+k2

6. 广度优先遍历类似于二叉树的（）. [单选题] * A. 先序遍历 B. 中序遍历 C. 后序遍历

D. 按层次遍历(正确答案)

7. 任何一个无向连通图的最小生成树（）. [单选题] * A. 只有一棵

B. 有一棵或多棵(正确答案) C. 一定有多棵 D. 可能不存在

二、多选题

8. 在某图中，下列选项中说法不正确的是（）. *

A. 不存在顶点到自身的边，或者重复的边，则该图是简单图

B. 不存在顶点到自身的边，或者重复的边，则该图是复杂图(正确答案) C. 不存在顶点到自身的边，或者重复的边，则该图是无向图(正确答案) D. 不存在顶点到自身的边，或者重复的边，则该图是有向图(正确答案)

9. 有关图的说法不正确的是（）. * A. 有向图的边是有向的，又称为弧

B. 有向图的边是有向的，又称为箭头(正确答案) C. 有向图的边是有向的，又称为边角(正确答案) D. 无正确答案(正确答案)

10. 关于有向图的说法不正确的是（）。 * A. 有向图边是有向的

B. 有向图边是无向的(正确答案)

C. 有向图边是可以有向也可以无向(正确答案) D. 无正确答案(正确答案)

11. 对图中顶点的集合，不正确的是（）. * A. 可以为空(正确答案) B. 不可以为空

C. 空与不空都可以(正确答案) D. 都不对(正确答案)

12. 对图的边或弧上的数的说法错误的是（）. * A. 量(正确答案) B. 值(正确答案) C. 权

D. 重(正确答案)

三、判断题

13. 有向图不能进行广度优先遍历。（）. [单选题] * A. 对

B. 错(正确答案)

14. 若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。（）. [单选题] * A. 对(正确答案) B. 错

15. 若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。（）. [单选题] * A. 对(正确答案) B. 错

16. 无向边是指没有方向的边。（）. [单选题] * A. 对(正确答案) B. 错

17. 用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（）. [单选题] * A. 对

B. 错(正确答案)

18. 图的遍历有：深度优先搜索和广度优先搜索等方法。（） [单选题] * A. 对(正确答案) B. 错

19. n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n*n）。（） [单选题] * A. 对(正确答案) B. 错

20. 图的逆邻接表存储结构只适用于无向图。（）. [单选题] * A. 对

B. 错(正确答案)

一、单选题

1.在图的表示法中，表示形式唯一的是（）. [单选题] * A. 邻接矩阵表示法(正确答案) B. 邻接表表示法 C. 逆邻接表表示法 D. 邻接表和逆临界表表示法

2. 在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（）. [单选题] * A. n B. e C. 2n D. 2e(正确答案)

3. 连通分量是（）的极大连通子图. [单选题] * A. 树 B. 图

C. 无向图(正确答案) D. 有向图

4. 下列关于图的存储结构叙述正确的是（）. [单选题] *

A. 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关(正确答案)

B. 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点无关 C. 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关 D. 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关

5. 设无向图的顶点个数为n，则该图最多有（）条边. [单选题] * A. n-1 B. n*n C. n(n+1)/2 D. n(n-1)/2(正确答案)

6. 带权的图称为（）. [单选题] * A. 权

B. 网(正确答案) C. 有向图 D. 路径

7. 两顶点之间的边有方向，则该边被称为（）. [单选题] * A. 无向边

B. 有向边(正确答案) C. 混合边 D. 都不对

8. 无向图的边都是（）. [单选题] * A. 可以无向也可以有向

B. 有向的 C. 无向的(正确答案) D. 以上都不对

二、多选题

9. 关于图，下列选项中说法不正确的是（）. * A. 任意两顶点之间的边都是有向边，则该图是有向图

B. 任意两顶点之间的边都是有向边，则该图是无向图(正确答案) C. 任意两顶点之间的边都是有向边，则该图是不确定(正确答案) D. 无正确答案(正确答案)

10. 关于边，下列选项中说法不正确的是（）. *

A. 两顶点之间的边有方向，则该边被称为无向边(正确答案) B. 两顶点之间的边有方向，则该边被称为有向边 C. 两顶点之间的边有方向，则该边被称为混合边(正确答案) D. 无正确答案(正确答案)

11. 无向图中，两顶点之间有边则不正确的是（）. * A. 互为兄弟(正确答案) B. 互为堂兄弟(正确答案) C. 互为邻接点 D. 互为邻居(正确答案)

12. 图中的边的集合错误的是（）. * A. 不可以为空(正确答案) B. 必须为空(正确答案) C. 可以为空

D. 都不对(正确答案)

13. 图按照边的不同，可分为（）. * A. 有向图(正确答案) B. 无向图(正确答案) C. 混合图 D. 以上都不对

三、判断题

14. 图的边或弧上的数称之为权。（）. [单选题] * A. 对(正确答案) B. 错

15. 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的入度 。（）[单选题] * A. 对(正确答案) B. 错

16. 图是一对多的结构（）. [单选题] * A. 对

B. 错(正确答案)

17. 图的存储结构有邻接矩阵、邻接表、十字链表。（）. [单选题] * A. 对(正确答案) B. 错

18. 有向图中，指向该结点的弧的数目称之为入度。（）. [单选题] * A. 对(正确答案)

. B. 错

19. 邻接矩阵是图的一种存储结构。（） [单选题] * A. 对(正确答案) B. 错

20. 对于具有n个顶点的图，其生成树有且仅有n条边。（）A. 对

B. 错(正确答案)

一、单选题

1. 在顺序表的查找中，顺序查找是指（）. [单选题] * A. 跳跃式比较

B. 用逐一比较的办法顺序查找关键字(正确答案) C. 随机选择位置比较 D. 无正确答案

2. 关于关键字，下列选项中说法正确的是（）. [单选题] * A. 主关键字是可以唯一标识一条记录的关键字(正确答案) B. 主关键字是可以识别若干记录的关键字 C. 主关键字是在表中出现的次数很多的关键字 D. 无正确答案

3. 关于查找表，以下说法正确的是（）. [单选题] * A. 若查找表中存在特定元素称为查找失败 B. 若查找表中存在特定元素称为查找中 C. 若查找表中存在特定元素称为未找到

单选题] * [ D. 若查找表中存在特定元素称为查找成功(正确答案)

4. 对线性表进行折半查找时，要求线性表必须（） [单选题] * A. 以顺序方式存储

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

D. 以顺序方式存储，且结点按关键字有序排序(正确答案)

5. 查找表是以（）为查找结构. [单选题] * A. 集合(正确答案) B. 图 C. 树 D. 文件

6. 衡量查找算法效率的主要标准是（）. [单选题] * A. 元素个数 B. 所需的存储量 C. 平均查找长度(正确答案) D. 算法难易程度

7. 在表长为ｎ的链表中进行线性查找，它的平均查找长度为（）. [单选题] * A. ASL＝n

B. ASL＝(n+1)/2(正确答案) C. ASL＝n^(1/2) + 1 D. ASL≈log2n

8. 链表适用于（）查找. [单选题] * A. 顺序(正确答案)

B. 二分 C. 随机 D. 顺序或二分

二、多选题

9. 有一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数不为（）. * A. 33/11

B. 34/11(正确答案) C. 32/11(正确答案) D. 35/11(正确答案)

10. 顺序查找法不适合于（）的存储结构. * A. 散列存储(正确答案) B. 顺序存储或链接存储 C. 压缩存储(正确答案) D. 索引存储(正确答案)

11. 采用二分查找方法查找长度为n的线性表时，时间复杂度不是（）（）. * A. O（n*n）(正确答案) B. O（nlog2n）(正确答案) C. O（n）(正确答案) D. O（log2n）

12. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时，查找成功后的比较次数不是（）. * A. 1(正确答案)

B. 2(正确答案) C. 4

D. 8(正确答案)

13. 对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式不为（）. * A. 从第0个元素往后查找该数据元素(正确答案) B. 从第n个元素往开始前查找该数据元素 C. 从第1个元素往后查找该数据元素(正确答案) D. 与查找顺序无关(正确答案)

三、判断题

14. 顺序查找法的平均查找长度为（n+1）/2。（）. [单选题] * A. 对(正确答案) B. 错

15. 查找表是不同类型的数据元素构成的集合。（）. [单选题] * A. 对

B. 错(正确答案)

16. 静态查找表是查找特定元素的查找表。（）. [单选题] * A. 对(正确答案) B. 错

17. 关键字是用于标识一个数据元素的某个数据项的值。（）. [单选题] * A. 对(正确答案) B. 错

18. 在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。（）. [单选题] * A. 对

B. 错(正确答案)

19. 顺序查找法，表中元素可以任意存放。（）. [单选题] * A. 对(正确答案) B. 错

20. 顺序查找不属于静态查找。（）. [单选题] * A. 对

B. 错(正确答案)

一、单选题

1. 边查找，边改变集合内的元素的查找表是（）. [单选题] * A. 静态查找表

B. 动态查找表(正确答案) C. 混合查找表 D. 都不对

2. 二叉排序树的叶子结点个数为5个，则度为2的结点的数目是（）. [单选题] * A. 6 B. 5 C. 4(正确答案) D. 3

3. 根据二叉排序树的特点，查找过程类似于（）. [单选题] *

A. 顺序查找

B. 折半查找(正确答案) C. 随机查找 D. 都不对

4. 二叉排序树是否可能是一棵完全二叉树（） [单选题] * A. 不可能 B. 可能(正确答案) C. 不确定能不能 D. 都不对

5. 二叉排序树的第3层最多有多少个结点（）. [单选题] * A. 2

B. 4(正确答案) C. 8 D. 1

6. 数据结构中，只查找，不改变集合内的元素的查找表是（）. [单选题] * A. 动态查找表

B. 静态查找表(正确答案) C. 混合查找表 D. 都不对

7. 数据结构与算法里，根据二叉排序的定义可知（）. [单选题] * A. 二叉排序树的右子树上结点的值小于根结点的值 B. 二叉排序树的右子树上结点的值大于根结点的(正确答案) C. 二叉排序树的右子树上结点的值等于根结点的值

D. 二叉排序树的右子树上结点的值小于等于根结点的值

8. 数据结构与算法里，关于二叉排序树的递归性说法对的是（）. [单选题] * A. 二叉排序树的左子树也是任意二叉树

B. 二叉排序树的左子树也是二叉排序树(正确答案) C. 二叉排序树的左子树也是普通树 D. 以上都不对

二、多选题

9. 二叉排序的的哪些遍历序列，不能得到一个升序序列，或非递减有序序列（）. * A. 先序序列(正确答案) B. 中序序列 C. 后序序列(正确答案) D. 按层次遍历序列(正确答案)

10. 已知一棵树是二叉排序树，则该树满足（）. *

A. 若左子树不为空，则左子树上的所有结点的值（关键字）都小于根节点的值；(正确答案)

B. 若右子树不为空，则右子树上的所有结点的值（关键字）都大于根节点的值；(正确答案)

C. 左、右子树都分别为二叉排序树；(正确答案) D. 其中序序列是一个非递减有序序列；(正确答案)

11. 动态查找不包括（）查找. * A. 顺序查找(正确答案) B. 二叉排序树 C. 有序表(正确答案) D. 索引顺序表(正确答案)

12. 动态查找表：边查找，边改变集合中的元素，改变的方式可以是（）. * A. 增加(正确答案) B. 删除(正确答案) C. 移动 D. 交换

13. 关于二叉排序树描述有误的是（）. *

A. 二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案) B. 二叉排序的左子树上结点的关键字小于右子树上的结点的关键字 C. 二叉排序的根结点的关键大于右子树上结点的关键字(正确答案) D. 二叉排序的根结点的关键大于左子树上结点的关键字

三、判断题

14. 二叉排序树的左子树一定是棵二叉排序树 。（）. [单选题] * A. 对(正确答案) B. 错

15. 动态查找表：表结构在查找过程中动态生成。（）. [单选题] * A. 对(正确答案) B. 错

16. 动态查找常用的是二叉排序树。（）. [单选题] * A. 对(正确答案) B. 错

17. 在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。（）. [单选题] *

A. 对

B. 错(正确答案)

18. 在二叉排序树中，根结点的值都小于孩子结点的值。（）. [单选题] * A. 对

B. 错(正确答案)

19. 动态查找表属于集合结构。（）. [单选题] * A. 对

B. 错(正确答案)

20. 二叉排序树根的左子树上的结点的值都小于根的右子树上的结点的值。（）. [单选题] * A. 对(正确答案) B. 错

一、单选题

1. 数据结构与算法里，关于二叉排序树的中序序列描述正确的是（）. [单选题] * A. 二叉排序树的中序遍历序列是升序序列(正确答案) B. 二叉排序树的中序遍历序列是降序序列 C. 二叉排序树的中序序遍历列是乱序序列 D. 无正确答案

2. 二叉排序树是（）经常使用的方式. [单选题] * A. 动态查找(正确答案) B. 静态查找 C. 随机查找

D. 都不对

3. 二叉排序树的定义具有（）性. [单选题] * A. 反复

B. 递归(正确答案) C. 回溯 D. 都不对

4. 先序遍历一颗二叉排序树的顺序是（）. [单选题] * A. 左子树 根 右子树 B. 左子树 根 右子树 C. 根 左子树 右子树(正确答案) D. 都不对

5. 只查找不改变集合内的元素的查找表是（）. [单选题] * A. 动态查找

B. 静态查找(正确答案) C. 不确定 D. 都不对

6. 二叉排序树的（）上结点的值都小于根结点的值。. [单选题] * A. 左子树(正确答案) B. 右子树 C. 左子树和右子树 D. 都不对

7. 数据结构与算法里，关于二叉排序树的遍历顺序说法正确的是（）. [单选题] * A. 中序遍历一颗二叉排序树的顺序是：左子树 根结点 右子树(正确答案)

B. 中序遍历一颗二叉排序树的顺序是：根结点 左子树 右子树 C. 中序遍历一颗二叉排序树的顺序是：左子树 右子树 根结点 D. 无正确答案

8. 数据结构与算法里，关于二叉排序树的结点个数为0时，描述正确的是（）. [单选题] *

A. 二叉排序树可以含有0个结点，这时它是一棵空二叉排序树(正确答案) B. 二叉排序树可以含有0个结点，这时它是一棵满二叉排序树 C. 二叉排序树可以含有0个结点，这时它是一棵完全二叉排序树 D. 无正确答案

二、多选题

9. 下列选项中说法正确的是（）. * A. 查找表有静态查找表法(正确答案) B. 查找表有动态查找表法(正确答案) C. 查找表分为混合查找表 D. 查找表分为物理查找表

10. O(n)是以下哪种算法的复杂度（）. * A. 顺序表直接获取某个下标位置的值 B. 顺序表删除元素(正确答案) C. 顺序表插入元素(正确答案) D. 单链表查找第i个元素(正确答案)

11. 查找的结果可能在集合中也可能不在集合中，分别称为（）. * A. 查找成功(正确答案) B. 查找失败(正确答案)

C. 不确定 D. 都不对

12. 查找表采用顺序存储结构简称为顺序表，顺序表的查找方式有（）. * A. 折半查找(正确答案) B. 顺序查找(正确答案) C. 随机查找 D. 都不对

13. 二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根不可能是:（）. * A. F(正确答案) B. E(正确答案) C. G

D. H(正确答案)

三、判断题

14. 中序遍历二叉排序树是降序序列。（）. [单选题] * A. 对

B. 错(正确答案)

15. 查找表是以集合为结构的。（）. [单选题] * A. 对(正确答案) B. 错

16. 顺序查找与折半查找前提一样。（）. [单选题] * A. 对

B. 错(正确答案)

17. 顺序查找的前提，顺序存储可以，链式存储也可以。（）. [单选题] * A. 对(正确答案) B. 错

18. 二叉排序树是递归定义的，因为要求的它的左右子树也必须是二叉排序树。（）. [单选题] * A. 对(正确答案) B. 错

19. 顺序查找即用逐一比较的办法顺序查找关键字。（）. [单选题] * A. 对(正确答案) B. 错

20. 二叉排序树的中序序列是一个降序序列或非递增有序序列。（）. [单选题] * A. 对

B. 错(正确答案)