第六章树和二叉树。
注：参***只能作为参考，也是有错的，自己要学会辨别。
一、单项选择题。
3．a4．c
5．b6．d
7．e8. d
9．c10．b
11. c12．a
13．d14．b
15．c16．b
17．d18．b
19. d20．c
二、判断题（在各题后填写“√”或“×”
1. 完全二叉树一定存在度为1的结点。×
2. 对于有n个结点的二叉树，其高度为log2n。×
3. 二叉树的遍历只是为了在应用中找到一种线性次序。√
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。×
5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。×
6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 √
7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√
8. 二叉树只能用二叉链表表示。×
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。√
10. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。×
11．树形结构中元素之间存在一个对多个的关系。√
12．将一棵树转成二叉树，根结点没有左子树。×
13．度为二的树就是二叉树。×
14.二叉树中序线索化后，不存在空指针域。×
15．霍夫曼树的结点个数不能是偶数。√
16．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。√
三、填空题。
1．p->lchild==null &&p->rchlid==null
2.(1)2k-1 (2)2k-1
4. 2n n-1 n+1
5． 先序遍历后序遍历中序遍历
6．.(1)2k-2+1（第k层1个结点，总结点个数是2h-1，其双亲是2h-1/2=2k-2）(2) log2i+1
8．任何结点至多只有右子女的二叉树。9．前序。
11． count++,countleaf(l->rchild,count)
12．(1) p=p->lchild //沿左子树向下（2）p=p->rchild
13．(1)0 （2）hl>hr3)hr=hl
14．(1)p->rchild (2)p->lchild (3)p->lchild
4)addq(q,p->lchild) (5)addq(q,p->rchild)
四、应用题。
1．树和二叉树逻辑上都是树形结构，树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。二叉树不是树的特例。
2．【解答】
具有3个结点的树具有3个结点的二叉树
3．解答：先根序列：a b c d e f g h i j;
中根序列：bcdafehjig;
后根序列：d c b f j i h g e a。
4．(1)kh-1(h为层数)
2）因为该树每层上均有kh-1个结点，从根开始编号为1，则结点i的从右向左数第２个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2<=n<=ik+1成立，因i是整数，故结点n的双亲i的编号为n-2)/k+1。
(3) 结点n(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点 n的第 i个孩子的编号是(n-1)*k+1+i。
4) 根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (n-1)%k!=0，其右兄弟编号是n+1。
6．（l）图略；
2）前序序列j
中序序列： e c b h f d j i g a
后序序列。3）图略。
7．字符a，b，c，d出现的次数为9,1,5,3。其哈夫曼编码如下a:1，b:000，c:01，d:001
五、算法设计题。
1．[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。
bitree creat建立二叉树的二叉链表形式的存储结构。
elemtype x；bitree bt;
scanf(“%d”,&x); 本题假定结点数据域为整型。
if(x==0) bt=null;
elseif(x>0)
else error(“输入错误”)；
return(bt);
//结束 bitree
int judgecomplete(bitree bt) /判断二叉树是否是完全二叉树，如是，返回1，否则，返回0
int tag=0; bitree p=bt, q;q是队列，元素是二叉树结点指针，容量足够大。
if(p==null) return (1);
queueinit(q); queuein(q,p); 初始化队列，根结点指针入队。
while (!queueempty(q))
p=queueout(q出队。
if (p->lchild &&tag) queuein(q,p->lchild); 左子女入队。
else /judgecomplete
算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。
2.[题目分析]后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。
本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。
再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。
typedefstruct
//沿左分枝向下。
if(bt==p) /不失一般性，假定p在q的左侧，遇结点p时，栈中元素均为p的祖先结点。
for(i=1;i<=top;i++)s1[i]=s[i]; top1=top; }将栈s的元素转入辅助栈s1 保存。
if(bt==q) /找到q 结点。
for(i=top;i>0;i--)将栈中元素的树结点到s1去匹配。
pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp)
while(top!=0 &&s[top].tag==1) top退栈。
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ 沿右分枝向下遍历。
//结束while(bt!=null ||top>0)
return(null);/p无公共祖先。
//结束ancestor
3．解答：本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。
void layorder (bitreptr t)
{initqueue (q队列初始化*/
if(t!=null)
{printf(“%f”, t->data);
enqueue (q, t入队列*/
while (not emptyqueue (q若队列非空*/
{outqueue (q,p出队*/
数据结构考研复习题第六章 数和二叉树 带答案
第六章树和二叉树。一 选择题。1 已知一算术表达式的中缀形式为 a b c d e，后缀形式为abc de 其前缀形式为 a a b c de b.a b cd e c abc ded.a bc de 北京航空航天大学 1999 一 3 2分 2 算术表达式a b c d e 转为后缀表达式后为 中...
数学建模习题 第六章
习题。1 在6.1节平衡状态的交通流模型中，从对于制动力 或驱动力 的假设 10 式及u 0 出发，推导平衡状态下的速度和流量函数 12 和 13 式。2.在交通流模型中如果假定制动力 或驱动力 与两车距离无关，推导平衡状态的速度和流量函数，这个结果符合实际吗？3 在6.2节捕鱼模型中，如果渔场鱼量...
计算机系统结构第六章 习题
1.设16个处理器编号分别为 要用单级互连网络。当互连函数分别为 cube3 pm2 3 pm2 0 shuffle shuffle shuffle 时，第13号处理器各与哪一个处理器相连？2.在编号分别为 f的16个处理器之间，要求按下列配对通信 b，1 8，2 7，d 6，c e，4 a，0 9...