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

第二章顺序存储结构的线性表习题课选择题1、一个顺序表的首元存储地址是100，每个元素的长度为2，则第5个元素的地址是____。A110B108C112D1202、一个栈的入栈序列为a,b,c,d,e，则栈的不可能的输出序列是____。AedcbaBdecbaCdceabDabcde3、若已知一个栈的入栈序列是1,2,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi=_____。AiBn-iCn-i+1D不能确定4、一个队列的入队序列为1，2，3，4，则其输出序列可能是____。A4,3,2,1B1,2,3,4C1,4,2,3D3,2,4,15、判定一个容量为m的队列为空的条件是_____。Arear-front=mBfront-rear=mCrear-front-1=mDfront-rear-1=mErear=frontFrear=front-16、栈和队列的共同点是_____。A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点填空题1、向量、栈和队列都是____结构，可以在向量的__位置插入和删除元素；对于栈只能在__插入和删除元素；对于队列只能在___插入元素和___删除元素。2、向一个长度为n的向量的第i(0in+2)个元素之前插入一个元素时，需向后移动____个元素。3、向一个长度为n的向量中删除第i(0in+2)个元素时，需向前移动____个元素。4、一个栈的输入序列是12345，如果栈的输出序列43512是_____。5、一个栈的输入序列是12345，如果栈的输出序列12345是_____。算法编写题1、已知一个顺序表按元素值的升序排列，编写一个算法：插入一个元素后保持该顺序表是有序的。PROCEDUREInsert(ETa[],intn,intx)If(x=a[n])a[n+1]=x;Else{inti=1;while(x=a[i])doi=i+1;forj=ntoidoa[j+1]=a[j];a[i]=x;n=n+1;}END第二题试写出在顺序存储结构下逆转线性表的算法，要求使用最少的附加空间。PROCEDUREnizhuan(ETa[],intn)Fork=1ton/2do{t=a[k];a[k]=a[n-k+1];a[n-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}PROCEDUREhebing(a[],b[],m,n)ETa[],ETb[],intm,intni=1;j=1;k=1;While(i=mandj=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)fort=(i+1)tomdo{c[k]=a[t];k=k+1}If(i=m)fort=(j+1)tondo{c[k]=b[t];k=k+1;}第四题设有n个人围成一圈，每个人的编号依次为1,2,3,…,n。现从编号为k的人开始报数，数到m的人便出列，接着从出列的下一个人开始重新报数，数到m的人又出列，以此类推，直到所有的人都出列为止。请写出算法求出n个人的出列顺序。分析设以自然数1,2,3,…,n为元素构成一个循环队列，并用一个数组a存放该队列中每个元素的直接后继，其中a[i]表示i的后继。显然该数组初始化时应该这样：a[i]=i+1,i=1,2,…,n-1a[n]=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便是下次开始报数者。fori=1tomdo{t=s;s=a[s];}这样就能够将每次出列者求出来，但是不便于实现上页所述的操作2。因此只要循环m-1次就两者都能兼顾了。此时的t正是当前出列者x的前驱。