十套數(shù)據(jù)結(jié)構(gòu)試卷和答案-供復(fù)習(xí)參考

對4．對5．對錯對4．對5．對錯9．錯10．錯一、選擇題1．B2．B3．C4．B5．B6．A7．C8．C9．B10．D二、判斷題1．對2．對36．對7．對8三、填空題1.s->left=p，p->right2.n(n-1)，n(n-1)/2n/2開放定址法，鏈地址法5.146.2h-1，2h-1(12，24，35，27，18，26)(12，18，24，27，35，26)5i<j&&r[i].key<x.key，r[i]=x四、算法設(shè)計題設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}設(shè)計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");

else{for(i=start-1,j=0;i<start+count-1;i++,j++)t[j]=s[i];t[j]='\0';}}設(shè)計求結(jié)點在二叉排序樹中層次的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){elseif(bt!=0)else{lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);level(bt->rchild,x);}}數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案一、選擇題1．C6．C2．C7．B3．C8．C4．B9．A5．B10．A二、判斷題1．對2．錯3．對4．錯5．錯6．對7．對8．對9．對10．對三、填空題1.(49，13，27，50，76，38，65，97)2.t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)p->next=shead->rlink，p->llinkCABD1，160(13，27，38，50，76，49，65，97)n-150四、算法設(shè)計題1.設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}2.設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案一、選擇題1．A2．A3．A4．C5．D6．D7．C8．B9．C10．A11．C12．C13．D14．A15．A二、填空題1.p->next，s->data2.503.m-16，85.快速，堆19/7CBDA6（24，65，33，80，70，56，48）8三、判斷題1．錯2．對3．對4．對5．錯6．錯7．對8．對9．錯10．對

四、算法設(shè)計題1．設(shè)計計算二叉樹中所有結(jié)點值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}2．設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]%2==0)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]%2==1)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}3．設(shè)計判斷單鏈表中元素是否是遞增的算法。intisriselk(lklist*head){if(head==0||head->next==0)return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案一、選擇題1一、選擇題1．A2．D3．B7．A8．D9．D4．B5．B6．D10．C11．B12．D二、填空題1.4，102.O(nlog2n)，O(n2)3.n4.1，25.n(m-1)+16.q->next7.線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)8.O(n2)，O(n+e)9.8/310.(38，13，27，10，65，76，97)(10，13，27，76，65，97，38)124653structnode*rchild，bt=0，createbitree(bt->lchild)lklist，q=p三、算法設(shè)計題1.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}設(shè)計在二叉排序樹上查找結(jié)點X的算法。bitree*bstsearch1(bitree*t,intkey){bitree*p=t;while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;return(0);}設(shè)關(guān)鍵字序列(