【文章內容簡介】 ，則隊列的輸出順序是（ ）。A 4321 B 1234 C 1432 D 3241【解答】B【分析】隊列的入隊順序和出隊順序總是一致的。⑺ 棧和隊列的主要區(qū)別在于（ ）。A 它們的邏輯結構不一樣 B 它們的存儲結構不一樣C 所包含的運算不一樣 D 插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結構都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數據結構在針對具體問題時包含的運算都可能不同。⑻ 設數組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（ ）。A S1的棧底位置為0，S2的棧底位置為n1B S1的棧底位置為0，S2的棧底位置為n/2C S1的棧底位置為0，S2的棧底位置為nD S1的棧底位置為0，S2的棧底位置為1【解答】A【分析】兩棧共享空間首先兩個棧是相向增長的，棧底應該分別指向兩個棧中的第一個元素的位置，并注意C++中的數組下標是從0開始的。⑼ 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（ ）。A 連接 B 模式匹配 C 求子串 D 求串長【解答】B3. 判斷題⑴ 有n個元素依次進棧，則出棧序列有(n1)/2種。【解答】錯。應該有 種。⑵ ?？梢宰鳛閷崿F(xiàn)過程調用的一種數據結構?！窘獯稹繉ΑＶ灰僮鳚M足后進先出性，都可以采用棧作為輔助數據結構。⑶ 在棧滿的情況下不能做進棧操作，否則將產生“上溢”?！窘獯稹繉?。⑷ 在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear?！窘獯稹垮e。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。⑸ 空串與空格串是相同的?！窘獯稹垮e?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數。4. 設有一個棧，元素進棧的次序為A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。⑴ C，E，A，B，D ⑵ C，B，A，D，E【解答】⑴不能，因為在C、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧。⑵可以，設Ｉ為進棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。5. 舉例說明順序隊列的“假溢出”現(xiàn)象。【解答】假設有一個順序隊列，如圖36所示，隊尾指針rear=4，隊頭指針front=1，如果再有元素入隊，就會產生“上溢”，此時的“上溢”又稱為“假溢出”，因為隊列并不是真的溢出了，存儲隊列的數組中還有2個存儲單元空閑，其下標分別為0和1。6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數k入棧，pop表示棧頂元素出棧。）【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖37所示。7． 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么？（EnQueue(k)表示整數k入隊，DeQueue表示隊頭元素出隊）。【解答】隊頭元素為5，隊尾元素為9。其執(zhí)行過程如圖38所示。8．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個數。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?. 算法設計⑴ 假設以不帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針。試設計相應的入隊和出隊的算法?！窘獯稹砍鲫牪僮魇窃谘h(huán)鏈表的頭部進行，相當于刪除開始結點，而入隊操作是在循環(huán)鏈表的尾部進行，相當于在終端結點之后插入一個結點。由于循環(huán)鏈表不帶頭結點，需要處理空表的特殊情況。入隊算法如下：出隊算法如下：⑵ 設順序棧S中有2n個元素，從棧頂到棧底的元素依次為a2n，a2n1，…，a1，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂到棧底的元素依次為a2n，a2n2，…，a2，a2n1，a2n3，…，a1，請設計算法實現(xiàn)該操作，要求空間復雜度和時間復雜度均為O(n)?！窘獯稹坎僮鞑襟E為：① 將所有元素出棧并入隊；② 依次將隊列元素出隊，如果是偶數結點，則再入隊，如果是奇數結點，則入棧；③ 將奇數結點出棧并入隊；④ 將偶數結點出隊并入棧；⑤ 將所有元素出棧并入隊；⑥ 將所有元素出隊并入棧即為所求。⑶ 用順序存儲結構存儲串S，編寫算法刪除S中第 i個字符開始的連續(xù)j個字符?！窘獯稹肯扰袛啻甋中要刪除的內容是否存在，若存在，則將第i+j1之后的字符前移j個位置。算法如下：⑷ 對于采用順序存儲結構的串S，編寫一個函數刪除其值等于ch的所有字符?！窘獯稹繌暮笙蚯皠h除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數，提高算法的效率。算法如下：⑸ 對串的模式匹配KMP算法設計求模式滑動位置的next函數?！窘獯稹繉W習自測及答案 1．在一個具有n個單元的順序棧中，假定以地址低端（即下標為0的單元）作為棧底，以top作為棧頂指針，當出棧時，top的變化為（ ）。A 不變 B top=0。 C top=top1。 D top=top+1?！窘獯稹緾2．一個棧的入棧序列是a, b, c, d, e，則棧的不可能的出棧序列是（ ）。A edcba B cdeba C debca D abcde 【解答】C3．從棧頂指針為top的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執(zhí)行（ ）。A x=top。 top=topnext。 B x=topdata。C top=topnext。 x=topdata。 D x=topdata。 top=topnext?！窘獯稹緿4．設元素1, 2, 3, P, A依次經過一個棧，進棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設計語言的變量名。【解答】PA321, P3A21, P32A1, P321A, AP321=I_ am_ a_ teacther，其長度為（ ）?！窘獯稹?5第 4 章 廣義線性表——多維數組和廣義表 課后習題講解 1. 填空⑴ 數組通常只有兩種運算：（ ）和（ ），這決定了數組通常采用（ ）結構來實現(xiàn)存儲?！窘獯稹看嫒?，修改，順序存儲【分析】數組是一個具有固定格式和數量的數據集合，在數組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數組中通常只有存取和修改兩種操作。⑵ 二維數組A中行下標從10到20，列下標從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（ ）?！窘獯稹?140【分析】數組A中每行共有6個元素，元素A[15][10]的前面共存儲了(1510)6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。⑶ 設有一個10階的對稱矩陣A采用壓縮存儲，A[0][0]為第一個元素，其存儲地址為d，每個元素占1個存儲單元，則元素A[8][5]的存儲地址為（ ）?！窘獯稹縟+41【分析】元素A[8][5]的前面共存儲了(1+2+…+8)+5=41個元素。⑷ 稀疏矩陣一般壓縮存儲方法有兩種，分別是（ ）和（ ）。【解答】三元組順序表，十字鏈表⑸ 廣義表((a), (((b),c)),(d))的長度是（　　　），深度是（　　?。?，表頭是（　　?。?，表尾是（　　　）。【解答】3，4，(a)，((((b),c)),(d))⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數取出LS中原子b的運算是（ ）?！窘獯稹縃ead(Head(Tail(LS)))2. 選擇題⑴ 二維數組A的每個元素是由6個字符組成的串，行下標的范圍從0~8，列下標的范圍是從0~9，則存放A至少需要（　　?。﹤€字節(jié)，A的第8列和第5行共占（　　?。﹤€字節(jié)，若A按行優(yōu)先方式存儲，元素A[8][5]的起始地址與當A按列優(yōu)先方式存儲時的（ ）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9]【解答】D，E，K【分析】數組A為9行10列，共有90個元素，所以，存放A至少需要906=540個存儲單元，第8列和第5行共有18個元素（注意行列有一個交叉元素），所以，共占108個字節(jié)，元素A[8][5]按行優(yōu)先存儲的起始地址為d+810+5=d+85，設元素A[i][j]按列優(yōu)先存儲的起始地址與之相同，則d+j9+i=d+85，解此方程，得i=4，j=9。⑵ 將數組稱為隨機存取結構是因為（　　?。〢 數組元素是隨機的 B 對數組任一元素的存取時間是相等的C 隨時可以對數組進行訪問 D 數組的存儲結構是不定【解答】B⑶ 下面的說法中，不正確的是（　　　）A 數組是一種線性結構 B 數組是一種定長的線性結構 C 除了插入與刪除操作外，數組的基本操作還有存取、修改、檢索和排序等D 數組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】數組屬于廣義線性表，數組被創(chuàng)建以后，其維數和每維中的元素個數是確定的，所以，數組通常沒有插入和刪除操作。⑷ 對特殊矩陣采用壓縮存儲的目的主要是為了（　　?。〢 表達變得簡單 B 對矩陣元素的存取變得簡單C 去掉矩陣中的多余元素 D 減少不必要的存儲空間【解答】D【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復存儲。⑸ 下面（　　?。┎粚儆谔厥饩仃?。A 對角矩陣 B 三角矩陣 C 稀疏矩陣 D 對稱矩陣 【解答】C⑹ 若廣義表A滿足Head(A)=Tail(A)，則A為（ ）A ( ) B (( )) C (( ),( )) D(( ),( ),( ))【解答】B⑺ 下面的說法中，不正確的是（　　?。〢 廣義表是一種多層次的結構 B 廣義表是一種非線性結構C 廣義表是一種共享結構 D 廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關系講，廣義表屬于線性結構。⑻ 下面的說法中，不正確的是（　　?。〢 對稱矩陣只須存放包括主對角線元素在內的下（或上）三角的元素即可。B 對角矩陣只須存放非零元素即可。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。如果零元素的分布有規(guī)律，就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應的映象函數。3. 判斷題⑴ 數組是一種復雜的數據結構，數組元素之間的關系既不是線性的，也不是樹形的?！窘獯稹垮e。例如二維數組可以看成是數據元素為線性表的線性表。⑵ 使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。⑶ 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。【解答】對。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關系。⑷ 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表?！窘獯稹繉Α＂?若一個廣義表的表頭為空表，則此廣義表亦為空表?！窘獯稹垮e。如廣義表L=(( )，(a，b))的表頭為空表，但L不是空表。4．一個稀疏矩陣如圖44所示，寫出對應的三元組順序表和十字鏈表存儲表示。【解答】對應的三元組順序表如圖45所示，十字鏈表如圖46所示。5．已知A為稀疏矩陣，試從空間和時間角度比較采用二維數組和三元組順序表兩種不同的存儲結構完成求 運算的優(yōu)缺點。【解答】設稀疏矩陣為m行n列，如果采用二維數組存儲，其空間復雜度為Ｏ(mn)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復雜度亦為Ｏ(mn)。如果采用三元組順序表進行壓縮存儲，假設矩陣中有t個非零元素，其空間復雜度為Ｏ(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時間復雜度亦為Ｏ(t)。當t mn時，采用三元組順序表存儲可獲得較好的時、空性能。6．設某單位職工工資表ST由“工資”、“扣除”和“實發(fā)金額”三項組成，其中工資項包括“基本工資”、“津貼”和“獎金”，扣除項包括“水”、“電”和“煤氣” 。⑴ 請用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎金”項；⑵ 畫出該工資表ST的存儲結構?！窘獯稹竣?ST=((基本工資，津貼，獎金)，(水，電，煤氣)，實發(fā)金額)Head(Tail(Tail(Head(ST))))=獎金⑵ 工資表ST的頭尾表示法如圖47所示。7．若在矩陣A中存在一個元素ai,j（0≤i≤n1，0≤j≤m1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設以二維數組存儲矩陣A，試設計一個求該矩陣所有馬鞍點的算法，并分析最壞情況下的時間復雜度?！窘獯稹吭诰仃囍兄鹦袑ふ以撔兄械淖钚≈担缓髮ζ渌诘牧袑ふ易畲笾?，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。具體算法如下：分析算法，外層for循環(huán)共執(zhí)行n次，內層第一個for循環(huán)執(zhí)行m