第二章顺序存储结构的线性表-习题课.ppt

第二章顺序存储结构的线性表;选择题;3、若已知一个栈的入栈序列是1,2,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi=_____。 A i B n-i C n-i+1 D 不能确定 4、一个队列的入队序列为1，2，3，4，则其输出序列可能是____。 A 4,3,2,1 B 1,2,3,4 C 1,4,2,3 D 3,2,4,1 5、判定一个容量为m的队列为空的条件是_____。 A rear-front=m B front-rear=m C rear-front-1=m D front-rear-1=m E rear=front F rear=front-1;6、栈和队列的共同点是_____。 A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 ;填空题;4、一个栈的输入序列是12345，如果栈的输出序列43512是_____。 5、一个栈的输入序列是12345，如果栈的输出序列12345是_____。;算法编写题;PROCEDURE Insert(ET a[],int n,int x) If(x=a[n]) a[n+1]=x; Else { int i=1; while(x=a[i]) do i=i+1; for j=n to i do a[j+1]=a[j]; a[i]=x; n=n+1; } END;第二题;PROCEDURE nizhuan(ET a[],int n) For k=1 to n/2 do { t=a[k]; a[k]=a[n-k+1]; a[n-k+1]=t; } END ;第三题;PROCEDURE hebing(a[], b[],m,n) ET a[], ET b[],int m,int n i=1; j=1; k=1; While(i=m and j=n) do If (a[i]b[j]) { c[k]=a[i];i=i+1;k=k+1; } Else {c[k]=b[j];j=j+1;k=k+1; } If(j=n) for t=(i+1) to m do { c[k]=a[t];k=k+1 } If (i=m) for t=(j+1) to n do { c[k]=b[t]; k=k+1; };第四题;分析;设x为当前所求的出列者(序号)，它的前驱为t，则有a[t]=x，而且x的后继为a[x]，则当前的队列为 ……, t , x , a[x] , …… 当x出列后，队列变为 ……, t , a[x] , …… 显然，此时t的后继已变为a[x]。由此可见，当x出列时，只需作以下两个操作： 1、将所求到的x存入另一个数组b。 2、a[x]赋值给a[t]，即 a[t]=a[x]。;接下来的问题是如何确定每次出列者。 设s首先指向每次第一个报数者，t指向s时，s便指向它的后继， t再指向s时，s又指向它的后继，如此循环m次后，t便是当前出列者x，s便是下次开始报数者。 for i =1 to m do { t=s; s=a[s]; } 这样就能够将每次出列者求出来，但是不便于实现上页所述的操作2。因此只要循环m-1次就两者都能兼顾了。此时的t正是当前出列者x的前驱。