數(shù)據(jù)結(jié)構(gòu)復習卷部分答案

1、華東華東理工大學理工大學繼續(xù)繼續(xù)教育學院教育學院《數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)》期中期中試卷（卷（閉卷）卷）班級學號姓名成績一填空題（共填空題（共2020分，每空分，每空2分）分）題號①②③④⑤小計解答題號⑥⑦⑧⑨⑩解答1設r指向單鏈表的某一個結(jié)點，要在該結(jié)點之后插入數(shù)據(jù)元素x，需執(zhí)行的語句是s=malloc(size)sdata=xsnext=rnextrnext=s。2一棵含有n個結(jié)點的二叉樹，它的最小深度為INT(log2(n)1)。log以2為

2、底的n的對數(shù)，加1后取整。3樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法，雙親表示法和孩子兄弟鏈表法。4已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹中有11個葉子結(jié)點。一棵度為M的樹中有N1個度為1的結(jié)點，N2個度為2的結(jié)點。。。Nm個度為m的結(jié)點，葉子數(shù)算法：N0=1N22N33N4…..(m1)nm就是不考慮度為1的結(jié)點5將一棵有100個結(jié)點的完全二叉樹按層編號，則編號為49的結(jié)點的雙親編號為24。完全二

3、叉樹某一結(jié)點N的雙親算法：INT(N2)6設s[maxsize]為一個順序存儲的棧，變量top指向棧頂位置，棧為滿的條件是top=maxsize1，因為C語言中top指針從0開始，7一棵哈夫曼樹T，其葉子結(jié)點的權(quán)分別為3，16，7，4，11，這棵哈夫曼樹的帶權(quán)路徑長度為41。哈夫曼樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和8若一棵二叉樹的葉子數(shù)為n，則該二叉樹中，左、右子樹皆非空的結(jié)點個數(shù)為n1。同第4題，n=1N2所以N2=

4、n19用循環(huán)鏈表存儲線性表，可以從表中任一結(jié)點出發(fā)都能訪問到所有結(jié)點。10設計一個判別表達式中左右括號是否配對的算法，采用棧數(shù)據(jù)結(jié)構(gòu)最佳。二、選擇題（共選擇題（共2020分，每空分，每空2分）分）題號①②③④⑤⑥⑦⑧⑨⑩小計選擇BADBDD16534BAD1設有一順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素出棧的順序是s2，s3，s4，s6，s5，s1，則棧的容量至少應該是B。A)2B)3C)5D)6進棧出棧表

5、如下：s1s1s2s1s1s3s1s1s4s1s1s5s1s5s6s1s5s102鏈棧和順序棧相比，有一個較明顯的優(yōu)點是A。A)通常不會出現(xiàn)棧滿的情況B)通常不會出現(xiàn)?？盏那闆rC)插入操作更加方便D)刪除操作更加方便鏈?？梢詿o限增加下去，⑥二叉樹是樹的特殊形式。⑦隊列是一個具有后進先出性質(zhì)的線性數(shù)據(jù)結(jié)構(gòu)。⑧串的數(shù)據(jù)元素類型只能是字符。⑨若一棵二叉樹的先序和后序遍歷序列正好相反，則該二叉樹一定只有一個結(jié)點。⑩順序表的存儲密度一定比鏈表的存

6、儲密度大。四、四、應用題（共（共20分，每小分，每小題5分）分）1設用于通訊的電文僅由7個字母組成，字母在電文中出現(xiàn)的頻率分別為3，12，9，6，17，21，32。請為這7個字母設計哈夫曼編碼。（注：寫出設計過程）2一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列ABDFKICEHJG中序序列DBKFIAHEJCG后序序列DKIFBHJEGCA3分別用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)