数据结构教程试题

1.一个线性表的元素按元素非递减有序排列,编写一个过程删除线性表中多余的值相同的元素.2.有两个顺序存贮的线性表A(有m个元素)和B(有n个元素),其元素均以从小到大的升序排列,编写一个过程将它们合并成一个线性表C,要求C的元素也是以从小到大的升序排列.1整理pptvoiddel(list,n)intlist[],n;{inti,j;i=0;while(i<n-1)if(a[i]!=a[i+1])i=i+1;else{for(j=i+1;j<n;j++)a[j]=a[j+1];n=n-1;}}1.2整理pptvoidlink(A,B,C,m,n)inta[],B[],C[],m,n;{inti,k,l,j;i=0;k=0;j=0;while(i<m&&j<n){if(A[i]<B[j])

{C[k]=A[i];i=i+1;k=k+1;}

2.3整理ppt

else

{C[k]=B[j];j=j+1;k=k+1;}}if(j>=n-1)for(l=i;i<m;l++)

{C[k]=A[l];k=k+1;}if(i>=m-1)for(l=j;l<n;l++)

{C[k]=B[l];k=k+1;}}4整理ppt3.编写一个倒置顺序存贮的线性表的C函数,要求尽量用最少的附加存贮空间来完成.intlist[];intn,i,t;for(i=0;i<n/2;i++){t=list[i];list[i]=list[n-1];list[n-1]=t;n--}print(……….)5整理ppt4.假设有两个栈共享一个数组stack[n],如以下图,试编写对任一栈作进栈和出栈运算的C函数:push(x,i)和pop(i),i=1,2.i=1表示左边的栈i=2表示右边的栈要求在整个数组元素都被占用时才产生溢出栈1底栈2底栈1顶栈2顶6整理ppt…….inttop1=0,top2=MAXN-1;charx;inti;{if(i==1)if(top1>top2)return(1);stack[top1++]=x;return(0);if(i==2)if(top2<top1)return(1);stack[top2--]=x;return(0);}7整理ppt…….{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);}8整理pptTop1=-1;top2=maxnintpush(x,i)charx;inti;{if(top1==top2-1)reutrn(0);elseif(i==1)stack[++top1]=x;elsestack[--top2]=x;return(1);}9整理pptintpop(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);}10整理ppt5.在一个最多可存放n个结点的顺序存贮的队列中,如果头指针指向队首结点,让尾指针指向下一个进队的存放位置,如以下图:试分别编写实现进队和出队的C函数.ABCheadtail11整理pptif(head=tail)return(1);*p_y=q[head++];return(0);if(tail>=MAXN)return(1);q[tail++]=x;return(0);12整理ppt6.设有一个环形队列,该队列只有一个队列头指针head,不设队列尾指针,而改置计数器count用以记录队列中结点的个数.试编写实现队列的五个运算;A.设置队列的初始空态B.判定队列是否为空C.取队列头结点的值给变量xD.将x元素入队E.删除队列头结点.13整理ppthead=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);}14整理pptintenqueue(x)charx;{if(count==MAXN)return(1);count++;q[(head+count)%MAXN]=x;return(0);}15整理pptintdequeue(p_y)char*p_y;{if(count==0)return(1);head=(head+1)%MAXN;*p_y=q[head];count--;return(0);}16整理ppt7.利用两个栈S1,S2模拟一个队列时,如何用栈的运算来实现该队列的运算:enqueue:插入一个元素;dequeue:删除一个元素;queue_empty:判定队列为空;17整理pptintenqueue(x)charx;{if(top1>=MAXN)return(0);push(s1,x);return(1);}18整理pptintdequeue(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))}19整理ppt作业1.试编写一个求单链表的数据域的平均值的函数2.带有头结点的环形链表中头指针为head，试写出删除并释放数据域值为x的所有结点的函数3.线性表中的元素值按递增有序排列,针对顺序表和环形链表两种不同的存储方式,分别编写函数删除线性表中值介于a与b(a<b)之的元素20整理pptintaver(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);}21整理pptvoiddel-link(node*head,intx){node*p,*q,*s;p=he