數據結構(本科)形成性考核冊答案(編輯修改稿)
2025-07-04 19:26 本頁面
【文章內容簡介】 d delqueue(LinkQueue *Q) /*出隊算法*/{ struct node *t。 if (Qrear==NULL) { printf(隊列為空!\n)。 return(0)。 } else if (Qrearnext==Qrear) /*只有一個結點時*/ { t=Qrear。 Qrear=NULL。 } else /*有多個結點時*/ { t=Qrearnext。 /*t指向第一個結點*/ 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)。}六、完成：實驗2――棧、隊列、遞歸程序設計根據實驗要求（見教材P203）認真完成本實驗，并提交實驗報告。作業(yè)3答案（本部分作業(yè)覆蓋教材第67章的內容）一、單項選擇題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．子樹樹木或后繼結點數2．樹中所有結點的度的最大值3．分支結點 非終端結點4．葉子結點 終端結點5．子樹的根 后繼結點 孩子結點6．祖先7．樹中結點的最大層數8． 9．根結點 左子樹 右子樹10．左子樹 根結點 右子樹11．左子樹 右子樹 根結點12．權13．帶權路徑長度之和14．最優(yōu)二叉樹 最小的二叉樹15．69 16．2m1 17．多對多18．所有頂點 一次19．先序 20．按層次21．n222．鄰接矩陣 鄰接表23．2(n1)24．n125．棧三、綜合題1．寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結點，左子樹和右子樹這三個基本部分組成，即依次遍歷整個二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù)分為根結點、左子樹和右子樹三個部分…..，這樣劃分一直進行到樹葉結點。(1)先序為“根左右”，先序序列為：fdbacegihl(2)中序為“左根右”，中序序列為：abcdefghij(3)后序為“左右根”，后序序列為：acbedhjigf2．已知某二叉樹的先序遍歷結果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍歷結果是：G，D，B，A，L，H，E，K，I，M，C，F和J，請畫出這棵二叉樹，并寫出該該二叉樹后續(xù)遍歷的結果。 （1）二叉樹圖形表示如下： （2）該二叉樹后序遍歷的結果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 3．答⑴ 已知深度為k的二叉樹最多有2k1個結點(K≥1)， 291892 2101，故樹的高度為10⑵ 對于完全二叉樹來說，度為1的結點只能是0或1 因為n=n0+n1+n2和n0=n2+1 得：設n1=0，892=n0+0+n2=2n2+1 得n2不為整數出錯 設n1=1，892=n0+1+n2=2n2+2 得n2 =445→ n0=n2+1=446 葉子結點數為446。⑶ 由⑵得單支結點數為1⑷ 對于n個結點的完全二叉樹，最后一個樹葉結點，即序號為n的葉結點其雙親結點 即為最后一個非終端結點，序號為892/2=446。4．（1）先序序列和中序序列相同的二叉樹為空樹或任一結點均無左孩子的非空二叉樹（2）中序和后序序列相同的二叉樹為空樹或任一結點均無右孩子的非空二叉樹（3）先序和后序序列相同的二叉樹為空樹或僅有一個結點5．（1）哈夫曼樹如圖B4所示。圖B4（2）其帶權路徑長度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的拓撲序列為：v1,v2,v4,v6,v5,v5,v3,
教學教案相關推薦
鄂ICP備17016276號-1