最新數(shù)據(jù)結(jié)構(gòu)形成性考核答案作業(yè)1-4(編輯修改稿)
2025-07-25 04:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ue(LinkQueue *Q) /*出隊(duì)算法*/{ struct node *t。 if (Qrear==NULL) { printf(隊(duì)列為空!\n)。 return(0)。 } else if (Qrearnext==Qrear) /*只有一個(gè)結(jié)點(diǎn)時(shí)*/ { t=Qrear。 Qrear=NULL。 } else /*有多個(gè)結(jié)點(diǎn)時(shí)*/ { t=Qrearnext。 /*t指向第一個(gè)結(jié)點(diǎn)*/ Qrearnext=tnext。 /*引成循環(huán)鏈*/ } free(t)。 } elemtype gethead(LinkQueue *Q) /*取隊(duì)首元素算法*/ { if (Qrear==NULL) printf(隊(duì)列為空!\n)。 else return(Qrearnextdata)。 } int emptyqueue(LinkQueue *Q) /*判斷隊(duì)列是否為空算法*/ { if (Qrear==NULL) return(1)。 /*為空,則返回true*/ else return(0)。 /*不為空,則返回flase*/ }void dispqueue(LinkQueue *Q) /*顯示隊(duì)列中元素算法*/{ struct node *p=Qrearnext。 printf(隊(duì)列元素:)。 while (p!=Qrear) { printf(%c ,pdata)。 p=pnext。 } printf(%c\n,pdata)。}六、完成：實(shí)驗(yàn)2――棧、隊(duì)列、遞歸程序設(shè)計(jì)根據(jù)實(shí)驗(yàn)要求（見教材P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。作業(yè)3答案一、單項(xiàng)選擇題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)路徑長(zhǎng)度之和14．最優(yōu)二叉樹 最小的二叉樹15．69 16．2m1 17．多對(duì)多18．所有頂點(diǎn) 一次19．先序 20．按層次21．n222．鄰接矩陣 鄰接表23．2(n1)24．n125．棧三、綜合題1．寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結(jié)點(diǎn)，左子樹和右子樹這三個(gè)基本部分組成，即依次遍歷整個(gè)二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù)分為根結(jié)點(diǎn)、左子樹和右子樹三個(gè)部分…..，這樣劃分一直進(jìn)行到樹葉結(jié)點(diǎn)。(1)先序?yàn)椤案笥摇?，先序序列為：fdbacegihl(2)中序?yàn)椤白蟾摇?，中序序列為：abcdefghij(3)后序?yàn)椤白笥腋保笮蛐蛄袨椋篴cbedhjigf2．已知某二叉樹的先序遍歷結(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，請(qǐng)畫出這棵二叉樹，并寫出該該二叉樹后續(xù)遍歷的結(jié)果。 （1）二叉樹圖形表示如下： （2）該二叉樹后序遍歷的結(jié)果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 3．答⑴ 已知深度為k的二叉樹最多有2k1個(gè)結(jié)點(diǎn)(K≥1)， 291892 2101，故樹的高度為10⑵ 對(duì)于完全二叉樹來(lái)說(shuō)，度為1的結(jié)點(diǎn)只能是0或1 因?yàn)閚=n0+n1+n2和n0=n2+1 得：設(shè)n1=0，892=n0+0+n2=2n2+1 得n2不為整數(shù)出錯(cuò) 設(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⑷ 對(duì)于n個(gè)結(jié)點(diǎn)的完全二叉樹，最后一個(gè)樹葉結(jié)點(diǎn)，即序號(hào)為n的葉結(jié)點(diǎn)其雙親結(jié)點(diǎn) 即為最后一個(gè)非終端結(jié)點(diǎn)，序號(hào)為892/2=446。4．（1）先序序列和中序序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹（2）中序和后序序列相同的二叉樹為空樹或任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹（3）先序和后序序列相同的二叉樹為空樹或僅有一個(gè)結(jié)點(diǎn)5．（1）哈夫曼樹如圖B4所示。圖B4（2）其帶權(quán)路徑長(zhǎng)度WPL值為270。（3）每個(gè)字符的哈夫曼編碼為：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號(hào)-1