一、单选题（共 15 道试题，共 75 分。）V 1. 下面程序段的时间复杂度是 O（ ）。 s ＝0； for（ I ＝0； i＜n； i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝ s ；
A. n
B. n^2
C. lg(n)
D. n^3
满分：5 分
2. 稀疏矩阵一般的压缩存储方式有两种，即（）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
满分：5 分
3. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。
A. O（1）
B. O（n）
C. O（n^2)
D. O（nlog2n）
满分：5 分
4. 栈和队列的共同点是（）。
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
满分：5 分
5. 如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
满分：5 分
6. 数据结构在计算机内存中的表示是指（）。
A. 数据存储结构
B. 数据结构
C. 数据的逻辑结构
D. 数据之间的逻辑关系
满分：5 分
7. 输入序列为ABC，可以变为CBA时，经过的栈操作为（）。
A. push，pop，push，pop，push，pop
B. push，push，push，pop，pop，pop
C. push，push，pop，pop，push，pop
D. push，pop，push，push，pop，pop
满分：5 分
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
满分：5 分
9. 线性表是具有n个（）的有限序列。
A. 字符
B. 数据元素
C. 数据项
D. 表元素
满分：5 分
10. 如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（）。
A. 只有表头指针没有表尾指针的循环单链表
B. 只有表尾指针没有表头指针的循环单链表
C. 非循环双链表
D. 循环双链表
满分：5 分
11. 在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。
A. 删除单链表中的第一个元素
B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素
满分：5 分
12. 链表不具备的特点是（）。
A. 可随机访问任一结点
B. 插入删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与其长度成正比
满分：5 分
13. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。
A. edcba
B. decba
C. dceab
D. abcde
满分：5 分
14. 带头结点的单链表head为空的判定条件是（）。
A. head->next＝＝NULL
B. head->next＝＝head
C. head==NULL
D. head！＝NULL
满分：5 分
15. 在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n＋1），元素的移动次数为：（）。
A. n–i＋1
B. n–i
C. i
D. i–1
满分：5 分