數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案.doc

《數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案.doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案.doc（48頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第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)上的一個基本運(yùn)算集構(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)實(shí)際的存儲形式。 （）9. 數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機(jī)的。 （）10. 算法是對解題方法和步驟的描述。 （）二、

2、填空題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é)點(diǎn)以外，其余每個結(jié)點(diǎn)只有1個前驅(qū)結(jié)點(diǎn)。6. 在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(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. 樹形結(jié)構(gòu)中的元素之間存在一對多 的關(guān)系。11. 圖形結(jié)構(gòu)的元素之間存在

3、多對多 的關(guān)系。12. 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法（或運(yùn)算） 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ù)雜度是指該算法所耗費(fèi)的存儲空間 ，它是該算法求解問題規(guī)模的n的函數(shù)。18. 若一個算法中的語句頻度之和為T(n)=6n+3nlog2n,則算法的時間復(fù)雜度為O（ nlog2n） 。19. 若一個算法的語句頻度之和為T(n)=3n+nlog2+n2,則

4、算法的時間復(fù)雜度為O（n2） 。20. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序問題中計算機(jī)的操作對象，以及它們之間的關(guān)系和運(yù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é)構(gòu)4. 非線性結(jié)構(gòu)中的每個結(jié)點(diǎn)（D）。A無直接前驅(qū)結(jié)點(diǎn) B無直接后繼結(jié)點(diǎn)C

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

6、 D散列結(jié)構(gòu)9. 每一個存儲結(jié)點(diǎn)不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）。A順序 B鏈?zhǔn)?C索引 D散列10. 以下任何兩個結(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ī)無關(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邏輯實(shí)現(xiàn) D存儲實(shí)現(xiàn)14. 每一個存儲結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，存儲結(jié)點(diǎn)存放

7、在連續(xù)的存儲空間，另外有一組指明結(jié)點(diǎn)存儲位置的表，該存儲方式是（C）存儲方式。A順序 B鏈?zhǔn)?C索引 D散列 15. 算法能正確的實(shí)現(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;in;i+)for(j=o;iprior-next=p-next；p-next-prior=p-prior 20. 在如圖所示的鏈表

8、中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個結(jié)點(diǎn)，則可用語句S-next-next=p-next和P- next=S；來實(shí)現(xiàn)該操作。 p a b s三、 選擇題1. 在具有n個結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)（ A）的操作，其算法的時間復(fù)雜度都是O(n). A.遍歷鏈表或求鏈表的第i個結(jié)點(diǎn) B.在地址為P的結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)C.刪除開始結(jié)點(diǎn) D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)2. 設(shè)a、b、c為3個結(jié)點(diǎn)，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

9、 B.等于1 C.小于1 D.不能確定4. 已知一個順序存儲的線性表，設(shè)每個結(jié)點(diǎn)占m個存儲單元，若第一個結(jié)點(diǎn)的地址為B，則第i個結(jié)點(diǎn)的地址為（ A ）。A.B+(i-1)m B.B+im C.B-im D.B+(i+1)m5. 在有n個結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時間復(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. 兩個指針P和Q

10、，分別指向單向鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是（ B ） AP-next= =Q-next B.P-next= =Q C.Q-next= =P D.P=Q8. 用鏈表存儲的線性表，其優(yōu)點(diǎn)是（ C ）。 A便于隨機(jī)存取 B花費(fèi)的存儲空間比順序表少C便于插入和刪除 D數(shù)據(jù)元素的物理順序與邏輯順序相同9. 在單鏈表中，增加頭結(jié)點(diǎn)的目的是（ C ）。 A使單鏈表至少有一個結(jié)點(diǎn) B標(biāo)志表中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn) D說明該單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)10. 下面關(guān)于線性表的敘述中，錯誤的是（ D ）關(guān)系。 A順序表必須占一片地址連續(xù)的存儲單元B順序表可以隨機(jī)存取任一元素C鏈表不必占

11、用一片地址連續(xù)的存儲單元D鏈表可以隨機(jī)存取任一元素11. L是線性表，已知LengthList(L)的值是5，經(jīng)DelList(L，2)運(yùn)算后，LengthList(L)的值是（ 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查找時間復(fù)雜度為O（1） C查找時間復(fù)雜度為O（n）D查找結(jié)點(diǎn)的次數(shù)約為n14. 等概率情況下，在有n個結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動結(jié)點(diǎn)的數(shù)目為（ 8 ）。An B.(

12、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.雙向循環(huán)鏈表16. 在順序表中，只要知道（ D ），就可以求出任一結(jié)點(diǎn)的存儲地址。A.基地址 B.結(jié)點(diǎn)大小 C.向量大小 D.基地址和結(jié)點(diǎn)大小17. 在雙向鏈表中做插入運(yùn)算的時間復(fù)雜度為（ A ）。AO（1） B.O（n） C. O(n2) D.O( log2n)18. 鏈表不具備的特點(diǎn)是（ A ）。A隨機(jī)訪問 B.不必事先估計存儲空間C. 插入刪除時不需要移動元素 D.所需空間與線性表成正比19. 以下關(guān)于線性表的論述，不正確的為（

13、 C ）。A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型B.線性順序表中包含的元素個數(shù)不是任意的C.線性表中的每個結(jié)點(diǎn)都有且僅有一個直接前驅(qū)和一個直接后繼D.存在這樣的線性表，即表中沒有任何結(jié)點(diǎn)20. 在（ B ）的運(yùn)算中，使用順序表比鏈表好。A.插入 B.根據(jù)序號查找 C.刪除 D.根據(jù)元素查找第3章 棧一、 判斷題1. 棧是運(yùn)算受限制的線性表。 （）2. 在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢。 （）3. 棧一定是順序存儲的線性結(jié)構(gòu)。 （）4. 棧的特點(diǎn)是“后進(jìn)先出”。 （）5. 空棧就是所有元素都為0的棧。 （）6. 在C（或C+）語言中設(shè)順序棧的長度為MAXLEN，則top=

14、MAXLEN時表示棧滿。 （）7. 鏈棧與順序棧相比，其特點(diǎn)之一是通常不會出現(xiàn)棧滿的情況。 （）8. 一個棧的輸入序列為：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，則表

15、示 棧空 。7. 向一個棧頂指針為top的鏈棧插入一個新結(jié)點(diǎn)*p時，應(yīng)執(zhí)行p-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é)點(diǎn)。12. 已知順序棧S，在對S進(jìn)棧操作之前首先要判斷 棧是否滿 。13. 已知順序棧S，在對S出棧操作之前首先要判斷 棧是否空 。14. 若內(nèi)在空間充足

16、， 鏈 ?？梢圆欢x棧滿運(yùn)算。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)運(yùn)算后，x的值是 C 。三、選擇題1. 插入和刪除操作只能在一端進(jìn)行的線性表，稱為（ C ）。A隊(duì)列 B循環(huán)隊(duì)列 C棧 D循環(huán)棧2. 設(shè)有編號為1，2。3，4的4輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序

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

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

19、xt;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)（初始化棧）; Push(s，a); Push(s，b); ReadTop(s)

20、 ；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. 向順序棧中輸入元素時（ B ）。A先存入元素，后移動棧頂指針 B先移動棧頂指針，后存入元素C誰先誰后無關(guān)緊要 D同時進(jìn)行1

21、8. 初始化一個空間大小為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章 隊(duì)列一、判斷題1. 隊(duì)列是限制在兩端進(jìn)行操作的線性表。 （）2. 判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個結(jié)點(diǎn)。 （）3. 在鏈隊(duì)列上做出隊(duì)操作時，會改變front指針的值。 （）

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

23、 。4. 在隊(duì)列中，允許刪除的一端稱為 隊(duì)首（或隊(duì)頭） 。5. 隊(duì)列在進(jìn)行出隊(duì)操作時，首先要判斷隊(duì)列是否為 空 。6. 順序隊(duì)列在進(jìn)行入隊(duì)操作時，首先在判斷隊(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為空時，LQ-front-next= NULL 。11. 設(shè)長度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)頭指針，則入隊(duì)操作的時間復(fù)雜度為 O(n) 。12. 設(shè)長度為n的鏈隊(duì)列用單循環(huán)表表示，若

24、只設(shè)尾指針，則入隊(duì)操作的時間復(fù)雜度為 O(1) 。13. 在一個鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為 空 。14. 設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)滿標(biāo)志為 front= =(rear+1)%MAXLEN 。15. 在一個鏈隊(duì)列中，若隊(duì)首指針為front，隊(duì)尾指針為rear，則判斷隊(duì)列只有一個結(jié)點(diǎn)的條件為front= =rear或front!。16. 向一個循環(huán)隊(duì)列中插入元素時，首先要判斷 隊(duì)尾指針 ，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。17. 讀隊(duì)首元素的操作 不改變或不影響隊(duì)列元素的個

25、數(shù)。18. 設(shè)循環(huán)隊(duì)列的容量為40（序號039），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=11，rear=19，則循環(huán)隊(duì)列中還有 8 個元素。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(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x的值是 a 。三、選擇題1. 隊(duì)列是限定在（D）進(jìn)行操作的線性表。A中間者 B.隊(duì)首 C.隊(duì)

26、尾 D.端點(diǎn)2. 隊(duì)列中的元素個數(shù)是（B）。A不變的 B.可變的 C.任意的 D.03. 同一隊(duì)列內(nèi)的各元素的類型（A）。A.必須一致 B.不能一致 C.可以不一致 D.不限制4. 隊(duì)列是一個（C）線性表結(jié)構(gòu)。A.不加限制的 B.推廣了的 C.加了限制的 D.非5. 當(dāng)利用大小為n的數(shù)組順序存儲一個隊(duì)列時，該隊(duì)列的最后一個元素的下標(biāo)為（B）。A.n-2 B.n-1 C.n D.n+16. 一個循環(huán)隊(duì)列一旦說明，其占用空間的大?。ˋ）。A.已固定 B.可以變動 C.不能固定 D.動態(tài)變化7. 循環(huán)隊(duì)列占用的空間（A）。A.必須連續(xù) B.不必連續(xù) C.不能連續(xù) D.可以不連續(xù)8. 存放循環(huán)隊(duì)列元素

27、的數(shù)組data有10個元素，則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個元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，則隊(duì)尾元素是（D）AA BB CC DD11. 4個元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行一次QutQueue(Q)操作后，隊(duì)頭元素是（B）。A.A B.B C.C D.D12. 4個元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行4次QutQueue(Q)操作后，再執(zhí)行QEmpty(Q)；后的值是（B）。A.0 B

28、.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-rear= =0 D.SQ-front= =015. 設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（A）操作。

29、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. 帶頭結(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)算時指針LQ

30、-frnot(A).LQ-frontH A B C D LQ-rear A.始終不改變 B.有時改變 C.進(jìn)隊(duì)時改變 D.出隊(duì)時改變19.隊(duì)列Q，經(jīng)過下列運(yùn)算后，再執(zhí)行QEmpty(Q)的值是（C）。InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；A.a B.b C.0 D.120.若用一個大小為6數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，front和rear的值分別為（B）。A.5和1 B.4和2 C.2和4 D.1和5第5章

31、串一、判斷題1. 串是n個字母的有限序列。 （）2. 串的數(shù)據(jù)元素是一個字符。 （）3. 串的長度是指串中不同字符的個數(shù)。 （）4. 如果兩個串含有相同的字符，則說明它們相等。 （）5. 如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。 （）6. 串的堆分配存儲是一種動態(tài)存儲結(jié)構(gòu)。 （）7. “DT”是“DATA”的子串。 （）8. 串中任意個字符組成的子序列稱為該串的子串。 （）9. 子串的定位運(yùn)算稱為模式匹配。 （）10. 在鏈串中為了提高存儲密度，應(yīng)該增大結(jié)點(diǎn)的大小。 （）二、填空題1. 由零個或多個字符組成的有限序列稱為 字符串（或串） 。2. 字符串按存儲方式可以分

32、為順序存儲、鏈接存儲和 堆分配存儲 。3. 串的順序存儲結(jié)構(gòu)簡稱為 順序串 。4. 串順序存儲非緊湊格式的缺點(diǎn)是 空間利用率低 。5. 串順序存儲緊湊格式的缺點(diǎn)是對串的字符處理 效率低 。6. 串鏈接存儲的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是 空間利用率 。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，

33、2005”，ConcatStr(S1，S2)的結(jié)果是 Today is 30 July,2005 。13. 求子串函數(shù)SubStr(“Today is 30 July，2005”，13，4)的結(jié)果是 July 。14. 在串的運(yùn)算中，EqualStr(aaa,aab)的返回值 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. 以下論述正確的是（

34、C）。A空串與空格串是相同的B”tel”是”Teleptone”的子串C空串是零個字符的串 D空串的長度等于14. 以下論述正確的是（B）。A空串與空格串是相同的B”ton”是”Teleptone”的子串C空格串是有空格的串 D空串的長度等于15. 以下論斷正確的是（A）。A全部由空格組成的串是空格串 B”BEUIJING”是”BEI JING”的子串C”something”Something” D”BIT”=”BITE”6. 設(shè)有兩個串S1和S2，則EqualStr（S1，S2）運(yùn)算稱作（D）。A串連接 B模式匹配 C求子串 D串比較7. 串的模式匹配是指（D）。A判斷兩個串是否相等 B對兩

35、個串比較大小C找某字符在主串中第一次出現(xiàn)的位置D找某子串在主串中第一次出現(xiàn)的第一個字符位置8. 若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯Γ僭O(shè)每個字符占用1個字節(jié)，每個指針占用2個字節(jié)。則該字符串的存儲密度為（D）。A20% B40% C50% D33.3%9. 若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯Γ僭O(shè)每個指針占用2個字節(jié)，若希望存儲密度為50%，則每個結(jié)點(diǎn)應(yīng)存儲（A）個字符。A.2 B.3 C.4 D.510. 設(shè)串S1=”IAM”，S2=”A SDUDENT”，則ConcatStr(S1，S2)=（B）。A”I AM” B.”I AM A SDUDENT” C.”IAMASDUDENT”

36、 D.”A SDUDENT”11. 設(shè)S=”，則LenStr(S)=（A）。A.0 B.1 C.2 D.312. 設(shè)目標(biāo)串T=”AABBCCDDE”，模式P=”ABCDE”，則該模式匹配的有效位移為（A）。A.0 B.1 C.2 D.313. 設(shè)目標(biāo)串T=”AABBCCDDEEFF”，模式P=”CCD”，則該模式匹配的有效位移為（D）。A.2 B.3 C.4 D.514. 設(shè)目標(biāo)串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外層循環(huán)進(jìn)行了（D）次。A.1 B.9 C.4 D.515. 模式匹配算法在最壞情況下的時間復(fù)雜是（D）。A.O(m) B.O(n) C.O(m

37、+n) D.O(mn)16. S=”morning”,執(zhí)行求子串函數(shù)SubSur(S,2,2)后結(jié)果為（B）。A. ”mo” B. ”or” C. ”in” D. ”ng”17. S1=”good”，S2”morning”，執(zhí)行串連接函數(shù)ConcatStr(S1，S2)后結(jié)果為（A）。A. ”goodmorning” B. ”good morning” C. ”GOODMORNING” D. ”GOODMORNING”18. S1=”good”, S2=”morning”執(zhí)行函數(shù)SubSur(S2,4,LenStr(S1)后的結(jié)果為（B）。A.”good” B.”ning” C.”go” D.”morn”19. 設(shè)串S1=”ABCDEFG”，S2=”PQRST”，則ConcatStr（SubStr(S1，2，LenStr（S2），SubStr(S1，LenStr（S2），2）的結(jié)果串為（D）。A. BCDEF B.BCDEFG C