一、单选题（共 20 道试题，共 60 分。）V 1. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A. 112
B. 132
C. 118
D. 140
满分：3 分
2. 若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B [1..n(n+1)/2 ] 中，则在B中确定aij ( i < j）的位置k的关系为 () 。
A. i*(i-1)/2+j
B. j*(j-1)/2+i
C. i*(i+1)/2+j
D. j*(j+1)/2+i
满分：3 分
3. 在线索二叉树中，p所指结点没有右子树的充要条件是 ( )。
A. p->rchild = = NULL
B. p->rtag = = 1
C. p->rtag = = 1且p->rchild = = NULL
D. p->rtag = = 0
满分：3 分
4. 对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A. 1000
B. 1010
C. 1008
D. 1020
满分：3 分
5. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
A. n
B. (n-1)/2
C. n/2
D. (n+1)/2
满分：3 分
6. 顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
满分：3 分
7. 在k叉树中，无父母的结点称为 ( )。
A. 根
B. 叶
C. 祖先
D. 子孙
满分：3 分
8. 在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A. 1/2
B. 1
C. 2
D. 4
满分：3 分
9. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A. 不确定
B. 0
C. 1
D. 2
满分：3 分
10. 用折半查找法查找表的元素的速度比顺序查找法()。
A. 必定快
B. 必定慢
C. 相等
D. 不能确定
满分：3 分
11. 一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。
A. acb
B. abc
C. bca
D. cab
满分：3 分
12. 一个顺序栈一旦被说明，其占用空间的大小 ( )。
A. 可以改变
B. 不能固定
C. 已固定
D. 动态变化
满分：3 分
13. B+ 树应用在 () 文件系统中。
A. ISAM
B. VSAM
C. 顺序
D. 散列
满分：3 分
14. 排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
满分：3 分
15. 有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
A. 60
B. 66
C. 18000
D. 33
满分：3 分
16. 下列四个序列中，哪一个是堆 () 。
A. 75 , 65 , 30 , 15 , 25 , 45 , 20 , 10
B. 75 , 65 , 45 , 10 , 30 , 25 , 20 , 15
C. 75 , 45 , 65 , 30 , 15 , 25 , 20 , 10
D. 75 , 45 , 65 , 10 , 25 , 30 , 20 , 15
满分：3 分
17. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
A. U
B. V
C. X
D. Y
满分：3 分
18. 数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
A. 直接选择排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
满分：3 分
19. 下列描述中正确的是 ( )。
A. 线性表的逻辑顺序与存储顺序总是一致的
B. 每种数据结构都具备查找、插入和删除三种基本运算
C. 数据结构实质上包括逻辑结构和存储结构两方面的内容
D. 选择合适的数据结构是解决应用问题的关键步骤
满分：3 分
20. 分块查找要求表中的结点 ()。
A. 全部无序
B. 块之间无序
C. 全部有序
D. 块之间有序
满分：3 分