數(shù)據(jù)結(jié)構(gòu)作業(yè)

1、 第二次作業(yè) 一、選擇題 1、設(shè)有編號(hào)為 1, 2, 3, 4 的 4 輛列車，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，下列不可能的出棧順序?yàn)?D 。 A. 1234 B. 1243 C. 1324 D. 1423 2、4 個(gè)元素按 A, B, C, D 順序進(jìn)入 S 棧，執(zhí)行兩次 Pop(S, x)運(yùn)算后，棧頂元素的值是 B 。 A. A B. B C. C D. D 3、從一個(gè)棧頂指針為 top 的鏈棧中刪除一

2、個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列 A 命令。 A. x=top; top=top->next; B. top=top->next; x=top->data; C. x=top->data; D. x=top->data; top=top->next; 4、向順序棧中輸入元素時(shí) A 。 A. 先存入元素，后移動(dòng)棧頂指針 B. 先移動(dòng)棧頂指針，后存入元素 C

3、. 誰先誰后無關(guān)緊要 D. 同時(shí)進(jìn)行 5、設(shè)有一個(gè)順序棧，元素 A, B, C, D, E, F 依次進(jìn)棧，如果 6 個(gè)元素出棧的順序是 B, D, C, F, E, A，則棧的容量至少為 A 。 A. 3 B. 4 C. 5 6. 6 6、設(shè)已將元素 A, B, C 依次入棧，元素 D 正等待進(jìn)棧。那么下列 4 個(gè)序列中不可能出現(xiàn)的出棧順序?yàn)?A 。 A. CADB B. CBDA C. CDBA D

4、. DCBA 7、棧和隊(duì)列的相同之處是 C 。 A.元素的進(jìn)出滿足先進(jìn)后出 B.元素的進(jìn)出滿足后進(jìn)先出 C.只允許在端點(diǎn)進(jìn)行插入和刪除操作 D.無共同點(diǎn) 8、設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)為空,元素 e1，e2，e3，e4，e5 和 e6 依次通過棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列 Q,若 6 個(gè)元素出隊(duì)的序列是 e2，e4，e3，e6，e5，e1，則棧 S 的容量至少應(yīng)該是 B

5、 。 A. 6 B. 4 C. 3 D. 2 9、隊(duì)列通常采用的兩種存儲(chǔ)結(jié)構(gòu)是( A)。 A. 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) B.散列方式和索引方式 C. 鏈表存儲(chǔ)結(jié)構(gòu)和線性存儲(chǔ)結(jié)構(gòu) D.線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu) 10、循環(huán)隊(duì)列 SQ 隊(duì)滿的條件是 B 。 A. SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ-&

6、gt;front B. SQ->rear==0 D. SQ->front==0 11、若用一個(gè)大小為 6 的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 front 和 rear 的值分別為 3 和 0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front 和 rear 的值分別為 B 。 A. 5 和 1 B. 4 和 2 C. 2 和 4 D. 1 和 5 12、鏈棧與順序棧相比，有一個(gè)較為明顯的優(yōu)點(diǎn)是 A

7、 。 6、鏈隊(duì)列 LQ 為空時(shí)，LQ->front->next= rear . 7、在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為 front，隊(duì)尾指針為 rear，則判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為 front+1=rear 。 8、設(shè)串 S=“Ilikecomputer” ，T=“com” ，則 Length(S)= 13 。Index(S, T)= 6

8、 。 9、在 KMP 算法中，next[j]只與 子 串有關(guān)，而與 主串 無關(guān)。 10、字符串“ababaab“的 Next 數(shù)組值是 0112342 。 三、試編寫一個(gè)整數(shù)進(jìn)制轉(zhuǎn)換的通用函數(shù) convert(int num, STACK S, int n)，要求將整數(shù) m轉(zhuǎn)換為 n 進(jìn)制數(shù)，n 進(jìn)制數(shù)的各位依次存放在棧 S 中。并在主函數(shù)中進(jìn)行測(cè)試。 要求：1、定義棧以及棧的型。

9、2、定義棧的各種操作。 3、實(shí)現(xiàn)函數(shù) convert。 4、在 main 函數(shù)中，通過調(diào)用函數(shù) convert 將 num 的 n 進(jìn)制數(shù)存放到一個(gè)棧中，并通過出棧的方法輸出該 n 進(jìn)制數(shù) #include using namespace std; #define maxlength 100 typedef int Elementtype; struct STACK { int top; Elementtype element

10、s[maxlength]; }; void MakeNull( STACK } bool Empty( STACK S ) { if ( S.top < 1 ) return true; else return false; } void error( string s ) { cout << s << endl; system(“pause“); } Elementtype Top

11、( STACK S ) { if( Empty( S ) ){ error ( “棧為空“ ) ; return -1; } else return ( S.elements[ S.top ] ); } void Pop( STACK else S.top = S.top-1 ; } void Push( Elementtype x, STACK else { S.top = S.top + 1 ; S.elemen