【文章內(nèi)容簡介】 操作受到限制的線性表，是一種特殊的線性表，因此棧也有__________和_________________兩種存儲結(jié)構(gòu)，分別稱為______________和___5．當(dāng)棧滿的時候，再進行人棧操作就會產(chǎn)生____________，這種情況的溢出稱為___________；當(dāng)棧空的時候，如果再進行出棧操作，也會_____________，這種情況下的溢出稱為__________________。6．棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為____________，是一種__________________。7．人們?nèi)粘Ｓ嬎阌玫降谋磉_式都被稱為____________，這是由于這種算術(shù)表達式的運算符被置于兩個操作數(shù)中間。8．計算機中通常使用___________，這是一種將運算符置于兩個操作數(shù)后面的算術(shù)表達式。這種表達式是由波蘭科學(xué)家謝維奇提出的，因此又稱為_____________9．隊列（Queue）也是一種___________，但它與棧不同，隊列中所有的插人均限定在表的一端進行，而所有的刪除則限定在表的另一端進行。允許插人的一端稱為_________，允許刪除的一端稱為_______________。10．隊列的特點是_________，因此隊列又被稱為_______________．的線性表，或稱為_________________表。11．隊列的_________又稱為__________，是用一組地址連續(xù)的存儲單元依次存放隊列中的元素。12．由于隊列中的元素經(jīng)常變化，對于隊列的刪除和插人分別在隊頭和隊尾進行，因此需要設(shè)置兩個指針分別指向__________和__________，這兩個指針又稱為__________和_____________。13．循環(huán)順序隊列（Circular Sequence Queue）經(jīng)常簡稱為___________，它是將存儲順序隊列的存儲區(qū)域看成是一個首尾相連的一個環(huán)，即將隊首和隊尾元素連接起來形成一個環(huán)形表。首尾相連的狀態(tài)是通過數(shù)學(xué)上的_________________來實現(xiàn)的。14．在算法或程序中，當(dāng)一個函數(shù)直接調(diào)用自己或通過一系列語句間接調(diào)用自己的時候，則稱這個函數(shù)為，也稱為____________。函數(shù)直接調(diào)用自己，則稱為__________；當(dāng)一個函數(shù)通過另一個函數(shù)來調(diào)用自己則稱為_________________。15．在循環(huán)隊列中規(guī)定：當(dāng)Qrear= =Qfront的時候循環(huán)隊列為___________， 當(dāng)（Qrear+1）％MAXSIZE＝front的時候循環(huán)隊列為____________________。16．用鏈表方式表示的隊列稱為____________________。17．已知棧的輸人序列為1，2，3，…，n，輸出序列為a1，a2，…，an，符合a2= =n的輸出序列共有__________________。18．一個棧的輸人序列是12345，則棧的輸出序列為43512是________（填是否可能）。19．一個棧的輸人序列是12345，則棧的輸出序列為12345是_________（填是否可能）。20．設(shè)sq[1．．maxsize]為一個順序存儲的棧，變量top指示棧頂元素的位置，則作入棧操作的條件是______________。21．設(shè)sq[1．．maxsize]為一個順序存儲的棧，變量top指示棧頂元素的位置，如果把棧頂元素彈出并送到X中，則需執(zhí)行語句______________。22．棧的特性是__________________。23．對棧進行退棧時的操作是先取出元素，后移動_________。24．設(shè)s[1．．max]為一個順序存儲的棧，變量top指示棧頂位置，棧為滿的條件是____。25．設(shè)鏈棧的棧頂指針為top，則棧非空的條件是___________。26．已知循環(huán)隊列用數(shù)組data[1...n]存儲元素值，用f，r分別作為頭尾指針， 則當(dāng)前元素個數(shù)為____________。27．在一個循環(huán)隊列中，隊首指針指向隊首元素的________位置。（前一個或后一個）28．隊列中允許進行刪除的一端稱為_______________。29．鏈隊列實際上是一個同時帶有頭指針和尾指針的單鏈表（1．．n），尾指針指向該單鏈表的第___________個元素。30．設(shè)雙向鏈表鏈列為lq，，則隊列為空的條件是____________。31．從循環(huán)隊列中刪除一個元素，其操作是先取出一個元素，后移動____________32．隊列中允許進行插入的一端稱為_________。1. 表尾、棧頂、棧底、空棧2. 進棧、入棧、退棧、出棧3. 棧頂元素、棧頂元素、棧頂元素、最先出棧、后進先出、LIFO4. 順序、鏈?zhǔn)?、順序棧、鏈?. 溢出、上溢、溢出、下溢6. 鏈棧、特殊的單鏈表7. 中綴表達式8. 后綴表達式、波蘭式9. 特殊的線性表、隊尾、隊頭10. 先進先出、先進先出、FIFO11. 順序存儲結(jié)構(gòu)、順序隊列12. 隊頭元素、隊尾元素、隊頭指針、隊尾指針13. 循環(huán)隊列、取模運算14. 遞歸函數(shù)、自調(diào)用函數(shù)、直接遞歸調(diào)用、間接遞歸調(diào)用15. 空、滿16. 鏈隊列17. n118. 不可能的19. 可能的20. top!=maxsize21. x=sq[top]。 top=top122. 先進后出23. 棧頂指針24. top==max25. top!=nil26. (n+rf)mod n27. 前一個28. 隊首29. n30. lqfront==lqrear31. 棧頂指針32. 隊尾 三、判斷題1．棧和隊列都是限制存取點的線性結(jié)構(gòu)。（ ）2．不同的入棧和出棧組合可能得到相同輸出序列。（ ）3．消除遞歸一定要用棧。（ ）4．循環(huán)隊列是順序存儲結(jié)構(gòu)。（ ）5．循環(huán)隊列不會產(chǎn)生溢出。（ ）6．循環(huán)隊列滿的時候rear= =front。（ ）7．在對鏈隊列（帶頭結(jié)點）做出隊操作時不會改變front指針的值。（）1. 正確。2. 錯誤：不同的入棧和出棧組合得到不同輸出序列。3. 錯誤：某些情況如尾遞歸可以轉(zhuǎn)換為遞推的形式。4. 正確。5. 錯誤：循環(huán)隊列不會產(chǎn)生假溢出。6. 錯誤。7. 正確。四、綜合題1．設(shè)有4個元素A、B、C和D進棧，給出它們所有可能的出棧秩序。可能的出棧序列：（共14個）ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCACBAD CBDA CDBA DCBA不可能的出棧序列：（共10個）ADBC BDAC CABD CADB CDABDABC DACB DBAC DBCA DCAB習(xí)題四一、選擇項l．空串與空格串（ ）。 A．相同 B．不相同 C．可能相同 D．無法確定2．設(shè)有兩個申S1與S2，求串S2在S1中首次出現(xiàn)位置的運算稱作（ ）。 A．連接 B．求子串 C．模式匹配 D．判子串3．串與普通的線性表相比較，它的特殊性體現(xiàn)在（ ）。 A．順序的存儲結(jié)構(gòu) B．鏈接的存儲結(jié)構(gòu) C．?dāng)?shù)據(jù)元素是一個字符 D．?dāng)?shù)據(jù)元素可以任意4．設(shè)有串S=‘Computer’，則其子串的數(shù)目是（ ）。 A．36 B．37 C．8 D．91. B 2. C 3. C 4. B二、境空題1．串是由零個或多個字符組成的____________。通常記作：s＝“c1，c2，…，”(n=0)，其中，S稱為________；串中的Ci（1=i=n）可以是字母、數(shù)字 字格或其他字符。用雙引號括起來的部分是_________．即串S的內(nèi)容。2．串中字符的個數(shù)稱為串的________。3．不含有任何字符的串稱為_________，它的長度為___________。4．由一個或多個空格構(gòu)成的串稱為____________，它的長度為___________。5．串中任意多個連續(xù)字符組成的子序列稱為該串的____________；包含___________的串稱為主串。6．字符在序列中的序號稱為該字符在串中的________________。 7．兩個字符串相等是指兩個字符串的，也就是說這兩個字符串不僅__________，而且對應(yīng)位置上的字符也。 8．兩個串的比較實際上是_________的比較。兩個串從第一個位置上的字符開始進行比較，當(dāng)?shù)谝淮纬霈F(xiàn)_____________大的串為大，若比較過程中出現(xiàn)一個字符串結(jié)束的情況，則另一個串為_________________。 9．串的_______________就是把串所包含的字符序列，依次存人連續(xù)的存儲單元中去。 10．有些計算機系統(tǒng)中為了充分利用存儲空間，允許一個存儲單元可以存放多個字符，串的這種存儲方式是一種__________________。 11．串的______________是以存儲單元為存儲單位，一個存儲單元中只存放__________。在這種情況下，即使一個存儲單元能存放多個字符，這時候也只存放________________。 12．串在非緊縮方式下，串長度的存儲是隱式的，__________即串的長度。 13．一些計算機是以字節(jié)為存取單位，恰好一個字符占用一個字節(jié)，自然形成了每個存儲單元存放__________的分配方式，這種方式就是一種__________。這種方式一般不需要存放____________的存儲單元，而需要以程序中各變量值所、的字符為結(jié)束符。 14．串的鏈?zhǔn)酱鎯Y(jié)構(gòu)是將存儲區(qū)域分成一系列大小相同的結(jié)點，每個結(jié)點有兩個城：____________域和________域。其中___________域用于存放數(shù)據(jù)，___________域用于存放下一個結(jié)點的指針。 15．子串定位StrIndex (s，t)，也稱為_______，是返回串t在s主串中的位置。1. 有限序列、串名、串值2. 長度3. 空串、零4. 空格串、空格的個數(shù)5. 子串、子串6. 位置7. 值相等、長度相等、相等8. ASCII碼、ASCII碼、較大者9. 順序存儲結(jié)構(gòu)10. 緊縮式存儲方式11. 非緊縮存儲方式、一個字符、一個字符12. 串所占用的存儲單元的個數(shù)13. 一個字符、單字節(jié)存儲方式、串長、不包含14. 數(shù)據(jù)、指針、數(shù)據(jù)、指針15. 模式匹配三、判斷回 1．子串是主串中字符構(gòu)成的有限序列。（） 2．KMP算法的最大特點是指示主串的指針不需要回溯。（ ） 3．串中的元素只能是字符。（ ）4．串中的元素只可能是字母。（）5．串是一種特殊的線性表。（ ）6．串中可以包含有空白字符。（ ）7．串的長度不能為零。（）8．兩個串相等必有串長度相同。（ ）9．兩個串相等則各位置上字符必須對應(yīng)相等。（ ）習(xí)題五一、選擇題 l．?dāng)?shù)組常用的兩種基本操作是（ ）。A．建立與查找 B．刪除與查找 C．插人與索引 D．查找與修改2．對稀疏矩陣進行壓縮存儲，常用的兩種方法是（ ）。A．二元組和散列表 B．三元組表和十字鏈表 C．三角矩陣和對角矩陣 D．對角矩陣和十字鏈表3．采用稀疏矩陣的三元組表形式進行壓縮存儲，若要完對三元組表進行成轉(zhuǎn)置，只要將行和列對換，這種說法（ ）。A．正確 B．錯誤 C． 無法確定 D．以上均不對4．一個廣義表的表頭總是一個廣義表，這種說法（ ）。 A．正確 B．錯誤 C．無法確定 D．以上均不對5．一個廣義表的表尾總是一個廣義表，這種說法（ ）。A．正確 B．錯誤 C．無法確定 D．以上均不對6．廣義表((a))的表頭是（ ）。 A．（ ） B．a(chǎn) C．（a） D．（（a））7．廣義表（（a））的表尾是（ ）。 A．（） B．a(chǎn) C．（a） D．（（a））8．廣義表（（a），a）的表頭是（ ）。 A．（ ） B．a(chǎn) C．（a） D．（（a））9．廣義表（（a），a）的表尾是（ ）。 A．( ) B．a(chǎn) C．（a） D．（（a））10．廣義表（a，b，c）的表頭是（ ）。 A．a(chǎn) B．（a） C．a(chǎn)，b D．（b，c）11．廣義表（a，b，c）的表尾是（ ）。 A．b，c B．（b