順序存儲結(jié)構(gòu)的線性表-習(xí)題

《順序存儲結(jié)構(gòu)的線性表-習(xí)題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章順序存儲結(jié)構(gòu)的線性表習(xí)題課選擇題1、一個順序表的首元存儲地址是100，每個元素的長度為2，則第5個元素的地址是____。A110B108C112D1202、一個棧的入棧序列為a,b,c,d,e，則棧的不可能的輸出序列是____。AedcbaBdecbaCdceabDabcde3、若已知一個棧的入棧序列是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,15、判定一

2、個容量為m的隊列為空的條件是_____。Arear-front=mBfront-rear=mCrear-front-1=mDfront-rear-1=mErear=frontFrear=front-16、棧和隊列的共同點是_____。A、都是先進后出B、都是先進先出C、只允許在端點處插入和刪除元素D、沒有共同點填空題1、向量、棧和隊列都是____結(jié)構(gòu)，可以在向量的__位置插入和刪除元素；對于棧只能在__插入和刪除元素；對于隊列只能在___插入元素和___刪除元素。2、向一個長度為n的向量的第i(0

3、一個長度為n的向量中刪除第i(0=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;}

4、END第二題試寫出在順序存儲結(jié)構(gòu)下逆轉(zhuǎn)線性表的算法，要求使用最少的附加空間。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)ET

5、a[],ETb[],intm,intni=1;j=1;k=1;While(i<=mandj<=n)doIf(a[i]

6、出列為止。請寫出算法求出n個人的出列順序。分析設(shè)以自然數(shù)1,2,3,…,n為元素構(gòu)成一個循環(huán)隊列，并用一個數(shù)組a存放該隊列中每個元素的直接后繼，其中a[i]表示i的后繼。顯然該數(shù)組初始化時應(yīng)該這樣：a[i]=i+1,i=1,2,…,n-1a[n]=1;設(shè)x為當(dāng)前所求的出列者(序號)，它的前驅(qū)為t，則有a[t]=x，而且x的后繼為a[x]，則當(dāng)前的隊列為……,t,x,a[x],……當(dāng)x出列后，隊列變?yōu)椤?t,a[x],……顯然，此時t的后繼已變?yōu)閍[x]。由此可見，當(dāng)x出列時，只需作以下兩個操作：1、將所求到的x存入另一個數(shù)組b。2、a[x]賦值給a[t]，即a[t]

7、=a[x]。接下來的問題是如何確定每次出列者。設(shè)s首先指向每次第一個報數(shù)者，t指向s時，s便指向它的后繼，t再指向s時，s又指向它的后繼，如此循環(huán)m次后，t便是當(dāng)前出列者x，s便是下次開始報數(shù)者。fori=1tomdo{t=s;s=a[s];}這樣就能夠?qū)⒚看纬隽姓咔蟪鰜恚遣槐阌趯崿F(xiàn)上頁所述的操作2。因此只要循環(huán)m-1次就兩者都能兼顧了。此時的t正是當(dāng)前出列者x的前驅(qū)。