【正文】 雜度用大Ｏ記號表示為：常數(shù)階( )、對數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )。【解答】表長的一半，表長，該元素在表中的位置⑵ 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）。【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題⑴ 線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。⑼ 對于n個元素組成的線性表，建立一個有序單鏈表的時間復(fù)雜度是（ ）。A pnext=s。3. 判斷題⑴ 線性表的邏輯順序和存儲順序總是一致的。⑴ 若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹??！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點的元素值與后繼結(jié)點的元素值不相等，則指針后移；否則刪除該后繼結(jié)點。在單鏈表中查找第一個大于mink的結(jié)點和第一個小于maxk的結(jié)點，再將二者間的所有結(jié)點刪除。【解答】數(shù)據(jù)元素的類型是一個字符⑽ 兩個串相等的充分必要條件是（ ）。為這兩個棧分配空間的最佳方案是（ ）?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個數(shù)。9. 算法設(shè)計⑴ 假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。A edcba B cdeba C debca D abcde 【解答】C3．從棧頂指針為top的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行（ ）?！窘獯稹縟+41【分析】元素A[8][5]的前面共存儲了(1+2+…+8)+5=41個元素?！窘獯稹垮e?！窘獯稹吭O(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲，其空間復(fù)雜度為Ｏ(mn)；因為要將所有的矩陣元素累加起來，所以，需要用一個兩層的嵌套循環(huán)，其時間復(fù)雜度亦為Ｏ(mn)。A (d) B (c,(d)) C b,(c,(d)) D (b,(c,(d)))【解答】D6．設(shè)有三對角矩陣Ann（行、列下標均從0開始），將其三條對角線上的元素逐行存于數(shù)組B[3n2]中，使得B[k]=aij求：⑴ 用i, j表示k的下標變換公式；⑵ 用k表示i, j的下標變換公式。⑺ 已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。A 2k2+1 B 2k1 C 2k 1 D 2k–1 1 E 2k+1 F 2k+1 1 G 2k 1+1 H 2k【解答】B，C，A【分析】深度為k的完全二叉樹最少結(jié)點數(shù)的情況應(yīng)是第k層上只有1個結(jié)點，最多的情況是滿二叉樹，編號最小的葉子應(yīng)該是在結(jié)點數(shù)最少的情況下，葉子結(jié)點的編號?！窘獯稹繉?。在前序遍歷序列中第一個訪問的一定是根結(jié)點，即二叉樹的根結(jié)點是a1，在中序遍歷序列中查找值為a1的結(jié)點，假設(shè)為bi，則a1=bi且b1b2… bi1是對根結(jié)點a1的左子樹進行中序遍歷的結(jié)果，前序遍歷序列a2a3… ai是對根結(jié)點a1的左子樹進行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3… ai和中序遍歷序列b1b2… bi1唯一確定了根結(jié)點的左子樹，同樣可證前序遍歷序列ai+1ai+2… ak+1和中序遍歷序列bi+1bi+2… bk+1唯一確定了根結(jié)點的右子樹。算法如下：【解答】對二叉樹進行后序遍歷，在遍歷過程中訪問某結(jié)點時交換該結(jié)點的左右子樹。A 左線索標志為0，右線索標志為1 B 左線索標志為1，右線索標志為0C 左、右線索標志均為0 D 左、右線索標志均為1【解答】C9．對于一棵具有n個結(jié)點的樹，其所有結(jié)點的度之和為（ ）。15．設(shè)計算法，判斷一棵二叉樹是否為完全二叉樹?！窘獯稹浚?n2)，Ｏ(elog2e)【分析】Prim算法采用鄰接矩陣做存儲結(jié)構(gòu)，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數(shù)組做存儲結(jié)構(gòu)，適合于求稀疏圖的最小生成樹。A G39?！窘獯稹繉?。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長度相同。【解答】從源點v1到其他各頂點的最短路徑如下表所示。鄰接矩陣存儲結(jié)構(gòu)定義如下：const int MaxSize=10。同理可證起點v1的度不能大于1，只能為1。⑺ 若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必定存在。3. 判斷題⑴ 一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等。 =(V39。⑸ 已知一個有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（ ）。14．以孩子兄弟表示法作為存儲結(jié)構(gòu)，編寫算法求樹的深度。A n0=n21 B n0=n2 C n0=n2+1 D 沒有規(guī)律【解答】C5．一棵滿二叉樹中共有n個結(jié)點，其中有m個葉子結(jié)點，深度為h，則（ ）。⑺ 一棵具有n個結(jié)點的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進行前序遍歷。具體算法如下：⑵ 設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點。（其中，n0為終端結(jié)點數(shù)）【解答】因為在滿二叉樹中沒有度為1的結(jié)點，所以有：n=n0+n2 設(shè)B為樹中分枝數(shù)，則n=B+1所以B=n0 +n21再由二叉樹性質(zhì)：n0=n2+1代入上式有：B=n0+n011=2(n01)5．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。A 借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算B 將樹、森林按二叉樹的存儲方式進行存儲并利用二叉樹的算法解決樹的有關(guān)問題C 將樹、森林轉(zhuǎn)換成二叉樹D 體現(xiàn)一種技巧，沒有什么實際意義【解答】B3. 判斷題⑴ 在線索二叉樹中，任一結(jié)點均有指向其前趨和后繼的線索。A 空或只有一個結(jié)點 B 高度等于其結(jié)點數(shù)C 任一結(jié)點無左孩子 D 任一結(jié)點無右孩子【解答】B【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。⑸ 深度為k的二叉樹中，所含葉子的個數(shù)最多為（ ）?！窘獯稹縟+22，d+1412．一個nn的對稱矩陣，按行優(yōu)先或列優(yōu)先進行壓縮存儲，則其存儲容量為（　　 ）。如廣義表L=(( )，(a，b))的表頭為空表，但L不是空表。C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。A 不變 B top=0。8．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？【解答】不含任何字符的串稱為空串，其長度為零。【解答】錯。A 4321 B 1234 C 1432 D 3241【解答】B【分析】隊列的入隊順序和出隊順序總是一致的?！窘獯稹浚╮earfront+n）% n【分析】也可以是（rearfront）% n，但rearfront的結(jié)果可能是負整數(shù)，而對一個負整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會有所不同。編寫算法，將元素x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度?！窘獯稹坷脝窝h(huán)鏈表的特點，通過指針s可找到其前驅(qū)結(jié)點r以及r的前驅(qū)結(jié)點p，然后將結(jié)點r刪除，如圖211所示，具體算法如下：⑹ 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。⑶ 應(yīng)選用鏈接存儲結(jié)構(gòu)。⑸ 在單鏈表中，要取得某個元素，只要知道該元素所在結(jié)點的地址即可，因此單鏈表是隨機存取結(jié)構(gòu)。D sprior=p。 D pnext=s。⑺ 若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用（ ）存儲方法最節(jié)省運算時間。 delete q。while (x {x*=2?！窘獯稹克惴ǖ膫未a描述如下：算法的C++描述如下：分析算法，只有一層循環(huán)，共執(zhí)行n2次，所以，T(n)=O(n)。 　　　 【解答】⑴ 基本語句是k=k+10*i，共執(zhí)行了n2次，所以T(n)=O(n)?！窘獯稹垮e。【解答】自然語言，程序設(shè)計語言，流程圖，偽代碼，偽代碼 ⑺ 在一般情況下，一個算法的時間復(fù)雜度是（ ）的函數(shù)?！窘獯稹繂栴}規(guī)模 ⑻ 設(shè)待處理問題的規(guī)模為n，若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（ ），若為n*log25n，則表示成數(shù)量級的形式為（ ）。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 ⑵ 基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。學(xué)習(xí)自測及答案 1．順序存儲結(jié)構(gòu)的特點是（ ），鏈接存儲結(jié)構(gòu)的特點是（ ）。count++?！痉治觥坎僮魇疽鈭D如圖29所示：⑺ 一個具有n個結(jié)點的單鏈表，在指針p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）。A 單鏈表 B 循環(huán)雙鏈表 C單循環(huán)鏈表 　　D 帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 snext=q。 snext=pnext?！窘獯稹垮e。因為一個城市的設(shè)計和規(guī)劃涉及活動很多，需要經(jīng)常修改、擴充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符?！窘獯稹勘绢}是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復(fù)上述步驟；否則，找到插入位置，將x插入。⑻ 用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別是（ ）和（ ）。⑺ 棧和隊列的主要區(qū)別在于（ ）。這是隊空的判定條件，在循環(huán)隊列中要將隊空和隊滿的判定條件區(qū)別開。僅含空格的串稱為空格串，它的長度為串中空格符的個數(shù)。 C top=top1。⑵ 二維數(shù)組A中行下標從10到20，列下標從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A[10][5]的存儲地址是1000，則元素A[15][10]的存儲地址是（ ）。D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲。4．一個稀疏矩陣如圖44所示，寫出對應(yīng)的三元組順序表和十字鏈表存儲表示。【解答】n(n+1)/23．設(shè)n行n列的下三角矩陣A（行列下標均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲，則A[i][j]在數(shù)組S中的存儲位置是（ ）。【解答】2k1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。⑷ 線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（ 　　）?！窘獯稹垮e。【解答】證明采用歸納法。【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處?！窘獯稹堪凑疹}目要求，設(shè)置一個工作棧以完成對該樹的非遞歸算法，思路如下：① 每訪問一個結(jié)點，將此結(jié)點壓棧，查看此結(jié)點是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到左子樹為空。A n=h+m B h+m=2n C m=h1 D n=2h1【解答】D 6．對于完全二叉樹中的任一結(jié)點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（ ）?！窘獯稹坎捎眠f歸算法實現(xiàn)?！窘獯稹壳蟮趈列的所有元素之和⑹ 有向圖G用鄰接矩陣A[n][n]存儲，其第i行的所有元素之和等于頂點i的（ ）。, E39?！窘獯稹繉?。【解答】對。7．已知一個連通圖如圖66所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點v1出發(fā)對該圖進行遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。template struct AdjMatrix{ T?！窘獯稹堪碢rim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：9．對于圖68所示的帶權(quán)有向圖，求從源點v1到其他各頂點的最短路徑。⑻ 在AOE網(wǎng)中一定只有一條關(guān)鍵路徑?br /【解答】錯。⑵ 用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。 是G的生成樹，則下面的說法中錯誤的是（ ）?！窘獯稹壳靶?，棧，層序，隊列⑻ 對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復(fù)雜度為（ ），利用Kruskal算法求最小生成樹的時間復(fù)雜度為（ ）。具體算法如下：A 3 B 4 C 5 D 6【解答】C8．在線索二叉樹中，一個結(jié)點是葉子結(jié)點的充要條件為（ ）。具體算法如下：⑻ 編寫算法交換二叉樹中所有結(jié)點的左右子樹。為此，將前序遍歷算法中的訪問操作改為條件打印即可。當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結(jié)點，所以，a1= b1，可以唯一確定該二叉樹；假設(shè)當(dāng)n=k時，前序遍歷序列a1a2a3… ak和中序遍歷序列b1b2b3… bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時，前序遍歷序列a1a2a3… akak+1和中序遍歷序列b1b2b3… bk bk+1可唯一確定一棵二叉樹。⑵ 在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。⑸ 深度為k的完全二叉樹至少有（ ）個結(jié)點，至多有（ ）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（ ）?！窘獯稹?0【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子。【解答】Head(Head(Tail(Tail(LS))))5．廣義表(a, b, (c, (d)))的表尾是（ ）。5．已知A為稀疏矩陣，