答案《數(shù)據(jù)結(jié)構(gòu)》試卷

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

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

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

3、和出棧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)returnERROR;e=*

4、--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],1);for(j--;j>=1

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

6、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棧非空，則不可進(jìn)行插入操作returnERROR；}else{　　//S1棧不滿，則直接進(jìn)棧Push(S1,x);returnOK;}}8StatusDeQueue(DataType&x){if!StackEmpty(S2)

7、{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è)主串的長(zhǎng)度為m，模式串的長(zhǎng)度為n，則在主串中尋找模式的KMP算法的時(shí)間復(fù)雜性是多少？如果某一模式p=”abcaacabaca”，請(qǐng)給出它的next函數(shù)值及nextv

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