數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、第1章 緒論一、 判斷題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。 （）2. 一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。 （）3. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （×）4. 數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。 （×）5. 程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。 （×）6. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 （）7. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映象。 （）8. 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。 （）9. 數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。 （×）

2、10. 算法是對(duì)解題方法和步驟的描述。 （）二、填空題1. 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲(chǔ)結(jié)構(gòu) 兩種結(jié)構(gòu)。2. 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu) 。3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu) 。4. 樹形結(jié)構(gòu) 和圖形結(jié)構(gòu) 合稱為非線性結(jié)構(gòu)。5. 在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)結(jié)點(diǎn)。6. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以任意多個(gè) 。7. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu) 。8. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ) 。9. 線性結(jié)構(gòu)中的元素之間存在一對(duì)一 的關(guān)系。10. 樹形結(jié)構(gòu)中的元素之間存

3、在一對(duì)多 的關(guān)系。11. 圖形結(jié)構(gòu)的元素之間存在多對(duì)多 的關(guān)系。12. 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法（或運(yùn)算） 3個(gè)方面的內(nèi)容。13. 數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系 有限集合。14. 算法是一個(gè)有窮指令 的集合。15. 算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法 。16. 一個(gè)算法的時(shí)間復(fù)雜度是算法 輸入規(guī)模 的函數(shù)。17. 算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲(chǔ)空間 ，它是該算法求解問題規(guī)模的n的函數(shù)。18. 若一個(gè)算法中的語句頻度之和為T(n)=6n+3nlog2n,則算法的時(shí)間復(fù)雜度為O（ nlog2n） 。19. 若一個(gè)算法的語

4、句頻度之和為T(n)=3n+nlog2+n2,則算法的時(shí)間復(fù)雜度為O（n2） 。20. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序問題中計(jì)算機(jī)的操作對(duì)象，以及它們之間的關(guān)系和運(yùn)算的學(xué)科。三、選擇題1. 數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互關(guān)系。A存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu) B存儲(chǔ)和抽象 C聯(lián)系和抽象 D聯(lián)系與邏輯2. 在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)。3. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。A存儲(chǔ)結(jié)構(gòu) B邏輯結(jié)構(gòu) C順序存儲(chǔ)結(jié)構(gòu) D鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4. 非線性結(jié)構(gòu)中的每個(gè)

5、結(jié)點(diǎn)（D）。A無直接前驅(qū)結(jié)點(diǎn) B無直接后繼結(jié)點(diǎn)C只有一個(gè)直接前驅(qū)結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)D可能有多個(gè)直接前驅(qū)結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)5. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（A）。A分兩部分，一部分存放結(jié)點(diǎn)的值，另一個(gè)部分存放表示結(jié)點(diǎn)間關(guān)系的指針。B只有一部分，存放結(jié)點(diǎn)的值。 C只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針。D分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放結(jié)點(diǎn)所占單元素6. 算法的計(jì)算量大小稱為算法的（C）。A現(xiàn)實(shí)性 B難度 C時(shí)間復(fù)雜性 D效率7. 數(shù)據(jù)的基本單位（B）。A數(shù)據(jù)結(jié)構(gòu) B數(shù)據(jù)元素 C數(shù)據(jù)項(xiàng) D文件8. 每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間里，這種存儲(chǔ)結(jié)構(gòu)稱

6、為（A）結(jié)構(gòu)。A順序結(jié)構(gòu) B鏈?zhǔn)浇Y(jié)構(gòu) C索引結(jié)構(gòu) D散列結(jié)構(gòu)9. 每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是（B）。A順序 B鏈?zhǔn)?C索引 D散列10. 以下任何兩個(gè)結(jié)點(diǎn)之間都沒有邏輯關(guān)系的是（D）。A圖形結(jié)構(gòu) B線性結(jié)構(gòu) C樹形結(jié)構(gòu) D集合11. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是（C）。A物理結(jié)構(gòu) B存儲(chǔ)結(jié)構(gòu) C邏輯結(jié)構(gòu) D邏輯和存儲(chǔ)結(jié)構(gòu)12. 下列4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（A）。A集合 B線性結(jié)構(gòu) C樹形結(jié)構(gòu) D圖形結(jié)構(gòu)13. 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的（A）。A邏輯結(jié)構(gòu) B存儲(chǔ)結(jié)構(gòu) C邏輯實(shí)現(xiàn) D存儲(chǔ)實(shí)現(xiàn)14.

7、 每一個(gè)存儲(chǔ)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，存儲(chǔ)結(jié)點(diǎn)存放在連續(xù)的存儲(chǔ)空間，另外有一組指明結(jié)點(diǎn)存儲(chǔ)位置的表，該存儲(chǔ)方式是（C）存儲(chǔ)方式。A順序 B鏈?zhǔn)?C索引 D散列 15. 算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（A）。A正確性 B易讀性 C健壯性 D高效性16. 算法在發(fā)生非法操作時(shí)可以作出相應(yīng)處理的特性稱為算法的（C）。A正確性 B易讀性 C健壯性 D高效性17. 下列時(shí)間復(fù)雜度中最壞的是（D）。AO（1） B.O（n） C.O( log2n) D.O(n2)18. 下列算法的時(shí)間復(fù)雜度是（D）。for(i=0;i<n;i+)for(j=o;i<n;j+) cij=i+j;AO（1）

8、 B.O（n） C.( log2n) D.O(n2)19. 算法分析的兩個(gè)主要方面是（A）。A.空間復(fù)雜性和時(shí)間復(fù)雜性 B.正確性和簡(jiǎn)明性 C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性20. 計(jì)算機(jī)算法必須具備輸入、輸出和（C）。A.計(jì)算方法 B.排序方法 C.解決問題的有限運(yùn)算步驟D.程序設(shè)計(jì)方法 第2章 線性表一、判斷題1. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。 （×）2. 鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。 （×）3. 在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。 （）4. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。 （×

9、;）5. 線性鏈表的刪除算法簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。 （×）6. 順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 （×）7. 線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。 （）8. 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 （）9. 順序表結(jié)構(gòu)適宜進(jìn)行順序存取，而鏈表適宜進(jìn)行隨機(jī)存取。 （×）10. 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中是最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。（×）二、填空題1. 順序表中邏輯上相鄰的元素在物理位置上必須相鄰。2.

10、線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一關(guān)系。3. 順序表相對(duì)于鏈表的優(yōu)點(diǎn)是節(jié)省存儲(chǔ)和隨機(jī)存取。4. 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便。5. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的元素時(shí)，應(yīng)采用 順序 存儲(chǔ)結(jié)構(gòu)。6. 順序表中訪問任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O（1）。7. 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度小。8. 在雙向鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，其時(shí)間復(fù)雜度為O（1）。9. 在單向鏈表中要在已知結(jié)點(diǎn)*P之前插入一個(gè)新結(jié)點(diǎn)，需找到*P的直接前驅(qū)結(jié)點(diǎn)的地址，其查找的時(shí)間復(fù)雜度為O(n)。10. 在單向鏈表中需知道頭指

11、針才能遍歷整個(gè)鏈表。11. 線性表中第一個(gè)結(jié)點(diǎn)沒有直接前驅(qū)，稱為開始結(jié)點(diǎn)。12. 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，要移動(dòng) n-i 個(gè)元素。13. 在一個(gè)長(zhǎng)度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移 n-i+1 個(gè)元素。14. 在無頭結(jié)點(diǎn)的單向鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其他結(jié)點(diǎn)的存儲(chǔ)地址存放在 前趨 結(jié)點(diǎn)的指針域中。15. 線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)行插入和刪除操作，應(yīng)采用 鏈子 存儲(chǔ)結(jié)構(gòu)。16. 在線性表中的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過 指針 決定。17. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其 前趨 結(jié)點(diǎn)，另一個(gè)指向其后

12、繼結(jié)點(diǎn)。18. 對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用 鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)為宜。19. 雙向鏈表中，設(shè)P是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為p->prior->next=p->next；p->next->prior=p->prior 20. 在如圖所示的鏈表中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個(gè)結(jié)點(diǎn)，則可用語句S->next->next=p->next和P-> next=S；來實(shí)現(xiàn)該操作。 p a b s三、 選擇題1. 在具有n個(gè)結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)（ A）的操作，其算法的時(shí)間復(fù)雜度都是O(n). A.遍

13、歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn) B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.刪除開始結(jié)點(diǎn) D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)2. 設(shè)a、b、c為3個(gè)結(jié)點(diǎn)，p、10、20分別代表它們的地址，則如下的存儲(chǔ)結(jié)構(gòu)稱為（ B ）。 p a 10 b 20 c A循環(huán)鏈表 B單向鏈表 C雙向循環(huán)鏈表 D雙向鏈表3. 單向鏈表的存儲(chǔ)密度（ C ）。A.大于1 B.等于1 C.小于1 D.不能確定4. 已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為B，則第i個(gè)結(jié)點(diǎn)的地址為（ A ）。A.B+(i-1)×m B.B+i×m C.B-i×m D.B+(i+1)

14、5;m5. 在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為（ B ）。AO（1） B.O（n） C. O(n2) D.O( log2n)6. 設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（ D ）。A.P= =L B.P->front= =L C.P= =NULL D.P->rear= =L7. 兩個(gè)指針P和Q，分別指向單向鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是（ B ） AP->next= =Q->next B.P->next= =Q C.Q->next= =P D.P

15、=Q8. 用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是（ C ）。 A便于隨機(jī)存取 B花費(fèi)的存儲(chǔ)空間比順序表少C便于插入和刪除 D數(shù)據(jù)元素的物理順序與邏輯順序相同9. 在單鏈表中，增加頭結(jié)點(diǎn)的目的是（ C ）。 A使單鏈表至少有一個(gè)結(jié)點(diǎn) B標(biāo)志表中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn) D說明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)10. 下面關(guān)于線性表的敘述中，錯(cuò)誤的是（ D ）關(guān)系。 A順序表必須占一片地址連續(xù)的存儲(chǔ)單元B順序表可以隨機(jī)存取任一元素C鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元D鏈表可以隨機(jī)存取任一元素11. L是線性表，已知LengthList(L)的值是5，經(jīng)DelList(L，2)運(yùn)算后，LengthList(L

16、)的值是（ C ）。 A2 B3 C4 D512. 單向鏈表的示意圖如下： L A B C D P Q R指向鏈表Q結(jié)點(diǎn)的前驅(qū)的指針是（ B ）。AL BP CQ DR13. 設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，則*p的直接前驅(qū)（ C ）。A找不到 B查找時(shí)間復(fù)雜度為O（1） C查找時(shí)間復(fù)雜度為O（n）D查找結(jié)點(diǎn)的次數(shù)約為n14. 等概率情況下，在有n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為（ 8 ）。An B.(n-1)/2 C.n/2 D.(n+1)/215. 在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是（ C ）。A.雙向鏈表 B.單循環(huán)鏈表 C.單向鏈表 D.雙向循

17、環(huán)鏈表16. 在順序表中，只要知道（ D ），就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A.基地址 B.結(jié)點(diǎn)大小 C.向量大小 D.基地址和結(jié)點(diǎn)大小17. 在雙向鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為（ A ）。AO（1） B.O（n） C. O(n2) D.O( log2n)18. 鏈表不具備的特點(diǎn)是（ A ）。A隨機(jī)訪問 B.不必事先估計(jì)存儲(chǔ)空間C. 插入刪除時(shí)不需要移動(dòng)元素 D.所需空間與線性表成正比19. 以下關(guān)于線性表的論述，不正確的為（ C ）。A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型B.線性順序表中包含的元素個(gè)數(shù)不是任意的C.線性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼D.存在這

18、樣的線性表，即表中沒有任何結(jié)點(diǎn)20. 在（ B ）的運(yùn)算中，使用順序表比鏈表好。A.插入 B.根據(jù)序號(hào)查找 C.刪除 D.根據(jù)元素查找第3章 棧一、 判斷題1. 棧是運(yùn)算受限制的線性表。 （）2. 在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生下溢。 （）3. 棧一定是順序存儲(chǔ)的線性結(jié)構(gòu)。 （×）4. 棧的特點(diǎn)是“后進(jìn)先出”。 （）5. 空棧就是所有元素都為0的棧。 （×）6. 在C（或C+）語言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN時(shí)表示棧滿。 （×）7. 鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況。 （）8. 一個(gè)棧的輸入序列為：A，B，C

19、，D，可以得到輸出序列：C，A，B，D。 （×）9. 遞歸定義就是循環(huán)定義。 （×）10. 將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。 （）二、填空題1. 在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為 棧頂 。2. 在順序棧中，當(dāng)棧頂指針top=-1時(shí)，表示 ?？?。3. 在有n個(gè)元素的棧中，進(jìn)棧操作時(shí)間復(fù)雜度為 O（1） 。4. 在棧中，出棧操作時(shí)間復(fù)雜度為 O（1） 。5. 已知表達(dá)式，求它的后綴表達(dá)式是 棧 的典型應(yīng)用。6. 在一個(gè)鏈棧中，若棧頂指針等于NULL，則表示 棧空 。7. 向一個(gè)棧頂指針為top的鏈棧插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行p->next=top;to

20、p=p；操作。8. 順序棧S存儲(chǔ)在數(shù)組S->data0MAXLEN-1中，進(jìn)棧操作時(shí)要執(zhí)行的語句有：S->top+。(或S->top+1)S->dataS->top=x9. 鏈棧LS，指向棧頂元素的指針是LS->next。10. 從一個(gè)棧刪除元素時(shí)，首先取出 棧頂元素 ，然后再移動(dòng)棧頂指針。11. 由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒有必要設(shè)置 頭 結(jié)點(diǎn)。12. 已知順序棧S，在對(duì)S進(jìn)棧操作之前首先要判斷 棧是否滿 。13. 已知順序棧S，在對(duì)S出棧操作之前首先要判斷 棧是否空 。14. 若內(nèi)在空間充足， 鏈 ?？梢圆欢x棧滿運(yùn)算。15. 鏈棧LS為空的

21、條件是 LS->next=NULL 。16. 鏈棧LS的棧頂元素是鏈表的 首 元素。17. 同一棧的各元素的類型 相同 。18. 若進(jìn)棧的次序是A、B、C、D、E，執(zhí)行3次出棧操作以后，棧頂元素為 B 。19. A+B/C-D*E的后綴表達(dá)式是 ABC/+DE*- 。20. 4個(gè)元素A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S,x)運(yùn)算后，x的值是 C 。三、選擇題1. 插入和刪除操作只能在一端進(jìn)行的線性表，稱為（ C ）。A隊(duì)列 B循環(huán)隊(duì)列 C棧 D循環(huán)棧2. 設(shè)有編號(hào)為1，2。3，4的4輛列車，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，下列不可能的出站順序?yàn)椋?D）。A1234 B1243 C132

22、4 D14233. 如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)（ B ）。A必須判別棧是否滿 B必須判別棧是否為空 C必須判別棧元素類型 D棧可不做任何判別4. 元素A、B、C、D依次進(jìn)棧以后，棧頂元素是（ D ）AA BB CC DD5. 順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（ B ）存儲(chǔ)元素。A鏈表 B數(shù)組 C循環(huán)鏈表 D變量6. 在C（或C+）語言中，一個(gè)順序棧一旦被聲明，其占用空間的大?。?A ）。A已固定 B不固定 C可以改變 D動(dòng)態(tài)變化7. 帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是（ A ）。LSH A B C D AA BB CC DD8. 鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是（ B ）

23、。A. 插入操作更加方便 B.通常不會(huì)出現(xiàn)棧滿的情況 C.不會(huì)出現(xiàn)?？盏那闆r D.刪除操作更加方便9. 從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列（d ）命令。Ax=top;top->next; B.top=top->next;x=top->dataC.x=top->data; D.x=top->data;top=top->next10. 在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列（ B ）命令。A.HS->next=S B.S->next=HS->next;HS->nex

24、t=S;C.S->next=HS->next;HS=S; D.S->next=HS=HS->next11. 4元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S，x)運(yùn)算后，棧頂元素的值是（ B ）。AA BB CC DD12. 元素A、B、C、D依次進(jìn)棧以后，棧底元素是（ A ）。AA BB CC DD13. 經(jīng)過下列棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是（ A ）。InitStack(s);Push(s，a); Push(s，b);Pob(s);A. a B.b C.1 D.014. 經(jīng)過下列棧的運(yùn)算后，x的值是（ B ）。InitStack(s)（初始化棧）

25、; Push(s，a); Push(s，b); ReadTop(s) ；Pob(s，x);A. a B.b C.1 D.015. 經(jīng)過下列棧的運(yùn)算后，x的值是（ B ）。InitStack(s)（初始化棧）; Push(s,a); Pob(s，x); Push(s,b); Pob(s，x);A.a B.b C.1 D.016. 經(jīng)過下列棧的運(yùn)算后,SEmpty(s)的值是（ C ）。InitStack(s)（初始化棧）; Push(s,a); Push(s,b); Pob(s，x); Pob(s，x);A.a B.b C.1 D.017. 向順序棧中輸入元素時(shí)（ B ）。A先存入元素，后移動(dòng)棧

26、頂指針 B先移動(dòng)棧頂指針，后存入元素C誰先誰后無關(guān)緊要 D同時(shí)進(jìn)行18. 初始化一個(gè)空間大小為5的順序棧S后，S->top的值是（ B ）。A0 B-1 C不再改變 D動(dòng)態(tài)變化19. 設(shè)有一個(gè)入棧的次序A、B、C、D、E，則棧不可能的輸出序列是（ C ）。AEDCBA BDECBA CDCEAB DABCDE20. 設(shè)有一個(gè)順序棧S，元素A、B、C、D、E、F依次進(jìn)棧，如果6個(gè)元素出棧的順序是B、D、C、F、E、A，則棧的容量至少應(yīng)是（ A ）。A3 B4 C5 D6第4章 隊(duì)列一、判斷題1. 隊(duì)列是限制在兩端進(jìn)行操作的線性表。 （）2. 判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一

27、個(gè)結(jié)點(diǎn)。 （）3. 在鏈隊(duì)列上做出隊(duì)操作時(shí)，會(huì)改變front指針的值。 （×）4. 在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front，其元素個(gè)數(shù)為rear-front。 （）5. 在單向循環(huán)鏈表中，若頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h。 （×）6. 鏈隊(duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)隊(duì)滿的情況。 （）7. 在循環(huán)鏈隊(duì)列中無溢出現(xiàn)象。 （×）8. 棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(gòu)。 （×）9. 在隊(duì)列中允許刪除的一端稱為隊(duì)尾。 （×）10. 順序隊(duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的。 （×）二、填空題1. 在隊(duì)列中存取數(shù)據(jù)應(yīng)

28、遵循的原則是 先進(jìn)先出 。2. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算線性表。3. 在隊(duì)列中，允許插入的一端稱為 隊(duì)尾 。4. 在隊(duì)列中，允許刪除的一端稱為 隊(duì)首（或隊(duì)頭） 。5. 隊(duì)列在進(jìn)行出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為 空 。6. 順序隊(duì)列在進(jìn)行入隊(duì)操作時(shí)，首先在判斷隊(duì)列是否為 滿 。7. 順序隊(duì)列初始化后，初始化后，front=rear= -1 。8. 解決順序隊(duì)列“假溢出”的方法是采用 循環(huán)隊(duì)列 。9. 循環(huán)隊(duì)列的隊(duì)指針為front，隊(duì)尾指針為rear，則隊(duì)空的條件為 front= =rear 。10. 鏈隊(duì)列LQ為空時(shí)，LQ->front->

29、;next= NULL 。11. 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為 O(n) 。12. 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)尾指針，則入隊(duì)操作的時(shí)間復(fù)雜度為 O(1) 。13. 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為 空 。14. 設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)滿標(biāo)志為 front= =(rear+1)%MAXLEN 。15. 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為front，隊(duì)尾指針為rear，則判斷隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為front= =rear

30、或front!。16. 向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要判斷 隊(duì)尾指針 ，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。17. 讀隊(duì)首元素的操作 不改變或不影響隊(duì)列元素的個(gè)數(shù)。18. 設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)039），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=11，rear=19，則循環(huán)隊(duì)列中還有 8 個(gè)元素。19. 隊(duì)列Q，經(jīng)過下列運(yùn)算：InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；QEmpty(Q)；后的值是 8 。20. 隊(duì)列Q經(jīng)過InitQueue(Q)(初始化隊(duì)列)；InQueue

31、(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x的值是 a 。三、選擇題1. 隊(duì)列是限定在（D）進(jìn)行操作的線性表。A中間者 B.隊(duì)首 C.隊(duì)尾 D.端點(diǎn)2. 隊(duì)列中的元素個(gè)數(shù)是（B）。A不變的 B.可變的 C.任意的 D.03. 同一隊(duì)列內(nèi)的各元素的類型（A）。A.必須一致 B.不能一致 C.可以不一致 D.不限制4. 隊(duì)列是一個(gè)（C）線性表結(jié)構(gòu)。A.不加限制的 B.推廣了的 C.加了限制的 D.非5. 當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元素的下標(biāo)為（B）。A.n-2 B.n-1 C.n D.n+16. 一個(gè)循環(huán)隊(duì)列一旦說明，其占用空間的大小（A）

32、。A.已固定 B.可以變動(dòng) C.不能固定 D.動(dòng)態(tài)變化7. 循環(huán)隊(duì)列占用的空間（A）。A.必須連續(xù) B.不必連續(xù) C.不能連續(xù) D.可以不連續(xù)8. 存放循環(huán)隊(duì)列元素的數(shù)組data有10個(gè)元素，則data數(shù)組的下標(biāo)范圍是（B）。A.010 B.09 C.19 D.1109. 若進(jìn)隊(duì)的序列為A、B、C、D，則出隊(duì)的序列是（C）。A.B、C、D、A B.A、C、B、D C.A、B、C、D D.C、B、D、A10. 4個(gè)元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，則隊(duì)尾元素是（D）AA BB CC DD11. 4個(gè)元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行一次QutQueue(Q)操作后，隊(duì)頭元素是（B）。A.

33、A B.B C.C D.D12. 4個(gè)元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行4次QutQueue(Q)操作后，再執(zhí)行QEmpty(Q)；后的值是（B）。A.0 B.1 C.2 D.313. 隊(duì)列Q，經(jīng)過下列運(yùn)算后，x的值是（B）。InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；A.a B.b C.0 D.114. 循環(huán)隊(duì)列SQ隊(duì)滿的條件是（B）。A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->frontC.SQ-&

34、gt;rear= =0 D.SQ->front= =015. 設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一個(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（A）操作。A.s->next=top->next;top->next=s; B.top->next=s;C.s->next=top;top->next; D.s->next=top;top=s;16. 帶頭結(jié)點(diǎn)的鏈隊(duì)LQ示意圖如下，鏈隊(duì)列的隊(duì)頭元素是（A）。LQ->frontH A B C D LQ->rear AA BB CC DD 17.

35、 帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，指向鏈隊(duì)列的隊(duì)頭指針是（C）。LQ->frontH A B C D LQ->rearA.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next18. 帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下,在進(jìn)行進(jìn)隊(duì)的運(yùn)算時(shí)指針LQ->frnot(A).LQ->frontH A B C D LQ->rear A.始終不改變 B.有時(shí)改變 C.進(jìn)隊(duì)時(shí)改變 D.出隊(duì)時(shí)改變19.隊(duì)列Q，經(jīng)過下列運(yùn)算后，再執(zhí)行QEmpty(Q)的值是（C）。InitQueue(Q)(初始

36、化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；A.a B.b C.0 D.120.若用一個(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第5章 串一、判斷題1. 串是n個(gè)字母的有限序列。 （×）2. 串的數(shù)據(jù)元素是一個(gè)字符。 （）3. 串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。 （×）4. 如果兩個(gè)串含有相同的字符，則說明它們相等。 （×）5. 如果一

37、個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說明前者是后者的子串。 （×）6. 串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。 （）7. “DT”是“DATA”的子串。 （×）8. 串中任意個(gè)字符組成的子序列稱為該串的子串。 （×）9. 子串的定位運(yùn)算稱為模式匹配。 （）10. 在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。 （）二、填空題1. 由零個(gè)或多個(gè)字符組成的有限序列稱為 字符串（或串） 。2. 字符串按存儲(chǔ)方式可以分為順序存儲(chǔ)、鏈接存儲(chǔ)和 堆分配存儲(chǔ) 。3. 串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為 順序串 。4. 串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是 空間利用率低 。5. 串順序存儲(chǔ)緊湊格式的缺

38、點(diǎn)是對(duì)串的字符處理 效率低 。6. 串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是 空間利用率 。7. 在C或C+語言中，以字符 0 表示串值的終結(jié)。8. 空格串的長(zhǎng)度等于 空格的個(gè)數(shù) 。9. 在空串和空格串中，長(zhǎng)度不為0的是 空格串 。10. 兩個(gè)串相等是指兩個(gè)串長(zhǎng)度相等，且對(duì)應(yīng)位置的 字符都相同 。11. 設(shè)“S=My Music”，則LenStr(s)= 8 。12. 兩個(gè)字符串分別為；S1=”Today is”、S2=”30 July，2005”，ConcatStr(S1，S2)的結(jié)果是 Today is 30 July,2005 。13. 求子串函數(shù)SubStr(“Today is 30

39、July，2005”，13，4)的結(jié)果是 July 。14. 在串的運(yùn)算中，EqualStr(aaa,aab)的返回值 <0 。15. 在串的運(yùn)算中，EqualStr(aaa,aaa)的返回值 0 。 16. 在子串的定位運(yùn)算中，被匹配的主串稱為目標(biāo)串，子串稱為 模式 。17. 模式匹配成功的起始位置稱為 有效位移 。18. 設(shè)S=”abccdcdccbaa”，T=”cdcc”，則第 6 次匹配成功。19. 設(shè)S=”c:/mydocument/text1.doc”，T=”mydont”，則字符定位的位置為 0 。20. 若n為主串長(zhǎng)度，m為子串長(zhǎng)度，n>>m，則模式匹配算法最壞情況下的時(shí)間復(fù)雜度為 (n-m+1)*m 。三、選擇題 1. 串是和種特殊的線性表，其特殊體現(xiàn)在（B）。A可能順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符C可以鏈接存儲(chǔ) D數(shù)據(jù)元素可以是多個(gè)字符2. 某串的長(zhǎng)度小于一常數(shù)，則采用（B）存儲(chǔ)方式最節(jié)省空間。A鏈?zhǔn)?B順序 C堆結(jié)構(gòu) D無法確定3. 以下論述正確的是（C）。A空串與空格串是相同的B”tel”是