《第四-六章+串、数组、树作业(参考答案)》由会员分享，可在线阅读，更多相关《第四-六章+串、数组、树作业(参考答案)（11页珍藏版）》请在金锄头文库上搜索。
1、第四-六章 串、数组、树作业一、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打 。 1（ ）子串是主串中任意个连续字符组成的序列。2（ ）线性结构只能用顺序结构存放，非线性结构只能用链表存放。3（ ）完全二叉树的某结点若无左孩子，则它必是叶结点。4（ ）二叉树有五种基本形态。5. （ ）由树的中序表示和前序表示可以导出树的后序表示。6. （ ）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。7. （ ）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。8. （ ）在Huffman树中，权值较大的叶子结点离根较远。9. （ ）用一维数组存储二叉树
2、时，是以先根遍历的次序存储结点。二、填空题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
3、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个结点的编号为 (
4、 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从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相
5、应编号写在对应栏内。有一个二维数组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，行下
6、标的范围是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的结点
7、的左孩子的编号为：( 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(sub
8、1,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的最后一个元素的
9、地址；按行存储时元素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
10、,则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) 前序序列与中序序列相同;(
11、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. 画出如下图所示树对应的二叉树。【解答】
12、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; r
13、eturn (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 s
