13春学期《数据结构Ⅰ》在线作业2
试卷总分：100 测试时间：--
单选题

、单选题（共 20 道试题，共 100 分。）
1. 下面说法错误的是 （1）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
A. -1
B. (1),(3)
C.
D.
   满分：5 分
2. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是
A. 索引存储方法
B. 散列存储方法
C.
D.
   满分：5 分
3. 高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
C.
D.
   满分：5 分
4. 三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为
A. 356
B. 358
C.
D.
   满分：5 分
5. 从逻辑上可以把数据结构分为两大类，即
A. 动态结构、静态结构
B. 线性结构、非线性结构
C.
D.
   满分：5 分
6. 下列排序方法中，稳定的排序方法为
A. 快速排序
B. 直接插入排序
C.
D.
   满分：5 分
7. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是
A. 1
B. 2
C.
D.
   满分：5 分
8. 栈是一种操作受限的线性结构，其操作的主要特征是
A. 先进先出
B. 后进先出
C.
D.
   满分：5 分
9. 与线性表相比，串的插入和删除操作的特点是
A. 通常以串整体作为操作对象
B. 需要更多的辅助空间
C.
D.
   满分：5 分
10. 无向图中一个顶点的度是指图中
A. 通过该顶点的回路数
B. 与该顶点连通的顶点数
C.
D.
   满分：5 分
11. 导致栈上溢的操作是
A. 栈满时执行的出栈
B. 栈满时执行的入栈
C.
D.
   满分：5 分
12. n个顶点的强连通图中至少含有
A. n-1条有向边
B. n条有向边
C.
D.
   满分：5 分
13. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为
A. （2，1，4，3，5，7，8，6）
B. （8，7，6，5，4，3，2，1）
C.
D.
   满分：5 分
14. 若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为
A. 图中每个顶点的入度
B. 图中每个顶点的出度
C.
D.
   满分：5 分
15. 顺序存储设计时，存储单元的地址
A. 一定连续
B. 一定不连续
C.
D.
   满分：5 分
16. 设计深度优先树算法采用的主要技术是
A. 回溯法
B. 贪心法
C.
D.
   满分：5 分
17. 抽象数据类型的三个组成部分分别为
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C.
D.
   满分：5 分
18. 下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 二分查找
B. 散列查找
C.
D.
   满分：5 分
19. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C.
D.
   满分：5 分
20. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
A. 树
B. 图
C.
D.
   满分：5 分