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

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