【文章內(nèi)容簡(jiǎn)介】 ext=hb。 else snext=ha。}數(shù)據(jù)結(jié)構(gòu)試卷（六）四、算法設(shè)計(jì)題(20分)１． 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。struct record {int key。 int others。}。int bisearch(struct record r[ ], int k){ int low=0,mid,high=n1。 while(low=high){ mid=(low+high)/2。 if(r[mid].key==k) return(mid+1)。 else if(r[mid].keyk) high=mid1。 else low=mid+1。 } return(0)。}２． 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。int minnum=32768,flag=1。typedef struct node{int key。 struct node *lchild,*rchild。}bitree。void inorder(bitree *bt){ if (bt!=0) {inorder(btlchild)。 if(minnumbtkey)flag=0。 minnum=btkey。inorder(btrchild)。}}在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法void straightinsertsort(lklist *amp。head){ lklist *s,*p,*q。 int t。 if (head==0 || headnext==0) return。 else for(q=head,p=headnext。p!=0。p=qnext) { for(s=head。s!=qnext。s=snext) if (sdatapdata) break。 if(s==qnext)q=p。else{qnext=pnext。 pnext=snext。 snext=p。 t=pdata。pdata=sdata。sdata=t。} }}數(shù)據(jù)結(jié)構(gòu)試卷（七）四、算法設(shè)計(jì)題(20分)1. 設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。void simpleselectsorlklist(lklist *amp。head){ lklist *p,*q,*s。 int min,t。 if(head==0 ||headnext==0) return。 for(q=head。 q!=0。q=qnext) { min=qdata。 s=q。 for(p=qnext。 p!=0。p=pnext) if(minpdata){min=pdata。 s=p。} if(s!=q){t=sdata。 sdata=qdata。 qdata=t。} }}2. 設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。void substring(char s[ ], long start, long count, char t[ ]){ long i,j,length=strlen(s)。 if (start1 || startlength) printf(The copy position is wrong)。 else if (start+count1length) printf(Too characters to be copied)。else { for(i=start1,j=0。 istart+count1。i++,j++) t[j]=s[i]。 t[j]= 39。\039。}}3. 設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。int lev=0。typedef struct node{int key。 struct node *lchild,*rchild。}bitree。void level(bitree *bt,int x){ if (bt!=0){lev++。 if (btkey==x) return。 else if (btkeyx) level(btlchild,x)。 else level(btrchild,x)。}}數(shù)據(jù)結(jié)構(gòu)試卷（八）四、算法設(shè)計(jì)題(20分)1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。void countnode(bitree *bt,int amp。count){ if(bt!=0) {count++。 countnode(btlchild,count)。 countnode(btrchild,count)。}}2. 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。typedef struct {int vertex[m]。 int edge[m][m]。}gadjmatrix。typedef struct node1{int info。int adjvertex。 struct node1 *nextarc。}glinklistnode。typedef struct node2{int vertexinfo。glinklistnode *firstarc。}glinkheadnode。void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j。 glinklistnode *p。for(i=0。i=n1。i++) g2[i].firstarc=0。for(i=0。i=n1。i++) for(j=0。j=n1。j++)if ([i][j]==1){p=(glinklistnode *)malloc(sizeof(glinklistnode))。padjvertex=j。pnextarc=g[i].firstarc。 g[i].firstarc=p。p=(glinklistnode *)malloc(sizeof(glinklistnode))。padjvertex=i。pnextarc=g[j].firstarc。 g[j].firstarc=p。}}數(shù)據(jù)結(jié)構(gòu)試卷（九）五、算法設(shè)計(jì)題(20分)1． 設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。void sum(bitree *bt,int amp。s){ if(bt!=0) {s=s+btdata。 sum(btlchild,s)。 sum(btrchild,s)。} }2． 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]。 while(ij){ while (ij amp。amp。 r[j]%2==0) j=j1。 if (ij) {r[i]=r[j]。i=i+1。} while (ij amp。amp。 r[i]%2==1) i=i+1。 if (ij) {r[j]=r[i]。j=j1。} } r[i]=x。}3． 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。int isriselk(lklist *head){if(head==0||headnext==0) return(1)。elsefor(q=head,p=headnext。 p!=0。 q=p,p=pnext)if(qdatapdata) return(0)。return(1)。}數(shù)據(jù)結(jié)構(gòu)試卷（十）三、算法設(shè)計(jì)題(22分)1． 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。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。}2． 設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。bitree *bstsearch1(bitree *t, int key){ bitree *p=t。 while(p!=0) if (pkey==key) return(p)。else if (pkeykey)p=plchild。 else p=prchild。 return(0)。}3． 設(shè)關(guān)鍵字序列(k1，k2，…，kn1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。設(shè)關(guān)鍵字序列(k1，k2，…，kn1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。 while (i=1) if (temp=r[i1])break。 else{r[j1]=r[i1]。 j=i。 i=i/2。} r[j1]=temp。}數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案三、計(jì)算題（每題6分，共24分）