第四-六章串、数组、树作业一、判断正误：（每小题1分，共5分）正确在（）内打√，否则打× .1．（√）子串是主串中任意个连续字符组成的序列.2．（×）线性结构只能用顺序结构存放，非线性结构只能用链表存放.3．（√）完全二叉树的某结点若无左孩子，则它必是叶结点.4．（√）二叉树有五种基本形态.5. （√）由树的中序表示和前序表示可以导出树的后序表示.6. （√）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树.7. （√）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的.8. （×）在Huffman树中，权值较大的叶子结点离根较远.9. （×）用一维数组存储二叉树时，是以先根遍历的次序存储结点.二、填空题1．已知二维数组A[0..10][0..20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的地址是1312(1024+2*(6*21+18)) .2. 深度为5的二叉树最多有_____31___个结点（根结点层数为1）.3．高度为h的完全二叉树最少有2h-1个结点.4. 二叉树的先序遍历序列为：EFHIGJK，中序遍历序列为：HFIEJKG，则该二叉树根的右子树的根是：G .5. N个结点的二叉树,采用二叉链表存放,空链域的个数为N+1 .6. 填空完成下面中序遍历二叉树的非递归算法：void InOrder（BiTree root）{ InitStack ( &S );p = ____root_____ ;while ( _____p________ || ! IsEmpty(S)){ while (p!=NULL){ Push(&S, __p___ ) ;p = _____p->lchild_________ ;}if ( ____! IsEmpty(S)___________ ){ Pop(&S, __p_____ ) ;Visit ( p -> data );p = ___p->rchild____________ ;}}}三、选择题1．表达式a*(b−c)+d的后缀表达式是( B）.A）abcd*−+ B）abc−*d+ C）abc*−d+ D）+−*abcd2．对于有N个结点高度为K的满二叉树(结点编号为1到N，根结点的层数为1)，其第K 层上最后1个结点的编号为 ( D ).A）2K B）2K−1 C）B）2K−1−1 D）2K−13．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：( C ) .A）48 B）49 C）50 D）514．在下列存储形式中，哪一个不是树的存储形式？( D ) .A）双亲表示法 B）孩子链表表示法C）孩子兄弟表示法 D）顺序存储表示法5．某二叉树结点的中序序列为：A、B、C、D、E、F、G，后序序列为：B、D、C、A、F、G、E，则其左子树中结点数目为：( C ) .A）3 B）2 C）4 D）56．从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在对应栏内.有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储.存储器按字节编址.假设存储数组元素A[0,1]的第一个字节的地址是0.存储数组A的最后一个元素的第一个字节的地址是 A .若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是 B 和 C .若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E .供选择的答案A～E：①28 ②44 ③76 ④92 ⑤108 ⑥116 ⑦132 ⑧176 ⑨184 ⑩188答案：A＝⑧B＝③C＝⑤D＝①E= ⑥7、从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在对应栏内.有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址.那么，这个数组的体积是 A 个字节.假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B .若按行存储，则A[2,4]的第一个字节的地址是 C .若按列存储，则A[5,7]的第一个字节的地址是 D .供选择的答案A～D：①12 ②66 ③72 ④96 ⑤114 ⑥120 ⑦156 ⑧234 ⑨276 ⑩282 (11)283 （12）288答案：A＝（12）B＝⑩C＝③D＝⑨8．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：( A )A）98 B）99 C）50 D）489. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3.与森林F对应的二叉树根结点的右子树上的结点个数是：( D )A）M1 B）M1+M2 C）M3 D）M2+M3四、综合题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’.给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));【解答】StrLength(s)=14;SubString(sub1,s,1,7) sub1=’I AM A ’;SubString(sub2,s,7,1) sub2=’ ’;StrIndex(s,4,’A’)=6;StrReplace(s,’STUDENT’,q); s=’I AM A WORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=’I AM A GOOD WORKER’.2. 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址.已知A的基地址为1000，计算：数组A共占用多少字节；数组A的最后一个元素的地址；按行存储时元素A36的地址；按列存储时元素A36的地址；【解答】设自定义数组的下标从1开始使用.（1）数组A共占用多少字节；（288）（2）数组A的最后一个元素的地址；（1282）（3）按行存储时，元素A36的地址；（1126）（4）按列存储时，元素A36的地址；（1192）3. 分别画出具有3个结点的树和3个结点的二叉树的所有不同形态.【解答】具有3个结点的树具有3个结点的二叉树4. 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k 的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则n=n0 + n1 + …… + n k树中分支数目为B,则B=n1 + 2n2 + 3n3+ …… + kn k因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1即n0 + n1 + …… + n k = n1 + 2n2 + 3n3+ …… + kn k + 1由上式可得叶子结点数为：n0 = n2 + 2n3+ …… + (k-1)n k + 15. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1所以n2=n0 –1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=996. 试分别找出满足以下条件的所有二叉树:(1) 前序序列与中序序列相同;(2) 中序序列与后序序列相同;(3) 前序序列与后序序列相同.【解答】(1) 前序与中序相同：空树或缺左子树的单支树；(2) 中序与后序相同：空树或缺右子树的单支树；(3) 前序与后序相同：空树或只有根结点的二叉树.7. 假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码.【解答】构造哈夫曼树如下：哈夫曼编码为：I1：11111I5：1100I2：11110I6：10I3：1110 I7： 01I4：1101 I8： 00 8. 画出如下图所示树对应的二叉树.【解答】9. 分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继.在先序线索二叉树T中，查找给定结点*p在先序序列中的后继.在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱.（1）找结点的中序前驱结点BiTNode *InPre (BiTNode *p)/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/{ if (p->Ltag= =1) pre = p->LChild; /*直接利用线索*/else{/*在p的左子树中查找“最右下端”结点*/for ( q=p->LChild; q->Rtag= =0; q=q->RChild);pre = q;}return (pre);}（2）找结点的中序后继结点BiTNode *InSucc (BiTNode *p)/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/{ if (p->Rtag= =1) succ = p->RChild; /*直接利用线索*/else{/*在p的右子树中查找“最左下端”结点*/for ( q=p->RChild; q->Ltag= =0; q=q->LChild);succ= q;}return (succ);}(3) 找结点的先序后继结点BiTNode *PreSucc (BiTNode *p)/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/{ if (p->Ltag= =0) succ = p->LChild;else succ= p->RChild;return (succ);}(4) 找结点的后序前驱结点BiTNode *SuccPre (BiTNode *p)/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/{ if (p->Ltag= =1) pre = p->LChild;else pre= p->RChild;return (pre);}10. 已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法.【解答】Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/{InitStack(&S);p=root;while(p!=NULL || !IsEmpty(S) ){ if(p!=NULL){Visit(p->data);push(&S,p);p=p->Lchild;}else{Pop(&S,&p);p=p->RChild;}}}11. 已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换.【解答】算法(一)Void exchange ( BiTree root ){p=root;if ( p->LChild != NULL || p->RChild != NULL ){temp = p->LChild; p->LChild = p->RChild;p->RChild = temp;exchange ( p->LChild );exchange ( p->RChild );}}算法(二)Void exchange ( BiTree root ){p=root;if ( p->LChild != NULL || p->RChild != NULL ){exchange ( p->LChild );exchange ( p->RChild );temp = p->LChild;p->LChild = p->RChild;p->RChild = temp;}}12．已知一棵树如图1所示.要求：给出树的先根遍历序列和后根遍历序列；画出树的孩子-兄弟链表； 将该树转化为二叉树. 【解：】（1）先根序列：（2）后根序列：（3）树的孩子-兄弟链表：（4）转化为二叉树：13. 画出和下列已知序列对应的二叉树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为CBEFDGAJIKLH.【解：】先根序列中G是整棵树的根，后根序列中H是整个树的根，矛盾，无解.14 假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA.请画出该树.【解：】15．假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF.请画出该树. 【解：】16．编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值.【解：】int n=0;Status Preorder (BiTree T, int k, ElemType &e){// 若k小于二叉树的总结点个数，则由变量e带回第k个结点的值并返回OK,// 否则返回ERRORif (T) { n++;if (n==k) { e=T->data; return OK ;}else {if (Preorder(T->lchild, k,e)) return OK;else return(Preorder(T->rchild, k, e)) ;}//else}//ifelse return ERROR;}17．编写递归算法，计算二叉树中叶子结点的数目.int CountLeaf (BiTree T){//返回指针T所指二叉树中所有叶子结点个数if (!T ) return 0;if (!T->lchild && !T->rchild) return 1;else{m = CountLeaf( T->lchild);n = CountLeaf( T->rchild);return (m+n);} //else} // CountLeaf18．编写算法，层次遍历一棵二叉树.给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问.解答：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放.算法中的front为队头指针，rear为队尾指针.levelorder (BiTree *t) //按层次遍历二叉树t{ BiTree *que[maxnum];int rear,front;if (t!=NULL){ front=0; //置空队列rear=1;que[1]=t;do{ front=front%maxsize+1; //出队t=que[front];printf(t->data);if (t->lchild!=NULL) //左子树的根结点入队{ rear=rear%maxsize+1;que[rear]=t->lchild;}if (t->rchild!=NULL) //右子树的根结点入队{ rear=rear%maxsize+1;que[rear]=t->rchild;}}while (rear= =front); //队列为空时结束}}*****************************思考题（不做在本子上）*****************************1．名词解释：树，子树，结点的度，叶子结点，孩子，双亲，兄弟，深度，有序树，森林，二叉树，遍历二叉树，树的带权路径长度，哈夫曼树.2．描述二叉树的性质.3．从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别.4．已知一棵树边的结点为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>}，试画出这棵树,并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？5．已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点.试求该树含有的叶子结点的数目.6．有n个结点的二叉树，已知叶子结点个数为n0，写出求度为1的结点的个数n1的计算公式；若此树是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式.7．找出所有满足下列条件的二叉树：（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同；（b）它们在后序遍历和中序遍历时，得到的结点访问序列相同；（c）它们在先序遍历和后序遍历时，得到的结点访问序列相同；11 / 11。