数据结构教程--试题

1.已知一个线性表的元素按元素非递减有序排列,编写一个过程删除线性表中多余的值相同的元素.2.有两个顺序存贮的线性表A(有m个元素)和B(有n个元素),其元素均以从小到大的升序排列,编写一个过程将它们合并成一个线性表C,要求C的元素也是以从小到大的升序排列.voiddel(list,n)intlist[],n;{inti,j;i=0;while(in-1)if(a[i]!=a[i+1])i=i+1;else{for(j=i+1;jn;j++)a[j]=a[j+1];n=n-1;}}1.voidlink(A,B,C,m,n)inta[],B[],C[],m,n;{inti,k,l,j;i=0;k=0;j=0;while(im&&jn){if(A[i]B[j]){C[k]=A[i];i=i+1;k=k+1;}2.else{C[k]=B[j];j=j+1;k=k+1;}}if(j=n-1)for(l=i;im;l++){C[k]=A[l];k=k+1;}if(i=m-1)for(l=j;ln;l++){C[k]=B[l];k=k+1;}}3.编写一个倒置顺序存贮的线性表的C函数,要求尽量用最少的附加存贮空间来完成.intlist[];intn,i,t;for(i=0;in/2;i++){t=list[i];list[i]=list[n-1];list[n-1]=t;n--}print(……….)4.假设有两个栈共享一个数组stack[n],如下图,试编写对任一栈作进栈和出栈运算的C函数:push(x,i)和pop(i),i=1,2.i=1表示左边的栈i=2表示右边的栈要求在整个数组元素都被占用时才产生溢出栈1底栈2底栈1顶栈2顶…….inttop1=0,top2=MAXN-1;charx;inti;{if(i==1)if(top1top2)return(1);stack[top1++]=x;return(0);if(i==2)if(top2top1)return(1);stack[top2--]=x;return(0);}…….{if(i==1)if(top1=0)return(1);*p_y=stack[--top1];return(0);if(i==2)if(top2=MAXN-1)return(1);*p_y=stack[++top2];return(0);}Top1=-1;top2=maxnintpush(x,i)charx;inti;{if(top1==top2-1)reutrn(0);elseif(i==1)stack[++top1]=x;elsestack[--top2]=x;return(1);}intpop(pop,i)char*pop;inti;{if(i==1){if(top1==-1)return(0);*pop=stack[top1--];return(1);}else{if(top2==n)return(0);*pop=stack[top2++];return(1);}5.在一个最多可存放n个结点的顺序存贮的队列中,如果头指针指向队首结点,让尾指针指向下一个进队的存放位置,如下图:试分别编写实现进队和出队的C函数.ABCheadtailif(head=tail)return(1);*p_y=q[head++];return(0);if(tail=MAXN)return(1);q[tail++]=x;return(0);6.设有一个环形队列,该队列只有一个队列头指针head,不设队列尾指针,而改置计数器count用以记录队列中结点的个数.试编写实现队列的五个运算;A.设置队列的初始空态B.判定队列是否为空C.取队列头结点的值给变量xD.将x元素入队E.删除队列头结点.head=0;count=0;intempty(){if(count==0)reutrn(0);return(1);}intgethead(x);charx;{if(count==0)return(1);x=q[(head+1)%MAXN];return(0);}intenqueue(x)charx;{if(count==MAXN)return(1);count++;q[(head+count)%MAXN]=x;return(0);}intdequeue(p_y)char*p_y;{if(count==0)return(1);head=(head+1)%MAXN;*p_y=q[head];count--;return(0);}7.利用两个栈S1,S2模拟一个队列时,如何用栈的运算来实现该队列的运算:enqueue:插入一个元素;dequeue:删除一个元素;queue_empty:判定队列为空;intenqueue(x)charx;{if(top1=MAXN)return(0);push(s1,x);return(1);}intdequeue(p_y)char*p_y;{inttop2=0;while(sempty(s1))push(s2,pop(s1));*p_y=pop(s2);while(sempty(s2))push(s1,pop(s2))}作业1.试编写一个求已知单链表的数据域的平均值的函数2.已知带有头结点的环形链表中头指针为head，试写出删除并释放数据域值为x的所有结点的函数3.线性表中的元素值按递增有序排列,针对顺序表和环形链表两种不同的存储方式,分别编写函数删除线性表中值介于a与b(ab)之的元素intaver(node*head){inti=0,sum=0,ave;node*p;p=head;while(p!=null){p=p-link;i++;sum-sum+p-data;}ave=sum/i;return(ave);}voiddel-link(node*head,intx){node*p,*q,*s;p=head;q=head-link;while(q!=head){if(q-data==x){p-link=q-link;s=q;q=q-link;free(s);}else{p=q;q=q-link;}}}