數(shù)據(jù)結(jié)構(gòu)山大專升本練習(xí)題模擬題參考答案課件

1、年級_；層次_；專業(yè)_；姓名_數(shù)據(jù)結(jié)構(gòu)模擬卷一、選擇題1. 在一個長度為 n的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（ A ）。A. O(n)B. O(n/2)C. O(1)D. O(n2)2. 帶頭結(jié)點(diǎn)的單鏈表 first為空的判定條件是：（ B ）。A. first = NULL;B. first-link = NULL;D. first != NULL;C. first-link = first;3. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C線性結(jié)構(gòu)、非線性結(jié)構(gòu)B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)4. 在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實(shí)際

2、參數(shù)的值。在傳值參數(shù)情形，需為對應(yīng)形式參數(shù)分配空間，以存放實(shí)際參數(shù)的副本；在引用參數(shù)情形，需保存實(shí)際參數(shù)的（ D），在被調(diào)用程序中可直接操縱實(shí)際參數(shù)。B. 副本 C. 返回地址 D. 地址A. 空間5. 以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ DA廣義表 B. 二叉樹6. 以下屬于邏輯結(jié)構(gòu)的是（ CA順序表 B. 哈希表）。C. 稀疏矩陣D.串）。C.有序表D. 單鏈表7. 對于長度為 9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（ C）的值除以 9。A. 20B. 18C. 25D. 228. 在有向圖中每個頂點(diǎn)的度等于該頂點(diǎn)的（ C）。A. 入度B. 出度C. 入度與

3、出度之和D. 入度與出度之差9. 在基于排序碼比較的排序算法中，（ CO(nlog2n)。）算法的最壞情況下的時間復(fù)雜度不高于A. 起泡排序10. 當(dāng)?shù)闹递^小時，散列存儲通常比其他存儲方式具有（ BA. 較慢 B. 較快 C. 相同 D.不同B. 希爾排序C. 歸并排序D. 快速排序）的查找速度。1年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_二、填空題1. 二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)組元素最多有_2_個直接前驅(qū)（或直接后繼）。2. 將一個 n階三對角矩陣 A的三條對角線上的元素按行壓縮存放于一個一維數(shù)組 B中，A00存放于 B0中。對于任意給定數(shù)組元素 BK，它應(yīng)是 A中

4、第_(K+1)/3 _行的元素。3. 鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結(jié)點(diǎn)，只需改變相關(guān)結(jié)點(diǎn)的_指針_域的值。4. 在一個鏈?zhǔn)綏Ｖ?，若棧頂指針等?NULL則為_空棧_。5. 主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的_返回_地址。6. 在一棵樹中，_葉子_結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)。7. 一棵樹的廣義表表示為 a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，結(jié)點(diǎn) f的層數(shù)為_3_。假定根結(jié)點(diǎn)的層數(shù)為 0。8. 在一棵 AVL樹（高度平衡的二叉搜索樹）中，每個結(jié)點(diǎn)的左子樹高度與右子樹高度之差的

5、絕對值不超過_1_。9. n (n0) 個頂點(diǎn)的無向圖最多有_n(n-1)/2_條邊，最少有_0_條邊。10. 在索引存儲中，若一個索引項(xiàng)對應(yīng)數(shù)據(jù)對象表中的一個表項(xiàng)（記錄），則稱此索引為_稠密_索引，若對應(yīng)數(shù)據(jù)對象表中的若干個表項(xiàng)，則稱此索引為_稀疏_索引。三、判斷題1. 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的(對)2. 鏈?zhǔn)酱鎯υ诓迦牒蛣h除時需要保持物理存儲空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序(錯)3. 在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針(對)4. 通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高(錯)5.

6、一個廣義表的表尾總是一個廣義表(對)6. 當(dāng)從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止(對)7. 對于一棵具有 n個結(jié)點(diǎn)，其高度為 h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為O(h)( 錯)8. 存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個數(shù)有關(guān)，而且與圖的邊數(shù)也有2年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_關(guān)(錯)9. 直接選擇排序是一種穩(wěn)定的排序方法(錯)10. 閉散列法通常比開散列法時間效率更高(錯)四、運(yùn)算題1. 設(shè)有一個 1010的對稱矩陣 A，將其下三角部分按行存放在一個一維數(shù)組 B中

7、，A00存放于 B0中，那么 A85存放于 B中什么位置。2. 這是一個統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的值等于給定值 x的結(jié)點(diǎn)數(shù)的算法，其中 while循環(huán)有錯，請重新編寫出正確的 while循環(huán)。int count ( ListNode * Ha, ElemType x ) / Ha為不帶頭結(jié)點(diǎn)的單鏈表的頭指針int n = 0;while ( Ha-link != NULL ) Ha = Ha-link;if ( Ha-data = x ) n+;return n;3. 已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C,

8、 B, A, E, F, D, I, H, J, G后序序列：4. 已知一個有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 順序存儲于一維數(shù)組 a12中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素 34, 56, 58, 63, 94時的比較次數(shù)。3456586394元素值比較次數(shù)5. 設(shè)散列表為 HT17, 待插入關(guān)鍵碼序列為 Jan, Feb, Mar, Apr, May, June, July, Aug,3年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_Sep, Oct, Nov, Dec ，散列函數(shù)為 H (key) =

9、 i 2，其中，i是關(guān)鍵碼第一個字母在字母表中的序號。現(xiàn)采用線性探查法解決沖突。字母序號字母A1NB2OC3PD4QE5RF6SG7TH8UI9VJKLM10 11 12 13WXYZ序號 14 15 16 17 18 19 20 21 22 23 24 25 26(1)試畫出相應(yīng)的散列表；(2)計(jì)算等概率下搜索成功的平均搜索長度；參考答案：1. 根據(jù)題意，矩陣 A中當(dāng)元素下標(biāo) I與 J滿足 IJ時，任意元素 AIJ在一維數(shù)組 B中的存放位置為 I * (I + 1) / 2 + J，因此，A85在數(shù)組 B中位置為8 * (8 + 1) / 2 + 5 = 41。2.while ( Ha !=

10、 NULL ) if ( Ha-data = x ) n+;Ha = Ha-link;3. 后序序列：C, B, F, E, I, J, H, G, D, A4. 判斷結(jié)果3402561583634944元素值比較次數(shù)/對 1個給 1分，全對給 8分5.H(Jan) = 102 = 5，成功.H(Feb) = 62 = 3，成功.4年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_H(Mar) = 132 = 6，成功.H(Apr) = 12 = 0，成功.H(May) = 132 = 6，= 7，成功， H(June) = 102 = 5，= 6，= 7，=8，成功.H(July) = 1

11、02 = 5，= 6，= 7，= 8，= 9，成功.H(Aug) = 12 = 0，= 1，成功.H(Sep) = 192 = 9，= 10，成功.H(Oct) = 152 = 7，= 8，= 9，= 10，= 11，成功.H(Nov) = 142 = 7，= 8，= 9，= 10，= 11，= 12，成功.H(Dec) = 42 = 2，成功.(1)相應(yīng)的散列表(6分)，錯一個存儲位置扣1分，最多扣6分。012345678910111213Apr Aug Dec FebJan Mar May Jun Jul Sep Oct Novey(1) (2)(1)(1)(2) (4) (5) (2)

12、(5) (6)(1)(1)(2) 搜索成功的平均搜索長度為1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12五、算法設(shè)計(jì)題已知二叉樹中的結(jié)點(diǎn)類型用 BinTreeNode表示，被定義為:struct BTreeNode char data; BinTreeNode *leftChild, *rightChild; ;其中 data（2分）為結(jié)點(diǎn)值域，leftChild和 rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù) BT初始指向

13、這棵二叉樹的根結(jié)點(diǎn)。int BTreeCount ( BinTreeNode* BT );數(shù)據(jù)結(jié)構(gòu)模擬卷一、單項(xiàng)選擇題1以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（CA循環(huán)隊(duì)列 B. 鏈表 C. 哈希表2以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ ）。）。D.棧D5年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_A廣義表3以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（A棧 B. 哈希表 C. 線索樹4在下面的程序段中，對 x的賦值語句的頻度為（B. 二叉樹C. 稀疏矩陣D.串B）。D. 雙向鏈表C）。FOR i:=1 TOFOR j:=1 TOx:=x+1;nnDODOA O(2n)BO(n)CO(n2)DO(lo

14、g2n)5.下面關(guān)于線性表的敘述中，錯誤的是哪一個（B）。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。6線性表是具有 n個（C）的有限序列（n0）。C數(shù)據(jù)元素A表元素 B字符D數(shù)據(jù)項(xiàng)E信息項(xiàng)7.若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲方式最節(jié)省時間。A順序表 B雙鏈表8.某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用）存儲方式最節(jié)省運(yùn)算時間。A單鏈表 B僅有頭指針的單循環(huán)

15、鏈表AC帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D單循環(huán)鏈表（DC雙鏈表D僅有尾指針的單循環(huán)鏈表9.下面給出的四種排序法中(D )排序法是不穩(wěn)定性排序法。C. 二路歸并A. 插入B. 冒泡D. 堆積10.下列排序算法中，其中（A. 堆排序，冒泡排序D）是穩(wěn)定的。B. 快速排序，堆排序D. 歸并排序，冒泡排序C. 直接選擇排序，歸并排序11.已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E，后綴形式為 ABC*+DE/-，其前綴形式為)。A-A+B*C/DE(DB. -A+B*CD/EC-+*ABC/DED. -+A*BC/DE6年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_12.算術(shù)表達(dá)式 a+b*（c+d

16、/e）轉(zhuǎn)為后綴表達(dá)式后為（B）。Dabcde*/+Aab+cde/*Babcde/+*+Cabcde/*+/+C*-EFGABD二、填空題，在橫線處填寫合適內(nèi)容1. 數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)包括順序、_鏈接_、索引和散列等四種。2. 在程序運(yùn)行過程中可以擴(kuò)充的數(shù)組是_動態(tài)_分配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。3. 在鏈表中進(jìn)行插入和刪除操作的效率比在順序存儲結(jié)構(gòu)中進(jìn)行相同操作的效率高。4. 棧是一種限定在表的一端進(jìn)行插入和刪除的線性表，又被稱為_后出先進(jìn)_表。5. 如果一個對象部分地包含自己，或自己定義自己，則稱這個對象是_遞歸_的對象。6. 一 棵 樹 的 廣 義 表 表 示 為 a(

17、b(c,d(e,f),g(h),i(j,k(x,y)， 結(jié) 點(diǎn) f 的 層 數(shù) 為_3_。假定樹根結(jié)點(diǎn)的層數(shù)為 0。7. 一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點(diǎn)肯定沒有_右_子女。8. 向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_左子樹_上。9.設(shè)圖 G=(V,E)，V=1,2,3,4,E=,，從頂點(diǎn) 1出發(fā)，對圖 G進(jìn)行廣度優(yōu)先搜索的序列有_2_種。10. 每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做_交換_排序。11. 快速排序在平均情況下的空間復(fù)雜度為_O(log2n)_。

18、12. 若對長度 n=10000的線性表進(jìn)行二級索引存儲，每級索引表中的索引項(xiàng)是下一級 20個表項(xiàng)的索引，則一級索引表的長度為_500_。三、判斷題1.在順序表中進(jìn)行順序搜索時，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序7年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_排列存放，則可得到最小的平均搜索長度（ 對）2. 在二叉搜索樹中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越小的結(jié)點(diǎn)離樹根越近，則得到的是最優(yōu)二叉搜索樹（錯）3. 對于 AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動都能使整個工程提前完成（錯4. 直接選擇排序是一種穩(wěn)定的排序方法（ 錯）5. 閉散列法通常比開散列法時間效率更高（ 錯）6

19、.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的（對7.順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問（ 對）8.在一個順序存儲的循環(huán)隊(duì)列中, 隊(duì)頭指針指向隊(duì)頭元素的后一個位置（錯9.用非遞歸方法實(shí)現(xiàn)遞歸算法時一定要使用遞歸工作棧（ 錯）10.在一棵二叉樹中，假定每個結(jié)點(diǎn)只有左子女，沒有右子女，對它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果（對四、運(yùn)算題）1. 設(shè)有一個二維數(shù)組 A1020，按行存放于一個連續(xù)的存儲空間中，A00的存儲地址是 200，每個數(shù)組元素占 1個存儲字，則 A62的存儲字地址是多少。A62的存儲字地址：2. 已知一棵二叉樹的中序和后序序列如

20、下，求該二叉樹的高度（假定空樹的高度為-1）和度為 2、度為 1及度為 0的結(jié)點(diǎn)個數(shù)。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a求解一下問題：高度：度為 2的結(jié)點(diǎn)數(shù)：度為 0的結(jié)點(diǎn)數(shù)：度為 1的結(jié)點(diǎn)數(shù)：3. 假定一組記錄為(36,75,83,54,12,67,60,40)，將按次序把每個結(jié)點(diǎn)插入到初始為空的一棵 AVL樹中，請回答在插入時需進(jìn)行“左單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，“不調(diào)整”的結(jié)點(diǎn)數(shù)各是多少？8年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_左單旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：不調(diào)整結(jié)

21、點(diǎn)個數(shù)：右單旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：4. 已知一個帶權(quán)圖的頂點(diǎn)集 V和邊集 G分別為：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;試根據(jù)迪克斯特拉(Dijkstra)算法求出從頂點(diǎn) 0到其余各頂點(diǎn)的最短路徑，在下面填寫對應(yīng)的路徑長度。頂點(diǎn)：01234560路徑長度：5. 已知一個數(shù)據(jù)表為36,25,25*,62,40,53，請寫出在進(jìn)行快速排序的過程中每次劃分后數(shù)據(jù)表的變化。(0) 36 25 25* 62 40 53(1

22、)(2)(3)參考答案：1. A62的存儲字地址：322答案說明：按行存儲時，計(jì)算 Aij地址的公式為9年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_LOC(i,j)=LOC(0,0)+(i*n+j)*d其中首地址 LOC(0,0)=200, 每個數(shù)組元素的存儲占用數(shù) d=1, 二維數(shù)組的列數(shù) n=20，根據(jù)題意，元素 A62的存儲地址為LOC(6,2)=200+(6*20+2)*1=3222.高度：4度為 2的結(jié)點(diǎn)數(shù)：3度為 1的結(jié)點(diǎn)數(shù)：3度為 0的結(jié)點(diǎn)數(shù)：43.左單旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：1右單旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：0先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：1先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個數(shù)：0不調(diào)整結(jié)點(diǎn)個數(shù)：64. 錯 1個

23、數(shù)值扣 2分，最多扣全部 8分。頂點(diǎn)：01234560161014252131路徑長度：5.(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53(2) 25* 25 36 53 40 62(3) 25* 25 36 40 53 62五、算法設(shè)計(jì)題1設(shè)有一個表頭為 first的單鏈表。試設(shè)計(jì)一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)按逆序鏈接。10年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_參考答案：解答 1template void List : : Tnerse() if (first= NULL )return ;ListNode * p=fi

24、rstlink ; , *pr =NULL ;While (p !=NULL ) Firstlink =pr ;Pr =first ;first =p ;p =plink;first -link =pr ;解答 2template void List : : Tnerse() ListNode * p , *head = new ListNode ( ) ;While (first ! = NULL ) P=first ;first = firstlink;plink =headlink ; headlink =p;first = headlink ; delete head ;數(shù)據(jù)結(jié)構(gòu)模擬卷

25、一、單項(xiàng)選擇題1數(shù)據(jù)結(jié)構(gòu)是（D）。A一種數(shù)據(jù)類型B數(shù)據(jù)的存儲結(jié)構(gòu)C一組性質(zhì)相同的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是（B）。A辨別數(shù)據(jù)結(jié)構(gòu)的合理性B評價算法的效率C研究算法中輸入與輸出的關(guān)系D鑒別算法的可讀性3在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（D）。11年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_A插入C排序B刪除D定位4若進(jìn)棧序列為 1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的出棧序列為（B）。A3，2，6，1，4，5C1，2，5，3，4，6B3，4，2，1，6，5D5，6，4，2，3，15設(shè)串 s

26、l=Data Structures with Java,s2=it，則子串定位函數(shù) index(s1,s2)的值為（D）。A15C17B16D186二維數(shù)組 A89按行優(yōu)先順序存儲，若數(shù)組元素 A23的存儲地址為 1087，A47的存儲地址為 1153，則數(shù)組元素 A67的存儲地址為（A）。A1207C1211B1209D12137在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）。A隊(duì)列B棧C線性表D有序表8在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（B）。A不一定相同C都不相同B都相同D互為逆序9若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的

27、（C）。A層次遍歷算法C中序遍歷算法B前序遍歷算法D后序遍歷算法10若用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數(shù)為（A）。A圖中每個頂點(diǎn)的入度C圖中弧的條數(shù)B圖中每個頂點(diǎn)的出度D圖中連通分量的數(shù)目11圖的鄰接矩陣表示法適用于表示（C）。A無向圖C稠密圖B有向圖D稀疏圖12在對 n個關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，12年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_則在進(jìn)行第 i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為（D）。AiBi+1Cn-iDn-i+1二、填空題1棧是_特殊_的線性表，其運(yùn)算遵循_后進(jìn)先出_的原則。2_棧_是限定僅在表尾進(jìn)行

28、插入或刪除操作的線性表。3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3，1，2_。4二叉樹由_根結(jié)點(diǎn)、 左子樹、右子樹_三個基本單元組成。5 在 二 叉 樹 中 ， 指 針 p 所 指 結(jié) 點(diǎn) 為 葉 子 結(jié) 點(diǎn) 的 條 件 是 _P-Lchild=NULL &P-Rchild=NULL_。6具有 256個結(jié)點(diǎn)的完全二叉樹的深度為_9_。7已知一棵度為 3的樹有 2個度為 1的結(jié)點(diǎn)，3個度為 2的結(jié)點(diǎn)，4個度為 3的結(jié)點(diǎn)，則該樹有_12_個葉子結(jié)點(diǎn)。8若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的_和記錄的_移動_。9.分別采用堆排序，快速排序，冒泡排序和歸

29、并排序，對初態(tài)為有序的表，則最省時間的是_算法，最費(fèi)時間的是_算法，最費(fèi)時間的是_快速排序_算法。10不受待排序初始序列的影響，時間復(fù)雜度為 O(N2)的排序算法是_選擇排序_，在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是_歸并排序_。三、解答題1某廣義表的表頭和表尾均為（a,(b,c)），畫出該廣義表的圖形表示。2已知二叉樹的先序序列和中序序列分別為 HDACBGFE和 ADCBHFEG。（1）畫出該二叉樹；（2）畫出與（1）求得的二叉樹對應(yīng)的森林。3已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：13年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_依此鄰接

30、表從頂點(diǎn) C出發(fā)進(jìn)行深度優(yōu)先遍歷。（1）畫出由此得到的深度優(yōu)先生成樹；（2）寫出遍歷過程中得到的從頂點(diǎn) C到其它各頂點(diǎn)的帶權(quán)路徑及其長度。參考答案：1.2.(1)14年級_；層次_；專業(yè)_年級_；層次_；專業(yè)_；姓名_(2)3.(1)(2)頂點(diǎn) C到頂點(diǎn) A的帶權(quán)路徑為（C,D,B,A），其長度為 8+20+11=39頂點(diǎn) C到頂點(diǎn) B的帶權(quán)路徑為（C,D,B），其長度為 8+20=28頂點(diǎn) C到頂點(diǎn) D的帶權(quán)路徑為（C,D），其長度為 8頂點(diǎn) C到頂點(diǎn) E的帶權(quán)路徑為（C,D,B,F,E），其長度為 8+20+9+14=51頂點(diǎn) C到頂點(diǎn) F的帶權(quán)路徑為（C,D,B,F），其長度為 8+20+9=37四、算法設(shè)計(jì)題1已知中序線索二叉樹 T右子樹不空。設(shè)計(jì)算法，將 S所指的結(jié)點(diǎn)作為 T的右子樹中的一個葉子結(jié)點(diǎn)插入進(jìn)去，并使之成為 TT的右子樹的（中序序列）第一個結(jié)點(diǎn)（同時要修改相應(yīng)的線索關(guān)系）。2寫出在中序線索二叉樹里；找指定結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法。參考答案：1.答 案