判断题

1. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。 正确

2. 顺序表查找是指在顺序存储结构上进行查找。 正确

3. 任何一棵二叉树的叶节点在三种遍历中的相对次序都是不变的。 正确

单选题

1. 在下列数据结构中，与所使用的计算机无关的是（A）。

A. 逻辑结构  B. 存储结构  C. 逻辑结构和存储结构  D. 物理结构

2. 采用开放定址法处理散列表的冲突时，其平均查找长度（D）。

A. 与链接法处理冲突相同  B. 高于二分查找  C. 低于链接法处理冲突  D. 高于链接法处理冲突

3. 若含有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（D）。

A. 9，5，3  B. 9，5，2，3  C. 1，2，3  D. 9，4，2，3

4. 设有n个待排序的记录关键字，则在堆排序中需要（A）个辅助记录单元。

A. 1  B. n-1  C.   D. n+1

5. 设某强连通图中有n个顶点，则该强连通图中至少有（C）条边。

A. n+1  B. n(n-1)  C. n  D. n(n+1)

6. 设一组初始记录关键字序列为(345,253,674,924,627)，则用基数排序需要进行（A）趟分配和回收，才能使得初始记录关键字序列变成有序序列。

A. 3  B. 8  C. 5  D. 6

7. 下列关于线性表的叙述，错误的是（A）。

A. 线性表中的每个节点有且仅有一个后继节点  B. 非空线性表只有一个根节点

C. 线性表通常采用顺序存储和链式存储两种结构  D. 线性表是有限序列

8. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中，需要做（D）次线性探测。

A. n(n+1)  B. n  C. n(n+1)/2  D. n(n-1)/2

9. 下列关于栈和队列的叙述，错误的是（D）。

A. 栈可以为空  B. 栈的使用原则是先进后出  C. 可以用顺序存储的线性表来表示队列

D. 根据循环队列的头指针与尾指针是否相等，可判断循环队列是否为空

10. 设一棵三叉树中有2个度为1的节点，2个度为2的节点，2个度为3的节点，则该三叉树中有（C）个度为0的节点。

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

解析：2+2+2+n=2*1+2*2+2*3+n*0+1

11. 判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（B）。

A. 广度优先遍历算法  B. 深度优先遍历算法  C. 求关键路径的方法  D. 求最短路径的方法

12. 下列叙述正确的是（C）。

A. 一个图的邻接矩阵表示是不唯一的，邻接表表示也是不唯一的

B. 一个图的邻接矩阵表示是唯一的，邻接表表示也是唯一的

C. 一个图的邻接矩阵表示是唯一的，邻接表表示不是唯一的

D. 一个图的邻接矩阵表示是不唯一的，邻接表表示是唯一的

13. 静态查找与动态查找的根本却别在于（D）。

A. 所包含的数据元素的类型不一样  B. 存储实现方式不一样

C. 逻辑结构不一样  D. 施加在其上的操作不一样

14. G是一个非连通无向图，共有28条边，则该图至少有（B）个顶点。

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

15. 下列说法错误的是（D）。

A. 广义表是一种共享结构  B. 广义表是一种递归结构

C. 广义表是一种多层次结构  D. 广义表是一种非线性结构

16. 二维数组A的每个元素是由6个字符组成的串，行下标的范围是0~8，列下标的范围是0~9，则存放数组A至少需要（B）个字节。

A. 240  B. 540  C. 90  D. 180

多选题

1. 算法设计的要求包括（ACD）。

A. 健壮性  B. 确定性  C. 正确性  D. 可读性

2. 下列属于算法重要特性的有（ABCD）。

A. 有输入和输出  B. 确定性  C. 可行性  D. 有穷性

3. 下列哪些不是顺序存储结构的优点？（BCD）

A. 存储密度大  B. 插入运算方便  C. 删除运算方便  D. 可方便地用于各种逻辑结构的存储表示

4. 串是一种特殊的线性表，下列不能体现其特殊性的有（ABD）。

A. 可以顺序存储  B. 数据元素可以是多个字符  C. 数据元素只能是一个字符  D. 可以链式存储

5. 下列属于线性表的有（BC）。

A. 二叉树  B. 栈  C. 队列  D. 集合

6. 关于数据结构，下列说法正确的有（ACD）。

A. 有四类基本结构  B. 数据元素是孤立存在的  C. 数据结构是一个二元组

D. 数据结构是相互之间存在一种或多种特定关系的数据元素的组合

解析：数据结构的四类基本结构为线性结构、树结构、图结构和集合结构。

7. 下列适合压缩存储稀疏矩阵的数据结构是（AB）。

A. 三元组表  B. 十字链表  C. 邻接矩阵  D. 二叉链表

8. 抽象数据类型按其值的不同特性，可分为（ABD）。

A. 原子类型  B. 固定聚合类型  C. 离子类型  D. 可变聚合类型

9. 有向图的连通包括（ACD）。

A. 弱连通  B. 多向连通  C. 强连通  D. 单向连通

10. 下列关于最小生成树的叙述，错误的有（BCD）。

A. 最小生成树的代价唯一  B. 所有权值最小的边一定会出现在所有的最小生成树中

C. 使用普里姆算法，从不同顶点开始得到的最小生成树一定相同

D. 使用普里姆算法和克鲁斯卡尔算法得到的最小生成树总是不同

11. 下列排序方法中，若将顺序存储改为链式存储，则算法的时间效率会降低的有（BC）。

A. 插入排序  B. 堆排序  C. 希尔排序  D. 冒泡排序

解析：堆排序和希尔排序都利用了顺序存储的随机访问特性。