《數(shù)據(jù)結(jié)構(gòu)與算法》試卷(1A)參考答案

江蘇技術(shù)師范學(xué)院2007—2008學(xué)年第2學(xué)期《數(shù)據(jù)結(jié)構(gòu)與算法》試卷（1A）一、選擇題（每題1.5分，共15分）題號(hào)12345678910答案BBADABADCC二、填空（每空1.5分，共15分）1、數(shù)據(jù)元素的有限集，D上關(guān)系的有限集2、n-i3、隊(duì)列4、20,35、開放定址法，再哈希法，鏈地址法，建立一個(gè)公共溢出區(qū)6、非零元很少(t<<m*n)且分布沒有規(guī)律7、簡(jiǎn)單路徑或簡(jiǎn)單回路或簡(jiǎn)單環(huán)8、31(n1+n2=0+n2=n0-1=31），26-1=329、log2n三、判斷題（10分，每題1分對(duì)的打‘√’，錯(cuò)的打‘×’）題號(hào)12345678910答案√×√√×××√×√四、簡(jiǎn)答、應(yīng)用題（共40分）1設(shè)順序表循環(huán)隊(duì)列中存放元素的數(shù)組data[]，容量為MAXSIZE，隊(duì)列中隊(duì)頭指針為begin，隊(duì)尾指針為end，指向隊(duì)列的指針為pring。采用少用一個(gè)元素空間的辦法判斷隊(duì)列空與滿。寫出元素x入隊(duì)列，x出隊(duì)列的操作(操作中不考慮隊(duì)列滿與空)。(4分)解：入隊(duì)列:pring->data[pring->end]=xpring->end=(pring->end+1)%MAXSIZE出隊(duì)列:x=pring->data[pring->begin]pring->front=(pring->front+1)%MAXSIZE2列出先序遍歷能得到ABC序列的所有不同的二叉樹。（5分）3已知某算法如下，試說明該算法實(shí)現(xiàn)的功能。（6分）#defineMax100voidunknow(intnum,intr){intst[Max],top=0;while(num!=0){st[top++]=num%r;num=num/r;}while(top>0)cout<<st[--top]<<““;cout<<endl;}答：將十進(jìn)制數(shù)num轉(zhuǎn)換成r進(jìn)制的數(shù)，并輸出結(jié)果。G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有多少個(gè)頂點(diǎn)？（5分）解：設(shè)有一個(gè)頂點(diǎn)為獨(dú)立的結(jié)點(diǎn)，其余結(jié)點(diǎn)為全連通圖，則具有28條邊的全連通圖其有結(jié)點(diǎn)數(shù)為28<=n(n-1)/2,則n取滿足該式的最小值為8，故該圖至少有9個(gè)頂點(diǎn)。5對(duì)于下圖所示的有向圖G，給出從頂點(diǎn)0到其余各頂點(diǎn)的最短路徑及路徑長(zhǎng)度。（6分）1：0-1132：0-283：0-2-3134：0-2-3-4195：0-2-3-4-5216：0-1-6206已知某二叉樹中序遍歷的結(jié)果為：DGBAECHF，其后半序遍歷的結(jié)果為：GDBEHFCA，試畫出這棵二叉樹。（6分）7對(duì)關(guān)鍵字序列（7，4，1，14，100，30，5，9，20，134），設(shè)哈希函數(shù)為H(k)=kmod13,試給出表長(zhǎng)為13的哈希表（用線性探測(cè)開放定址法處理沖突），并求出在等概率情況下，查找成功的平均查找長(zhǎng)度。（7分）解：H(7)=7mod13=7H(4)=4mod13=4H(1)=1mod13=1H(14)=14mod13=1沖突H1=（14+1）mod13=2H(100)=100mod13=9H(30)=30mod13=4沖突H1=（30+1）mod13=5H(5)=5mod13=5沖突H1=（5+1）mod13=6H(9)=9mod13=9沖突H1=（9+1）mod13=10H(20)=20mod13=7沖突H1=（20+1）mod13=8H(134)=134mod13=4沖突H1=（134+1）mod13=5沖突H1=（134+2）mod13=6沖突H1=（134+3）mod13=7沖突H1=（134+4）mod13=8沖突H1=（134+5）mod13=9沖突H1=（134+6）mod13=10沖突H1=（134+7）mod13=11沖突在等概率情況下：ASL=（1*4+5*2+1*8）/10=2.2五、算法設(shè)計(jì)題（20分）1．[題目分析]本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。首先要查找最小值結(jié)點(diǎn)。將其移到鏈表最前面，實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下（不是刪除并回收空間），再插入到鏈表的最前面。LinkedListdelinsert（LinkedListlist）∥list是非空線性鏈表，鏈結(jié)點(diǎn)結(jié)構(gòu)是（data，link），data是數(shù)據(jù)域，link是鏈域?！伪舅惴▽㈡湵碇袛?shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。{p=list->link；∥p是鏈表的工作指針pre=list；∥pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)。q=p；∥q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn)while（p->link!=null）{if（p->link->data<q->data）{pre=p；q=p->link；}∥找到新的最小值結(jié)點(diǎn)；p=p->link；}if(q!=list->link)∥若最小值是第一元素結(jié)點(diǎn)，則不需再操作{pre->link=q->link；∥將最小值結(jié)點(diǎn)從鏈表上摘下；q->link=list->link；∥將q結(jié)點(diǎn)插到鏈表最前面。list->link=q；}}∥算法結(jié)束[算法討論]算法中假定list帶有頭結(jié)點(diǎn)，否則，插入操作變?yōu)閝->link=list；list=q。2.解：intLeafCount_BiTree(BitreeT)//求二叉樹中葉子結(jié)點(diǎn)的數(shù)目{if(!T)return0;//空樹沒有葉子elseif(!T->lc