【正文】 插入一個新結(jié)點只需修改指針，所以時間復(fù)雜度為 Ο(1)；而在給定值為 x 的結(jié)點 后插入一個新結(jié)點需要先查找值為 x 的結(jié)點，所以時間復(fù)雜度為 Ο(n)。⑵ 線性表采用鏈接存儲時，其地址（ ）。【解答】B⑷ 鏈表不具有的特點是（ ）。⑹ 若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用（ ）存儲方法 最節(jié)省時間。⑻ 在具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是（ ）。⑽ 使用雙鏈表存儲線性表，其優(yōu)點是可以（ ）。A snext=pnext。 C pnext=snext?！窘獯稹緽【分析】注意此題是在 q 和 p 之間插入新結(jié)點，所以，不用考慮修改指針的順序。 pnextprior=s。 sprior=p。 pnext=s。 pnextprior=s。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。⑶ 設(shè) p，q 是指針，若 p=q，則*p=*q?！窘獯稹垮e。要找到該結(jié)點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。⑶ 描述一個城市的設(shè)計和規(guī)劃。單鏈表的缺點：① 指針的結(jié)構(gòu)性開銷；② 存取表中任意元素不方便，只能進(jìn)行順序存取。⑵ 應(yīng)選用鏈接存儲結(jié)構(gòu)。而順序表的插入、刪除的效率低，故不合適。分析算法，第一次調(diào)用 Reverse 函數(shù)的時間復(fù)雜度為 O(k)，第二次調(diào)用 Reverse 函數(shù)的時間復(fù)雜度為 O(nk)， 第三次調(diào)用 Reverse 函數(shù)的時間復(fù)雜度為 O(n)，所以，總的時間復(fù)雜度為 O(n)。⑶ 試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點的單鏈表上的插入操作的實 現(xiàn)進(jìn)行比較。具體算法如下：單鏈表的逆置請參見 算法 24 和算法 26?！窘獯稹吭趩捂湵?A 中依次取元素，若取出的元素是字母，把它插入到字母鏈表 B 中，若取出的元素是數(shù) 字，則把它插入到數(shù)字鏈表 D 中，直到鏈表的尾部，這樣表 B，D，A 中分別存放字母、數(shù)字和其他字符。【解答】設(shè)工作指針 p 和 q 分別指向循環(huán)雙鏈表的開始結(jié)點和終端結(jié)點，若結(jié)點 p 和結(jié)點 q 的數(shù)據(jù)域相等， 則工作指針 p 后移，工作指針 q 前移，直到指針 p 和指針 q 指向同一結(jié)點（循環(huán)雙鏈表中結(jié)點個數(shù)為奇數(shù)）， 或結(jié)點 q 成為結(jié)點 p 的前驅(qū)（循環(huán)雙鏈表中結(jié)點個數(shù)為偶數(shù)）。A O(0) B O(1) C O(n) D O(n2)【解答】C3．在一個長度為 n 的順序表的第 i（1≤i≤n+1）個元素之前插入一個元素，需向后移動（ ）個元素，刪除 第 i（1≤i≤n）個元素時，需向前移動（ ）個元素?！窘獯稹壳膀?qū)，后繼7．設(shè) A 是一個線性表（a1, a2, …, an），采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在 ai 與 ai+1 之間（1≤i≤n）的概率為 ，則平均每插 入一個元素所要移動的元素個數(shù)又是多少？【解答】。具體 算法如下：9. 已知單鏈表中各結(jié)點的元素值為整型且遞增有序，設(shè)計算法刪除鏈表中所有大于 mink 且小于 maxk 的所有元素，并釋放被刪結(jié)點的存儲空間。請將該循環(huán)鏈表拆成兩個單循環(huán)鏈表 L1 和 L2，使得 L1 中含有原 L1 表中序號為奇數(shù)的結(jié)點且遍歷結(jié)果為：x1, x3,… ；L2 中含有原 L1 表中序 號為偶數(shù)的結(jié)點且遍歷結(jié)果為：… , x4, x2?！窘獯稹織！痉治觥窟f歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性?！窘獯稹亢筮M(jìn)先出，先進(jìn)先出，對插入和刪除操作限定的位置不同⑹ 循環(huán)隊列的引入是為了克服（ ）。【解答】Ｏ(1)，Ｏ(n)【分析】在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結(jié)點，這只需修改相應(yīng)指針；入隊即是在終端結(jié)點 的后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點的地址。2. 選擇題⑴ 若一個棧的輸入序列是 1，2，3，…，n，輸出序列的第一個元素是 n，則第 i 個輸出元素是（ ）。⑶ 一個棧的入棧序列是 1，2，3，4，5，則棧的不可能的輸出序列是（ ）。A 棧 B 隊列 C 數(shù)組 D 線性表【解答】B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。A 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲結(jié)構(gòu)不一樣C 所包含的運算不一樣 D 插入、刪除運算的限定不一樣【解答】D【分析】棧和隊列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。⑼ 設(shè)有兩個串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運算稱作（ ）。⑵ 棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。【解答】對。⑸ 空串與空格串是相同的。⑴ C，E，A，B，D⑵ C，B，A，D，E【解答】⑴不能，因為在 C、E 出棧的情況下，A 一定在棧中，而且在 B 的下面，不可能先于 B 出棧。6. 在操作序列 push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù) k 入棧，pop 表示棧頂元素出棧?！窘獯稹筷狀^元素為 5，隊尾元素為 9。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計算串長時應(yīng)包括這些空格符?！窘獯稹砍鲫牪僮魇窃谘h(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進(jìn)行， 相當(dāng)于在終端結(jié)點之后插入一個結(jié)點。⑶ 用順序存儲結(jié)構(gòu)存儲串 S，編寫算法刪除 S 中第 i 個字符開始的連續(xù) j 個字符。算法如下：⑸ 對串的模式匹配 KMP 算法設(shè)計求模式滑動位置的 next 函數(shù)。 D top=top+1。 top=topnext。 D x=topdata。【解答】156．對于棧和隊列，無論它們采用順序存儲結(jié)構(gòu)還是鏈接存儲結(jié)構(gòu)，進(jìn)行插入和刪除操作的時間復(fù)雜度都是（ ）。9. 利用兩個棧 S1 和 S2 模擬一個隊列，如何利用棧的運算實現(xiàn)隊列的插入和刪除操作，請簡述算法思想。11．假設(shè)一個算術(shù)表達(dá)式中可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”以及花括號“{”和“}”，且這三種括號可按任意的次序嵌套使用。除了 初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。【解答】d+41【分析】元素 A[8][5]的前面共存儲了(1+2+…+8)+5=41 個元素。【解答】Head(Head(Tail(LS)))2. 選擇題⑴ 二維數(shù)組 A 的每個元素是由 6 個字符組成的串，行下標(biāo)的范圍從 0~8，列下標(biāo)的范圍是從 0~9，則存 放 A 至少需要（ ）個字節(jié)，A 的第 8 列和第 5 行共占（ ）個字節(jié)，若 A 按行優(yōu)先方式存儲， 元素 A[8][5]的起始地址與當(dāng) A 按列優(yōu)先方式存儲時的（ ）元素的起始地址一致。⑸ 下面（ ）不屬于特殊矩陣。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲?！窘獯稹垮e。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。⑷ 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表。如廣義表 L=(( )，(a，b))的表頭為空表，但 L 不是空表?！窘獯稹吭O(shè)稀疏矩陣為 m 行 n 列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為Ｏ(mn)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復(fù)雜度亦為Ｏ(mn)。⑴ 請用廣義表形式表示所描述的工資表 ST，并用表頭和表尾求表中的“獎金”項；⑵ 畫出該工資表 ST 的存儲結(jié)構(gòu)?！窘獯稹吭诰仃囍兄鹦袑ふ以撔兄械淖钚≈担缓髮ζ渌诘牧袑ふ易畲笾?，如果該列上的最大值與該行 上的最小值相等，則說明該元素是鞍點，將它所在行號和列號輸出。注意矩陣元素的表示方法?！窘獯稹?i1，(n+1)/2，(n1)/2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為 n0，度為 2 的結(jié)點個數(shù)為 n2，由于滿二叉樹中不存在度為 1 的 結(jié)點，所以 n=n0+n2；由二叉樹的性質(zhì) n0=n2+1，得 n0=(n+1)/2，n2=(n1)/2?！窘獯稹?k1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達(dá)到最多。則該樹中有（ ） 個葉子結(jié)點。⑼ 在具有 n 個結(jié)點的二叉鏈表中，共有（ ）個指針域，其中（ ）個指針域用于指向其左右孩子，剩下的（ ）個指針域則是空的。A 1 B 2 C 3 D 4【解答】D⑵ 設(shè)二叉樹有 n 個結(jié)點，則其深度為（ ）。⑷ 線索二叉樹中某結(jié)點 R 沒有左孩子的充要條件是（ ）。⑹ 一個高度為 h 的滿二叉樹共有 n 個結(jié)點，其中有 m 個葉子結(jié)點，則有（ ）成立。⑻ 如果 T39。A 前序 B 中序 C 后序 D 層序【解答】A，B⑼ 設(shè)森林中有 4 棵樹，樹中結(jié)點的個數(shù)依次為 nnnn4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的 右子樹上有（ ）個結(jié)點，根結(jié)點的左子樹上有（ ）個結(jié)點?！窘獯稹垮e。由前序遍歷的操作定義可知。⑷ 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的?！窘獯稹垮e。【解答】證明采用歸納法。6．已知一棵度為 m 的樹中有：n1 個度為 1 的結(jié)點，n2 個度為 2 的結(jié)點，……，nm 個度為 m 的結(jié)點，問 該樹中共有多少個葉子結(jié)點？【解答】設(shè)該樹的總結(jié)點數(shù)為 n，則n=n0+n1+n2+……+nm 又： n=分枝數(shù)+1=0n0+1n1+2n2+……+mnm+1 由上述兩式可得：n0= n2+2n3+……+(m1)nm+17．已知二叉樹的中序和后序序列分別為 CBEDAFIGH 和 CEDBIFHGA，試構(gòu)造該二叉樹。樹的帶權(quán)路徑長度為：WPL=24+34+53+73+83+92+112=1209．已知某字符串 S 中共有 8 種字符，各種字符分別出現(xiàn) 2 次、1 次、4 次、5 次、7 次、3 次、4 次和 9 次， 對該字符串用[0，1]進(jìn)行前綴編碼，問該字符串的編碼至少有多少位?！窘獯稹勘舅惴ú皇且蛴∶總€結(jié)點的值，而是求出結(jié)點的個數(shù)。相同之處是打印次序均為前序，不 同之處是此處不是打印每個結(jié)點的值，而是打印出其中的葉子結(jié)點，即為有條件打印。具體算法如下：⑷ 編寫算法，要求輸出二叉樹后序遍歷序列的逆序。具體算法如下：⑹ 以二叉鏈表為存儲結(jié)構(gòu)，在二叉樹中刪除以值 x 為根結(jié)點的子樹。② 從棧彈出一個結(jié)點，如果此結(jié)點有右子樹，訪問右子樹執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。【解答】先在鏈表中進(jìn)行遍歷，在遍歷過程中查找值等于 x 的結(jié)點，然后由此結(jié)點的最左孩子域 firstchild 找到值為 x 結(jié)點的第一個孩子，再沿右兄弟域 rightsib 找到值為 x 結(jié)點的第 i 個孩子并返回指向這個孩子的 指針。具體算法如下：學(xué)習(xí)自測及答案1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。A n0=n21 B n0=n2 C n0=n2+1 D 沒有規(guī)律【解答】C5．一棵滿二叉樹中共有 n 個結(jié)點，其中有 m 個葉子結(jié)點，深度為 h，則（ ）。A 左線索標(biāo)志為 0，右線索標(biāo)志為 1 B 左線索標(biāo)志為 1，右線索標(biāo)志為 0C 左、右線索標(biāo)志均為 0 D 左、右線索標(biāo)志均為 1【解答】C9．對于一棵具有 n 個結(jié)點的樹，其所有結(jié)點的度之和為（ ）。⑵ 中序序列和后序序列相同。⑶ 空二叉樹、只有一個根結(jié)點的二叉樹13．將下面圖 516 所示的樹轉(zhuǎn)換為二叉樹，圖 517 所示的二叉樹轉(zhuǎn)換為樹或森林。若樹為空樹，則其深度為 0，否則其深度等于第一棵子樹的深度+1 和兄弟子 樹的深度中的較大者。因此可采用按層次遍歷二叉樹的方 法依次對每個結(jié)點進(jìn)行判斷是否滿足上述兩個條件。⑵ 任何連通圖的連通分量只有一個，即是（ ）?！窘獯稹浚?n+e)【分析】在無向圖的鄰接表中，頂點表有 n 個結(jié)點，邊表有 2e 個結(jié)點，共有 n+2e 個結(jié)點，其空間復(fù)雜度 為Ｏ(n+2e)=Ｏ(n+e)?！窘獯稹壳靶?，棧，層序，隊列⑻ 對于含有 n 個頂點 e 條邊的連通圖，利用 Prim 算法求最小生成樹的時間復(fù)雜度為（ ），利用 Kruskal算法求最小生成樹的時間復(fù)雜度為（ ）。【解答】vi, vj, vk【分析】對由頂點 vi, vj, vk 組成的圖進(jìn)行拓?fù)渑判?。A n B n+1 C n1 D n(n1)E 無回路 F 有回路 G 環(huán)狀 H 樹狀【解答】A，G⑶ 含 n 個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（ ）。A 唯一 B 不唯一 C 唯一性不能確定 D n E n +1 F n1【解答】C，F(xiàn)⑹ 設(shè)無向圖 G=(V, E)和 G39。 是 G 的生成樹，則下面的說法中錯誤的是（ ）。 為 G 的極小連通子圖且 V = V39。A 6 B 7 C 8 D 9【解答】D【分析】n 個頂點的無向圖中，邊數(shù) e≤n(n1)/2，將 e=28 代入，有 n≥8，現(xiàn)已知無向圖非連通，則 n=9