《答案《數(shù)據(jù)結(jié)構(gòu)》試卷》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、廈門大學(xué)《＿數(shù)據(jù)結(jié)構(gòu)＿》課程期中試卷信息科學(xué)與技術(shù)學(xué)院計算機科學(xué)系2003年級＿＿＿專業(yè)主考教師：＿＿＿＿試卷類型：（A卷/B卷）任選5題（（1，2），（3，4），（5，6），（7，8）中必須至少做一題），每題20分。一、試設(shè)計一個雙棧結(jié)構(gòu)，它有兩個端點end1和end2，滿足從end1端插入的表目只能從end1端被刪除，從end2端插入的表目只能從end2端被刪除，并給出指定端i（i=1，2）的進棧push(S,e,i)和出棧pop(S,e,i)操作的算法描述。再設(shè)計一個算法，它能夠?qū)⒁粋€有限長度的數(shù)據(jù)序列a1，a2

2、，…，an，按照下標(biāo)奇偶序號交替的方式將ai(1≤i≤n)分別從兩端入棧，然后將數(shù)據(jù)出棧以實現(xiàn)整個數(shù)據(jù)序列的倒排。該雙棧宜采用順序存儲、棧頂迎面增長的存儲方式，其形式定義如下：#defineSTACK_SIZE1000typedefstruct{SElemTypebase[STACK_SIZE];SElemType*top[3];//top[1]表示end1端的棧頂指針，top[2]表示end2端的棧頂指針//初始值分別為base和base+STACK_SIZE-1}DSqStack;指定端i（i=1，2）的進棧pus

3、h(S,e,i)和出棧pop(S,e,i)操作的算法描述如下：Statuspush(DSqStack&S,SElemTypee,inti){if(S.top[1]-S.top[2]==1)//棧滿exit(OVERFLOW);elseif(i==1)*S.top[1]++=e;elseif(i==2)*S.top[2]--=e;elsereturnERROR;returnOK;}Statuspop(DSqStack&S,SElemType&e,inti){if(i==1){if(S.top[1]==S.base)ret

4、urnERROR;e=*--S.top[1]=e;returnOK;}elseif(i==2){if(S.top[2]==S.base+STACK_SIZE-1)returnERROR;e=*++S.top[2];8returnOK;}elsereturnERROR;}基于上述結(jié)構(gòu)的數(shù)據(jù)序列的倒排算法描述如下：Statusresevers(DSqStack&S,SElemTypea[],intn){for(j=1;j<=n;j++)if(j%2==0)push(S,a[j-1],2);elsepush(S,a[j-1]

5、,1);for(j--;j>=1;j--)if(j%2==0)pop(S,a[n-j],2);elsepop(S,a[n-j],1);returnOK;}二、利用兩個棧S1、S2模擬一個隊列（如客戶隊列）時，如何用棧的運算實現(xiàn)隊列的插入、刪除運算。使用算法描述。解：利用兩個棧S1、S2模擬一個隊列（如客戶隊列）時，當(dāng)需要向隊列中輸入元素時，用S1來存放輸入元素，用push運算實現(xiàn)。當(dāng)需要從隊列中輸出元素時，到棧S2中去取，如果S2為空，則將S1中的元素全部送入到S2中，然后再從S2中輸出元素。判斷隊空的條件是：S1和S

6、2同時為空。StatusEnQueue(DataTypex){ifStackFull(S1){//S1棧滿ifStackEmpty(S2){//S1棧滿，S2?？誻hile(!StackEmpty(S1)){Pop(S1,y);Push(S2,y);//棧S1的內(nèi)容反向搬到棧S2Push(S1,x);returnOK;}else//S1棧滿，S2棧非空，則不可進行插入操作returnERROR；}else{　　//S1棧不滿，則直接進棧Push(S1,x);returnOK;}}8StatusDeQueue(DataT

7、ype&x){if!StackEmpty(S2){Pop(S2,x);returnOK;}else{if!StackEmpty(S1){while(!StackEmpty(S1)){Pop(S1,y);Push(S2,y);}//棧S1的內(nèi)容反向搬到棧S2Pop(S2,x);returnOK;}else//棧S1和S2都為空returnERROR;}}三、模式匹配算法是在主串中快速尋找模式的一種有效的方法。如果設(shè)主串的長度為m，模式串的長度為n，則在主串中尋找模式的KMP算法的時間復(fù)雜性是多少？如果某一模式p=”abc

8、aacabaca”，請給出它的next函數(shù)值及nextval函數(shù)值。解：在主串中尋找模式的KMP算法的時間復(fù)雜度是O（n+m）。模式p=”abcaacabaca”，它的next函數(shù)值及nextval函數(shù)值分別是：j1234567891011模式abcaacabacanext[j]01112212321nextval[j]01102