沈阳理工大学应用技术学院
信息与控制学院 计算机科学与技术教研室
2011-5-8
数据结构复习题：树和二叉树 单选题
1、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为___16__。 2、假定一棵二叉树的结点数为18个，则它的最小高度__5___。 3、在一棵二叉树中第五层上的结点数最多为__16___。 4、在一棵具有五层的满二叉树中，结点总数为__31___。
5、已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为___2__。
6、由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为__44___。
7、在树中除根结点外，其余结点分成m(m≥0)个___互不相交__的集合T1,T2,T3...Tm,每个 集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。
8、下面答案__二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于其右子树（如果存在）所有结点的关键字值__是查找二叉树（又称二叉排序树）。 9、如果结点A有三个兄弟，而且B是A的双亲，则B的出度是__4___。
- 31 -
10、一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每 个结点都有K棵非空子树。如果按层次顺序从１开始对全部结点编号，编号为n的有右兄弟的条件是__(n-1)%k!=0___。 11、在完全二叉树中，当i为奇数且不等于１时，结点i的左兄弟是结点__i+1___，否则没有左兄弟。 12、某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,?,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按__前序遍历序列___编号。 13、最小代价生成树_____。
14、将递归算法转换成对应的非递归算法时,通常需要使用_____栈_____。 15、设二维数组A[m][n],每个数组元素占用K个存储单元,第一个数组元素的存储地址是Loc(a[0][0]),求按行优先顺序存放的数组元素a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为___ Loc(a[0][0])+[i*n+j]*k ___。 16、设二维数组A[m][n],每个数组元素占用k个存储单元,第一个数组元素的存储地址是Loc(a[0][0]),求按列优先顺序存放的数组元素a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为______。 17、设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][0]的存储地址为860,则a[3][5]的存储地址是___1000___。 18、设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是______。
19、若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中,第一个非零元素a1,1存于B[0]中,则应存放到B[k]中的非零元素ai,j(1<=i<=n,1<=j<=i)的下标i、j与k的对应关系是_j(j-1)/2+i-1_。 20、若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中,第一个非零元素a1,1存于B[0]中,则应存放到B[k]中的非零元素ai,j(1<=i<=n,1<=j<=i)的下标i、j与k的对应关系是___(j-1)(2n-j+1)/2+i-j___。
21、对稀疏矩阵进行压缩存储的目的是___节省存储空间___。 22、稀疏矩阵压缩后,必会失去___随机存取___功能。
23、一个n*n的对称矩阵A,采用压缩方式存放到一维数组B中,则B的容量为___(n^2)/2___. 24、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为____53_____。
25、在一棵深度为h的具有n个元素的二叉搜索树中，一个元素的最大搜索长度（即 经比较的结点数） 为_____h____。
26、根据集合{25,30,16,48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况下成功查找一个元素的平均查找长度为____2.5_____。
27、利用n个值作为叶结点的权生成的霍夫曼树中共包含有____2*n-1_____个结点。 28、利用n个值作为叶结点的权生成的霍夫曼树中共包含有_____n-1____个双支结点。
29、利用3,6,8,12这4个值作为叶子结点的权，生成一棵霍夫曼树，该树中所有叶子的最长带权路径长度为____18_____。
30、在平衡二叉树中，每个结点的平衡因子的绝对值被限制为_____1____。
数据结构复习题：树和二叉树 判断题
1、由树转换成二叉树，其根结点的右子树总是空的。
2、后序遍历树和中序遍历与该树对应的二叉树，其结果不同。F
3、有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的
- 32 -
最后一个结点。
4、若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。T
5、已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个。 6、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。F 7、中序遍历二叉排序树的结点就可以得到排好序的结点序列。
8、在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可。 9、堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。 10、用一维数组元素矩阵,可以简化对矩阵的存取操作。F
11、对角矩阵的特点是非零元素只出现在矩阵的两条对角线上。 12、在n(n>3)阶三对角线矩阵中,每一行都有3个非零元素。 13、在n(n>3)阶三对角矩阵中,每一行都有3个非零元素。
数据结构复习题答案：树和二叉树 判断题 1、True 2、False 3、False 4、True 5、False 6、False 7、True 8、True 9、True 10、False 11、False 12、False 13、False
数据结构复习题：树和二叉树
1、己知二叉树采用二叉链存储结构存储,设计一个算法使用栈对二叉树进行先序遍历. void PreOrder1(BTNode *b) { BTNode *p; struct { BTNode *pt; int tag; //1:未访问，0:可访问 } St[MaxSize]; int top=-1; top++; St[top].pt=b; St[top].tag=1; while (top>-1) //栈不空时循环 { if (St[top].tag==1) //不能直接访问的情况
- 33 -
{ p=St[top].pt; top--; if (p!=NULL) {
//(2)式
top++; //右孩子结点进栈 St[top].pt=p->rchild; St[top].tag=1;
top++; //左孩子结点进栈 St[top].pt=p->lchild; St[top].tag=1; top++; //根结点进栈 St[top].pt=p; St[top].tag=0; } } //end of if (St[top].tag==1)
if (St[top].tag==0) //直接访问的情况 { printf(\ top--; } } //while }
数据结构复习题答案：树和二叉树 第二种方法
数据结构复习题：树和二叉树 填空题
1、对于一棵具有n个结点的树，则该树中所有结点的度之和为___n-1___。
2、在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0=___n2+1___。 3、在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为____2____， 若它存在左孩子，则左孩子结点的下标为____10____，若它存在右孩子，则右孩子结点的下标为____11_____。 4、在一棵二叉排序树中，按____中序___遍历得到的结点序列是一个有序序列。
5、由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为____55____。 6、有如下递归函数: int dunno (int m) {
int value; if (m==0) value=3; else
value=dunno(m-1)+5; return (value); }
- 34 -
执行语句printf(\；的结果是____18____。
7、所谓稀疏矩阵指的是___非零元素很少且分布没有规律___的矩阵。 8、一个稀疏矩阵Am*n采用三元组表示后,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。这句话___不是___正确的。 9、若稀疏矩阵采用三元组压缩方法存储,只要把每个元素的行下标和列下标互换,就成了对该矩阵的转置运算,这种观点___错误___(正确或错误).
10、在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵______二叉搜索树______。 11、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______有序序列______。
12、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_____查找成功_______，若元素的值小于根结点的值，则继续向______左子树______查找，若元素的值大于根结点的值，则继续向______右子树______查找。
13、在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为______2i+1______，右孩子元素的下标为______2i+2______。
14、在一个小根堆中，堆顶结点的值是所有结点中的______最小值______，在一个大根堆中，堆顶结点的值是所有结点中的______最大值______。
15、当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层______向上______调整，直到被调整到______栈顶______位置为止。
16、不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为______奇数____个。 17、在中序线索二叉搜索树中，具有最小值结点的左指针域的值为______空_____。
数据结构复习题：树和二叉树 问答题
1、对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。 其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２。
2、分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。 解答：中根遍历的非递归算法： status inorder(bt){ top＝0; p＝bt; do{
(1) while (p!=nil ){
top＝top＋1; s[top]＝p;
p:＝p->left; //p指向左子树 }
(2) if (top>0 ){
p＝s[top]; top＝top－1; printf(p->data);
p＝p->right; // p指向右子树 }
}while !((top＝0) && (p＝nil)); }
解答: 先根遍历的非递归算法：
- 35 -
