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

第四-六章 串、数组、树作业一、判断正误：（每小题 1 分，共 5 分）正确在（ ）内打，否则打 。 1（ ）子串是主串中任意个连续字符组成的序列。2（ ）线性结构只能用顺序结构存放，非线性结构只能用链表存放。3（ ）完全二叉树的某结点若无左孩子，则它必是叶结点。4（ ）二叉树有五种基本形态。5. （ ）由树的中序表示和前序表示可以导出树的后序表示。6. （ ）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。7. （ ）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。8. （ ）在 Huffman 树中，权值较大的叶子结点离根较远。9. （ ）用一维数组存储二叉树时，是以先根遍历的次序存储结点。二、填空题1已知二维数组 A010020采用行序为主方式存储，每个元素占 2 个存储单元,并且 A00的存储地址是 1024, 则 A618的地址是 1312 (1024+2*(6*21+18) 。2. 深度为 5 的二叉树最多有_31_个结点（根结点层数为 1）。3高度为 h 的完全二叉树最少有 2 h-1 个结点。4. 二叉树的先序遍历序列为：EFHIGJK，中序遍历序列为：HFIEJKG，则该二叉树根的右子树的根是： G 。5. N 个结点的二叉树,采用二叉链表存放,空链域的个数为 N+1 。6. 填空完成下面中序遍历二叉树的非递归算法：void InOrder（BiTree root） InitStack ( p = _root_ ;while ( _p_ | ! IsEmpty(S) while (p!=NULL) Push(p = _p-lchild_ ;if ( _! IsEmpty(S)_ ) Pop( 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）2 K B）2 K1 C）B）2 K11 D）2 K13将一棵有 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 的结点，n 2 个度为 2 的结点，n k 个度为 k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为 n,则 n=n0 + n1 + + nk树中分支数目为 B,则 B=n1 + 2n2 + 3n3 + + knk因为除根结点外，每个结点均对应一个进入它的分支，所以有 n= B + 1即 n0 + n1 + + nk = n1 + 2n2 + 3n3 + + knk + 1由上式可得叶子结点数为：n 0 = n2 + 2n3 + + (k-1)nk + 15. 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n 0 表示叶子结点数，n 2 表示度为 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：1100I2：11110 I6： 10I3：1110 I 7： 01 I4：1101 I 8： 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(p=root;while(p!=NULL | !IsEmpty(S) ) if(p!=NULL)Visit(p-data);push(p=p-Lchild;elsePop( 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）先根序列：ABCEFIJGHKD（2）后根序列：BEIJFGKHCDA（3）树的孩子-兄弟链表：AB C DHGFEKJI图 1A 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； 树的后根次序访问序列为 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 个位置的结点的值。【解：】int n=0;Status Preorder (BiTree T, int k, ElemType 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 elsem = 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 *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;querear=t-lchild;if