中大实践考核数据结构试题和答案(上机考试)

1数据结构样题1、已知整数a、b，假设函数succ(x)=x+1、pred(x)=x-1，不许直接用“＋”、“－”运算符号，也不许用循环语句，只能利用函数succ()和pred()，试编写计算a+b，a-b的递归函数add(a,b)，sub(a,b)，并在主程序中验证函娄的正确性。#includestdio.h#includeconio.hintsucc(intx){returnx+1;}intpred(intx){returnx-1;}intadd(inta,intb){if(b==0)returna;if(b0)returnsucc(add(a,pred(b)));elsereturnpred(add(a,succ(b)));}intsub(inta,intb){if(b==0)returna;if(b0)returnpred(sub(a,pred(b)));elsereturnsucc(sub(a,succ(b)));}voidmain(){intk,a,b;clrscr();printf(\nPleaseinputab:);scanf(%d%d,&a,&b);printf(\na+b=%d,a+b);printf(\na-b=%d,a-b);printf(\nadd(a,b)=%d,add(a,b));printf(\nsub(a,b)=%d,sub(a,b));if((a+b==add(a,b))&&(a-b==sub(a,b)))printf(\nIt'sright!);elseprintf(\nIt'swrong!\n\n);}样题2试编写一个求解Josephus问题的函数。用整娄序列1，2，3，……，n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构，然后使用n=9，s=1，m=5，以及n=9，s=1，m=0，或者n=9，s=1，m=10作为输入数据，验证的正确性。Josephus问题:设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。Josephus问题是：对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。#includeconio.h#includeiostream.h#defineN100voidJosephus(intn,ints,intm){inti,j,k,l;intA[N];if(n1||s1||m1)return;for(i=0;in;i++)A[i]=i+1;l=s-2;k=0;while(kn){for(j=0;jm;){l=(l+1)%n;if(A[l]!=-1)j++;}coutA[l],;A[l]=-1;k=k+1;}}voidmain(){intn,s,m;clrscr();cout\nJosephusquestionPleasecheckTheResult:\nPleaseinput:nsm=;cinnsm;cout\nJosephus(nsm)\n;Josephus(n,s,m);cout\n\n\nPressanykeytoExit.;getch();}样题3依次输入10个整数，分别用顺序表与单链表存储，并实现其就地逆置。#includeiostream.h#includeconio.h#defineListSize10typedefstruct{intdata[ListSize];intlenght;}SeqList;typedefstructnode{intdata;structnode*next;2}ListNode;typedefListNode*LinkList;voidmain(){inti,j,k;inta[ListSize],temp;SeqListSL,*L;ListNode*s,*r,*p;LinkListhead;clrscr();coutInputNumber:\n;for(i=0;iListSize;i++)cina[i];L=&SL;L-lenght=0;for(i=0;iListSize;i++){L-data[i]=a[i];L-lenght++;}coutSeqListOrder:\n;for(i=0;iListSize;i++)coutL-data[i];//invertSeqListj=0;k=L-lenght-1;while(jk){temp=L-data[j];L-data[j]=L-data[k];L-data[k]=temp;j++;k--;}cout\nInvertSeqListOrder:\n;for(i=0;iListSize;i++)coutL-data[i];head=NULL;r=NULL;i=0;while(iListSize){s=newListNode[sizeof(ListNode)];s-data=a[i];if(head==NULL)head=s;elser-next=s;r=s;i++;}if(r)r-next=NULL;cout\nListNodeOrder:\n;s=head;while(s){couts-data;s=s-next;}//invertListNodes=head-next;r=head;while(s){p=s-next;s-next=r;r=s;s=p;}head-next=NULL;head=r;cout\nInvertListNodeOrder:\n;s=head;while(s){couts-data;s=s-next;}cout\n\n\n;}样题4设有环队列类型如下：typedefstruct{dnintypedata[maxsize];intfront,rear;}cyequeue;cycqueuesq;编写入队操作intEnQueue(cycqueuesq,datarypex)的代码，并调试通过。（提示：将x入队列sq，成功返回1，否则，返回0）#includestdio.h#includestdlib.h#includeconio.h#includestring.h#includemalloc.h#definemaxsize10#definedatatypechartypedefstruct{datatypedata[maxsize];intfront,rear;}cycqueue;cycqueue*sq;voidInitQueue(cycqueue*sq){sq-front=sq-rear=0;3}intEnQueue(cycqueue*sq,datatypex){if(((sq-rear+1)%maxsize)==(sq-front%maxsize))return0;sq-data[sq-rear]=x;sq-rear=(sq-rear+1)%maxsize;return1;}voidmain(){inti,j,k;chars[100],x;j=0;clrscr();sq=(cycqueue*)malloc(sizeof(cycqueue));InitQueue(sq);printf(\nInputstring:);gets(s);j=strlen(s);i=0;while(j!=0){x=s[i++];k=EnQueue(sq,x);if(k==1)printf('%c'EnQueueOK!\n,x);else{printf('%c'EnQueueError,overflow!\n,x);break;}j--;}}样题5设有两个整数类型的顺序表A（有5个元素）和B（有4个元素），其元素均以从小到大的升序排列。请编写一个函数，将这两个顺序表合并成一个顺序表C（要求C的元素也以从小到大的升序排列），并编写主程序验证该函数的正确性。#includeiostream.h#includeconio.h#defineLA5#defineLB4#defineLCLB+LAvoidMergeSort(intA[],intB[],intC[]){inti,j,k;i=0;j=0;k=0;while(iLA&&jLB){if(A[i]B[j])C[k++]=B[j++];elseC[k++]=A[i++];}while(iLA)C[k++]=A[i++];while(jLB)C[k++]=B[j++];}voidmain(){inti;intA[LA],B[LB],C[LC];clrscr();cout\nInputSeqListA(5integers):\n;for(i=0;iLA;i++)cinA[i];cout\nInputSeqListB(4integers):\n;for(i=0;iLB;i++)cinB[i];cout\nSeqListA:;for(i=0;iLA;i++)coutA[i];cout\nSeqListB:;for(i=0;iLB;i++)coutB[i];MergeSort(A,B,C);cout\nSeqListC:;for(i=0;iLC;i++)coutC[i];cout\n\n\n;}样题6编写一个算法程序frequency,统计在一个输入字体串中各个不同字符出现的频度。算法返回两个数组：A[]记录字体串中有多少种不同的字符，C[]记录每一种字符的出现次数。此外，还要返回不同字符数。#includeconio.h#includestdio.h#includeiostream.h#includestring.h#defineMaxSize500//统计字符串S有多少种字符,是些什么字符,和这些字符出现的频度intfrequency(charA[],intC[],charS[],intmax){inti,j,k;i=0;j=0;while(jmax){for(k=0;kj;k++){if(A[k]!=S[j])continue;4else{C[k]++;break;}}if(k==j){A[i]=S[j];C[i]=1;i++;}j++;}A[i]='\0';returni;}voidmain(){intcount,i,j;charA[MaxSize],*S;intC[MaxSize];clrscr();cout\nPleaseinputstringforcounting:\n;j=strlen(gets(S));count=frequency(A,C,S,j);cout\nThereiscountkindscharinString\n;for(i=0;icount;i++){coutChar[A[i]]:C[i]times.\n;}cout\n\n\nPressanykeytoExit.;getch();}样题7设在一个带表头结点的单链表中所有元素结点的数据值按递增顺序排列，请编写一个函数，删除表中所有大于min，小于max的元素（若存在），并编写主程序验证该函数的正确性。//J7.CPP#includestdio.h#includeconio.h#includemalloc.htypedefstructnode{chardata;structnode*next;}ListNode;typedefListNode*LinkList;LinkListCreateListR(void)//WithHeadNode{charch;LinkListhead=(LinkList)malloc(sizeof(ListNode));ListNode*s,*r;r=head;while