數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)_考試題及答案匯總(共7套)

1、華東交大數(shù)據(jù)結(jié)構(gòu)期考試卷及答案(一)參考答案以及評分標(biāo)準(zhǔn)(A )卷題號四五六七八九十總分累分人 簽名題分20205010100得分考生注意事項：1、本試卷共上頁，總分100分,考試時間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。一甲的用孫alp淋 =la。系辿sis魁一廿運出拈悵哩三靜-H卦帝郛K-定東盤與三陽勿舊聞 盟數(shù)eEw震疥幽卡津賓卻”YWT都鐘？YW磐S京員zsis s數(shù)據(jù)結(jié)構(gòu)(C )課程 課程類別：堂、限、任閉卷(1開卷(范圍)(僅限課本)：考試日期：20卷-7-5一、選擇題(每題2分，共20分)|得分|評閱人1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為(C

2、 )A)內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B)靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)I I0線性結(jié)構(gòu)與非線性結(jié)構(gòu) D)緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)2、在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入結(jié)點s, 則執(zhí)行( D )。A) sTink=plink;p->link=s;B) plink=s;slink=q;C) plink=slink;slink=p;D) qlink=s;sTink=p;3、隊和棧的主要區(qū)別是(D )A)邏輯結(jié)構(gòu)不同B)存儲結(jié)構(gòu)不同C)所包含的運算個數(shù)不同D)限定插入和刪除的位置不同4、在循環(huán)隊列中用數(shù)組A0.mT存放隊列元素，其隊頭和隊尾指針分別為 front和rear,則當(dāng)前隊列中的元素

3、個數(shù)是( D )。A) (front rear+1)%mB) (rear front+l)%mC) (front rear+m)%mD) (rear front+m)%m5、下面程序段的時間復(fù)雜度為( C )for (int i=0;i<m;i+)for (int j=O;j<n;j+) aij=i*j;A) 0(m:) B) 0(n2) C) 0 (m*n) D) 0 (m+n)6、 一棵二叉樹的前序遍歷序列為ABCDEFG,它的中序序列可能是（B/D）A） CABDEFG B） ABCDEFG C） DACEFBG D）BADCFEG7、下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（E

4、）A）鄰接矩陣B）逆鄰接表C）鄰接多重表D）十字鏈表E）鄰接表8、一個對象序列的排序碼為46, 79, 56, 38, 40, 84,采用快速排序以位于最 左位置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為（C ）。A） 38, 46, 79, 56, 40, 84B） 38, 79, 56, 46, 40, 84C） 40, 38, 46, 56, 79, 84D） 38, 46, 56, ?9, 40, 849、設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，則B中右指針域為空的結(jié)點有（C ）個。A）n-1 B） n C） n+110、線性鏈表不具有的特點是（A ）。A）隨機(jī)訪問0插

5、入與刪除時不必移動元素D） n+2B）不必事先估計所需存儲空間大小D）所需空間與線性表長度成正比二、填空題（每題1分，共20分）得分評閱人1、采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為（n+l）/2 ）2、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用（棧 ）3、二又樹中第5層上的結(jié)點個數(shù)最多為（16）4、已知五個元素ABCDE的進(jìn)棧次序為ABCDE,若C為第一個出棧元素，則下一個 出棧的元素不可能是（A ）；5、向一個由HS指向的帶頭結(jié)點的鏈棧中插入一個結(jié)點時p時，需要執(zhí)行的操作 是（.p->next=HS->next; HS->next=p ）；

6、刪除一個結(jié)點時，需要執(zhí)行的操作 是（_ HS->next =HS->next->next _）（假設(shè)棧不空而且無需回收被刪除結(jié)點）。 6、已知鏈棧的結(jié)點結(jié)構(gòu)的棧頂指針為top,則實現(xiàn)將指針p所指結(jié)點插入棧頂?shù)?語句依次為（ p->next=top ）和（ top=p ）o7、對于線性表（70, 34, 55, 23, 65, 41, 20）進(jìn)行散列存儲時，若選用H （K） 二K%7作為散列函數(shù)，則散列地址為0的元素有（1 ）個，散列地址為6的有（4） 個。8、假定一棵樹的廣義表表示為A （D （E, G）, H （I, J）,則樹中所含的結(jié)點數(shù) 為7個，樹的深度為_3

7、,樹的度為2_o9、若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一 維數(shù)組A中，即編號為0的結(jié)點存儲到A0中。其余類推，則Ai元素的左孩 子元素為_21+1,右孩子元素為 2i+2,雙親元素為一（i-l）/2_o 10、在一個具有10個頂點的無向完全圖中，包含有_45一條邊，在一個具有n 個頂點的有向完全圖中，包含有_n（n-1）條邊。1. 11、后綴算式79 2 30 +- 4 2 /*的值為_94。中綴算式（3+X*Y） -2*Y/3對應(yīng)的后綴算式為_3 XY* + 2Y*3 / -。三、簡答題（5題，共50分）1、已知某二義樹的前序序列為EBADCFHGI ,中序序

8、列為 ABCDEFGHL請畫出二義樹并寫出它的后序序列。（構(gòu)造出二叉樹 7分，后序遍歷3分，共10分） 參考答案：得分評閱人后序序列:ACDBGIHFE 二義樹為:第12頁共5頁評分標(biāo)準(zhǔn)：構(gòu)造出二叉樹7分，后序遍歷3分2、將關(guān)鍵碼53, 78, 65, 17, 87, 09, 81, 45, 23依次插入到一棵初始為空的 二又搜索樹中，畫出每插入一個關(guān)鍵碼后的二又排序樹。（每個過程1分，共9分） 參考答案：評分標(biāo)準(zhǔn)：（每個過程1分，共9分）3、假定用于通訊的電文僅有8個字母Cl, C2,，C8組成，各個字母在電文中 出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4,試為這8

9、個字母設(shè)計哈夫曼編 碼樹并寫出每個字母的編碼。（畫出哈夫曼樹得3分，寫出一個字母的編碼是1分, 總分共n分） 參考答案：cS cl雖然哈夫曼樹的帶權(quán)路徑長度是唯一的，但形態(tài)不唯一。本題中各字母編碼如下: cl:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:ll c8:0011評分標(biāo)準(zhǔn)：畫出哈夫曼樹得3分，每個字母的編碼是1分，共8分4、已知一個圖的定點集V各邊集G如下：(16分)V=0,1,2, 3, 4, 5, 6, 7, 8, 9);E=(0, 1), (0,4), (1,2), (1,7), (2, 8), (3,4), (3, 8), (5,6

10、), (5, 8), (5, 9), (6, 7),(7,8), (8, 9)當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的定點序列和按廣度優(yōu)先搜索遍歷得到的定點序列。假定每個頂點鄰接表中的節(jié)點是按頂點序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時鄰接表表示時參考答案4、圖浜度優(yōu)先序列廣度優(yōu)先序列鄰接印陽表示時0, I. 2, 8, 3, 4,工 6, 7, 90, B, $ 2, 7, 3, 8. 6, 5, 9鄰接表表示時Or 4, 3, 8, 9r 5, 6, 7, b 20, 4, 1, 3, 7, 2, 8, 6, 9, 5評分標(biāo)

11、準(zhǔn)：正確寫出每個序列得4分5、 LinkList mynote(LinkList L)/L是不帶頭結(jié)點的單鏈表的頭指針if(L&&L->next)q=L； L=L>next： p=L；SI：while(p >next) p=p >next；S2：p >next=q： q>next=NULL：return L：）請回答下列問題：（l）說明語句SI的功能；（2）說明語句組S2的功能;（3）設(shè)鏈表表示的線性表為（al,a2,an），寫出算法執(zhí)行后的返回值所 表示的線性表。答案：（1）查詢鏈表的尾結(jié)點 （1分）（2）將第一個結(jié)點鏈接到鏈表的尾部，作為

12、新的尾結(jié)點-一（1分）（3）返回的線性表為（a2, a3, , an, al） （2分）四、程序編程題（每題5分，共10分）得分評閱人1、統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。int CountX（LNode* HL, ElemType x）參考答案：int CountX（LNode* HL, ElemType x） int i=0; LNode* p=乩;1.為計數(shù)器 （1 分）while（p!=NULL） if （P->data=x） i+;p=p_>next;/while,出循環(huán)時i中的值即為x結(jié)點個數(shù) （3分）return i ;（ 1 分）/CountX2、試寫

13、一算法寫出用二義鏈表表示給定二義樹的葉子結(jié)點總數(shù)。int GetLeaves（ BinTree root）參考答案：int GetLeaves（ BinTree root）求葉結(jié)點總數(shù)static int leaf=0;此1用于記葉結(jié)點數(shù)，注意用靜態(tài)變量（1分）if（root） 遞歸計算葉結(jié)點數(shù)if（!（root->lchiId root->rchiId）leaf+;如果該結(jié)點無左右孩子，則葉子數(shù)加1GetLeaves（root->lchild）;算左子數(shù)的葉結(jié)點數(shù)GetLeaves （root->rchild）; 算右子樹的葉結(jié)點數(shù)）（3分）return leaf;

14、返回結(jié)果 （1 分）華東交大數(shù)據(jù)結(jié)構(gòu)期考試卷及答案（二）數(shù)據(jù)結(jié)構(gòu)（C ）課程 課程類別：必、限、任閉卷（1開卷（范圍）（僅限課本）：考試日期：一用常淋nip淋 圣需 。去皿盡£魁一mW田理悵哩as題號四五六七八九十總分累分人 簽名題分2026241416100得分考生注意事項：1、本試卷共L頁，總分100分,考試時間120 分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。一、 選擇題（每小題2分，共20分）1 .在一個帶有附加表頭結(jié)點的單鏈表HL中，若要向表頭插入一 個由指針P指向的結(jié)點，則執(zhí)行（）。A. HL=p; p->next=HL;B. p->nex

15、t=HL->next;C. p->next=HL; p=HL;D. p->next=HL; HL=p;HL->next=p;2 .若順序存儲的循環(huán)隊列的QueueMaxSizef,則該隊列最多可存儲（）個元A. nB. n-1 C. n+13 .下述哪一條是順序存儲方式的優(yōu)點？（）A.存儲密度大C.獲取符合某種條件的元素方便D.不確定B.插入和刪除運算方便D.查找運算速度快4,設(shè)有一個棧的輸入序列為1 2 3,則下列序列中不可能是棧的輸出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35 .下列關(guān)于二叉樹遍歷的敘述中，正確的是()。A.若一

16、個樹葉是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二義樹的 前序遍歷最后一個結(jié)點B.若一個點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二義樹的中序 遍歷的最后一個結(jié)點、C.若一個結(jié)3捻某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的 前序最后一個結(jié)點D.若一個樹葉是某二叉樹的前序最后一個結(jié)點，則它必是該二義樹的中序遍 歷最后一個結(jié)點6 . k層二義樹的結(jié)點總數(shù)最多為().A. 2-1 B. 2K+1 C. 2K-1 D. 27 .對線性表進(jìn)行二分法查找，其前提條件是().A.線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序B.線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C.線性表以順

17、序方式存儲，并且按關(guān)鍵碼值排好序D.線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序8 .對n個記錄進(jìn)行堆排序，所需要的輔助存儲空間為A. 0 (log:n) B. 0 (n) C. 0(1) D. 0 (n2)9 .對于線性表(7, 34, 77, 25, 64, 49, 20, 14)進(jìn)行散列存儲時，若選用H (K) =K%7作為散列函數(shù)，則散列地址為。的元素有()個，A. 1B. 2C. 3D. 410 .下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是().A.數(shù)組是不同類型值的集合B .遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C .樹是一種線性結(jié)構(gòu)D,用一維數(shù)組存儲一棵完全二義樹是有效的

18、存儲方法2、 填空題(每空1分，共26分)1 .數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、和 四利I。2 . 一個算法的時間復(fù)雜度為(3/+2000Hog二加90)/,其數(shù)量級表示為 03 .對于一個長度為n的單鏈存儲的隊列，在表頭插入元素的時間復(fù)雜度為 ，在表尾插入元素的時間復(fù)雜度為。4 .假定一棵樹的廣義表表示為A (D (E, G), H (I, J),則樹中所含的結(jié)點數(shù)為 個，樹的深度為，樹的度為 c5 .后綴算式79 2 30 +- 4 2 / *的值為 二中綴算式(3+X*Y)-2Y/3對應(yīng)的后綴算式為 o6 .若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0

19、的結(jié)點存儲到A0中。其余類推，則A i 元素 的左孩子元素為,右孩子元素為，雙親元素為7 .在樹中，一個結(jié)點的直接后繼結(jié)點稱為該結(jié)點的,一個結(jié)點的直接 前趨結(jié)點稱為該結(jié)點的 O8 .在一個具有10個頂點的無向完全圖中，包含有 條邊，在一個具有n個頂點的有向完全圖中，包含有 條邊。9 .棧又稱為 表，隊列又稱為 表。10 .表示圖的兩種常用的存儲結(jié)構(gòu)為 和 c11 .隊列的插入操作是在隊列的 進(jìn)行，刪除操作是在隊列的進(jìn)行。12 .在線性表的散列存儲中，裝填因子a乂稱為裝填系數(shù)，若用m表示散列表的長 度，n表示待散列存儲的元素的個數(shù)，則a等于。3、 運算題(每題3分，共24分)1 .在如下數(shù)組A中

20、鏈接存儲了一個線性表，表頭指針存放在A 0. next,試寫 出該線性表。234567data next2 .已知一棵二義樹的前序遍歷的結(jié)果是ABKCDFGHIJ,中序遍歷的結(jié)果是 KBCDAFHIGJ,試畫出這棵二叉樹。3 .已知一個圖的頂點集V為：¥=1, 2, 3, 4, 5, 6, 7);其共有10條邊。該圖用如下邊集數(shù)組存儲:122552261364547677751122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。4、 閱讀算法(每題7分，共14分)1 .在下面的每個程序段中，假定線性表La的類型為List,元素類型ElemType 為i

21、nt,并假定每個程序段是連續(xù)執(zhí)行的。試寫出每個程序段執(zhí)行后所得 到的線性表Lao(1) InitList(La);Int a = 100, 26, 57, 34, 79;For (i=0;i<5;i+)Insert (La, ai);TraverseList(La);(2) DeleteFront (La);InsertRear(La, DeleteFront(La);TraverseList(La);(3) ClearList(La);For (i=0;i<5;i+)InsertFront(La, ai);TraverseList(La);2 .現(xiàn)面算法的功能是什么？void A

22、BC(BTNode * BT)(if BT cout«BT->data«，'ABC(BT->left);ABC(BT->right);5、 編寫算法(共16分)HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。 bool Find(LNode* HL, ElemType &item)參考答案:1、 單選題(每題2分，共20分)l.B 2.B 3.A 4.C 5.D 6.A 7.C8.C9.D10.D2、 填空題(每空1分，共26分)2. 集合結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)3. 0(n)4. 0(1)0(1)5. 7226

23、. 943 XY* + 2Y*3/-7. 2i+l2i+2(i-l)/28. 孩子(或子)結(jié)點 雙親(或父)結(jié)點9. 45 n(n-l)10. 先進(jìn)后出先進(jìn)先出11. 鄰接矩陣鄰接表邊集數(shù)組12. 尾首13. n/m3、 運算題(每題6分，共24分)1 . 線性表為:(90, 40, 78, 50, 34, 60)2 .當(dāng)前序序列為ABKCDFGHIJ,中序序列為KBCDAFHIGJ時，逐步形成二叉樹的過程如 下圖4所示：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74.見圖5。L La=(26.34,57,79,100) La=(57.79,10

24、0.34)(3)La=(79.34,57,26/00)2.前序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。五?編寫算法(16分)bool Find(LNode* HL. ElemType &item)LNode* p=HL;if (p->data=item) return true;)else p=p->next;return false;)華東數(shù)據(jù)結(jié)構(gòu)期考試卷及答案（三）第17頁共5頁參考答案（B ）卷數(shù)據(jù)結(jié)構(gòu)（C ）課程 課程類別：名、限、任閉卷（1開卷（范圍）（僅限課本）:考試日期：題號四五7V七八九十總分累分人 簽名題分20304010100得分考生注意事項：1、本試卷共上頁，總分10

25、0分,考試時間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。一、 單選題（每題2分，共20分）1 .以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（ B）A.有向圖 B.隊列C.線索二叉樹D.B樹2 .在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指向 的結(jié)點，則執(zhí)行如下（D）語句序列。A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3 .以下哪一個不是隊列的基本運算？ （ A

26、）A.在隊列第i個元素之后插入一個元素B.從隊頭刪除一個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值4 .字符A、B、C依次進(jìn)入一個棧，按出棧的先后順序組成不同的字符串，至多 可以組成（B）個不同的字符串？A. 14B. 5C. 6D. 8A. 11 B. 35 C. 19圖15 .由權(quán)值分別為3,862的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（B ）。以下68題基于圖6.A. E> G F、A、C、D、B該二叉樹結(jié)點的前序遍歷的序:列為（CF、B、DD、G、FB. E、 A、 G CsD. E、 G、 As C、 D、 F、 BC. E、A、C、B、7 .該二又樹結(jié)點的中序遍歷的

27、序列為（AA. A、 B、 C、 D、 E、 G> FB. E、 A、 G、 C、 F、 B、 DC. E、A、C、B、D、G、FE. B、D、C、A、F、G、E8 .該二叉樹的按層遍歷的序列為（C）oB. E、A、Cx B、D、G、FD. E、 G、 A、 C、 D、 F、 BA. E G、 F、 A、 C、 D、 BC. E A、 G、 C、 F、 B、 D9 .下面關(guān)于圖的存儲的敘述中正確的是（B ）oA.用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)B.用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān) C.用鄰接矩陣法存儲圖，占用的存儲空間大

28、小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)D.用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點 個數(shù)無關(guān)10 .設(shè)有關(guān)鍵碼序列（q, g, m, z, a, n, p, x, h）,下面哪一個序列是從上述序 列出發(fā)建堆的結(jié)果?（B ）A. a, g, h, m, n, p, q, x, zB.a, g, m, h, q, n, p, x, zC. g, m, q, a, n, p, x, h, zD.h, g, m, p, a, n, q, x, z2、 填空題（每空1分，共26分）1 .數(shù)據(jù)的物理結(jié)構(gòu)被分為順序、鏈表、索引、散列一四種。2 .對于一個長度為n的順序存儲的線性表，在表頭插入元

29、素的時間復(fù)雜 度為-0（n） ,在表尾插入元素的時間復(fù)雜度為一 0（1；二3 .向一個由HS指向的鏈棧中插入一個結(jié)點時p時，需要執(zhí)行的操作是 p->next=HS;HS=p ；刪除一個結(jié)點時，需要執(zhí)行的操作是 HS=HS->next （假設(shè)棧不空而且無需回收被刪除結(jié)點）。4 .對于一棵具有n個結(jié)點的二義樹，一個結(jié)點的編號為i（lWiWn）,若它有左孩子則左孩子結(jié)點的編號為_2i,若它有右孩子，則右孩子 結(jié)點的編號為_2i+l,若它有雙親，則雙親結(jié)點的編號為i/2（或 i/2 ）5 .當(dāng)向一個大根堆插入一個具有最大值的元素時，需要逐層一向上一 調(diào)整，直到被調(diào)整到一根位置為止。6 .表

30、示圖的兩種常用的存儲結(jié)構(gòu)為_鄰接矩陣_、_鄰接表7 .對于線性表(70, 34, 55, 23, 65, 41, 20)進(jìn)行散列存儲時，若選 用H (K) =K%7作為散列函數(shù)，則散列地址為。的元素有_1一個, 散列地址為6的有4個。8 .在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為-0(n),整個排序 過程的時間復(fù)雜度為 0(nlog：n：1,空間復(fù)雜度為_0(n)。3、 運算題(每題10分,共30分)1 .寫出下列中綴表達(dá)式的后綴形式:(1) 3X/(Y-2)+l(2) 2+X*(Y+3)答案：(1) 3 X *Y 2 -/I +(2) 2 X Y 3 + * +2 .試對圖2中的二義樹畫出其

31、：(I)順序存儲表示的示意圖；(2)二義鏈表存儲表示的示意圖。123456789答案：(1)：0123678910111213141516(2)：見圖3所示3 .已知一個圖的頂點集V和邊集E分別為:V=1,2, 3,4, 5, 6,7;E=(1,2)3, (1,3)5, (1,4)8, (2,5)10, (2, 3)6, (3,4)15, (3, 5)12, (3,6)9, (4,6)4, (4,7)20, (5,6)18, (6, 7)25;按照普里姆算法從頂點1出發(fā)得到最小生成樹，試寫出在最小生成樹中依 次得到的各條邊。答案：普里姆算法從頂點1出發(fā)得到最小生成樹為：(1,(2) (1,3)

32、5， (1,4)8, (4,6)4,(2,5)10, (4,7)204、 閱讀算法(每題10分,共20分)1. void AE(Stack& S)InitStack(S);Push(S,3);Push(S, 4);int x=Pop(S)+2*Pop(S);Push(S, x);int i, a5 = l, 5, 8,12,15);for(i=0;i<5;i+) Push(S, 2*ai);while(!StackEmpty(S) cout«Pop(S)«,;該算法被調(diào)用后得到的輸出結(jié)果為：30 24 16 10 2 102. void ABC (BTNode

33、 *BT,int &cl,int &c2) if (BT !=NULL) ABC(BT->Cft,c 1 ,c2);cl+;if (BT->left=NULL&&BT->right=NULL) c2+;ABC(BT->right,c 1 ,c2);)/if該函數(shù)執(zhí)行的功能是什么？答案：該函數(shù)的功能是：統(tǒng)計出BT所指向的二叉樹的結(jié)點總數(shù)和葉子總數(shù)5、 編寫算法(共10分)編寫從類型為List的線性表L中將第i個元素刪除的算法，(假定不需要對i 的值進(jìn)行有效性檢查,也不用判別L是否為空表。)void Delete(List& L, i

34、nt i)答案：void Delete(List& L, int i)(for (int j=i-l;j<L size-1; j+)L. listj>L. listCj+1;第 i 個元素的下標(biāo)為 i-1L. size;)華東交大數(shù)據(jù)結(jié)構(gòu)期考試卷及答案（四）一”蛇撲DIP孫DIP孫。瞇辿S求蜜SH5與aB謖奧孌喀絲Te罪常七黑窕隱茶杰琪坦香R數(shù)據(jù)結(jié)構(gòu)（C ）課程課程類別：堂、限、任閉卷（1開卷（范圍）（僅限課本）：考試日期：2011-1 -12題號四五六七八九十總分累分人 簽名題分20304010100得分考生注意事項：1、本試卷共上頁，總分100分,考試時間120分鐘。2

35、、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。一、選擇題（每題2分，共20分）1、數(shù)據(jù)的四種存儲結(jié)構(gòu)是（A ）A,順序存儲結(jié)構(gòu)、鏈接存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)B.線性存儲結(jié)構(gòu)、非線性存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)和圖型存儲結(jié)構(gòu)C.集合存儲結(jié)構(gòu)、一對一存儲結(jié)構(gòu)、一對多存儲結(jié)構(gòu)和多對多存儲結(jié)構(gòu)D,順序存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)2、若對某線性表最常用的操作是在最后一個結(jié)點之后插入一個新結(jié)點或刪除最后 一個結(jié)點，要使操作時間最少，下列選項中，應(yīng)選擇的存儲結(jié)構(gòu)是（C）A.無頭結(jié)點的單向鏈表B.帶頭結(jié)點的單向鏈表C.帶頭結(jié)點的雙循環(huán)鏈表 D.帶頭結(jié)點的單循環(huán)鏈表3、若元素

36、的入棧順序為1, 2, 3., n,如果第2個出棧的元素是n,則輸出的 第i （l<=i<=n）個元素是（D ）A. n-iB. n-i+1C. n-i+2D.無法確定4、若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二義樹可能的形狀是 （B ）A.樹中沒有度為2的結(jié)點 B.樹中只有一個根結(jié)點C.樹中非葉結(jié)點均只有左子樹D.樹中非葉結(jié)點均只有右子樹5、下面程序段的時間復(fù)雜度為( C )for (int i=0;i<m;i+)for (int j=O;j<n;j+) ai j=i*j;A) 0(m2) B) 0(n2) C) 0 (m*n)D) 0 (m+n)6、 設(shè)

37、有一組關(guān)鍵字(19, 14, 23, 1, 6, 20, 4, 27, 5, 11, 10, 9),用散列 函數(shù)H(key)=key%13構(gòu)造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄 個數(shù)為(C ) A. 1B. 2C. 3 D. 47、指針p、q和r依次指向某循環(huán)鏈表中三個相鄰的結(jié)點，交換結(jié)點*q和結(jié)點*r 在表中次序的程序段是(A) A. p->next=r； q->next=r->next； r->next=q： B. p->next=r； r->next=q： q->next=r->next； C. r->next=q； q

38、->next=r->next； p->next=r； D. r->next=q： p->next=r： q->next=r->next；8、一個對象序列的排序碼為46, 79, 56, 38, 40, 84>,采用快速排序以位于最 左位置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為(C )。A) 38, 46, 79, 56, 40, 84B) 38, 79, 56, 46, 40, 84C) 40, 38, 46, 56, 79, 84D) 38, 46, 56, ?9, 40, 849、串的操作函數(shù)str定義為：int str(charts) cha

39、r *p-s； while (*p !='0' ) p+； return p-s； 則str( abcde")的返回值是(C)A. 3 B. 4 C. 5 D. 610、設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過 一次元素的交換就使第m+1個元素排序到位，該方法是(D )oA.折半排序B.冒泡排序C.歸并排序D.簡單選擇排序得分評閱人二、填空題(每題2分，共30分)3、采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為(n+l)/2 )4、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用(棧 )5、數(shù)據(jù)的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是借

40、助(指針)表示數(shù)據(jù)元素之間的邏輯關(guān)系。6、下面程序段的時間復(fù)雜度為(0(n)osum=l；for (i=0;sum<n;i+) sum+=l；5、給定一組數(shù)據(jù)6, 2, 7, 10, 3, 12以它構(gòu)造一棵哈夫曼樹，則樹高為_5_, 帶權(quán)路徑長度WPL的值為_96_。6、假定一棵樹的廣義表表示為A （D （E, G）, H （I, J）,則樹中所含的結(jié)點數(shù) 為7個，樹的深度為_3，樹的度為-2_o7、假定一個最大堆（大根堆）為（56, 38, 42, 30, 25, 40, 35, 20）,則依次 向它插入45和64兩個元素后得到的最大堆為：64, 56, 42, 38, 45, 40,

41、 35, 20, 30, 25 8、在一個具有10個頂點的無向完全圖中，包含有_45一條邊，在一個具有n個 頂點的有向完全圖中，包含有_n（n-l）條邊。9、后綴算式79 2 30 +- 4 2 /*的值為_94。中綴算式（3+X*Y）-2*Y/3 對應(yīng)的后綴算式為_3 XY* + 2Y*3/-o10、.由字符集（s, t, a, e, 1及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫區(qū)樹如圖所示。已知某段 電文的哈夫曼編碼為111000010100,請根據(jù)該哈夫噠樹進(jìn)行譯碼，寫出原來的電文（eatst）。第21頁共5頁得分評閱人三、簡答題（5題，共53分）1、己知某二義樹的前序序列為EBADCFHGI ,

42、中序序列為 ABCDEFGHL請畫出二叉樹并寫出它的后序序列。（構(gòu)造出二叉樹 7分，后序遍歷3分，共10分）參考答案：后序序列:ACDBGIHFE二義樹為：B) »EF評分標(biāo)準(zhǔn)：構(gòu)造出二義樹7分，后序遍歷3分2、在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為20、30、8、12、34、5、60、3、1, 29, 畫出插入關(guān)鍵碼后的二義查找樹。（5分）3、.要在的向量空間中建立兩個棧stackl和stack2,請回答:應(yīng)該如何設(shè)計這兩個棧才能充分利用整個向量空間？（5分）若stackl的棧頂指針為topi, stack2的棧頂指針為top2,如果需要充分利用 整個向量空間，則：棧stack

43、l空的條件是：（）;（2分）棧stack2空的條件是：（）;（2分）棧stackl和棧stack2滿的條件是：（）。（2分）答：（1）采用雙向棧的形式，stackl的棧底設(shè)置在下標(biāo)為0的元素上，stack2的棧底設(shè)置在下標(biāo)為n-1的元素上。（2）topl=-l» top2=n, topl-l=top24、設(shè)有單鏈表類型定義如下： typedef struct node int data;struct node *next; *LinkList;閱讀下列算法，并回答問題：void f (LinkList head, int A, int B) LinkList p二NULL;while

44、 (head !=NULL)if （head->data>A&&head->data<B）p=head;head=head->next;if （p !=NULL）printf（"%dn”, p->data）;（1）已知鏈表h如下圖所示，給出執(zhí)行f（h, 5, 8）之后的輸出結(jié)果；（5分）簡述算法f的功能。 （5分）答：（1）7（2）輸出鏈表h中（若存在）最后一個大于A到小于B的值。5、 LinkList mynote（LinkList L）/L是不帶頭結(jié)點的單鏈表的頭指針if（L&&L-next）q=L； L=L&g

45、t;next； p=L；SI：while（p >next） p=p >next；S2：p >next=q； q>next=NULL；return L： 請回答下列問題： （1）說明語句SI的功能：（2）說明語句組S2的功能;（3）設(shè)鏈表表示的線性表為（al,a2,an），寫出算法執(zhí)行后的返回值所 表示的線性表。答案：（1）查詢鏈表的尾結(jié)點 （1分）（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 -一（1分）（3）返回的線性表為（a2, a3, , an, al） （2分）得分評閱人四、程序編程題（每題10分，共10分）1、已知二義樹的定義如下： typedef st

46、ruct node int data;struct node *lchild, *rchild;*Bitptr;編寫遞歸算法求二義樹的高度。函數(shù)原型為：int BiTreeHeight (Bitptrt)； 答：int BiTreeHeight (Bitptr t) if(!t) return 0;lh= BiTreeHeight (t->lchild);rh= BiTreeHeight (t->rchild);return lh>rh?lh+l:rh+l;)一W蛇 孫 圣舟。興辿s£魁一廿坦田弗誕映 軀戮eE話震洋健本津?qū)崊s物YWT部仲NYWS翅汞員.老蚓迎回教殳

47、，內(nèi)城M鐘知京看華東教數(shù)據(jù)結(jié)構(gòu)課程據(jù)結(jié)構(gòu)期考試卷及答案（五）試卷編號:(A)卷課程類別：必題號四五六七八九十總分累分人 簽名題分2030103010XXXXX100得分XXXXX考生注意事項：1、本試卷共工頁，總分100分,考試時間120分鐘。2、考試結(jié)束看，考生不得將試卷、答題紙和草稿紙帶出考場。一、選擇題（每題2分，共20分）1、在一個鏈隊列中，若f, r分別為隊首、隊尾指針,指結(jié)點的操作為（ ）（A） f->next=c； f=s（C） s->next=r； r=s2、下面程序的時間復(fù)雜度為（for（i=0;i<m;i+）(B) r->next=s； r=s(D)

48、 s->next=f； f=s )for(j=0;j<n;j+)AiQ=iwj；(A) O(M2)(B) O(N2)(C) O(M*N) (D) O(M+N)3、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二義樹中所包含的結(jié)點數(shù)至少為：()(A) 2h(B) 2h-1(C) 2h+1(D) h+14、設(shè)指針變量p指向單鏈表中結(jié)點A,若刪除單鏈表中結(jié)點A,則需要修改指針的 操作序列為()。(A) q=p->next： p->data=q->data； p->next=q>>next； free(q)：(B) q=p->next： q-

49、>data=p->data； p->next=q->next； free(q)：(C) q=p->next； p->next=q->next； free(q)：(D) q=p->next； p->data=q->data； free(q)；5、含N個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過()(D)N14, 18, 21, 36, 40, 10),則以20 )°(A) 1(B) N/2(C) N-16、設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20, 15, 為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(7 7 H/A B c D/

50、10, 15, 14, 18,10, 15, 14, 18,10, 15, 14, 20,15, 10, 14, 18,20, 36,20, 40,18, 40,20,40, 2136, 2136, 2I36, 40, 21第27頁共5頁7、若在線性表中采用折半查找法查找元素，該線性表應(yīng)該()o(A)元素按值有序(B)采用順序存儲結(jié)構(gòu)(C)元素按值有序，且采用順序存儲結(jié)構(gòu)(D)元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)8、. n個節(jié)點的完全二叉樹，編號為i的節(jié)點是葉子結(jié)點的條件是()o(A) i<n (B) 2"iv=n (C) 2*i+1 >n (D) 2*i>n9、如果只

51、想得到1024個元素組成的序列中的前5個最小元素，那么用()方法最快。(A)起泡排序(B)快速排序 (C)堆排序 (D)直接選擇排序10、對于線性表(7, 34, 77, 25, 64, 49, 20, 14)進(jìn)行散列存儲時，若選用H(K) =K%7作為散列函數(shù)，則散列地址為0的元素有()個，(A)1(B)2(C)3(D)4二、填空題(每空2分，共30分)1、對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為 (1),在表尾插入元素的時間復(fù)雜度為(2) o2、設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較 (3) 一次就可以斷定數(shù)據(jù)元素X是否在查找表

52、中3、若無向圖G中有n個頂點m條邊，采用鄰接矩陣存儲，則該矩陣中非0元素的 個數(shù)為 (4)o4、若一棵二義樹中只有葉子結(jié)點和左、右子樹皆非空的結(jié)點，設(shè)葉結(jié)點的個數(shù)為M, 則左、右子樹皆非空的結(jié)點個數(shù)為一(5)5、設(shè)數(shù)組data 0m作為循環(huán)隊列SQ的存儲空間(判斷隊列滿，少用一個元素 空間)，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為(6)06、設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有(7)個度數(shù)為1的結(jié)點。7、設(shè)一組初始記錄關(guān)鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50),則以d=4 為增量的一趟希爾排序結(jié)束后的結(jié)果為 (8) o8、隊列的

53、插入操作在 (9) 進(jìn)行,刪除操作在(10) 進(jìn)行。9、下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。 typedef struct node int data; struct node wlchild; (11) ;)bitree; void createbitree(bitree *&bt) (scanf( "c"，&ch);if(ch=,#t)(12;else bt=(bitree*)malloc(sizeof(bitree);bt->data=ch;(13);createbitree(bt->rchild); )10、下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處 填上正確的內(nèi)容。typedef struct