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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章顺序存储结构的线性表,习题课,选择题,1、一个顺序表的首元存储地址是100，每个元素的长度为2，则第5个元素的地址是_。,A 110 B 108 C 112 D 120,2、,一个栈的入栈序列为,a,b,c,d,e，,则栈的不可能的输出序列是_。,A edcba B decba,C dceab D abcde,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、,没有共同点,填空题,1、向量、栈和队列都是_结构，可以在向量的_位置插入和删除元素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。,2、向一个长度为,n,的向量的第,i(0in+2),个元素之前插入一个元素时，需向后移动_个元素。,3、,向一个长度为,n,的向量中删除第,i(0i=an)an+1=x;,Else,int i=1;,while(x=ai)do i=i+1;,for j=n to i do aj+1=aj;,ai=x;,n=n+1;,END,第二题,试写出在顺序存储结构下逆转线性表的算法，要求使用最少的附加空间。,PROCEDURE nizhuan(ET a,int n),For k=1 to n/2 do,t=ak;,ak=an-k+1;,an-k+1=t;,END,第三题,有两个顺序表,A,和,B，分别有,m,个和,n,个元素，其元素均以从小到大的升序排列，编写一个算法将它们合并成一个顺序表,C，,要求,C,的元素也是以从小到大的升序排列。,比如,A=3，5，8，11,B=2，6，8，9，11，15，20,则,C=2,3,5,6,8,8,9,11,11,15,20,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(aibj)ck=ai;i=i+1;k=k+1;,Else ck=bj;j=j+1;k=k+1;,If(j=n)for t=(i+1)to m do ck=at;k=k+1 ,If(i=m)for t=(j+1)to n do,ck=bt;k=k+1;,第四题,设有,n,个人围成一圈，每个人的编号依次为1,2,3,n。,现从编号为,k,的人开始报数，数到,m,的人便出列，接着从出列的下一个人开始重新报数，数到,m,的人又出列，以此类推，直到所有的人都出列为止。请写出算法求出,n,个人的出列顺序。,分析,设以自然数1,2,3,n,为元素构成一个循环队列，并用一个数组,a,存放该队列中每个元素的直接后继，其中,ai,表示,i,的后继。显然该数组初始化时应该这样：,ai=i+1,i=1,2,n-1,an=1;,设,x,为当前所求的出列者(序号)，它的前驱为,t，,则有,at=x,，,而且,x,的后继为,ax，,则当前的队列为,t,x,ax,当,x,出列后，队列变为,t,ax,显然，此时,t,的后继已变为,ax。,由此可见，当,x,出列时，只需作以下两个操作：,1、将所求到的,x,存入另一个数组,b。,2、ax,赋值给,at，,即,at=ax。,接下来的问题是如何确定每次出列者。,设,s,首先指向每次第一个报数者，,t,指向,s,时，,s,便指向它的后继，,t,再指向,s,时，,s,又指向它的后继，如此循环,m,次后，,t,便是当前出列者,x，s,便是下次开始报数者。,for i=1 to m do t=s;s=as;,这样就能够将每次出列者求出来，但是不便于实现上页所述的操作2。因此只要循环,m-1,次就两者都能兼顾了。此时的,t,正是当前出列者,x,的前驱。,