計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料

計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料PAGE1計算機(jī)科學(xué)與技術(shù)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料1一、填空題1．若規(guī)定二叉樹根結(jié)點的層次為1，則第4層上最多有________個結(jié)點。2．具有N個結(jié)點的無向完全圖共有________條邊。3．樹轉(zhuǎn)換為二叉樹，其根結(jié)點的________子樹一定為空。4．對一棵二叉排序樹進(jìn)行中序遍歷時，得到的結(jié)點序列是一個________。5．已知二維數(shù)組a[10][8]采用行優(yōu)先存儲方式，每個元素占2個存儲單元，第一個元素的存儲地址是1012，則元素a[4][5]的存儲地址為（）。6．快速排序在平均情況下的時間復(fù)雜度為_____，在最壞情況下的時間復(fù)雜度為_____。7．畫出具有3個結(jié)點的二叉樹的所有形態(tài)：________。8.對于一個單鏈接存儲的線性表，假定表頭指針指向鏈表的第一個結(jié)點，則在表頭插入結(jié)點的時間復(fù)雜度為________，在表尾插入結(jié)點的時間復(fù)雜度為________。9．?dāng)?shù)據(jù)結(jié)構(gòu)課程是研究數(shù)據(jù)的________、________、________等三個方面的內(nèi)容。10.已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)是________。二、應(yīng)用題1．已知二叉樹的中序遍歷序列和后序遍歷序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。2．若一個圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，從頂點A開始分別對該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點值小的鄰接點被優(yōu)先訪問，則寫出得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點序列。3．下圖所示是一個無向帶權(quán)圖，請按Prim算法求最小生成樹。4．給定數(shù)據(jù)元素系列為{47，23，2，15，98，57，22，6，12}，請寫出直接選擇排序各趟的結(jié)果。5．已知散列函數(shù)H(k)=kmod12，鍵值序列為(25,37,52,43,84,99,120,15,26,11,70,82)，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度。計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共1頁，當(dāng)前為第1頁。

答案計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共1頁，當(dāng)前為第1頁。一、填空題1.82.N(N+1)/23.右子樹4.有序序列5.1050.6.O(log2n),O(log2n)7.8.O(1),O(n)9.操作對象、關(guān)系、操作10.68二、應(yīng)用題1.二叉樹的構(gòu)造過程如圖：2.深度優(yōu)先搜索得到的頂點序列：A,B,D,E,F,C廣度優(yōu)先搜索得到的頂點序列：A,B,C,D,F,E3.解答：按Prim算法求最小生成樹的過程如下：計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共2頁，當(dāng)前為第2頁。計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共2頁，當(dāng)前為第2頁。4.解答：初始：47，23，2，15，98，57，22，6，12.第一趟：2，【23，47，15，98，57，22，6，12】第二趟：2，6，【47，15，98，57，22，23，12】第三趟：2，6，12，【15，98，57，22，23，47】第四趟：2，6，12，15，【98，57，22，23，47】第五趟：2，6，12，15，22，【57，98，23，47】第六趟：2，6，12，15，22，23，【98，57，47】第七趟：2，6，12，15，22，23，47，【57，98】第八趟：2，6，12，15，22，23，47，57，【98】最后所得：2，6，12，15，22，23，47，57，985.解答：H(25)=1,H(37)=1,H(52)=4,H(43)=7,H(84)=0,H(99)=3,H(120)=0,H(15)=3,H(26)=2,H(11)=11,H(70)=10,H(82)=10。構(gòu)造的開散列表如下：計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共3頁，當(dāng)前為第3頁。計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共3頁，當(dāng)前為第3頁。

計算機(jī)科學(xué)與技術(shù)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料2一、應(yīng)用題1．對給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。2．若一個圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，從頂點A開始分別對該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點值小的鄰接點被優(yōu)先訪問，則寫出得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點序列。3．已知一組元素為（46,25,78,62,12,37,70,29），試畫出按元素排列次序插入生成的一棵二叉排序樹。4．給定數(shù)據(jù)元素系列為{47，23，2，15，98，57，22，6，12}，請寫出直接選擇排序各趟的結(jié)果。5．設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27，55，11，試畫出用線性探查法解決沖突時所構(gòu)造的散列表。二、算法設(shè)計題1.設(shè)計一個算法，在順序線性表L中刪除第i個元素，并返回其值。計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共4頁，當(dāng)前為第4頁。

答案計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共4頁，當(dāng)前為第4頁。一、應(yīng)用題1.構(gòu)造的哈夫曼樹如圖：樹的帶權(quán)路徑長度為：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202.深度優(yōu)先搜索得到的頂點序列：A,B,D,E,F,C廣度優(yōu)先搜索得到的頂點序列：A,B,C,D,F,E3.解答：4.解答：初始：47，23，2，15，98，57，22，6，12.第一趟：2，【23，47，15，98，57，22，6，12】第二趟：2，6，【47，15，98，57，22，23，12】第三趟：2，6，12，【15，98，57，22，23，47】第四趟：2，6，12，15，【98，57，22，23，47】第五趟：2，6，12，15，22，【57，98，23，47】第六趟：2，6，12，15，22，23，【98，57，47】第七趟：2，6，12，15，22，23，47，【57，98】第八趟：2，6，12，15，22，23，47，57，【98】最后所得：2，6，12，15，22，23，47，57，985.解答：設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm，給定的關(guān)鍵碼序列為計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共5頁，當(dāng)前為第5頁。19,14,23,01,68,20,84,27,55,11,則有計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共5頁，當(dāng)前為第5頁。H(19)=6，成功；H(14)=1,成功；H(23)=10,成功；H(01)=1，沖突，=2，成功；H(68)=3,成功；H(20)=7,成功；H(84)=6，沖突，=7，沖突，=8，成功；H(27)=1，沖突，=2，沖突，=3，沖突，=4，成功；H(55)=3，沖突，=4，沖突，=5，成功；H(11)=11,成功。

012345678910111214016827551920842311(1)(2)(1)(4)(3)(1)(1)(3)(1)(1)二、算法設(shè)計題1.【解答】StatusListDelete_Sq(SqList&L,inti,ElemType&e){if(i<1||i>L.length)teturnERROR;p=&L.elem[i-1];e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p+1)=*p;--L.length;returnOK;}計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共6頁，當(dāng)前為第6頁。

計算機(jī)科學(xué)與技術(shù)《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料3計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共6頁，當(dāng)前為第6頁。一、應(yīng)用題1．對于下列二叉樹，請寫出：（1）前、中、后序遍歷次序；（2）中序線索二叉樹；AABCGDEFH2．若一個圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，從頂點A開始分別對該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點值小的鄰接點被優(yōu)先訪問，則寫出得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點序列。3．給定葉子結(jié)點的權(quán)值{1，4，6，2，9}，請構(gòu)造哈夫曼樹，并給出葉子結(jié)點的哈夫曼編碼。4．已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用快速排序法進(jìn)行排序時每一趟的排序結(jié)果。5．設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm，給定的關(guān)鍵碼序列為19,14,23,01,68,20,84,27,55,11,試畫出用線性探查法解決沖突時所構(gòu)造的散列表。二、算法設(shè)計題1、設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共7頁，當(dāng)前為第7頁。

答案計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共7頁，當(dāng)前為第7頁。一、應(yīng)用題1.(1)前序遍歷次序：ABDGCEFH中序遍歷次序：DGBAECHF后序遍歷次序：GDBEHFCA(2)中序線索二叉樹AABCGDEFHNILLNILL2.深度優(yōu)先搜索得到的頂點序列：A,B,D,E,F,C廣度優(yōu)先搜索得到的頂點序列：A,B,C,D,F,E3.解答：112469各符號的哈夫曼編碼為：1:000；2：0001；4：001；6：01；9：14.解答：初始：[46745314263886652734]第一趟：[3414263827]46[86655374]第二趟：[271426]343846[746553]86第三趟：[2614]27343846[5365]7486計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共8頁，當(dāng)前為第8頁。第四趟：14262734384653657486計算機(jī)本科《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)資料全文共8頁，當(dāng)前為第8頁。5.解答：設(shè)散列表的長度m=13；散列函數(shù)為H(K)=Kmodm，給定的關(guān)鍵碼序列為19,14,23,01,68,20,84,27,55,11,則有H(19)=6，成功；H(14)=1,成功；H(23)=10,成功；H(01)=1，沖突，=2，成功；H(68)=3,成功；H(20)=7,成功；H(84)=6，沖突，=7，沖突，=8，成功；H(27)=1，沖突，=2，沖突，=3，沖突，=4，成功；H(55)=3，沖突，=4，沖突，=5，成功；H(11)=11,成功。

012345678910111214016827551920842311(1)(2)(1)(4)(3)(1)(1)(3)(1)(1)二、算法設(shè)計題1.【解答】ElemTypeMax(LinkListL){//假定第一個結(jié)點中數(shù)據(jù)具有最大值if(L-