第四-六章+串、数组、树作业(参考答案).doc

第四-六章 串、数组、树作业一、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打 。 1（ ）子串是主串中任意个连续字符组成的序列。2（ ）线性结构只能用顺序结构存放，非线性结构只能用链表存放。3（ ）完全二叉树的某结点若无左孩子，则它必是叶结点。4（ ）二叉树有五种基本形态。5. （ ）由树的中序表示和前序表示可以导出树的后序表示。6. （ ）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。7. （ ）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。8. （ ）在Huffman树中，权值较大的叶子结点离根较远。9. （ ）用一维数组存储二叉树时，是以先根遍历的次序存储结点。二、填空题1已知二维数组A0.100.20采用行序为主方式存储，每个元素占2个存储单元,并且A00的存储地址是1024, 则A618的地址是 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*(bc)+d的后缀表达式是( B ）。A）abcd*+B）abc*d+C）abc*d+D）+*abcd2对于有N个结点高度为K的满二叉树(结点编号为1到N，根结点的层数为1)，其第K层上最后1个结点的编号为 ( D )。A）2K B）2K1 C）B）2K11 D）2K13将一棵有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个字节存储。存储器按字节编址。假设存储数组元素A0,1的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A3,5和A5,3的第一个字节的地址分别是 B 和 C 。若按列存储，则A7,1和A2,4的第一个字节的地址分别是 D 和 E 。供选择的答案AE：28 44 76 92 108 116 132 176 184 188答案：A B C D E= 7、从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在对应栏内。有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 A 个字节。假设存储数组元素A1,0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A2,4的第一个字节的地址是 C 。若按列存储，则A5,7的第一个字节的地址是 D 。供选择的答案AD：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的结点，nk个度为k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则n=n0 + n1 + + nk树中分支数目为B,则B=n1 + 2n2 + 3n3 + + knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1即n0 + n1 + + nk = n1 + 2n2 + 3n3 + + knk + 1由上式可得叶子结点数为：n0 = n2 + 2n3 + + (k-1)nk + 15. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1 所以n2= n0 1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=99 6. 试分别找出满足以下条件的所有二叉树:(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：11111 I5：1100 I2：11110 I6： 10I3：1110 I7： 01 I4：1101 I8： 008. 画出如下图所示树对应的二叉树。【解答】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所示。要求：给出树的先根遍历序列和后根遍历序列；ABCDHGFEKJI图1画出树的孩子-兄弟链表；将该树转化为二叉树。【解：】（1）先根序列：ABCEFIJGHKD（2）后根序列：BEIJFGKHCDA（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,/ 否则返回 ERROR if (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/if else 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) /按层次遍历二叉树tBiTree *quemaxnum;int rear,front;if (t!=NULL)front=0; /置空队列rear=1;que1=t;do front=front%maxsize+1; /出队 t=quefront; printf(t-data); if (t-lchild!=NULL) /左子树的根结点入队 rear=rear%maxsize+1; quer