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