數據結構復習題及答案-資料下載頁

　　

【正文】 t=trchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。三、計算題1． H(36)=36 mod 7=1。 H１(22)=(1+1) mod 7=2。 ….沖突H(15)=15 mod 7=1。….沖突 H2(22)=(2+1) mod 7=3。 H１(15)=(1+1) mod 7=2。H(40)=40 mod 7=5。H(63)=63 mod 7=0。H(22)=22 mod 7=1。 ….沖突（1） 0 1 2 3 4 5 66336152240（2）ASL=(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18四、算法設計題1. 設計在單鏈表中刪除值相同的多余結點的算法。typedef int datatype。typedef struct node {datatype data。 struct node *next。}lklist。void delredundant(lklist *amp。head){ lklist *p,*q,*s。 for(p=head。p!=0。p=pnext) { for(q=pnext,s=q。q!=0。 ) if (qdata==pdata) {snext=qnext。 free(q)。q=snext。} else {s=q,q=qnext。} }}2. 設計一個求結點x在二叉樹中的雙親結點算法。typedef struct node {datatype data。 struct node *lchild,*rchild。} bitree。bitree *q[20]。 int r=0,f=0,flag=0。void preorder(bitree *bt, char x){ if (bt!=0 amp。amp。 flag==0)if (btdata==x) { flag=1。 return。}else {r=(r+1)% 20。 q[r]=bt。 preorder(btlchild,x)。 preorder(btrchild,x)。 }}void parent(bitree *bt,char x){ int i。 preorder(bt,x)。 for(i=f+1。 i=r。 i++) if (q[i]lchilddata==x || q[i]rchilddata) break。 if (flag==0) printf(not found x\n)。 else if (i=r) printf(%c,btdata)。 else printf(not parent)。}數據結構試卷（四）參考答案一、選擇題1．C 2．D 3．D 4．B 5．C6．A 7．B 8．A 9．C 10．A二、填空題1. O(n2)，O(nlog2n)2. pllinkrlink=prlink。 prlinkllink=prlink3. 34. 2k15. n/26. 50，517. m1，(RF+M)%M8. n+1i，ni9. (19，18，16，20，30，22)10. (16，18，19，20，32，22)11. A[i][j]=112. 等于13. BDCA14. hashtable[i]=0，hashtable[k]=s三、計算題1．2． (1) ABCDEF。 BDEFCA；(2) ABCDEFGHIJK。 BDEFCAIJKHG林轉換為相應的二叉樹；3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設計題1. 設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedef char datatype。typedef struct node {datatype data。 struct node *next。}lklist。void split(lklist *head,lklist *amp。ha,lklist *amp。hb,lklist *amp。hc){ lklist *p。 ha=0,hb=0,hc=0。 for(p=head。p!=0。p=head) { head=pnext。 pnext=0。 if (pdata=39。A39。 amp。amp。 pdata=39。Z39。) {pnext=ha。 ha=p。} else if (pdata=39。039。 amp。amp。 pdata=39。939。) {pnext=hb。 hb=p。} else {pnext=hc。 hc=p。} }}2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。typedef struct node {int data。 struct node *lchild,*rchild。} bitree。void swapbitree(bitree *bt){ bitree *p。 if(bt==0) return。swapbitree(btlchild)。 swapbitree(btrchild)。p=btlchild。 btlchild=btrchild。 btrchild=p。}3. 在鏈式存儲結構上建立一棵二叉排序樹。define n 10typedef struct node{int key。 struct node *lchild,*rchild。}bitree。void bstinsert(bitree *amp。bt,int key){ if (bt==0){bt=(bitree *)malloc(sizeof(bitree))。 btkey=key。btlchild=btrchild=0。} else if (btkeykey) bstinsert(btlchild,key)。 else bstinsert(btrchild,key)。}void createbsttree(bitree *amp。bt){ int i。 for(i=1。i=n。i++) bstinsert(bt,random(100))。}數據結構試卷（五）參考答案一、選擇題1．A 2．B 3．A 4．A 5．D6．B 7．B 8．B 9．C 10．C二、填空題1. top1+1=top22. 可以隨機訪問到任一個頂點的簡單鏈表3. i(i+1)/2+j14. FILO，FIFO5. ABDECF，DBEAFC，DEBFCA6. 8，647. 出度，入度8. ki=k2i amp。amp。 ki=k2i+19. ni，r[j+1]=r[j]10. mid=(low+high)/2，r[mid].keyk三、應用題1. DEBCA2. E={(1,5),(5,2),(5,3),(3,4)},W=103. ASL=(1*1+2*2+3*4)/7=17/74. ASL1=7/6，ASL2=4/3四、算法設計題1. 設計判斷兩個二叉樹是否相同的算法。typedef struct node {datatype data。 struct node *lchild,*rchild。} bitree。int judgebitree(bitree *bt1,bitree *bt2){ if (bt1==0 amp。amp。 bt2==0) return(1)。 else if (bt1==0 || bt2==0 ||bt1data!=bt2data) return(0)。 else return(judgebitree(bt1lchild,bt2lchild)*judgebitree(bt1rchild,bt2rchild))。}2. 設計兩個有序單鏈表的合并排序算法。void mergelklist(lklist *ha,lklist *hb,lklist *amp。hc){ lklist *s=hc=0。 while(ha!=0 amp。amp。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。 else {snext=ha。 s=ha。}。ha=hanext。} else {if(s==0) hc=s=hb。 else {snext=hb。 s=hb。}。hb=hbnext。} if(ha==0) snext=hb。 else snext=ha。}