是（ C ）

(A)a4，a3，a2，a1 (B)a3，a2，a4，a1 (C)a3，a1，a4，a2 (D)a3，a4，a2，a1

10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ D ） (A)rear－qulen (B)rear－qulen＋m

(C)m－qulen (D)1＋（rear＋m－qulen）% m 二、填空题

1.栈的特点是____先进后出____,队列的特点是___先进先出___。

2.线性表、栈和队列都是___线性___结构,可以在线性表的___任何__位置插入和删除元素，对于栈只能在___栈顶__插入和删除元素，对于队列只能在___队尾__插入元素和___对头__删除元素。

3.一个栈的输入序列是12345,则栈有输出序列12345是___正确___。(正确/错误)

4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳__3__个元素。

第五章 数组和广义表

一、选择题

1. 常对数组进行的两种基本操作是（ C）

（A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引

2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素(B ) 的起始地址相同。

（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]

3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（C）。 （A）80（B）100（C）240（D）270

4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（C ）。

（A）SA+141（B）SA+144（C）SA+222（D）SA+225

5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（B ）。 （A）SA+141（B）SA+180（C）SA+222（D）SA+225 6.稀疏矩阵一般的压缩存储方法有两种,即（C ）。 （A） 二维数组和三维数组（B）三元组和散列 （C）三元组和十字链表 （D）散列和十字链表

7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（B）。 （A）正确（B）错误

8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（B ）。 （A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1 (D)i(i+1)/2+j 二、填空题

1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是__ loc(A[0][0])+(n*i+j)*k __。

2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是__332__。

3.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且A[0][0]=1),则A[8][5]的地址是__42__。

4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是__ i*(i+1)/2+j+1__。

5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为__1039__,该数组共占用___72__个存储单元。

第六章 树和二叉树

一、选择题

1.在线索化二叉树中,t所指结点没有左子树的充要条件是（B ） （A）t-〉left==NULL （B）t-〉ltag==1

（C）t-〉ltag=1且t-〉left=NULL（D）以上都不对

2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法B （A）正确 （B）错误 （C）不同情况下答案不确定

3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（A ） (A)正确 (B)错误 （C）不同情况下答案不确定

4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（B ） （A）正确 （B）错误 （C）不同情况下答案不确定

5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（B ）。

（A）2h （B）2h-1（C）2h+1（D）h+1

6.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（D ）。 （A）acbed （B）decab（C）deabc （D）cedba

7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（A ） （A）前序（B）中序（C）后序（D）层次序

8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（D ）。

（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca

9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（B ）

（A）正确（B）错误（C）不同情况下答案不确定 10.按照二叉树的定义,具有3个结点的二叉树有（ C）种。 （A）3（B）4（C）5（D）6

11.在一非空二叉树的中序遍历序列中,根结点的右边（A ） （A）只有右子树上的所有结点（B）只有右子树上的部分结点 （C）只有左子树上的部分结点（D）只有左子树上的所有结点 12.树最适合用来表示（C ）。

（A）有序数据元素（B）无序数据元素

（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据

13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A ） （A）不发生改变（B）发生改变（C）不能确定D.以上都不对

14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（C ）存储结构。

（A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构 15.对一个满二叉树,m个树叶,n个结点,深度为h,则（D ） （A）n=h+m （B）h+m=2n（C）m=h-1（D）n=2h-1

16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（C ） （A）uwvts （B）vwuts（C）wuvts （D）wutsv 17.具有五层结点的二叉平衡树至少有（C ）个结点。 （A）10（B）12（C）15（D）17 二、判断题

1.二叉树中任何一个结点的度都是2。（× ）

2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（× ） 3.一棵哈夫曼树中不存在度为1的结点。（√）

4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（√ ） 三、填空题

1.指出树和二叉树的三个主要差别__树的结点个数至少为1，而二叉树的结点个数可以为0__,__树种结点的最大读书没有限制，而二叉树结点的最大度数不能超过2__,__树的结点无左右之分，而二叉树的结点有左右之分__。

2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是___树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题___ 3.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是___4___

4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有__ n+1__个空指针域。

5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列__ DGEBHJIFCA __。

6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列___ ABDEGCEH ___。

7.找出满足下列条件的二叉树

1）先序和中序遍历，得到的结点访问顺序一样。____无左子树____ 2）后序和中序遍历，得到的结点访问顺序一样。_____无右子树____