數(shù)據(jù)結(jié)構(gòu)試卷(二)及答案

《數(shù)據(jù)結(jié)構(gòu)試卷(二)及答案》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（）。(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。(A)2m-1(B)2m(C)2m+1(D)4m3．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（

2、）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。(A)BADC(B)BCDA(C)CDAB(D)CBDA5．設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有（）條邊。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-16．設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（）。(A)9(B)10(C)11(D)127．設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點(diǎn)。(A)n-1(B)n(C)n+1(D)2n-18．設(shè)一

3、組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8二、填空題(24分)1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(s

4、tack.top==m-1)printf(“overflow”);else{____________________;_________________;}}3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。1.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。2.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)

5、之和為d，則e=_______。3.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。4.設(shè)某無向圖G的鄰接表為，則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。三、應(yīng)用題(36分)1．設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2．設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序

6、列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink）。3．設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4．設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5．設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6．設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求

7、構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計題(16分)1．設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。2．設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題1.D2.B3.C4.A5.A6.C7.B8.C二、填空題1.構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法2.stack