2012014數(shù)據(jù)結(jié)構(gòu)A卷-參考答案

1、：名簽生學(xué) 號學(xué) 級班 業(yè)。果后切一的起引此由擔(dān)承愿，位學(xué)士學(xué)予授不將分處上以及過記 受弊作因和籍學(xué)除開被將者考人他代或考代人他請道知還，性重嚴(yán)的弊作、紀(jì)違試考道知，律紀(jì)場考守遵格嚴(yán)將我：諾華東交通大學(xué) 20132014學(xué)年第一學(xué)期考試卷試卷編號：（A ）卷數(shù)據(jù)結(jié)構(gòu) 課程 課程類別：必題號一二三四五六七八九十總分累分人 簽名題分203010364100得分開卷（僅限教材）： 考試日期： 2014-1-16考生注意事項(xiàng)： 1、本試卷共 5 頁，總分 100 分，考試時間 120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。一、選擇題 （每題 2 分，共 20分）1、由兩個棧共享一

2、個向量空間的好處是： （ ）（ A ） 減少存取時間，降低下溢發(fā)生的機(jī)率（ B ） 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率（ C ） 減少存取時間，降低上溢發(fā)生的機(jī)率（ D ） 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率2、設(shè)數(shù)據(jù)結(jié)構(gòu) A=（D，R），其中 D=1，2，3，4，R=r，r=1，2，2，3，3， 4 ，4，1，則數(shù)據(jù)結(jié)構(gòu) A 是（）。（A） 線性結(jié)構(gòu) （B） 樹型結(jié)構(gòu) （C） 圖型結(jié)構(gòu) （D） 集合3、設(shè)數(shù)組 datam作為循環(huán)隊(duì)列 SQ 的存儲空間， front 為隊(duì)頭指針， rear 為隊(duì)尾指 針，則執(zhí)行出隊(duì)操作后其頭指針 front 值為（ ）(A) front=front+1(C) fr

3、ont=(front-1)%m(B) front=(front+1)%(m-1)(D) front=(front+1)%m4、設(shè)一組初始記錄關(guān)鍵字序列 （5，2，6， 3，8），以第一個記錄關(guān)鍵字 5 為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ ）第1 頁共5 頁(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，85、設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作()。(A) 必須判別棧是否為滿 (B) 必須判別棧是否為空(C) 判別棧元素的類型 (D) 對棧不作任何判別6、設(shè)一組初始記錄關(guān)鍵字序列為 (25，50，15，35，80，85， 20，40 ，36，7

4、0)， 其中含有 5 個長度為 2 的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行 一趟歸并后的結(jié)果為( )。(A) 15 ，25，35，50 ，20，40，80，85，36，70(B) 15 ，25，35，50 ，80，20，85，40，70，36(C) 15 ，25，35，50，80，85，20，36，40，70(D) 15 ，25，35，50，80，20，36，40，70，857、設(shè)一棵完全二叉樹中有 65 個結(jié)點(diǎn)，則該完全二叉樹的深度為()。(A) 8 (B) 7 (C) 6 (D) 58、設(shè)一組初始記錄關(guān)鍵字序列為 (13，18，24，35 ，47，50，62，83，90，11

5、5， 134),則利用二分法查找關(guān)鍵字 90 需要比較的關(guān)鍵字個數(shù)為()。(A) 1 (B) 2 (C) 3 (D) 49、設(shè)無向圖 G 中的邊的集合 E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)， (f，c)，則從頂點(diǎn) a 出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為()。(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc10、設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲方式最節(jié)省運(yùn)算時間。(A) 單向鏈表 (B) 單向循環(huán)鏈表 (C) 雙向鏈表 (D) 雙向循環(huán)鏈表二、填空題(每空 2分，共 30分

6、)第2 頁共5 頁（1）、設(shè)散列表的長度為 8，散列函數(shù) H（k）=k % 7 ，用線性探測法 解決沖突，則根據(jù)一組初始關(guān)鍵字序列 （8，15 ，16，22，30 ，32） 構(gòu)造出的散列表的平均查找長度是 _ _（1） 。（2）、數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為四種基本類型： _ _（2）_、（3）、_ _（4）和_ _（5）。（3）、for（i=1，t=1，s=0；inext;while (p !=null & p-costnext; if (p!=null & p-cose=h ) p-num+=m ;else t=(LNode*) malloc (sizeof (LNode); t-cost=h

7、； t-num=m ; q-next=t; t-next=p; 答案寫在答題紙上，寫在試卷上成績無效第5 頁共5 頁受 弊 作 因 和 籍 學(xué) 除 開 被 將 者 考 人 他 代 或 考 代 人 他 請 道 知。 還果名簽 生 學(xué)號學(xué)道知位學(xué) 級 知，學(xué)士 班 律學(xué) 紀(jì)予 場授 考不 守將 遵分 格處 嚴(yán)上 將以 我及諾 記 業(yè) 承到 專華東交通大學(xué) 20132014學(xué)年第一學(xué)期考試卷參考答案 （A 卷）題號一二三四五六七八九十總分累分人 簽名題分203010364100得分?jǐn)?shù)據(jù)結(jié)構(gòu) 課程 課程類別：必 開卷（僅限教材）： 考試日期： 2014-1-16考生注意事項(xiàng)： 1、本答題紙共 2頁，總

8、分 100 分，考試時間 120分鐘。一、選擇題 （每題 2分，共 20 分）得分閱卷人12345678910BCDCBABBAD2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場。二、填空題（每空 2分，共 30分）得分閱卷人(1)8/3(2)集合(3)線性結(jié)構(gòu)(4)樹型結(jié)構(gòu)(5)圖型結(jié)構(gòu)(6)O（n）(7)-1(8)3 4 X * + 2 Y * 3 / -(9)6(10)head-rlink(11)p-llink(12)2O(n2)(13)O(nlog 2n)(14)4(15)16第3 頁共4 頁三、判斷題 （每題 1分，共 10 分）得分閱卷人12345678910第3 頁共4 頁3E=（1，3），（1，2），（3，5），（5，6），（6，4）4(1) 一趟希爾排序 : 12,2,10,20,6,18,4,16,30,8,28( D=5)(2) 一趟快速排序： 6,2,10,4,8,12,28,30,20,16,185散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412平均查找長度：