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

對(duì)4．對(duì)5．對(duì)錯(cuò)對(duì)4．對(duì)5．對(duì)錯(cuò)9．錯(cuò)10．錯(cuò)一、選擇題1．B2．B3．C4．B5．B6．A7．C8．C9．B10．D二、判斷題1．對(duì)2．對(duì)36．對(duì)7．對(duì)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è)計(jì)題設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(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è)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(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è)計(jì)求結(jié)點(diǎn)在二叉排序樹中層次的算法。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．對(duì)2．錯(cuò)3．對(duì)4．錯(cuò)5．錯(cuò)6．對(duì)7．對(duì)8．對(duì)9．對(duì)10．對(duì)三、填空題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è)計(jì)題1.設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}2.設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(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．錯(cuò)2．對(duì)3．對(duì)4．對(duì)5．錯(cuò)6．錯(cuò)7．對(duì)8．對(duì)9．錯(cuò)10．對(duì)

四、算法設(shè)計(jì)題1．設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}2．設(shè)計(jì)將所有奇數(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è)計(jì)判斷單鏈表中元素是否是遞增的算法。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è)計(jì)題1.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(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è)計(jì)在二叉排序樹上查找結(jié)點(diǎn)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)鍵字序列(