2022年第四-六章+串、数组、树作业 .pdf

《2022年第四-六章+串、数组、树作业 .pdf》由会员分享，可在线阅读，更多相关《2022年第四-六章+串、数组、树作业 .pdf（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（B

3、iTree 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）+- *abcd 2对于有N 个结点高度为K 的满二叉

4、树 ( 结点编号为1 到 N，根结点的层数为1) ，其第K层上最后 1 个结点的编号为 ( D )。A）2KB ）2K-1 C ）B）2K-1- 1 D）2K- 1 3将一棵有100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：( C ) 。A）48 B ）49 C）50 D）51 4在下列存储形式中，哪一个不是树的存储形式？( D ) 。A）双亲表示法 B）孩子链表表示法C）孩子兄弟表示法 D）顺序存储表示法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

5、师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 5某二叉树结点的中序序列为：A、B 、C、D、E 、 F、G，后序序列为：B、D 、C、A、F、G、E，则其左子树中结点数目为：( C ) 。A）3 B）2 C ）4 D）5 6从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在对应栏内。有一个二维数组A，行下标的范围是0 到 8，列下标的范围是1 到 5，每个数组元素用相邻的 4 个字节存储。 存储器按字节编址。假设存储数组元素A0,1 的第一个字节的地址是0。存储数组A 的最后一个元素的第一个字节的地址是A 。若按行存储，

6、则A3,5 和A5,3 的第一个字节的地址分别是B 和C 。若按列存储，则A7,1 和 A2,4 的第一个字节的地址分别是D 和E 。供选择的答案AE： 28 44 76 92 108 116 132 176 184 188 答案： ABCDE= 7、从供选择的答案中，选出应填入下面叙述内的最确切的解答，把相应编号写在对应栏内。有一个二维数组A，行下标的范围是1 到 6，列下标的范围是0 到 7，每个数组元素用相邻的 6 个字节存储，存储器按字节编址。那么，这个数组的体积是A 个字节。假设存储数组元素A1,0 的第一个字节的地址是0， 则存储数组A 的最后一个元素的第一个字节的地址是B 。若按

7、行存储，则A2,4 的第一个字节的地址是C 。若按列存储，则A5,7 的第一个字节的地址是D 。供选择的答案A D： 12 66 72 96 114 120 156 234 276 282 (11)283 （12）288 答案： A（ 12）BCD8将一棵有100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49 的结点的左孩子的编号为：( A )A）98 B）99 C）50 D）48 9. 设森林 F 中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2 和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是：( D )A）M1

8、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

9、,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的地址；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

10、 - - - - - - 第 2 页，共 11 页 - - - - - - - - - 按列存储时元素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的结点，则该树中有多少个叶子

11、结点？【解答】设树中结点总数为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 + 1 5. 已知二叉树有50 个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】 n0表示叶子结点数，n2表示度为2 的结点数，则n0 = n2+1 所以 n2= n0 1=49 ，当二叉树中没有度为1 的结点时，总

12、结点数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 个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：名师资料总结 - - -精品资料欢迎下载 - - - -

13、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 哈夫曼编码为：I1：11111I5：1100I2：11110I6： 10I3：1110 I7： 01I4：1101 I8： 00 8. 画出如下图所示树对应的二叉树。【解答】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 9. 分别写出算法， 实现在中序线索二叉树T

14、中查找给定结点*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 (p

15、re); （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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11

16、 页 - - - - - - - - - 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;

17、 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. 已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。【解

18、答】算法 (一) Void exchange ( BiTree root ) p=root; if ( p-LChild != NULL | p-RChild != NULL ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - temp = p-LChild; p-LChild = p-RChild; p-RChild = temp; exchange ( p-LChild ); exchange ( p-RChild );

19、算法 (二) 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）先根序列： ABCEFIJGHKD （2）后根序列： BEIJFGKHCDA （3）树的孩

20、子 -兄弟链表：A B C D H G F E K J I 图 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - A B C E F I J G D H K （4）转化为二叉树：A B G F C E I J D H K 13. 画出和下列已知序列对应的二叉树T：树的先根次序访问序列为GFKDAIEBCHJ ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

21、师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 树的后根次序访问序列为CBEFDGAJIKLH。【解： 】先根序列中G 是整棵树的根，后根序列中H 是整个树的根，矛盾，无解。14 假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA 。 请画出该树。【解： 】A B I C G H J F K D E 15 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF 。 请画出该树。【解： 】A B C D E G F I J H 16编写递归算法，在二叉树中求位于先序序列中第k 个位置的结

22、点的值。【解： 】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) ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

23、名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - /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编写算法，

24、层次遍历一棵二叉树。给定一棵用二叉链表表示的二叉树，其中的指针t 指向根结点， 试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。解答：考虑用一个顺序队que 来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que 为一个指向数据类型为bitree 的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front 为队头指针，rear 为队尾指针。levelorder (BiTree *t) /按层次遍历二叉树t BiTree *quemaxnum;int rear,front; if (t!=NULL) front=0; /置空队

25、列rear=1; que1=t; do front=front%maxsize+1; /出队t=quefront; printf(t-data); if (t-lchild!=NULL) /左子树的根结点入队 rear=rear%maxsize+1; querear=t-lchild; if (t-rchild!=NULL) /右子树的根结点入队 rear=rear%maxsize+1; querear=t-rchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共

26、 11 页 - - - - - - - - - while (rear= =front); /队列为空时结束 *思考题（不做在本子上） * 1名词解释：树，子树，结点的度，叶子结点，孩子，双亲，兄弟，深度，有序树，森林，二叉树，遍历二叉树，树的带权路径长度，哈夫曼树。2描述二叉树的性质。3从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别。4已知一棵树边的结点为, ,，试画出这棵树,并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点G 的双亲？（4）哪些是结点G 的祖先？（5）哪些是结点G 的孩子？（6）哪

27、些是结点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 页 - - - - - - - - -