【正文】 我不知道年少輕狂，我只知道勝者為王。 }}//算法結(jié)束習(xí)題五參考答案一、單選題（每題2分，共20分）1．B 2．D 3．A 4．B 5．B6．D 7．C 8．A 9．D 10．A二、填空題（每空1分，共25分）1．集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 圖形結(jié)構(gòu)2．O（n） O（1）3．行號(hào) 列號(hào) 元素值（次序無(wú)先后）4．35．top= =06．5507．168．最小值 最大值9．n110．O（n2） O（n十e） O（e）11．順序 有序12．稠密稀疏13．O（1og2n） O（n）三、運(yùn)算題（每題5分，共20分）1．（40，38．35，30，25，20）2．（0，3）2，（4，6）4，（0，2）5，（1，5）6，（0，1）8，（3，6）10，（5，7） 203．（50，42，46，38，40，56 ，79，84）4．［36 38 40 40 46 56 79 80］［25 66 75 84］四、閱讀算法，回答問(wèn)題（每題5分，共10分）1．（50，30，5，8，12，15）2．12 15 5 30 18五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容（10分）（A[i] stn＜x．stn）QuickSort（A，s，j 1） QuickSort（A，j + 1，t）；六、編寫(xiě)算法（15分） int count（RtreeNOde*BT）／／統(tǒng)計(jì)出二叉樹(shù)中所有葉子結(jié)點(diǎn)數(shù) { if（BT= =NULL）return 0： else if（BT一left= =NULLamp。void b(int P[],int i,int k)//從集合（1..n）中選取k（k=n）個(gè)元素的所有組合{if (k==0) printf(P)。即包括1時(shí)，求出集合（2..n）中取出k1個(gè)元素的所有組合；不包括1 時(shí)，求出集合（2..n）中取出k個(gè)元素的所有組合。}習(xí)題四參考答案一、選擇題（每題2分，共20分）12345678910CDACCDCDBC二、填空題（每空2分，共30分）1．算法的時(shí)間復(fù)雜度和空間復(fù)雜度2．有窮性； 確定性； 可行性。return true。 （2分） 最小生成樹(shù)的權(quán)：55 3 1 2 5 6 四、閱讀算法，回答問(wèn)題（第一題7分，第二題8分） （12，26，9，8，15，30，50） 向HBT堆中插入一個(gè)值為item的元素，使得插入后仍是一個(gè)堆。6．答：（1）176 （2）76和108 （3）28和116。再把另外兩個(gè)元素按折半插入排序方法，插入到上述某個(gè)序列中共需4次比較，從而共需7次比較。（n2=n01） （3）哈夫曼樹(shù)見(jiàn)下圖，其帶權(quán)路徑長(zhǎng)度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=514561235．答：n（n0）個(gè)結(jié)點(diǎn)的d度樹(shù)共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)福试摌?shù)的空鏈域有nd(n1)=n(d1)+1個(gè)。五、算法填空，在畫(huà)有橫線的地方填寫(xiě)合適的內(nèi)容（10分）從一維數(shù)組A[n]上進(jìn)行快速排序的遞歸算法。 數(shù)據(jù)排列情況： 。三、運(yùn)算題（每題5分，共20分）1．假定一個(gè)大堆為（56，38，42，30，25，40，35，20），則依次從中刪除兩個(gè)元素后得到的堆為 。10．假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，貝采用鄰接矩陣、鄰接表和邊集數(shù)組表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為 、 和 。6．假定一棵三叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小深度為 ，最大深度為 。2．對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為 。(lgn) (nlgn) (n2) (n)8．廣義表(A,B,E,F,G)的表尾是（ ）。A前一個(gè) B后一個(gè) C當(dāng)前4．向二叉搜索樹(shù)中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（ ）。例如，從集合{1..4}中選取2個(gè)元素的所有組合的輸出結(jié)果為：1 2，1 3，1 4，2 3， 2 4，3 4?！={0,2,1,3,1,4,2,4,2,5,3,6,3,7,4,7,4,8,5,7,6,7,7,8}?！={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20,(6,7)30}。三、計(jì)算題（每題6分，共30分）1．如果輸入序列為1 2 3 4 5 6,試問(wèn)能否通過(guò)棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5 4 2 6。7．廣義表的_______ 定義為廣義表中括弧的重?cái)?shù)。4．對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 ______個(gè)，單鏈表為_(kāi)______個(gè)。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改9．若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10．棧和隊(duì)列的共同點(diǎn)是（ ）。pLlink=q。pLlinkRlink=q。qRlink=p。qRlink=p。A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（ ）？ A．廣義表 B. 二叉樹(shù) C. 稀疏矩陣 D. 串3．連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（ ）。}else return 1。int Binsch( ElemType A[] , int low , int high , KeyType K ){ if ( low=high ){int mid = (low+high)/2。 } [i]=x。 while ( i != 0 ){ int j=(i1)/2。void AH(Heap amp。for ( int i=0。 HL){ InitList(HL)。最小生成樹(shù)的權(quán)： 。先根： 。 1二分查找過(guò)程所對(duì)應(yīng)的判定樹(shù)既是一棵 ，又是一棵 。 對(duì)于一棵含有40個(gè)結(jié)點(diǎn)的理想平衡樹(shù)，它的高度為 。 在初始化一個(gè)稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說(shuō)明為 參數(shù)。A、f+1==r B、r+1==f C、f==0 D、f==r由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù) 。請(qǐng)構(gòu)造一棵哈曼夫樹(shù)，并計(jì)算該哈曼夫樹(shù)的帶權(quán)路徑長(zhǎng)度wpl。2．有一隨機(jī)數(shù)組(25,84,21,46,13,27,68,35,20),現(xiàn)采用某種方法對(duì)它們進(jìn)行排序,其每趟排序結(jié)果如下, 則該排序方法是什么? 初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 3．請(qǐng)?jiān)冢? ）內(nèi)填入正確的排序方法。8．在一棵二叉樹(shù)中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。4．在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為 和 。A、無(wú)向圖 B、有向圖 C、稠密圖 D、稀疏圖10．若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C、一組