山東大學(xué)網(wǎng)絡(luò)教育數(shù)據(jù)結(jié)構(gòu)A-C

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

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

3、排序算法中，（）算法的最壞情況下的時(shí)間復(fù)雜度不高于O（nlog 2n） 。A.起泡排序B.希爾排序C.歸并排序 D.快速排序）的查找速度。10 .當(dāng)“的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有（A.較慢B.較快C.相同 D.不同二、填空題1 .二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有 2 個(gè)直接前驅(qū)（或直接后繼）。2 .將一個(gè)n階三對(duì)角矩陣A的三條對(duì)角線上的元素按行壓縮存放于一個(gè)一維數(shù)組 B中， A00存放于B0中。對(duì)于任意給定數(shù)組元素BK,它應(yīng)是A中第【（K+1） /3】行的元素。3 .鏈表對(duì)于數(shù)據(jù)元素的插入和刪除不需移動(dòng)結(jié)點(diǎn)，只需改變相關(guān)結(jié)點(diǎn)的 指針 域的值。4 .在一個(gè)鏈?zhǔn)綏?/p>

4、中，若棧頂指針等于NULL則為一空棧。5 .主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用， 它們都需要利用棧保存調(diào)用后的返回 地址。6 .在一棵機(jī)中， 葉子結(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樹（高度平衡的二叉搜索樹）中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過1。9 . n （n > 0）個(gè)頂點(diǎn)的無向圖最多有 n（n-1）/2 條邊，最少有 0 條邊。10 .在索引存儲(chǔ)中，若一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)

5、對(duì)象表中的一個(gè)表項(xiàng)（記錄），則稱此索引為 稠密 索引，若對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的若干個(gè)表項(xiàng)，則稱此索引為 稀疏 索引。三、判斷題1 .數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的（對(duì)）2 .鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序（錯(cuò)）3 .在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針（對(duì)）4 .通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高（錯(cuò)）5 . 一個(gè)廣義表的表尾總是一個(gè)廣義表（對(duì)）6 .當(dāng)從一個(gè)小根堆（最小堆）中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后 再按條件把它逐層向下調(diào)整

6、，直到調(diào)整到合適位置為止（對(duì)）7 .對(duì)于一棵具有 n個(gè)結(jié)點(diǎn)，其高度為 h的二叉樹，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O(h)(錯(cuò))而且與圖的邊數(shù)也有8 .存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān),關(guān)(錯(cuò))9 .直接選擇排序是一種穩(wěn)定的排序方法(錯(cuò))10 .閉散列法通常比開散列法時(shí)間效率更高(錯(cuò))四、運(yùn)算題1 .設(shè)有一個(gè)10 10的對(duì)稱矩陣A,將其下三角部分按行存放在一個(gè)一維數(shù)組 存放于B0中，那么A85存放于B中什么位置。2 .這是一個(gè)統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)的算法，其中請(qǐng)重新編寫出正確的while循環(huán)。int count ( ListNode * Ha, Ele

7、mType 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, B, A, E, F, D, I, H, J, G后序序列：4 . 已知一個(gè)有序表 (15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )于一維數(shù)組a12中，根據(jù)折半搜索過程

8、填寫成功搜索下表中所給元素94時(shí)的比較次數(shù)。B 中，A00while循環(huán)有錯(cuò),順序存儲(chǔ)34, 56, 58, 63,3456586394元素值 比較次數(shù)5 .設(shè)散列表為 HT17,待插入關(guān)鍵碼序列為 Jan, Feb, Mar, Apr, May, June,July, Aug, Sep, Oct, Nov, Dec ,散列函數(shù)為 H (key) = i 2 ,其中，i 是關(guān)鍵碼第一個(gè)字母在字母表中的序號(hào)?，F(xiàn)采用線性探查法解決沖突。字母ABCDEFGHIJKLM序號(hào)12345678910111213字母NOPQRSTUVWXYZ序號(hào)14151617181920212223242526(1)試畫

9、出相應(yīng)的散列表;(2)計(jì)算等概率下搜索成功的平均搜索長度；參考答案：1.根據(jù)題意，矩陣 A中當(dāng)元素下標(biāo)I與J滿足I >J時(shí)，任意元素 AIJ在一維數(shù)組B中的存放位置為I * (I + 1) / 2 + J ,因此，A85在數(shù)組B中位置為8 * (8 + 1) / 2 + 5 = 41。2 .while ( Ha != NULL ) if ( Ha->data = x ) n+;Ha = Ha->link;3 .后序序列：C, B, F, E, I, J, H, G, D, A4.3456586394021344元素值比較次數(shù)/對(duì)1個(gè)給1分，全對(duì)給8分AprAugDecFebJ

10、anMarMayJun eJulySepOctNov067(1)(2)(2)(4)(5)(2)(5)(6)1112138910123455.H(Jan)=102H(Feb) =62 = 3 ,成功.H(Mar)=132H(Apr) =1 2 = 0 ,成功.H(May)=132H(June) =10 2 = 5 , = 6 ,功.H(July)=H(Aug)=H(Sep) =19 2 = 9H(Oct)=11 ,成功.H(Nov)=11 , = 12 ,成功.H(Dec)=42 = 2 ,成功.相應(yīng)的散列表(6分)，錯(cuò)一個(gè)存儲(chǔ)位置扣1分，最多扣6分。(2)搜索成功的平均搜索長度為1/12 *

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

12、 BT );解:int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0;else return BTreeCount ( BT->leftChild ) + BTreeCount(BT->rightChild )+ 1數(shù)據(jù)結(jié)構(gòu)模擬卷、單項(xiàng)選擇題1 .以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（）。A.循環(huán)隊(duì)列B. 鏈表C.哈希表 D. 棧2 .以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）。A.廣義表 B. 二叉樹 C. 稀疏矩陣D.串3 .以下那一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（）。A.棧B.哈希表 C. 線索樹 D.雙向鏈表4 .在下

13、面的程序段中，對(duì)x的賦值語句的頻度為（）。FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A. O（2n） B . O（n）C. O（n2）D . O（log J）5 .下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)（）。A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。6 .線性表是具有 門個(gè)（）的有限序列（n>0）。A.表元素 B .字符C.數(shù)據(jù)元素D .數(shù)據(jù)項(xiàng) E .信息項(xiàng)則利7 .若某線性表最常用的操作是存取任一指

14、定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算,9 .下面給出的四種排序法中（）A.插入 B. 冒泡10 .下列排序算法中，其中（A.堆排序，冒泡排序C.直接選擇排序，歸并排序11 .已知一算術(shù)表達(dá)式的中綴形式為A. -A+B*C/DE B. -A+B*CD/E C-+*ABC/DED. -+A*BC/DE用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表 B .雙鏈表 C .帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D .單循環(huán)鏈表8 .某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表 B .僅有頭指針的單循環(huán)鏈表C .雙鏈表D.僅有尾指針的單循環(huán)鏈表排序法是不穩(wěn)定性

15、排序法。C.二路歸并D.堆積）是穩(wěn)定的。B.快速排序，堆排序D.歸并排序，冒泡排序A+B*C-D/E,后綴形式為 ABC*+DE/-,其前綴形式為12.算術(shù)表達(dá)式a+b* （c+d/e ）轉(zhuǎn)為后綴表達(dá)式后為（）。A. ab+cde/*B . abcde/+*+C . abcde/*+ D . abcde*/+二、填空題，在橫線處填寫合適內(nèi)容1 .數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、鏈接、索引和散列等四種。2 .在程序運(yùn)行過程中可以擴(kuò)充的數(shù)組是 動(dòng)態(tài) 分配的數(shù)組。這種數(shù)組在聲明它時(shí)需要使用數(shù)組指針。3 .在鏈表中進(jìn)行插入和刪除操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率4 .棧是一種限定在表的一端進(jìn)行

16、插入和刪除的線性表，又被稱為 后進(jìn)先出 表。5 .如果一個(gè)對(duì)象部分地包含自己，或自己定義自己，則稱這個(gè)對(duì)象是 遞歸 的對(duì)象。6 . 一棵樹的廣義表表示為a（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)換成對(duì)應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點(diǎn)肯定沒有 右 子女。8 .向一棵二叉搜索樹中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根 結(jié)點(diǎn)的 左子樹 上。9 .設(shè)圖 G=（V,E） , V=1,2,3,4,E=<1,2>,<1,3>,<2,4>,<3,4&g

17、t;，從頂點(diǎn) 1 出發(fā)，對(duì)圖 G進(jìn)行廣度優(yōu)先搜索的序列有 2 種。10 .每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做 交換 排序。11 .快速排序在平均情況下的空間復(fù)雜度為 O （log2n） 。12 .若對(duì)長度n=10000的線性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí)20個(gè)表項(xiàng)的索引，則一級(jí)索引表的長度為 500。三、判斷題1 .在順序表中進(jìn)行順序搜索時(shí)，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長度（ 對(duì)）2 .在二叉搜索樹中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越小的結(jié)點(diǎn)離樹根越近，則得到的

18、是最優(yōu)二叉搜索樹（ 錯(cuò)）3 .對(duì)于AOER絡(luò)，加速任一關(guān)鍵活動(dòng)都能使整個(gè)工程提前完成（ 錯(cuò)）4 .直接選擇排序是一種穩(wěn)定的排序方法（ 錯(cuò)）5 .閉散列法通常比開散列法時(shí)間效率更高（ 錯(cuò)）6 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的（對(duì)）7 .順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問（對(duì)）8 .在一個(gè)順序存儲(chǔ)白循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置（ 錯(cuò)）9 .用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)一定要使用遞歸工作棧（ 錯(cuò)）10 .在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果（ 對(duì)）四、運(yùn)算題1 .設(shè)有

19、一個(gè)二維數(shù)組 A1020,按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200,每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A62的存儲(chǔ)字地址是多少。A62 的存儲(chǔ)字地址:2 .已知一棵二叉樹的中序和后序序列如下，求該二叉樹的高度(假定空樹的高度為-1)和度為2、度為1及度為0的結(jié)點(diǎn)個(gè)數(shù)。中序序歹 U： c,b,d,e,a,g,i,h,j,f后序序歹 U： c,e,d,b,i,j,h,g,f,a求解一下問題：高度：度為2的結(jié)點(diǎn)數(shù)：度為1的結(jié)點(diǎn)數(shù)：度為0的結(jié)點(diǎn)數(shù)：3 .假定一組記錄為(36,75,83,54,12,67,60,40),將按次序把每個(gè)結(jié)點(diǎn)插入到初始為空的一棵AVL樹中，請(qǐng)回答在插入時(shí)需進(jìn)行“左

20、單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，“不調(diào)整”的結(jié)點(diǎn)數(shù)各是多少？左單旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：右單旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：不調(diào)整結(jié)點(diǎn)個(gè)數(shù)：4 .已知一個(gè)帶權(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)的最短路徑，在下面填寫對(duì)應(yīng)的路徑長度。頂點(diǎn)： 0123 4560路徑長度:5.已知一個(gè)數(shù)據(jù)表為

21、36,25,25*,62,40,53，請(qǐng)寫出在進(jìn)行快速排序的過程中每次劃分后數(shù)據(jù)表的變化。(0) 36 25 25* 62 40 53(2)參考答案：1. A62的存儲(chǔ)字地址：322答案說明：按行存儲(chǔ)時(shí)，計(jì)算 Aij地址的公式為LOC(i,j)=LOC(0,0)+(i*n+j)*d其中首地址LOC(0,0)=200,每個(gè)數(shù)組元素的存儲(chǔ)占用數(shù)d=1,二維數(shù)組的列數(shù) n=20,根據(jù)題意，元素A62的存儲(chǔ)地址為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)個(gè)數(shù)：1先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù):先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：

22、0不調(diào)整結(jié)點(diǎn)個(gè)數(shù)：64. 錯(cuò)1個(gè)數(shù)彳1扣2分，最多扣全部 8分。0161014252131頂點(diǎn)： 0123 45 6路徑長度: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è)有一個(gè)表頭為first的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)按逆序鏈接。參考答案：解答1template <class Type > void List <Type>: : Tnerse() if (first= NULL )re

23、turn ;ListNode <Type >* p=first link ; , *pr =NULL ;While (p !=NULL ) First f link =pr ;Pr =first ;first =p ;p =pf link;first ->link =pr ;解答2template <class Type > void List <Type>: : Tnerse() ListNode <Type >* p , *head = new ListNode <Type > ();While (first ! = NUL

24、L ) P=first ;first = firstf link;尸 link =head f link ; head f link =p;first = head flink ; delete head ;數(shù)據(jù)結(jié)構(gòu)模擬卷、單項(xiàng)選擇題1 .數(shù)據(jù)結(jié)構(gòu)是（）。A. 一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2 .算法分析的目的是（）。A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性B.評(píng)價(jià)算法的效率C.研究算法中輸入與輸出的關(guān)系D.鑒別算法的可讀性3 .在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（）。A.插入B.刪除C.排序D.定位4

25、.若進(jìn)棧序列為1,2, 3, 4, 5, 6,且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的出棧序列為（）。A. 3, 2, 6, 1, 4, 5C. 1,2, 5, 3, 4, 6B. 3, 4, 2, 1, 6, 5D. 5, 6, 4, 2, 3, 15.設(shè)串 sl= " Data Structureswith Java" ,s2= " it ",則子串定位函數(shù)index(s1,s2)值為（）。A. 15B. 16C. 17D. 186 .二維數(shù)組A89按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A23的存儲(chǔ)地址為1087, A47的存儲(chǔ)地址為1153,則數(shù)組元素A67的

26、存儲(chǔ)地址為（）。A.1207B,1209C.1211D.12137 .在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（）。A.隊(duì)列B.棧C.線性表D.有序表8 .在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（）。A.不一定相同B,都相同C.都不相同D.互為逆序9 .若采用孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（）。A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法10 .若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的1的個(gè)數(shù)為（）。A.圖中每個(gè)頂點(diǎn)的入度B.圖中每個(gè)頂點(diǎn)的出度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目11 .圖的鄰接矩陣表

27、示法適用于表示（）。A.無向圖B.有向圖C.稠密圖D.稀疏圖12 .在對(duì)n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元 素，則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個(gè)數(shù)為（）。A. iB. i+1C. n-iD. n-i+1二、填空題1 .棧是特殊 的線性表，其運(yùn)算遵循后進(jìn)先出 的原則。2 .棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3 . 一個(gè)棧的輸入序列是：1, 2, 3則不可能的棧輸出序列是 3, 1, 2。4 .二叉樹由(1)根節(jié)點(diǎn) ,(2)左子樹, (3)右子樹三個(gè)基本單元組成。5 .在二叉樹中，指針 p 所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是=p->lch

28、ild=NULL&&p->rchild=NULL 。6 .具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_9。7 .已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該 樹有 12 個(gè)葉子結(jié)點(diǎn)。8 .若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的比較和記錄的移動(dòng) 。9 .分別采用堆排序， 快速排序，冒泡排序和歸并排序，對(duì)初態(tài)為有序的表，則最省時(shí)間的是冒泡排序 算法，最費(fèi)時(shí)間的是快速排序算法。10 .不受待排序初始序列的影響，時(shí)間復(fù)雜度為O(M)的排序算法是選擇排序，在排序 算法的最后一趟開始之前， 所有元素都可能不在其最終位置上的排序算

29、法是歸并排序 C三、解答題1 .某廣義表的表頭和表尾均為(a,(b,c),畫出該廣義表的圖形表示。2 .已知二叉樹的先序序列和中序序列分別為HDACBGFE ADCBHFEG(1)畫出該二叉樹；(2)畫出與(1)求得的二叉樹對(duì)應(yīng)的森林。3 .已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：依此鄰接表從頂點(diǎn) C出發(fā)進(jìn)行深度優(yōu)先遍歷。(1)畫出由此得到的深度優(yōu)先生成樹；(2)寫出遍歷過程中得到的從頂點(diǎn)C到其它各頂點(diǎn)的帶權(quán)路徑及其長度。參考答案：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的右子樹中的 一個(gè)葉子結(jié)點(diǎn)插入進(jìn)去，并使之成為TT的右子樹的（中序序列）第一個(gè)結(jié)點(diǎn)（同時(shí)要修改相應(yīng)的線索關(guān)系）。2 .寫出在中序線索二叉樹里；找指定結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法。 參考答案：1 .答案：題目分析若使新插入的葉子結(jié)點(diǎn) S成T右子樹中序序列的第一個(gè)結(jié)點(diǎn)，則應(yīng)在 T 的右子樹中最左面的結(jié)