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