C．可以链式存储 D．数据元素可以是多个字符
61．设有两个串p和q，求q在p中首次出现的位置的运算称为 B 。 A．连接 B． 模式匹配 C．求子串 D．求串长
62．数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[8][5]的起始地址为 C 。
A．SA＋141 B． SA＋144 C．SA＋222 D．SA＋225
63．数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[5][8]的起始地址为 C 。
A．SA＋141 B． SA＋180 C．SA＋222 D．SA＋225
64．若声明一个浮点数数组如下： froat average[]=new float[30];
假设该数组的内存起始位置为200， average[15]的内存地址是 C 。 A．214 B．215 C．260 D．256
65．设二维数组A[1… m,1… n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B中的下标为 A 。
A．n*(i-1)+j B． n*(i-1)+j-1 C．i*(j-1) D．j*m+i-1
13
66．有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是 B 。 A．20 B． 66 C．18 000 D．33
67．数组A[0 … 4，-1 … -3，5 …7]中含有的元素个数是 A 。 A．55 B． 45 C．36 D．16
68．对矩阵进行压缩存储是为了 D 。
A．方便运算 B． 方便存储 C．提高运算速度 D．减少存储空间
69．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1，1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8，5的地址为 B 。
A．13 B． 33 C．18 D．40
70．稀疏矩阵一般的压缩存储方式有两种，即 C 。 A．二维数组和三维数组 B． 三元组和散列 C．三元组和十字链表 D． 散列和十字链表
71．树最适合用来表示 C 。
A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
14
72．深度为5的二叉树至多有 C 个结点。 A．16 B． 32 C． 31 C． 10
73．对一个满二叉树，m个叶子，n个结点，深度为h，则 D 。 A．n = h+m B h+m = 2n C m = h-1 D n = 2h-1
74．任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 A 。
A．不发生改变 B．发生改变 C．不能确定 D．以上都不对
75．在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，还是线索化信息，若0标识树结构信息，1标识线索，对应叶结点的左右链域，应标识为__ D __。
A．00 B．01 C．10 D．11
76．在下述论述中，正确的是 D 。
①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；
④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④
77．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结
15
点个数为n，森林F中第一棵树的结点的个数是 A 。 A．m-n B．m-n-1 C．n+1 D．不能确定
78．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是 B 。
A．9 B．11 C．15 D．不能确定
79．具有10个叶子结点的二叉树中有 B 个度为2的结点。 A．8 B．9 C．10 D．11
80．在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。 A．1/2 B 1 C 2 D 4
81．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A．1/2 B 1 C 2 D 4
（左中右）我按我做的题目举例吧：后序序列为：bfegcda, 中序序列为：badefcg,求前序序列。
这里会用：后序列序列最后一个值即树（或子树）的根。
由后序“bfegcda”知a为根，由中序“badefcg”知a的左子树仅有b一个节点。即图1.
去除序列中的b和a得后序“fegcd”和中序“defcg”，可知，d为a的右子树树根（后序最后一个值）且d的左子树为空（d前面无值），同理再去掉d得到，“fegc”和“efcg”，可知c为d的右子树树根，如图2.
由中序“efcg”知c的右子树为g，左子树为e,f，同理得最后结果树为图3. 于是得出前序列为： abdcefg
82．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为： C A．3 B．2 C．4 D．5
16