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

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

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

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

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

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

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