工大数据结构作业

1、 工大数据结构第三章作业 作者： 日期: 数据结构与算法上机作业 第三章 树 、选择题 、在一棵树中，如果结点 A 有 3 个兄弟 ,是 A 的双亲 ,则的度为D ?A 1B 2? . 3? D 2、深度为 h 的完全二叉树至少有个结点 ,至多有 个结点 ?A. h?. 2h-?C. 2+1D. 21 2（ -1） -1 +1 2（h- ） 前（n 1）层满，第 h 层只有一结点 3、具有 n 个结点的满二叉树有C 个叶结点。 A. /2 （-1）/2? . （n+1） 2? D. n/2+1 因为 二叉树中，有这样一个性质，如果其终端结点数（也就是叶子节点）的个 数为 n1,度为 2 的结点

2、数为 n2，则1n2+1；?假设叶子节点有 x 个,则度为 2 的个数为 x1： 所以： x- ； 所以 x = （n ）/2 （满二叉树） 所以 叶子节点个数为 :（n+1 ）/2 非终端结点为 ： （n1）/2- 、一棵具有 2个叶结点的完全二叉树最多有 B 个结点。 A. 48?B. ?C 50 ?D. 5 、已知二叉树的先根遍历序列是 BCDE ,中根遍历序列是 CBA DF,则后根遍历序列是 A。 ?A. CBEFD ?B. FE B?. EDFD. 不定 6、具有个叶结点的二叉树中有 个度为 2 的结点。 . 8?B 9. 0 ?D. 11 7、一棵非空二叉树的先序遍历序列与后序遍

3、历序列正好相反，则该二叉树一定满足 。 A 所有非叶结点均无左孩子 ? B. 所有非叶结点均无右孩子 C. 只有一个叶子结点 ? D A 和 B 同时成立 8、在线索二叉树中 ,所指结点没有左子树的充要条件是 ?A. t-leftUL? ?B. t-lt g=TRU ? C. t lta =TRU 且 -left=NULL ?D. 以上都不对 、个结点的 线索 二叉树上含有的线索数为 C 。 A 2B. -1 ?C. n+1D. n n-表示结点的左右子树，其余n-指针为空 线索取代原来的空链 10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法 B。 A 正确? B

4、 错误 C. 不确定 ? D. 都有可能 1、具有 n（n1）个结点的完全二叉树中 ,结点 （2in ）的左孩子结点是D 。 ?A. 2i . i+1 2i-1 D. 不存在 1、具有 4 个结点的完全二叉树的深度为C 。 A 5?B? ?C ?D?. 8 、将一颗有个结点的完全二叉树从上到下、从左到右一次对结点进行编号,根结 点的编号为 1 ，则编号为 45 的结点的右孩子的编号为 C 。 ?A. 46 ?B. 47C. 0 1 2i 举个简单的例子就可以看出来，比如 7 个节点时（也就是三层时 ） ，编 号为 1的左子树编号是 2，编号 2的左子树是 4，编号 3 的左子树编号为 。以此就

5、可以看出来。 左结点是 2i, 右结点才是 2i+1 14、在结点数为 n 的堆中插入一个结点时 ,复杂度为C A. O（n）? . （n） ?C. O（log2n）D. O（log n2） 15、两个二叉树是等价的，则它们满足 A 它们都为空 ? ?B 它们的左右子树都具有相同的结构 ?. 它们对应的结点包含相同的信息?D. A、B 和 C 6、包含 n 个元素的堆的高度为C。（符号 a 表示取不小最小整数 ） A ?B. lognC. log2（+）? . n+ 1、以下说法错误的是 。 ?A. 存在这样的二叉树 ,对其采用任何次序的遍历其结点访问序列均相同 ?B 二叉树是树的特殊情形 C

6、. 由树转换成二叉树 ,其根结点的右子树总是空的 D. 在二叉树中只有一棵子树的情形下，也要指出是左子树还是右子树 18、设 F是一个森林，是由 F变换得到的二叉树。若 F中有 n 个非终端结点 ,则 B 中没有 右孩子的结点有 个。 A. n-1 ?B. ?C. n+D. n+2 19、将一棵树 T 转换为二叉树 ,则 T 的后根序列是的B 。 A. 先根序列 ? . 中根序列C. 后根序列 ?D. 层次序列 2、将一棵树转换为二叉树后，这颗二叉树的形态是A 。 ?. 唯一的 ,根结点没有左孩子. 唯一的 ,根结点没有右孩子 ?C 有多种 ,根结点都没有左孩子D 有多种 ,根结点都没有右孩子

7、 树转换成二叉树，根节点是没有右孩子的，这由转换规则应该不难理解,且转换 规则是唯一的 ,所以转换成的二叉树是唯一的 21、设树的度为 4，其中度为 1, 2, 3, 4 的结点个数分别为 , 2, 1, ，则 T 中的叶结点的 个数为 D 。 A. 5 ?B. 6C. 7D. 8 22、设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为M1, M2 ， M3。与森 林 F 对应的二叉树根结点的右子树上的结点个数为 D 。 A. M ?. +2? C. M2 ?D. M23 2、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二 叉树是 C 。 A. 二叉排序

8、树 ?B 哈夫曼树 . 堆? 线索二叉树 2、用 5 个权值 3, ， 4, 5， 1构造的哈夫曼树的带权路径长度是 A. ?B. 3 C. 34? D 1 二、填空题 1、一棵二叉树有 6个结点 ,结点的度是 0 和。问这棵二叉树中度为 2 的结点有 3 个。 2、含 , B, C 三个结点的不同形态的二叉树有5 棵。 3、含有个度为的结点和 5 个叶子结点的完全二叉树， 有 1 或 0 个度为 的结点。 4、具有 0 个结点的完全二 叉树的叶子结点数为 0。 5、在用左右链表示的具有 n 个结点的二叉树中 , 共有 2n 个指针域 ,其中 n 1 个指针域用于指向其左右孩子 ,剩下的n+

9、个指针域是空的。 、如果一颗完全二叉树的任意一个非终结结点的元素都 不小于 其左儿子结点 和右儿子结点 （如果有的话 ）的元素，则称此完全二叉树为最大堆。 、堆是一种特殊形式的 完全 二叉树，对于最大堆而言，其根结点的元 素的值应该是所有结点元素中 最大的。 、二叉树的复制是指按照一棵已知的二叉树复制一个副本,使两者 等价 。复制二 叉树最长用的方法是 后根遍历递归算法 。 9、在定义堆时，通常采用结构体 方式定义相应的二叉树，这样可以很容 易实现其相关操作。 、在构建选择树时 , 根据孩子结点的获胜者确定他们双亲结点所得到的选择树称为 胜者树 。根据孩子结点的失败者确定他们双亲结点所得到的选

10、择树称为 败者树 。 11、树的表示方法包括数组 、 邻接表 和 左右 链。 12、表达式（+b*（ d）f 的波兰式（前缀式）是-+a*b- /ef，逆波兰式（后缀式）是 b d-*+ f 13、设 F 是由 T1 、T2、T三棵树组成的森林， 与 F对应的二叉树为 B。已知 T, T2， 3 的结点数分别为 n1, n2 和 n3, 则二叉树 B 的左子树中有n1个结点， 二叉树的右子树中有n2 n3个结点。 14、设二叉树的中根序列为 ABCDE ，后根序列为 B C FGE。则该二叉树的先根序 列为 AC DGF。该二叉树对应的森林中包含 2 棵 树。 15、先根次序遍历森林等同于按先

11、根 遍历对应的二叉树 ,后根次序遍历 森林等同与按 中根 遍历对应的二叉树。 16、一棵哈夫曼树有 19 个结点 ,则其叶子结点的个数为10 。 1、设有数据 WG, 19, 2， , , 3, 2, 0叶节点权重集合，则所构建哈 夫曼树的高是 ，带权路径长度 PL 为 169 。 8、设有一份电文中共使用 6 个字符 , b, c, d, e, f,其中出现频率依次为 2,3,4,7，8,19, 则字符 c 的哈夫曼编码是001,电文编码的总长度为80 。 20、在有个结点的哈夫曼树中 ,叶子结点总数为（n+1）/2,非叶结点的总数为（n 1）/2。 、试分别画出具有个结点的二叉树的所有不同

12、形态。 四、已知一棵二叉树的中根序列和后根序列分别是BDCEA G 和 DECBH A，请画出 此二叉树。 五、已知非空二叉树 T,写一个算法 ,求度为的结点的个数。 要求 : ?1、定义二叉树的抽象数据类型和型TREE，并定义基本操作。 2、编写函数 cou t2（BTRE T），返回度为 2 的节点的个数。 3、在主函数中，构建一个二叉树，并验证所编写的算法。 六、用递归方法写一个算法，求二叉树的叶子结点数int leaf u（ BTREE T）。 要求： 1、 定义二叉树的抽象数据类型和型 BTR ，并定义基本操作。 2、 编写函数 l fnum（BTR E T）,返回树 T 的叶子节点

13、的个数。 在主函数中 ,构建一个二叉树，并验证所编写的算法。 七、画出下图所表示的二叉树的中序线索二叉树和先序线索二叉树。 八、已知二叉树的先根序列是A FB DH KJ,中根序列是 E A CHKIJD, 画出此二 叉树，并画出后序线索二叉树。 九、在中序线索二叉树中插入一个结点 Q 作为树中某个结点 P 的左孩子，试给出相应的算 法。 要求 : 1、 定义中序线索二叉树的型 THRE 以及基本操作。 2、 定义函数 vo nsert（ HT EE P, HTRE ）； 实现题目要求的操作。 在主函数中， 利用操作 RInrt 和 LInsrt 构造一个线索二叉树 ,并中序输出二叉树的结点

14、的元素 ,验证结果。 ncl d # n l de # clud # nclud #i lude si g namespace td; y edef in el mentt p； truct ode /节点的型 e lchil ; noe* rchi ; bol lt g； ? ol rtg; ?element ype lemen ; ； typede node* ea； /指向树根 r t ef node* t ee； /指向线索树的根节点 oid ak N ll（he d h-ltag=false; ?h- child ； ?h-rt g ru ; head pointToree（head

15、 ?h- tag= rue； ?h rta rue; re ur h; /中根遍历的下一个节点 od in ext（ de p） ?n de* q=p- chil ; ? （p t g=true） /如果有右子树，找出右子树的最左节点 ?h le（q-ltag=true） ?q=q- chil ; ? t r q; /中根遍历的上一个节点 node* inPr （node* p ） ode *q= p-lchil ; if（ ltag true） /如果 P 的左子树存在，则其前驱结点为左子树的最右结点 ? ile（q g=true） ?= - chil ; return ;/左子树的最右结点

16、 中序遍历 vid t InOrder（head h） ?nod* t mp； ?temp=h; ?do ?temp=inNext（t mp） ; f（te p！ h） ? ?cout lement rchild=s-rchild; ?r-rtag s- rtag; r- i d=s； ? lta =false;/新插入的节点木有左子树，所以lchi 指向的是父节点 ? ch ld=r; ?s- a =true;/ 原节点的右孩子为新插入的节点 f（r-ra =tr e） ?/这里是神马意思呢 |?？ |,就是如果被插节点有右子树， /找出被插节点 s 的的 n xt 位置，即右子树中的最左节

17、点 ,令其 lchild 指向新添加的节 点r ?/因为插入前该最左节点的 l i d指向的是原来节点 s ? =i Ne t(r); ? -lch ld= ； /插入左孩子 voi lI sert(node s,node ) ?n e* w; l h l =s-lc ild; ?l ta s- l a； -r il =; rtagfa se； ?s-lc ild=l; ?s-lta =true ； ?if( -ltg=t ue)/与插入右孩子方法相似，只需把左右方向对调即可 ?w=inP e(l); ? w- child=l; ? i t mai() ? ead =n nd； nde roo

18、t new node; nd* c ew oe; node* rc=new no e; ?node c e n de; rot- e ent 1; ?lc-element 2； ? c-ele ent=3； c-el m nt ; ? ?h-rc ild=ro ； ?h lchil h； ?h tag=t ; ?h-r ag=true; oot- child h; o t- rch l； ootltag fals ; ?r o-tag=alse; ?/构造线索树 13 In ert( o,lc); ?rInsert(root,rc )； ?thInO der(h); ?c thea. leme

19、nt / . ata） heap.el ments =hea. lements / ; i/=2; epn+； H . lementsi e em ; Elmnttpe DeleteM x（HE P e p） 删除堆中最大元素 int ar t=1, hi d=2； Elemen t pe le ent,tm ; f（！ He Emp y（ a ） Element=heape em ts1; Tmp= p.e ementshe n; While （chil hap.n） If（ hildheap. ） He p.eleme tspar e = apeem tch d; P ra nt= il

20、; Child*=2; H ap.e en sp raent= ; R tu n el m nt; It nd（H AP,d atyp x） int m=1; While（ （ m H n） else ret r 0; e e m+ ； i （ m=H.n）retu n m; e se return 0; Int m in（） HEP H； E en ty e lement； Int data 1,3， 5,7,9,1,13; H.n=0; or（in i= ;i7;i+） e em nt ke =i+1; Elmnt.ata=data ; I ser （H, lement）; or（int

21、； i H.n;i + ） coutH.elem ntsi at edl; D le eMax （H）； F r（int i=1;i=H. ;i+ ）coutH.el men .dat ; Co t， endl; tx ； CoutF nd（H ， x）endl; 十二、给定叶子结点的权值集合 15, 3,1, 2, , 9, 16, 1 ，构造相应的哈夫曼树，并 计算其带权路径长度。 十三、已知 n= 和一组等价关系： 1 5、 6 8、 7、 8、37、4 2、93 试应用抽象数据类型 MSET 设计一个算法，按输入的等价关系进行等价分类。 #incl d dfine n 9/EFET 元

22、素个数 /MST 抽象数据型 str c ode int fath r； /指向父节点的链 int co ;/树结点个数 ; y ede mfnode MFS n+ ; id Unio （in A, it B, FST ） / 合并 A 和 B if（CA .countCB.coun ） C B ther=A;/B 并入 A A.co t+=CB .c nt; se CA f herB； /A 并入 B B.coun +=CA .co n； int ind（ i , M C） /求包含元素的树的根 int f; f=x ； while（fa r!=0）/ 未到根 f=C f.father ；

23、re n f; voi Iial（int ， FSET C）集合 A只包含元素 A C . ather0; CA .ou t=1; / 等价分类 void Equ lnce（FST S） int ， j, m, k; f r （ i=1; i ; 0 结束等价分类 cinj; whil （!（ = m=Find（j ， ）; if （k!=m） Unio （ , ， S） ； ? ini; c n ； vid int_M SET（FSET ） /输出等价类 int n+1n+1=0, k; for（ i=1; =n; i ） k=F d（ , S） ; rk0 +; rkrk =i; r（ =

24、1; 0） cout ; fo （ t j1; r 0; j+） coutrij ,； o tr r edl; void main（ ） MFST S; Eq ivalence（ ） ; pi _M ET（S）； 十四、画出下图所示的森林经转换后所对应的二叉树， 并指出在二叉树中某结点为叶子结点 时，所对应的森林中结点应满足的条件。 五、已知森林 F 的先根序列为 :ABCDEF HIJKL, 后根序列为 :CBE DG IKLH ，试画 出森林 F。 提示:先画出森林 F 所对应的二叉树，然后再将转换为森林。 十六、画出表达式（ B C/D）*E+F*G 所对应的树结构 ,并写出该表达式的波

25、兰表示式和 逆波兰表示式。 具体要求 1 实现二叉树的基本操作 2 实现将一个四则混合运算转换成二叉树的函数 3 4 十七、利用逆波兰表达式求一个四则混合元算的值。 #inclu e. st .cp 定义二叉树的型 BT E和位置的型 iion 实现计算四则混合运算的值的函数 :dube computer（BTR t）,其中 ,参数 bt 为四则运算所对应的树 ,返回值为计算结果。提示：先求树的的波兰表达式,然后利 用栈结构计算表达式的值。 BTRE c nver （ ha *ex ress），其中参数 xpre 为四则混合运算表达式 ,返回值为生成的树。 在主函数中进行测试 ,求 +*（5+

26、8）/45 的值 include #icud #defi AX 30 sing a esp ce td; char matc= =; ca opra =+-* （）; cons har ?w ile（o erai!=ch1） i+ ; while（ p a j!= h2） j+ ； ?re rn at hi*7+j ； class T ode public: TNode（ tring st =, nt b=0,T o *l NUL ， TN de *r= ULL ， TNode *p=N LL） ?strcpy（ d,str.c_str（）; ? t=; ?lf=l； ?r gh r； ? p

27、a nt=p ； ?TN d （const ch ch,TNode *l=N LL,TN de NU L,TNode p=NU L） ?id =ch; id1=0 ； b t=0； ?lft=; right= ; p rent=p; ? ont TNo e ? bit=t .bit; eft=tn left； ?r ght t .rih; arent= .parent; hr idA I; ? nt bi； ? o e *p ret,*l ft,* ight; ; nt Rea Expr （ c a tr, h *xpr,it sart，in bit,in i（ trstart =0 ） ex

28、pr; ?r t rn 0； ? els if（s rs a t= * | t s art=/ |st st rt= str t ） ?expr =strsta t; ? ex 1=0; ? leng h 1; ?re urn 2; ? le if（ bit|is igi （ st star）|str tart =） int b= ； t =0; /index fr exp ?while（s r s t= +|s rstart=-） / ead sgn ?i?（ str tar =-） +; ? star +; ? ?lengt + ； ? ? if（ %2） exprk+= ; ?hil （

29、 isd git（st tart ）| s rstart= .） ?e?xprk +=st tart ; ? len th+; ? ? ex k =0; re ur 1； els if （ st star = + | rstart =-） re （|strs art=）| / read digit string a oper or - int =0 ； hile(ststa = |st tar =-) ? f(strsta t=- ) b+; ? tar ; l ngth +； ? f(b%2) xp =-; ?else pr =+; ? expr1=0; ? rtrn 2; ?el re u

30、r -1; /error to a TNoe *Tra s ate(ons tring t) / ra sl te a xpres on srin expres o t e ?char su trMAXSIZE ; Sta k c tk； t ck s ; ? ar *tempstr=new h tr.length() ; int sa =0,bi =; nt t,l ngt； str p (temp tr,sr c_str( ); e tstr.leng h() = ; ? em r tr.len h()+1 0； ? s .pus （ ）; ?t=ReaExpr(tempstr ， ubs

31、tr, tar , t, ngh)； while(c tk.t ( )!= |subst 0 ！=) ?if ( =1)/is a dit string TNode np=n w N e(substr,1)； ?tstk. ush(np) ; bit0; ?else ( t=2) /is a per ?i?f(subtr0=() =1; ? e s i=0； ? hr tc= t top() ； ?if( atch(t h, b tr ) = ) TNod *r t=tstk. op(); t tk.pop(); ? ? Node left= st p(); ? t .po( ) ； ? ?N

32、od *np w Node(tch ， left, i t); ? ?lef arnt np； ? ?righ -pa t np; ? t k.p sh( np) ; ? ? c tk.po (); ?cntn e; ? ? ?ee if(M tch(tc , u s )= left） ? p int（root-l ft） ； ?p int（ o t righ ）; cout； el e co t d; void rin （Noe*）; dou l sove（TNode* ） ; o print x r（ tr g str） TNde * oot Translat （ tr） ?c ut 后缀

33、式 :; ?prin （ oot）; ?co end ; cout 中缀式： ； ?p ts（ro t）; cou = s e（ ot）eft=NULL） couti ;/is a leaf els if（root-pare t= NUL ） ? prnts（r o- left）; ?couti ; ?pri s（r t-righ ）; ?else if（root- ren -le t=root ?out id; ? rnt（ ot-right ） ; ? els if（ro t- are t-right= root） i（Match（oot rent id ,root-id0）=paren

34、- d0= +） ? ri （ro t- eft ）； out id; ? rints （ ro t rgh ）; ? else ?c?outle t）； ?cout id; r s（ oot-ri h ）; cou ）； ? ?else ?coutleft）; ?co tid; ?prit（r ot-right）; ? outleft=N LL） istrng tream in; ? i.str（ oot- id）; dou le va ue; ? invalue ； ?r turn val ； else witch（r o-id 0） cae ? tur lve（root-left）+so

35、lve（ ot ri ）; ca e - re rn s lve（r ot-left）-so ve（ oot-r gh ）; c s re urn olve（root lef ）*sol e（ rot right ） cas /: ?return solv（oo-lft）/ olv（root-right） ； ? ? vo d Chec（ ch r *str） /判断为带符号且紧跟括号的情况 ,酌情在前面添 0- ?it k=0,i 0; ?f（str0=+|tr0 =-） ?nt b=0 ； wile（strk=+|strk =-） ? if（ r= ） b+； ? k +; ? ?i（ str !=（ ） ret ； ? ha *np new