.
A. 1175 B. 1180 C. 1205 D. 1210
6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ A ）。
A. 3
B. 4
C. 7
D. 8
7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。
A. 正确
B. 错误
C. 无法确定
D. 以上均不对
8、广义表(a,b,c)的表尾是（ B ）。
A. b,c
B. (b,c)
C. c
D. (c)
9、常对数组进行两种基本操作是（ C ）。
A. 建立和删除 查找与索引
10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。
A. 表达变得简单
B. 对矩阵元素的存取变得简单 D. 减少不必要的存储空间的开销
B. 索引和修改
C. 查找和修改
D.
C. 去掉矩阵中的多余元素
11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。
A. 13
B. 33
C. 18
D. 40
12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ B ）。
A. i(i-1)/2+j-1 i(i+1)/2+j
B. i(i-1)/2+j
C. i(i+1)/2+j-1
D.
可编辑范本
.
13、广义表A=((a),a)的表头是（ B ）。
A. a
B. (a)
C. b
D. ((a))
14、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。
A. 二维数组和三维数组 表
D. 散列和十字链表
B. 三元组和散列
C. 三元组和十字链
15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ）。
?0?8?0?7A. ?00???50??0?8?0?0C. ?70???50?060??000?
000??400??060??003?
000??400???0?8?0?7B. ??50??00?060??003?
400??000??060??000?
403??000??
?0?8?0?7 D. ??50??00?16、以下有关广义表的表述中，正确的是（ A ）。
A. 由0个或多个原子或子表构成的有限序列 表
C. 不能递归定义
D. 不能为空表
B. 至少有一个元素是子
17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（D ）。
A. 的 二、判断题
（× ）1、广义表中原子个数即为广义表的长度。
（ ×）2、一个稀疏矩阵采用三元组表示，若把三元组中有关行下标与列下标的值互换，并把mu和nu的值进行互换，则完成了矩阵转置。
B. e
C. (e)
D. （e,f）
可编辑范本
.
（√ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。 （× ）4、广义表的长度是指广义表中括号嵌套的层数。
（√ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。 三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。 2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： (x,y,z) 。 3、二维数组，可以按照 列序为主和行序为主 两种不同的存储方式。
4、稀疏矩阵的压缩存储方式有： 三元组 和 十字链表 。 四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。
?0?1??0??0300?0??
210??0?20?10答案：
i112334j231233v31121-2
第六章 树
一、选择题
可编辑范本
.
1、二叉树的深度为k，则二叉树最多有（ C ）个结点。
A. 2k
B. 2k-1 C. 2k-1 D. 2k-1
2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。
A. R[2i-1]
B. R[2i+1]
C. R[2i]
D. R[2/i]
3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。
A. a在b的右方 的子孙
4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（ D ）。
A. adbce
B. decab C. debac
D. abcde
B. a在b的左方
C. a是b的祖先
D. a是b
5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31
B. 32
C. 33 D. 16
6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。
A. 能
B. 不能
7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。
A. 3
B. 2
C. 4
D. 5
8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。
A. 67
B. 68
C. 69
D. 70
9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ A ）。
可编辑范本
.
A. 98 B. 99 C. 50 D. 48
10、表达式a*(b+c)-d的后缀表达式是（ B ）。
A. abcd+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。
A. DBFEAC
B. DFEBCA
C. BDFECA
D. BDEFAC
12、树最适合用来表示（ C ）。
A. 有序数据元素 系的数据
B. 无序数据元素 C. 元素之间具有分支层次关
D. 元素之间无联系的数据
13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ）。
A. A*B+C/D-E+F
B. AB*C+D/E-F+
C. ABC+*DE-F+/
D.
ABCDED*+/-+
14、在线索二叉树中，t所指结点没有左子树的充要条件是（B ）。
A. t->left==NULL
D. 以上都不对
B. t->ltag==1
C. t->ltag==1&&t->left==NULL
15、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A ）。
A. 不发生改变 以上都不对
16、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（ B ）个。
A. 15
B. 16
C. 17
D. 47
B. 发生改变
C. 不能确定
D.
17、在下列情况中，可称为二叉树的是（ B ）。
可编辑范本