2005級數(shù)據(jù)結(jié)構(gòu)A及答案

1、浙江工商大學(xué)2006/2007學(xué)年第一學(xué)期考試試卷課程名稱：_數(shù)據(jù)結(jié)構(gòu)匕_考試方式：_閉卷完成時限：120分鐘 班級名稱：mm學(xué)號：_in姓名：_題號-二二三四五六總分分值101010142036100得分閱卷人.判斷題(每題1分，共10 分)1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個方面。()2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲結(jié)構(gòu)相關(guān)，是依賴于計算機(jī)的。()3、線性表中的每個結(jié)點(diǎn)最多只有一個直接前驅(qū)和一個直接后繼。()4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。()5、 二維數(shù)組是其數(shù)組元素為線性表

2、的線性表。 ()6、 單鏈表形式的隊列，頭指針 F指向隊列的第一個結(jié)點(diǎn)，尾指針R指向隊列的最后一個結(jié)點(diǎn)。()7、 由一棵二叉樹的前序序列和后序序列可以唯一確定它。(錯)8、在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行查找的最佳方法是順序查找(線性查找)。()9、 多重表文件和倒排文件都?xì)w屬于多關(guān)鍵字文件。 ()10、 不定長文件是指文件的長度不固定。 ().填空題(每題1分，共10分)1、若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組 (D，R)，其中D是數(shù)據(jù)元素的有限集合，則R是D上_關(guān)系的有限集合。2、在一個帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的o指針head可用p表示為3、若不帶頭結(jié)點(diǎn)的單

3、鏈表的頭指針為head，則該鏈表為空的判定條件是。4、對于順序存儲的棧，因為棧的空間是有限的，在進(jìn)行的上溢，在進(jìn)行運(yùn)算時，可能發(fā)生棧的下溢。5、 樹的存儲結(jié)構(gòu)常見的有雙親表示法，孩子鏈表法子-兄弟表示法運(yùn)算時，可能發(fā)生棧雙親表示法6 深度為k的完全二叉樹至少有個結(jié)點(diǎn)，至多有個結(jié)點(diǎn)。7、一棵有n個結(jié)點(diǎn)的滿二叉樹有0 個度為1的結(jié)點(diǎn)、有支（非終端）結(jié)點(diǎn)和 （n+1）/2個葉子，該滿二叉樹的深度為1 。(n-1 ) 12 個分og2n +8、大多數(shù)排序算法都有兩個基本的操作9、 線性有序表（a1, a2, a3，a256）是從小到大排列的，對一個給定的值k,用二分法查找表中與 k相等的元素，在查找不

4、成功的情況下，最多需要查找 8次。設(shè)有100個結(jié)點(diǎn)，用二分法查找時，最大比較次數(shù)是7。）中的關(guān)鍵字按字母序的 ;初始步長為 快速排序一趟掃描的10、設(shè)要將序列（Q, H, C, Y, P, A, M, S, R, D, F, X 升序重新排列，則：冒泡排序一趟掃描的結(jié)果是的希爾（shell ）排序一趟的結(jié)果是5士甲曰結(jié)果是三.選擇題（每題1分，共10 分）1、算法指的是（）A.計算機(jī)程序B.解決問題的計算方法C.排序算法D.解決問題的有限運(yùn)算序列2、 線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（）A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲地址相連續(xù)3、 將長度為n的單鏈表鏈

5、接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（）A. 0（1） B. 0（n）C. O（m）D. O（m+n）4、 已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行操作（）A. s->li nk = p ;p->li nk= s;B. s->li nk = p->li nk;p->li nk= s;C. s->link = p->link;p = s;D. p->li nk = s; s->li nk = p ;5、若進(jìn)棧序列為1 , 2, 3, 4, 5, 6,且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn) 的出棧序列是（D ）A

6、. 2 , 4, 3, 1, 5, 6 B. 3 , 2, 4, 1, 6, 5C. 4 , 3, 2, 1, 5, 6 D. 2 , 3, 5, 1, 6, 46、 判斷線索二叉樹中p節(jié)點(diǎn)有右孩子的條件是（C ）A. p != NULLB. p->rchild != NULLC. p->rtag = 0D. p->rtag = = 17、若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個 數(shù)是（B ）A . 9B. 11C. 15D.不確定8、 在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為（）A. ASL = nB. ASL = （n +1）/2C

7、. ASL =n +1D. ASL = log 2（n+1）-19、 對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要 比較（5）次關(guān)鍵字。A. 3 B . 4 C . 5 D . 610、 在二叉排序樹中，每個結(jié)點(diǎn)的關(guān)鍵字 A_ , B_一棵二叉排序，即可得到排序序 列。同一個結(jié)點(diǎn)集合，可用不同的二叉排序樹表示，人們把平均檢索長度最短 的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(jié)構(gòu)上的特點(diǎn)是_C_。 供選擇的答案：A:比左子樹所有結(jié)點(diǎn)的關(guān)鍵字大，比右子樹所有結(jié)點(diǎn)的關(guān)鍵字小 比左子樹所有結(jié)點(diǎn)的關(guān)鍵字小，比右子樹所有結(jié)點(diǎn)的關(guān)鍵字大 比左右子樹的所有結(jié)點(diǎn)的關(guān)鍵字都大 與左子樹和右子樹各自

8、所有結(jié)點(diǎn)的關(guān)鍵字無必然關(guān)系B:前序遍歷 中序（對稱）遍歷后序遍歷 層次遍歷C:除最下二層可以不滿外，其余都是充滿的 除最下一層可以不滿外，其余都是充滿的 每個結(jié)點(diǎn)的左右子樹的高度之差的絕對值不大于1 最下層的葉子必須在最左邊答案：A=B=C=四. 簡答題（每題7分，共14分）1、假設(shè)以數(shù)組seqn mO存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。（1）寫出隊滿的條件表達(dá)式；（2）寫出隊空的條件表達(dá)式；（3）設(shè)m=40, rear=13, quelen=19,求隊頭元素的位置；（4）寫出一般情況下隊頭元素位置的表達(dá)式。2、什么叫線索，線索二叉樹，

9、線索化?將二叉樹各節(jié)點(diǎn)中的空的左孩子指針域改為指向其前驅(qū)，空的右孩子指針域改為指向其 后繼，稱這種新的指針為線索，所得到的二叉樹稱為線索二叉，將二叉樹轉(zhuǎn)變成線 索二叉樹的過程稱為線索化。五. 算法題(每題10分，共20 分)1、閱讀下面的算法:Lin kList myn ote(Li nkList * L)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L-> next)1q=L; L=L >next ; p=L;SHwhile(p >next) p=p >next ;:p >next=q ; q >next=NULL;(1) 說明語句S1的功能

10、；(2) 說明語句組S2的功能；(3) 設(shè)鏈表表示的線性表為(a1,a2,an),寫出算法執(zhí)行后的返回值所表示的線性表。2、利用兩個棧sl,s2模擬一個隊列時，如何用棧的運(yùn)算實現(xiàn)隊列的插入，刪除以 及判隊空運(yùn)算。請簡述這些運(yùn)算的算法思想。六. 應(yīng)用題(每題6分，共36 分)1、分析下面程序段的時間復(fù)雜性：y=0; while(n>=(y+1)*(y+1) y+;2、已知二叉樹如下圖所示:(1) 寫出上圖二叉樹的中序遍歷和后序遍歷的結(jié)果;(2) 畫出此二叉樹還原成森林的圖。3、試畫出對下圖執(zhí)行深度優(yōu)先遍歷產(chǎn)生的生成樹(從 1開始)，并寫出遍歷序列。(2) 若查找元素54,需依次與哪些元素比

11、較？(3) 若查找元素90,需依次與哪些元素比較？(4) 假定每個元素的查找概率相等，求查找成功時的平均查找長度。5、設(shè)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 37, 70, 29 ,試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。& 設(shè)待排序的排序碼序列為 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。(1) 直接插入排序(2) 希爾排序(增量為5,2,1)(3) 冒泡排序(4) 快速排序參考答案及評分標(biāo)準(zhǔn)一. 判斷題(每題1分，共10分)1>V;

12、2、X； 3>V; 4、X； 5>V;6>V; 7、X； 8>V; 9>V; 10、X；二. 填空題(每題1分，共10分)1、關(guān)系的有限集合；2、head = p >next >next ；3、head = = NULL ；4、進(jìn)棧、出棧；5、雙親表示法 ，孩子鏈表表示法 ，孩子-兄弟表示法；6、 2k-1、 2k-1 ；7、0、(n-1)/2、(n +1)/2、|ljog2n + 1 ；8、比較、移動；9、& 7；10、H C Q P A M S R D F X Y、 P A C S Q H F X R D M Y、 F H C D P A

13、M Q R S Y X ；.選擇題(每題1分，共10 分)1、D ； 2、B ； 3、C; 4、B ； 5、D ；6、C； 7、B； 8、B； 9、C； 10、;四. 簡答題(每題7分，共14分)1、(1) quelen = = m ；(2) quelen = = 0 ;(3) 34(4) (rear-quelen + m) % m ;2、將二叉樹各節(jié)點(diǎn)中的空的左孩子指針域改為指向其前驅(qū)，空的右孩子指針域改為指 向其后繼，稱這種新的指針為線索，所得到的二叉樹稱為線索二叉，將二叉樹轉(zhuǎn)變 成線索二叉樹的過程稱為線索化。五. 算法題(每題10分，共20分)1、(1)找到next域為NULL的節(jié)點(diǎn)，即

14、鏈表的尾節(jié)點(diǎn)；(2)令尾節(jié)點(diǎn)的next域指向原表頭，即鏈表中的第一個節(jié)點(diǎn)；再令第一個節(jié)點(diǎn)的next域為NULL ;從而將原來鏈表中的第一個節(jié)點(diǎn)變?yōu)槲补?jié)點(diǎn)。(3)算法執(zhí)行后的線性表為(a2,an , a1 )。2、(1)用棧s1和s2模擬一個隊列的輸入：設(shè) s1和s2容量相等。分以下三種情況討壓棧入s2,之后元素入si棧；若si滿，s2不空（已有出隊列元素），則不能 入隊。（2）用棧si和s2模擬隊列出隊（刪除）：若棧s2不空，退棧，即是隊列的出隊； 若s2為空且si不空，則將si棧中全部元素退棧，并依次壓入s2中，s2棧頂元素退棧，這就是相當(dāng)于隊列的出隊。若棧si為空并且s2也為空，隊列空，不

15、能出隊。（3）判隊空 若棧si為空并且s2也為空，才是隊列空。六. 應(yīng)用題（每題6分，共36分）1、 該程序段中主要計算量在于循環(huán)過程。當(dāng)y的平方小于等于n時，y在每次循環(huán)過程中加i,直到y(tǒng)的平方大于n為止。所以該循環(huán)總共執(zhí)行 y次，且在循環(huán)退出時有 y*y = n成立，注意到y(tǒng)是從0開始自加的，因此總的執(zhí)行次數(shù)為 y = sqrt（n）， 從而復(fù)雜度為O（sqrt（ n）。2、（ i）中序：bjfdgachei （i分，次序錯一處都不得分 ）后序：jfgdbhieca （i分，次序錯一處都不得分 ）（2）評分標(biāo)準(zhǔn)：每畫對一個樹，得 i分。4、(1)先畫出判定樹如下(注： mid= (1+12

16、)/2 =6)(2) 查找元素 54,需依次與 30, 63, 42, 54等元素比較；(3) 查找元素 90,需依次與 30, 63,87, 95, 72等元素比較；(4) 求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前3層共查找1+ 2X 2+ 4 X 3=17次；但最后一層未滿，不能用8 X 4,只能用5 X 4=20次，所以ASL =1/12 (17 + 20)= 37/12 3.08。5、加兀加引加悠空樹加恥加256、(1)直接插入排序初始排 01列i = 1i = 2i = 3i = 4i = 5i = 6i = 7i = 8i = 912 2'2 122 12222

17、2222231630163016304528 10281028 106716* 2016* 2016* 20896 186 186 1812163028101620 618、1216283010*1620 618、1012162830*1620 618、101216*16283020 618、101216*16202830618、'6101216i1620283018、X、6101216i161820 2830排序碼比較次 數(shù)111253338(2)希爾排序(增量為5,2,1)初始排 列1021661812162030281+1+3+1+3+1+1+ 1+2 =/p>

18、9排序碼比較次數(shù)(1+1+2+1)(1+1+ 1 + 1) = 9102166161218203028d = 1 III261012161618202830(3)起泡排序初始排0123456789排序碼比較次列數(shù)i = 01216302810*16206189* *4*#*4*4*2i = 12161630281016201882_i = 2261101630281618207*-MH-f2i = 326101161630-一 28一182062i = 42610116183028205126i = 526101616182030284*-4»12i = 6261016*161202

19、8303128261016*161820283012PivPvtpos0 123456789排序碼比較次ot數(shù)120,1,2,3116302810*1620618 92 poszf pospos f pos60,16122816*16203018 2pos 2 posio 284,5,6,7,826101228 161 pos f pos*16f pos20f pos30posf18 5184,5,62101218 16*1620I283036pos f posi pos42101216 16182028301*166* pos 2101216* 16182028306Whe n you ar

20、e old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you

21、,And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of yo

22、uYet you don't know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you can't see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.Is not being apart while being in loveBut whe n I pla inly cannot resist the year ningYe

23、t prete nding you have n ever bee n in my heart.The furthest dista nee in the worldIs not struggli ng aga inst the tidesBut using on e's in differe nt heartTo dig an un crossable riverFor the one who loves you.Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorro