浙江工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷

1、精選優(yōu)質(zhì)文檔-傾情為你奉上浙工大0708學(xué)年 數(shù)據(jù)結(jié)構(gòu)試卷A一、單選題. (201 = 20分)1常用的算法時(shí)間復(fù)雜度中，按照復(fù)雜度優(yōu)劣排列正確的是（ ）。A) O(1)O(log2n) O(n) O(n2) O(nlog2n) B) O(1)O(n) O(log2n)O(n2) O(nlog2n)C) O(1)O(log2n) O(n) O(nlog2n ) O(n2)D) O(1)O(n) O(l og2n)O(nlog2n)O(n2)2線性表如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)或不連續(xù)

2、都可以3用于解決圖的點(diǎn)對(duì)之間的最短路徑的算法是（ ）。A) 圖的深度優(yōu)先遍歷算法 B) 圖的Dijkstra算法C) 圖的Warshall算法 D) 圖的floyd算法4以下的數(shù)據(jù)結(jié)構(gòu)中，是線性結(jié)構(gòu)的是（ ）。A) 棧 B) 散列 C) 圖 D) 優(yōu)先隊(duì)列5以下滿足隊(duì)列特點(diǎn)是（ ）。A) 后到先服務(wù)B) 在相同的端點(diǎn)添加和刪除元素 C) 在一端添加元素，在另一端刪除元素D) 先進(jìn)后出6. 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（ ）。 A)線性結(jié)構(gòu)B)樹型結(jié)構(gòu)C)鏈?zhǔn)浇Y(jié)構(gòu) D)圖型結(jié)構(gòu)7根據(jù)二叉樹的定

3、義， 3個(gè)結(jié)點(diǎn)的二叉樹有幾種形態(tài)（ ）。A) 6 B) 5 C) 4 D) 38下列應(yīng)用中，需使用隊(duì)列的是（ ）。A）實(shí)現(xiàn)遞歸算法 B）實(shí)現(xiàn)樹的層次遍歷C）實(shí)現(xiàn)表達(dá)式計(jì)算 D）實(shí)現(xiàn)深度優(yōu)先搜索9使用按照中序遍歷二叉排序樹，得到的遍歷序列滿足（ ）。A)亂序 B) 降序 C) 升序 D) 情況隨機(jī)10設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（ ）。A)15，25，35，50，20，40，80，85，36，70B)15，25，35，50，80，20，85，40

4、，70，36C)15，25，35，50，80，85，20，36，40，70D)15，25，35，50，80，20，36，40，70，8511在以下的序列中，哪個(gè)是最小堆？（ ） A)29，53，56，72，34，67，86 B) 86，72， 34，48， 56， 53，29 C)29，33，50，72，48，92，133 D) 34，42，53， 12， 5， 29， 3312散列表長(zhǎng) m = 15, 散列函數(shù)hash(key) = key % 13, 表中已經(jīng)有了4個(gè)結(jié)點(diǎn), 關(guān)鍵字分別是18, 32, 59, 73, 其余地址為空，如是采用開地址散列(線性探測(cè)法)處理沖突，那么關(guān)鍵字109

5、的結(jié)點(diǎn)地址為（ ）。A) 8 B) 9 C) 5 D) 413采用犧牲元素法來構(gòu)造循環(huán)隊(duì)列時(shí)，長(zhǎng)度為n的向量可以存放的元素個(gè)數(shù)為:（ ）。 A) n-2 B) n-1 C) n D) n+1 14如果對(duì)二叉樹采用的遍歷方式是右子樹左子樹根，那么左下圖的二叉樹相應(yīng)的遍歷序列為（ ）。A) 9, 7, 5, 4, 1 B) 4, 1, 9, 7, 5 C) 7, 9, 5, 4, 1 D) 9, 7, 4, 1, 55 71 9415將一棵有99個(gè)結(jié)點(diǎn)的完全二叉樹按順序編號(hào)，根結(jié)點(diǎn)的編號(hào)為0,那么編號(hào)為49的結(jié)點(diǎn)的右子結(jié)點(diǎn)的編號(hào)為（ ）。 A) 98 B) 99 C) 100 D) 不存在16一個(gè)

6、棧的入棧序列是a,b,c,d,下列出棧序列中不可能的出棧序是哪個(gè)？（ ）。A) abcd B) acbd C) dcba D) cabd1710000個(gè)結(jié)點(diǎn)要構(gòu)造二叉樹(樹高從0層開始)，則最高的二叉樹和最低的二叉樹的樹高為（ ）。A）5000, 100 B）10000, 18C）5000,14 D）99999, 1418如下圖，從頂點(diǎn)1出發(fā)，按照廣度優(yōu)先規(guī)則遍歷，可能得到的序列為（ ）。7216453A) B) C) D) 19設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。v1v2v3v4v7v5v6A）5 B）6 C）7 D）820已知有向圖G = (V, E), 如右

7、圖所示，G的可能的拓?fù)渑判驗(yàn)椋?）。A) V1, V3, V4, V6, V2, V5, V7 B) V1, V3, V5, V6, V4, V2, V7C) V1, V3, V4, V5, V2, V6, V7 D) V1, V2, V5, V3, V4, V6, V7二、填空題(102 = 20分)1對(duì)于聲明：ListStack myStack; 有一些操作：myStack.push(A); myStack.push(K);myStack.push(D); myStack.pop();myStack.push(H); myStack.push(K); myStack.pop(); mySt

8、ack.pop();myStack.push(D); 此時(shí)，棧內(nèi)元素從棧底向棧頂依次為_（1）_。 2 一個(gè)二叉樹的前序遍歷結(jié)果為：ABDEHCFIGJ; 中序遍歷結(jié)果為：DBEHAIFCJG;請(qǐng)給出這個(gè)二叉樹的后序便歷序列_（2）_。 3表達(dá)式 f+(a+b)/(d-e)*2 對(duì)應(yīng)的后綴表達(dá)式是_（3）_。4求如下程序段的時(shí)間復(fù)雜度，復(fù)雜度采用大O表示。_ （4） _。/假設(shè)n, data 均有定義int low=0;int high=n;while(lowhigh)int mid=(low+high)/2;if(datamid=value) cout”find the data at:”m

9、id;else if(datamidvalue) low=mid+1;else high=mid;cout”cant find the data,the last searching:”low;5使用上題的策略對(duì)排序向量：170，275，426，503，509，512，612，653，677，703，765，897，908檢索元素703，請(qǐng)問依次比較的元素為_（5）_。6假設(shè)有向量(Q, H, C, Y, P, A, M, S, R, D, F, X) ，如果要將該向量調(diào)整成最大堆，則結(jié)果是_（6）_； 如果要將該向量按字母升序排列，則采用選擇排序的第二趟排序的結(jié)果是_（7）_；采用快速排序的

10、第二趟排序的結(jié)果是_（8）_。 7有排序二叉樹的原始圖如下所示:（二叉樹的原始圖）在原始圖上添加結(jié)點(diǎn)77后，該排序樹變?yōu)開（9）_在原始圖上刪除結(jié)點(diǎn)112，該排序樹變?yōu)開（10）_三、算法分析與設(shè)計(jì):（60分）1將關(guān)鍵碼序列為C, B, X, W, U, V, Y依次插入到一個(gè)空的AVL樹中，畫出每次插入完成后的AVL樹 （8分）2已知帶權(quán)圖如圖所示，請(qǐng)給出它的鄰接矩陣表示形式。（5分）3 設(shè)待排序的關(guān)鍵碼序列為最大堆30，28，20，18，12，10，16，6，2，試寫出使用堆排序的前3趟結(jié)果。（6分） 4. 有9個(gè)關(guān)鍵碼的開地址散列向量 32，13，49，55，22，39，20，97，56

11、，散列函數(shù)為取余運(yùn)算（即%11，如關(guān)鍵碼32的向量地址為32%11 = 10），散列表空間為11個(gè)單元。試分別完成按以上關(guān)鍵碼順序插入到線性開地址散列解決沖突的散列表之后的結(jié)果。（5分）5設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹的全過程。（6分）6. 對(duì)于下圖，試模擬Dijkstra算法，給出從編號(hào)為A的頂點(diǎn)出發(fā)到其它各個(gè)結(jié)點(diǎn)的最短路徑的過程。（10分）121025281618221424816AGBFEDC7假設(shè)用于通訊的電文僅有6個(gè)字母abcdef組成，字母在電文中出現(xiàn)的頻率分別為7，19，5，16，42，11。試為這6個(gè)字母設(shè)計(jì)哈夫曼編碼。（8分）8. 已知一個(gè)隊(duì)列的模板類如下#

12、define queue_size 1000template class queueVector protected: T dataqueue_size;/ 隊(duì)列空間int nextSlot; /入隊(duì)指示int nextUse;/出隊(duì)指示 public: / 構(gòu)造和析構(gòu)函數(shù)queueVector ( );queueVector (const queueVector& other); T dequeue( );/出隊(duì)動(dòng)作 void enqueue(T value);/入隊(duì)動(dòng)作;請(qǐng)完善這個(gè)這個(gè)隊(duì)列。已知模板類的各個(gè)函數(shù)實(shí)現(xiàn)情況如下，請(qǐng)補(bǔ)充完整。template queueVector:queueV

13、ector ( ) /初始化隊(duì)列：設(shè)置隊(duì)列相關(guān)屬性初始值。 nextSlot=0; nextUse=0;template queueVector:queueVector (const queueVector& other )/拷貝構(gòu)造函數(shù)，根據(jù)參數(shù)初始化隊(duì)列對(duì)象本身。（4分） template T queueVector:dequeue ( ) /出隊(duì)動(dòng)作：若隊(duì)列不空，則刪除隊(duì)列首元素，并返回該元素。（4分） template void queueVector:enqueue (T value )/入隊(duì)動(dòng)作：若隊(duì)列不滿，則往隊(duì)列末尾添加元素。（4分）一、選擇題（20分）1.C 2.D 3.D

14、4.A 5.C6. B,D 7.B 8.B 9.C 10.A11.C 12.B 13.B 14.D 15.D16.D 17.D(送分) 18.C 19.A 20.A二、填空題. （20分）1（1）A K D 注意：從棧底到棧頂，若寫成D K A，得1分。2（2）D H E B I F J G C A3（3）f a b + d e - / 2 * +4（4）O(log2n)5（5）6612,10765,8677,9703 或 6612,97036（6）Y S X R P C M H Q D F A （7）A C H Y P Q M S R D F X （8）A D C F P H M Q R S

15、 Y X575044130796093134575044112796093771341307（9） （10）三、算法分析設(shè)計(jì)(60分)1（8分）WUCVCBUWCBX右單旋WCBXCBXCB右左雙旋WXBXUYV1分 1 分 1分 1分 2分 2分2（5分）ABCDEMA08010B20050C030100D90040E0M1502邊1分，共9邊；對(duì)角線為0，1分；3（6分）2281820106121630調(diào)整281862010212163030281820101612162 2分20186161028122302186201028121630調(diào)整 2分18126161028220302186

16、161028122030調(diào)整 2分4（5分）32%11=10 13%11=2 49%11=5 55%11=0 22%11=0 39%11=6 20%11=9 97%11=9 56%11=155 22 13 97 56 49 39 20 320 1 2 3 4 5 6 7 8 9 102個(gè)數(shù)據(jù)1分，扣完為止。5（6分）任選1點(diǎn)出發(fā)即可，1點(diǎn)得1分，共6點(diǎn)，最小生成樹的權(quán)值是11。465231652315231231311 1分 1分 1分 1分 1分 1分6（10分）從A點(diǎn)出發(fā)；一組數(shù)據(jù)1.5分，共6組數(shù)據(jù)，完全正確再得1分。0 8 10 28A B C D E F GA A，D A-D 80

17、26 8 32 10 28A B C D E F GA A，D，F(xiàn) A-F 10 0 26 8 32 10 28 A B C D E F GA A，D，F(xiàn)，B A-D-B 26 0 26 38 8 32 10 28A B C D E F GA A，D，F(xiàn)，B，G A-G 280 26 38 8 32 10 28A B C D E F GA A，D，F(xiàn)，B，G，E A-D-E 320 26 38 8 32 10 28A B C D E F GA A，D，F(xiàn)，B，G，E，C A-D-B-C 387（8分）答案不唯一，但是WPL=228；圖1分，每個(gè)編碼1分（6分），完全正確得1分。或 寫出構(gòu)造哈夫

18、曼樹的全過程（6分），編碼（2分）。10042(e)58352319(b)16(d)11(f)125(c)7(a) 為哈夫曼樹設(shè)計(jì)編碼，左子樹為0，右子樹為1；a:0000 b:011 c:0001 d:010 e:1 f:0018.（12分） template queueVector:queueVector (const queueVector& other )/拷貝構(gòu)造函數(shù)，根據(jù)參數(shù)初始化隊(duì)列對(duì)象本身。If(other.nextUse= =other.nextSlot) nextSlot=0; nextUse=0; （1分或0分）else nextSlot=other.nextSlot; 1分 nextUse=other.nextUse; 1分 for(int i=0;i queue_size;i+) datai=other.datai; 2分（或1分）template T queueVector:dequeue ( ) /出隊(duì)動(dòng)作：若隊(duì)列不空，則刪除隊(duì)列首元素，并返回該元素。assert (!isEmpty() ; /首先要判斷非空 1分 int data