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

1、江蘇技術(shù)師范學(xué)院2007-2008學(xué)年第2學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法試卷（1A）參考答案與評分標(biāo)準(zhǔn)、選擇題（每題1.5分，共15分）題號12345678910“案BBADABADCC:、填空（每空1.5分，共15分）1、數(shù)據(jù)元素的有限集，D上關(guān)系的有限集2、n-i3、隊列4、20,35、開放定址法，再哈希法，鏈地址法，建立一個公共溢出區(qū)6、非零元很少（t<<m*n）且分布沒有規(guī)律7、簡單路徑或簡單回路或簡單環(huán)8、31（m+n2=0+n2=nc-1=31）,26-1=329、log2n三、判斷題（10分，每題1分對的打如，錯的打X'）題號12345678910卜案VXVVXXXVXV

2、四、簡答、應(yīng)用題（共40分）1設(shè)順序表循環(huán)隊列中存放元素的數(shù)組data口，容量為MAXSIZE隊列中隊頭指針為begin，隊尾指針為end,指向隊列的指針為pring。采用少用一個元素空間的辦法判斷隊列空與滿。寫出元素x入隊列，x出隊列的操作（操作中不考慮隊列滿與空）。（4分）解：入隊歹U:pring->datapring->end=xpring->end=（pring->end+1）%MAXSIZE出隊歹U:x=pring->datapring->beginpring->front=（pring->front+1）%MAXSIZE2列出先序遍歷

3、能得到ABC序列的所有不同的二叉樹。（5分）3已知某算法如下，試說明該算法實現(xiàn)的功能。（6分）#defineMax100voidunknow(intnum,intr)(intstMax,top=0;while(num!=0)(sttop+=num%r;num=num/r;while(top>0)cout<<st-top<<cout<<endl;答：將十進(jìn)制數(shù)num轉(zhuǎn)換成r進(jìn)制的數(shù)，弁輸出結(jié)果。5分)3G是一個非連通無向圖，共有28條邊，貝U該圖至少有多少個頂點?結(jié)點數(shù)為28<=n（n-1）/2，則n取滿足該式的最小值為解：設(shè)有一個頂點為獨立的結(jié)點

4、，其余結(jié)點為全連通圖,5對于下圖所示的有向圖G給出從頂點0到其余各頂點的最短路徑及路徑長度。（6分）1: 0-1132: 0-283: 0-2-3134: 0-2-3-4195: 0-2-3-4-5216: 0-1-6206已知某二叉樹中序遍歷的結(jié)果為：DGBAECHF,則具有28條邊的全連通圖具有8,故該圖至少有9個頂點。(6分)其后半序遍歷的結(jié)果為：GDBEHFCA,試畫出這棵二叉樹。(A；(B)D)(EJQF(G)(H)7對關(guān)鍵字序列(7,4,1,14,100,30,5,9,20,134),設(shè)哈希函數(shù)為H(k)=kmod13,試給出表長為13的,弁求出在等概率情況下，查找成功的平下標(biāo)01

5、2345789101112K11443057201009134探查i欠121221128哈希表（用線性探測開放定址法處理沖突）均查找長度。（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)=13

6、4mod13=4沖突H1=(134+1)mod13=5沖突H1=(134+2)mod13=6沖突_H1(134+3)mod13=7沖突H1=(134+4)mod13=8沖突H1=H1=H1=(134+5)mod13=9沖突(134+6)mod13=10沖突(134+7)mod13=11沖突在等概率情況下：ASL=(1*4+5*2+1*8)/10=2.2五、算法設(shè)計題（20分）1.題目分析本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點移到鏈表的最前面。首先要查找最小值結(jié)點。將其移到鏈表最前面，實質(zhì)上是將該結(jié)點從鏈表上摘下（不是刪除弁回收空間），再插入到鏈表的最前面。LinkedListdelinsert(L

7、inkedListlist)/list是非空線性鏈表，鏈結(jié)點結(jié)構(gòu)是(data,link),data是數(shù)據(jù)域，link是鏈域。/本算法將鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面。(p=list->link；/p是鏈表的工作指針pre=list;/pre指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū)。q=p;/q指向數(shù)據(jù)域最小值結(jié)點，初始假定是第一結(jié)點while(p->link!=null)(if(p->link->data<q->data)(pre=p;q=p->link;/找到新的最小值結(jié)點；p=p->link;/ 若最小值是第一元素結(jié)點，則不需再操作if(q!=list->link)(pre->link=q->link;/將最小值結(jié)點從鏈表上摘下；q->link= list->link ;q結(jié)點插到鏈表最前面。list->link=q;/算法結(jié)束算法討論算法中假定list帶有頭結(jié)點，否則，插入操作變?yōu)閝->link=list;list=q。2.解：intLeafCount_BiTree(BitreeT)/求二叉樹中葉子結(jié)點的數(shù)目(if(!T)return0;/空樹沒有葉子elseif(!T->lchild&&a