數(shù)據(jù)結(jié)構(gòu)練習(xí)試題和答案解析

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

2、算機(jī)的。 （×）10. 算法是對解題方法和步驟的描述。 （）二、填空題1. 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲結(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é)點以外，其余每個結(jié)點只有1個前驅(qū)結(jié)點。6. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以任意多個 。7. 數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu) 。8. 數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存?。9. 線性結(jié)構(gòu)中的元素之間存在一對一 的關(guān)系。10

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

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

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

6、存儲空間里，這種存儲結(jié)構(gòu)稱為（A）結(jié)構(gòu)。A順序結(jié)構(gòu) B鏈?zhǔn)浇Y(jié)構(gòu) C索引結(jié)構(gòu) D散列結(jié)構(gòu)9. 每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）。A順序 B鏈?zhǔn)?C索引 D散列10. 以下任何兩個結(jié)點之間都沒有邏輯關(guān)系的是（D）。A圖形結(jié)構(gòu) B線性結(jié)構(gòu) C樹形結(jié)構(gòu) D集合11. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是（C）。A物理結(jié)構(gòu) B存儲結(jié)構(gòu) C邏輯結(jié)構(gòu) D邏輯和存儲結(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)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（A）。A邏輯結(jié)構(gòu) B存儲結(jié)構(gòu) C

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

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

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

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

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

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

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

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

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

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

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

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

19、棧的輸入序列為：A，B，C，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時，表示 ?？?。3. 在有n個元素的棧中，進(jìn)棧操作時間復(fù)雜度為 O（1） 。4. 在棧中，出棧操作時間復(fù)雜度為 O（1） 。5. 已知表達(dá)式，求它的后綴表達(dá)式是 棧 的典型應(yīng)用。6. 在一個鏈棧中，若棧頂指針等于NULL，則表示 棧空 。7. 向一個棧頂指針為top的鏈棧插入一個新結(jié)點*p時，應(yīng)執(zhí)行p-&g

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

21、算。15. 鏈棧LS為空的條件是 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個元素A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S,x)運算后，x的值是 C 。三、選擇題1. 插入和刪除操作只能在一端進(jìn)行的線性表，稱為（ C ）。A隊列 B循環(huán)隊列 C棧 D循環(huán)棧2. 設(shè)有編號為1，2。3，4的4輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序為（ D）。A12

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

23、比較明顯的優(yōu)點是（ B ）。A. 插入操作更加方便 B.通常不會出現(xiàn)棧滿的情況 C.不會出現(xiàn)?？盏那闆r D.刪除操作更加方便9. 從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(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. 在一個棧頂指針為HS的鏈棧中，將一個S指針?biāo)傅慕Y(jié)點入棧，應(yīng)執(zhí)行下列（ B ）命令。A.HS->next=S B.S->next=HS->ne

24、xt;HS->next=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)運算后，棧頂元素的值是（ B ）。AA BB CC DD12. 元素A、B、C、D依次進(jìn)棧以后，棧底元素是（ A ）。AA BB CC DD13. 經(jīng)過下列棧的運算后，再執(zhí)行ReadTop(s)的值是（ A ）。InitStack(s);Push(s，a); Push(s，b);Pob(s);A. a B.b C.1 D.014. 經(jīng)過下列棧的運算后，x的值是（ B ）。InitS

25、tack(s)（初始化棧）; Push(s，a); Push(s，b); ReadTop(s) ；Pob(s，x);A. a B.b C.1 D.015. 經(jīng)過下列棧的運算后，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)過下列棧的運算后,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. 向順序棧中輸入元素時（ B

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

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

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

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

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

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

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

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

34、t;frontC.SQ->rear= =0 D.SQ->front= =015. 設(shè)鏈棧中結(jié)點的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點，則應(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é)點的鏈隊LQ示意圖如下，鏈隊列的隊頭元素是（A）。 LQ->frontH A B C D LQ->rear A

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

36、nitQueue(Q)(初始化隊列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；A.a B.b C.0 D.120.若用一個大小為6數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為（B）。A.5和1 B.4和2 C.2和4 D.1和5第5章 串一、判斷題1. 串是n個字母的有限序列。 （×）2. 串的數(shù)據(jù)元素是一個字符。 （）3. 串的長度是指串中不同字符的個數(shù)。 （×）4. 如果兩個串含有相同的字符，則說明它們相等。

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

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

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