最新數(shù)據(jù)結(jié)構(gòu)形成性考核答案作業(yè)1-4(編輯修改稿)
2025-07-25 04:51 本頁面
【文章內(nèi)容簡介】 ue(LinkQueue *Q) /*出隊算法*/{ struct node *t。 if (Qrear==NULL) { printf(隊列為空!\n)。 return(0)。 } else if (Qrearnext==Qrear) /*只有一個結(jié)點(diǎn)時*/ { t=Qrear。 Qrear=NULL。 } else /*有多個結(jié)點(diǎn)時*/ { t=Qrearnext。 /*t指向第一個結(jié)點(diǎn)*/ Qrearnext=tnext。 /*引成循環(huán)鏈*/ } free(t)。 } elemtype gethead(LinkQueue *Q) /*取隊首元素算法*/ { if (Qrear==NULL) printf(隊列為空!\n)。 else return(Qrearnextdata)。 } int emptyqueue(LinkQueue *Q) /*判斷隊列是否為空算法*/ { if (Qrear==NULL) return(1)。 /*為空,則返回true*/ else return(0)。 /*不為空,則返回flase*/ }void dispqueue(LinkQueue *Q) /*顯示隊列中元素算法*/{ struct node *p=Qrearnext。 printf(隊列元素:)。 while (p!=Qrear) { printf(%c ,pdata)。 p=pnext。 } printf(%c\n,pdata)。}六、完成：實(shí)驗2――棧、隊列、遞歸程序設(shè)計根據(jù)實(shí)驗要求（見教材P203）認(rèn)真完成本實(shí)驗，并提交實(shí)驗報告。作業(yè)3答案一、單項選擇題1．B 2．B 3．D 4．C 5．B 6．A 7．A 8．C 9．A 10. D11. A 12．C 13．C 14．B 15．B 16．C 17．B 18．C 19．A 20．B21．D 22．B 23. B 24. B 25. C 26. A 27．A 28．C二、填空題 1．子樹樹木或后繼結(jié)點(diǎn)數(shù)2．樹中所有結(jié)點(diǎn)的度的最大值3．分支結(jié)點(diǎn) 非終端結(jié)點(diǎn)4．葉子結(jié)點(diǎn) 終端結(jié)點(diǎn)5．子樹的根 后繼結(jié)點(diǎn) 孩子結(jié)點(diǎn)6．祖先7．樹中結(jié)點(diǎn)的最大層數(shù)8． 9．根結(jié)點(diǎn) 左子樹 右子樹10．左子樹 根結(jié)點(diǎn) 右子樹11．左子樹 右子樹 根結(jié)點(diǎn)12．權(quán)13．帶權(quán)路徑長度之和14．最優(yōu)二叉樹 最小的二叉樹15．69 16．2m1 17．多對多18．所有頂點(diǎn) 一次19．先序 20．按層次21．n222．鄰接矩陣 鄰接表23．2(n1)24．n125．棧三、綜合題1．寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結(jié)點(diǎn)，左子樹和右子樹這三個基本部分組成，即依次遍歷整個二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù)分為根結(jié)點(diǎn)、左子樹和右子樹三個部分…..，這樣劃分一直進(jìn)行到樹葉結(jié)點(diǎn)。(1)先序為“根左右”，先序序列為：fdbacegihl(2)中序為“左根右”，中序序列為：abcdefghij(3)后序為“左右根”，后序序列為：acbedhjigf2．已知某二叉樹的先序遍歷結(jié)果是：A，B，D，G，C，E，H，L，I，K，M，F(xiàn)和J，它的中序遍歷結(jié)果是：G，D，B，A，L，H，E，K，I，M，C，F(xiàn)和J，請畫出這棵二叉樹，并寫出該該二叉樹后續(xù)遍歷的結(jié)果。 （1）二叉樹圖形表示如下： （2）該二叉樹后序遍歷的結(jié)果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 3．答⑴ 已知深度為k的二叉樹最多有2k1個結(jié)點(diǎn)(K≥1)， 291892 2101，故樹的高度為10⑵ 對于完全二叉樹來說，度為1的結(jié)點(diǎn)只能是0或1 因為n=n0+n1+n2和n0=n2+1 得：設(shè)n1=0，892=n0+0+n2=2n2+1 得n2不為整數(shù)出錯 設(shè)n1=1，892=n0+1+n2=2n2+2 得n2 =445→ n0=n2+1=446 葉子結(jié)點(diǎn)數(shù)為446。⑶ 由⑵得單支結(jié)點(diǎn)數(shù)為1⑷ 對于n個結(jié)點(diǎn)的完全二叉樹，最后一個樹葉結(jié)點(diǎn)，即序號為n的葉結(jié)點(diǎn)其雙親結(jié)點(diǎn) 即為最后一個非終端結(jié)點(diǎn)，序號為892/2=446。4．（1）先序序列和中序序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無左孩子的非空二叉樹（2）中序和后序序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無右孩子的非空二叉樹（3）先序和后序序列相同的二叉樹為空樹或僅有一個結(jié)點(diǎn)5．（1）哈夫曼樹如圖B4所示。圖B4（2）其帶權(quán)路徑長度WPL值為270。（3）每個字符的哈夫曼編碼為：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01 6．答（1）深度優(yōu)先遍歷：v1,v2,v3,v8,v5,v7,v4,v6 廣度優(yōu)先遍歷：v1,v2,v4,v6,v3,v5,v7,v8(2) G的拓?fù)湫蛄袨椋簐1,v2,v4,v6,v5,v5,v3,v5,v7,v8(3
試題試卷相關(guān)推薦
鄂ICP備17016276號-1