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

第1章 緒論一、 判斷題1. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(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. 程序和算法原則上沒(méi)有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。 （）6. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)兩類(lèi)。 （）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)是依賴(lài)于計(jì)算機(jī)的。 （）10. 算法是對(duì)解題方法和步驟的描述。 （）二、填空題1. 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲(chǔ)結(jié)構(gòu) 兩種結(jié)構(gòu)。2. 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu) 。3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們是線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) 。4. 樹(shù)形結(jié)構(gòu) 和圖形結(jié)構(gòu) 合稱(chēng)為非線(xiàn)性結(jié)構(gòu)。5. 在樹(shù)形結(jié)構(gòu)中，除了樹(shù)根結(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. 線(xiàn)性結(jié)構(gòu)中的元素之間存在一對(duì)一 的關(guān)系。10. 樹(shù)形結(jié)構(gòu)中的元素之間存在一對(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ǔ)空間 ，它是該算法求解問(wèn)題規(guī)模的n的函數(shù)。18. 若一個(gè)算法中的語(yǔ)句頻度之和為T(mén)(n)=6n+3nlog2n,則算法的時(shí)間復(fù)雜度為O（ nlog2n） 。19. 若一個(gè)算法的語(yǔ)句頻度之和為T(mén)(n)=3n+nlog2+n2,則算法的時(shí)間復(fù)雜度為O（n2） 。20. 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序問(wèn)題中計(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線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)。3. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱(chēng)之為（C）。A存儲(chǔ)結(jié)構(gòu) B邏輯結(jié)構(gòu) C順序存儲(chǔ)結(jié)構(gòu) D鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4. 非線(xiàn)性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)（D）。A無(wú)直接前驅(qū)結(jié)點(diǎn) B無(wú)直接后繼結(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ì)算量大小稱(chēng)為算法的（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)稱(chēng)為（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)之間都沒(méi)有邏輯關(guān)系的是（D）。A圖形結(jié)構(gòu) B線(xiàn)性結(jié)構(gòu) C樹(shù)形結(jié)構(gòu) D集合11. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(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線(xiàn)性結(jié)構(gòu) C樹(shù)形結(jié)構(gòu) D圖形結(jié)構(gòu)13. 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（A）。A邏輯結(jié)構(gòu) B存儲(chǔ)結(jié)構(gòu) C邏輯實(shí)現(xiàn) D存儲(chǔ)實(shí)現(xiàn)14. 每一個(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ù)定功能的特性稱(chēng)為算法的（A）。A正確性 B易讀性 C健壯性 D高效性16. 算法在發(fā)生非法操作時(shí)可以作出相應(yīng)處理的特性稱(chē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;in;i+)for(j=o;iprior-next=p-next；p-next-prior=p-prior 20. 在如圖所示的鏈表中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個(gè)結(jié)點(diǎn)，則可用語(yǔ)句S-next-next=p-next和P- next=S；來(lái)實(shí)現(xiàn)該操作。 p a b s三、 選擇題1. 在具有n個(gè)結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)（ A）的操作，其算法的時(shí)間復(fù)雜度都是O(n). A.遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn) B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.刪除開(kāi)始結(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)稱(chēng)為（ 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ǔ)的線(xiàn)性表，設(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+im C.B-im D.B+(i+1)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=Q8. 用鏈表存儲(chǔ)的線(xiàn)性表，其優(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說(shuō)明該單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)10. 下面關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是（ D ）關(guān)系。 A順序表必須占一片地址連續(xù)的存儲(chǔ)單元B順序表可以隨機(jī)存取任一元素C鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元D鏈表可以隨機(jī)存取任一元素11. L是線(xiàn)性表，已知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查找時(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ā)訪(fǎng)問(wèn)到其余各結(jié)點(diǎn)的是（ C ）。A.雙向鏈表 B.單循環(huán)鏈表 C.單向鏈表 D.雙向循環(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ī)訪(fǎng)問(wèn) B.不必事先估計(jì)存儲(chǔ)空間C. 插入刪除時(shí)不需要移動(dòng)元素 D.所需空間與線(xiàn)性表成正比19. 以下關(guān)于線(xiàn)性表的論述，不正確的為（ C ）。A.線(xiàn)性表中的元素可以是數(shù)字、字符、記錄等不同類(lèi)型B.線(xiàn)性順序表中包含的元素個(gè)數(shù)不是任意的C.線(xiàn)性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼D.存在這樣的線(xiàn)性表，即表中沒(méi)有任何結(jié)點(diǎn)20. 在（ B ）的運(yùn)算中，使用順序表比鏈表好。A.插入 B.根據(jù)序號(hào)查找 C.刪除 D.根據(jù)元素查找第3章 棧一、 判斷題1. 棧是運(yùn)算受限制的線(xiàn)性表。 （）2. 在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生下溢。 （）3. 棧一定是順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu)。 （）4. 棧的特點(diǎn)是“后進(jìn)先出”。 （）5. 空棧就是所有元素都為0的棧。 （）6. 在C（或C+）語(yǔ)言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN時(shí)表示棧滿(mǎn)。 （）7. 鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿(mǎn)的情況。 （）8. 一個(gè)棧的輸入序列為：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)中，允許插入、刪除的一端稱(chēng)為 棧頂 。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;top=p；操作。8. 順序棧S存儲(chǔ)在數(shù)組S-data0MAXLEN-1中，進(jìn)棧操作時(shí)要執(zhí)行的語(yǔ)句有：S-top+。(或S-top+1)S-dataS-top=x9. 鏈棧LS，指向棧頂元素的指針是LS-next。10. 從一個(gè)棧刪除元素時(shí)，首先取出 棧頂元素 ，然后再移動(dòng)棧頂指針。11. 由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒(méi)有必要設(shè)置 頭 結(jié)點(diǎn)。12. 已知順序棧S，在對(duì)S進(jìn)棧操作之前首先要判斷 棧是否滿(mǎn) 。13. 已知順序棧S，在對(duì)S出棧操作之前首先要判斷 棧是否空 。14. 若內(nèi)在空間充足， 鏈 棧可以不定義棧滿(mǎn)運(yùn)算。15. 鏈棧LS為空的條件是 LS-next=NULL 。16. 鏈棧LS的棧頂元素是鏈表的 首 元素。17. 同一棧的各元素的類(lèi)型 相同 。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)行的線(xiàn)性表，稱(chēng)為（ C ）。A隊(duì)列 B循環(huán)隊(duì)列 C棧 D循環(huán)棧2. 設(shè)有編號(hào)為1，2。3，4的4輛列車(chē)，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，下列不可能的出站順序?yàn)椋?D）。A1234 B1243 C1324 D14233. 如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)（ B ）。A必須判別棧是否滿(mǎn) B必須判別棧是否為空 C必須判別棧元素類(lèi)型 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+）語(yǔ)言中，一個(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 ）。A. 插入操作更加方便 B.通常不會(huì)出現(xiàn)棧滿(mǎ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-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)運(yùn)算后，棧頂元素的值是（ B ）。AA BB CC DD12. 元素A、B、C、D依次進(jìn)棧以后，棧底元素是（ A ）。AA BB CC DD13. 經(jīng)過(guò)下列棧的運(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)過(guò)下列棧的運(yùn)算后，x的值是（ B ）。InitStack(s)（初始化棧）; Push(s，a); Push(s，b); ReadTop(s) ；Pob(s，x);A. a B.b C.1 D.015. 經(jīng)過(guò)下列棧的運(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)過(guò)下列棧的運(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)棧頂指針 B先移動(dòng)棧頂指針，后存入元素C誰(shuí)先誰(shuí)后無(wú)關(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)行操作的線(xiàn)性表。 （）2. 判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個(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ì)滿(mǎn)的情況。 （）7. 在循環(huán)鏈隊(duì)列中無(wú)溢出現(xiàn)象。 （）8. 棧和隊(duì)列都是順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu)。 （）9. 在隊(duì)列中允許刪除的一端稱(chēng)為隊(duì)尾。 （）10. 順序隊(duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿(mǎn)和隊(duì)空的判斷條件是一樣的。 （）二、填空題1. 在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是 先進(jìn)先出 。2. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算線(xiàn)性表。3. 在隊(duì)列中，允許插入的一端稱(chēng)為 隊(duì)尾 。4. 在隊(duì)列中，允許刪除的一端稱(chēng)為 隊(duì)首（或隊(duì)頭） 。5. 隊(duì)列在進(jìn)行出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為 空 。6. 順序隊(duì)列在進(jìn)行入隊(duì)操作時(shí)，首先在判斷隊(duì)列是否為 滿(mǎn) 。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-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ì)滿(mǎn)標(biāo)志為 front= =(rear+1)%MAXLEN 。15. 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為front，隊(duì)尾指針為rear，則判斷隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為front= =rear或front!。16. 向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要判斷 隊(duì)尾指針 ，然后再向指針?biāo)傅奈恢脤?xiě)入新的數(shù)據(jù)。17. 讀隊(duì)首元素的操作 不改變或不影響隊(duì)列元素的個(gè)數(shù)。18. 設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)039），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=11，rear=19，則循環(huán)隊(duì)列中還有 8 個(gè)元素。19. 隊(duì)列Q，經(jīng)過(guò)下列運(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)過(guò)InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x的值是 a 。三、選擇題1. 隊(duì)列是限定在（D）進(jìn)行操作的線(xiàn)性表。A中間者 B.隊(duì)首 C.隊(duì)尾 D.端點(diǎn)2. 隊(duì)列中的元素個(gè)數(shù)是（B）。A不變的 B.可變的 C.任意的 D.03. 同一隊(duì)列內(nèi)的各元素的類(lèi)型（A）。A.必須一致 B.不能一致 C.可以不一致 D.不限制4. 隊(duì)列是一個(gè)（C）線(xiàn)性表結(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ì)列一旦說(shuō)明，其占用空間的大?。ˋ）。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.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)過(guò)下列運(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ì)滿(mǎn)的條件是（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是棧頂指針，若想在鏈棧的棧頂插入一個(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. 帶頭結(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)過(guò)下列運(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.若用一個(gè)大小為6數(shù)組來(lái)實(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è)串含有相同的字符，則說(shuō)明它們相等。 （）5. 如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說(shuō)明前者是后者的子串。 （）6. 串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。 （）7. “DT”是“DATA”的子串。 （）8. 串中任意個(gè)字符組成的子序列稱(chēng)為該串的子串。 （）9. 子串的定位運(yùn)算稱(chēng)為模式匹配。 （）10. 在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。 （）二、填空題1. 由零個(gè)或多個(gè)字符組成的有限序列稱(chēng)為 字符串（或串） 。2. 字符串按存儲(chǔ)方式可以分為順序存儲(chǔ)、鏈接存儲(chǔ)和 堆分配存儲(chǔ) 。3. 串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為 順序串 。4. 串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是 空間利用率低 。5. 串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理 效率低 。6. 串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是 空間利用率 。7. 在C或C+語(yǔ)言中，以字符 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 July，2005”，13，4)的結(jié)果是 July 。14. 在串的運(yùn)算中，EqualStr(aaa,aab)的返回值 m，則模式匹配算法最壞情況下的時(shí)間復(fù)雜度為 (n-m+1)*m 。三、選擇題 1. 串是和種特殊的線(xiàn)性表，其特殊體現(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無(wú)法確定3. 以下論述正確的是（C）。A空串與空格串是相同的B”tel”是”Teleptone”的子串C空串是零個(gè)字符的串 D空串的長(zhǎng)度等于14. 以下論述正確的是（B）。A空串與空格串是相同的B”ton”是”Teleptone”的子串C空格串是有空格的串 D空串的長(zhǎng)度等于15. 以下論斷正確的是（A）。A全部由空格組成的串是空格串 B”BEUIJING”是”BEI JING”的子串C”something”Something” D”BIT”=”BITE”6. 設(shè)有兩個(gè)串S1和S2，則EqualStr（S1，S2）運(yùn)算稱(chēng)作（D）。A串連接 B模式匹配 C求子串 D串比較7. 串的模式匹配是指（D）。A判斷兩個(gè)串是否相等 B對(duì)兩個(gè)串比較大小C找某字符在主串中第一次出現(xiàn)的位置D找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置8. 若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)。則該字符串的存儲(chǔ)密度為（D）。A20% B40% C50% D33.3%9. 若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)指針占用2個(gè)字節(jié)，若希望存儲(chǔ)密度為50%，則每個(gè)結(jié)點(diǎn)應(yīng)存儲(chǔ)（A）個(gè)字符。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” 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. 模式匹配算法在最壞情況下的時(shí)間復(fù)雜是（D）。A.O(m) B.O(n) C.O(m+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=”P(pán)QRST”，則ConcatStr（SubStr(S1，2，LenStr（S2），SubStr(S1，LenStr（S2），2）的結(jié)果串為（D）。A. BCDEF B.BCDEFG C