本科計(jì)算機(jī)信息第三學(xué)期數(shù)據(jù)結(jié)構(gòu)參考答案

1、數(shù)據(jù)結(jié)構(gòu)模擬卷A、選擇題1. 在一個(gè)長(zhǎng)度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（A）。2A.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;C.first->link=first;D.first!=NULL;3. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類(lèi)。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ù)情形，需為對(duì)應(yīng)形式參數(shù)分配空間

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

3、起泡（O（nlOgB2n）oD.快速排序10.當(dāng)a的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有（B）的查找速度。28A.較慢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)綏Ｖ校魲ｍ斨羔樀扔贜ULL則為空棧_。5. 主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)

4、用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的返回_地址。6. 在一棵樹(shù)中，_葉子_結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)。7. 一棵樹(shù)的廣義表表示為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樹(shù)（高度平衡的二叉搜索樹(shù)）中，每個(gè)結(jié)點(diǎn)的左子樹(shù)高度與右子樹(shù)高度之差的絕對(duì)值不超過(guò)1_。9. n（n>0）個(gè)頂點(diǎn)的無(wú)向圖最多有n（n-1）/2_條邊，最少有_0條邊。10. 在索引存儲(chǔ)中，若一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的一個(gè)表項(xiàng)（記錄），則稱此索引為_(kāi)稠密索引，若對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的若干個(gè)表項(xiàng)，則稱此索引為_(kāi)稀疏索引。三、判斷題1. 數(shù)組是一種復(fù)雜的

5、數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹(shù)形的（對(duì)）2. 鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序（錯(cuò)）3. 在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針（對(duì)）4. 通常遞歸的算法簡(jiǎn)單、易懂、容易編寫(xiě)，而且執(zhí)行的效率也高（錯(cuò)）5. 一個(gè)廣義表的表尾總是一個(gè)廣義表（對(duì)）6. 當(dāng)從一個(gè)小根堆（最小堆）中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止（對(duì)）7. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O（h）（錯(cuò)）8. 存儲(chǔ)圖的鄰接矩陣中

6、，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)（錯(cuò)）9. 直接選擇排序是一種穩(wěn)定的排序方法（錯(cuò)）10?閉散列法通常比開(kāi)散列法時(shí)間效率更高（錯(cuò)）設(shè)有一個(gè) 10 10 的B 中， A00四、運(yùn)算題1.對(duì)稱矩陣A,將其下三角部分按行存放在一個(gè)一維數(shù)組存放于B0中，那么A85存放于B中什么位置。解：根據(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。x 的結(jié)點(diǎn)數(shù)的算法，其中 while 循環(huán)有錯(cuò) ,2. 這是一個(gè)統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的值等于給定值請(qǐng)重新編寫(xiě)出正確的whi

7、le循環(huán)。intcount(ListNode*Ha,ElemTypex)/Ha為不帶頭結(jié)點(diǎn)的單鏈表的頭指針intn=0;while(Ha->link!=NULL)Ha=Ha->link;if(Ha->data=x)n+;returnn;解：while(Ha!=NULL)if(Ha->data=x)n+;Ha=Ha->link3. 已知一棵二叉樹(shù)的前序和中序序列，求該二叉樹(shù)的后序序列。前序序列:A,B,C,D,E,F,G,H,I,J已知一個(gè)有序 順序存儲(chǔ)于34, 56, 58, 63, 94中序序列：C,B,A,E,F,D,I,H,J,G后序序列：解：后序序列：C,

8、B,F,E,I,J,H,G,D,A4.表(15,26,34,39,45,56,58,63,74,76,83,94)元素值3456586394比較次數(shù)時(shí)的比較次數(shù)。解：判斷結(jié)果元素值比較次數(shù)34565863940213445.設(shè)散列表為 HT17,待插入關(guān)鍵碼序列為 Jan, Feb, Mar, Apr, May, June, July,Aug, Sep, Oct, Nov, Dec ,散列函數(shù)為 H (key) = li 2 ,其中，i是關(guān)鍵碼第字母ABCDEFGHIJKLM序號(hào)12345678910111213字母NOPQRSTUVWXYZ序號(hào)141516171819202122232425

9、26個(gè)字母在字母表中的序號(hào)?，F(xiàn)采用線性探查法解決沖突。(1)試畫(huà)出相應(yīng)的散列表H(Jan) = _10 2 = 5 ,成功.H(Mar) = I113 2 = 6 ,成功H(May) = I113 2 = 6 , = 7,成功,H(Feb) = _6 2 = 3 ,成功？H(Apr) = _1 2 = 0，成功.H(June) = I110 2 = 5 , = 6,=7,=8,成功H(July)= I110 2 = 5 ,H(Aug)= ：_1 2 = 0 ,=6, = 7 , =8, = 9 ,成功.1,成功？ H(Sep) = ll_19 2 = 9，=:10,成功H(Oct)= _15

10、2 = 7 , = = 8H(Nov)= I114 2 = 7, =8=9, =10, = 11 ,成功？=9, =10, = 11 , = 12 ,成功？H(Dec)= H4 2 = 2 ,成功.AprAugDecFebJanMarMayJuneJulySepOctNov相應(yīng)的散列表012345678910111213一維數(shù)組a12中，根據(jù)折半搜索過(guò)程填寫(xiě)成功搜索下表中所給元素(1)(5)(2)(5)(6)(2)計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度;1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12五、算法設(shè)計(jì)題已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為

11、：structBTreeNodechardata;BinTreeNode*leftChild,*rightChild;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)中結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹(shù)的根結(jié)點(diǎn)。intBTreeCount(BinTreeNode*BT);解：intBTreeCount(BinTreeNode*BT)if(BT=NULL)return0;2分elsereturnBTreeCount(BT->leftChild)+BTreeCount(BT-&

12、gt;rightChild)+1;4分?jǐn)?shù)據(jù)結(jié)構(gòu)模擬卷B一、單項(xiàng)選擇題1 .以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是(A.循環(huán)隊(duì)列B.鏈表C.哈希表D.2 .以下數(shù)據(jù)結(jié)構(gòu)中,哪一個(gè)是線性結(jié)構(gòu)(A.廣義表B.二叉樹(shù)C.稀疏矩陣D.3 .以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)?A.棧B.哈希表C.線索樹(shù)D.雙向鏈表4 .在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為(C)FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)5 .下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)(B)。A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B.線性表采用順序存儲(chǔ)，

13、便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。6 .線性表是具有n個(gè)(C)的有限序列(n>0)。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)7 .若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用(A)存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表8 .某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用(D)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B?僅有頭指針的單循環(huán)鏈表C?雙鏈表D?僅有尾指針的單循環(huán)鏈表9 .下面給出的四

14、種排序法中(D)排序法是不穩(wěn)定性排序法。A.插入B.冒泡C.二路歸弁D.堆積10.下列排序算法中，其中(DA.堆排序，冒泡排序C.直接選擇排序，歸弁排序)是穩(wěn)定的。B.快速排序，堆排序D. 歸弁排序，冒泡排序11.已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E ,后綴形式為 ABC*+DE/-,其前綴形式為(D )。A. -A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DEabcde/*+ D . abcde*/+A. ab+cde/* Babcde/+*+ C12.算術(shù)表達(dá)式a+b*(c+d/e)轉(zhuǎn)為后綴表達(dá)式后為(B)二、填空題，在橫線處填寫(xiě)合適內(nèi)容

15、1. 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、一鏈接一、索引和散列等四種。2. 在程序運(yùn)行過(guò)程中可以擴(kuò)充的數(shù)組是_動(dòng)態(tài)一分配的數(shù)組。這種數(shù)組在聲明它時(shí)需要使用數(shù)組指針。3. 在鏈表中進(jìn)行插入和刪除操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高。一后出先進(jìn)表。4. 棧是一種限定在表的一端進(jìn)行插入和刪除的線性表，又被稱為一遞歸的對(duì)象。5. 如果一個(gè)對(duì)象部分地包含自己，或自己定義自己，則稱這個(gè)對(duì)象是結(jié)點(diǎn)f的層數(shù)為6. 一棵樹(shù)的廣義表表示為a(b(c,d(e,f),g(h),i(j,k(x,y)3。假定樹(shù)根結(jié)點(diǎn)的層數(shù)為0。7. 一棵樹(shù)按照左子女-右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)，則該二叉樹(shù)中樹(shù)根結(jié)點(diǎn)肯定沒(méi)有右子女

16、。8 .向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的左子樹(shù)一上。9 .設(shè)圖G=(V,E),V=1,2,3,4,E=<1,2>,<1,3>,<2,4>,<3,4>,從頂點(diǎn)1出發(fā)，對(duì)圖G進(jìn)行廣度優(yōu)先搜索的序列有一2種。10.每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素,若出現(xiàn)逆序排列就交換它們的位置,這種排序方法叫做交換排序。11. 快速排序在平均情況下的空間復(fù)雜度為_(kāi)O（log2n）_。12. 若對(duì)長(zhǎng)度n=10000的線性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí)20個(gè)表項(xiàng)的索引，則一級(jí)索引表的長(zhǎng)度為_(kāi)500。

17、三、判斷題1. 在順序表中進(jìn)行順序搜索時(shí)，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長(zhǎng)度（對(duì)）2. 在二叉搜索樹(shù)中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越小的結(jié)點(diǎn)離樹(shù)根越近，則得到的是最優(yōu)二叉搜索樹(shù)（錯(cuò)）3. 對(duì)于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動(dòng)都能使整個(gè)工程提前完成（錯(cuò)）4. 直接選擇排序是一種穩(wěn)定的排序方法（錯(cuò)）5. 閉散列法通常比開(kāi)散列法時(shí)間效率更高（錯(cuò)）6. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的（對(duì)）7. 順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問(wèn)（對(duì)）8. 在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素

18、的后一個(gè)位置（錯(cuò)）9. 用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)一定要使用遞歸工作棧（錯(cuò)）10. 在一棵二叉樹(shù)中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒(méi)有右子女，對(duì)它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果（對(duì)）四、運(yùn)算題1. 設(shè)有一個(gè)二維數(shù)組A1020，按行存放于一個(gè)連續(xù)的存儲(chǔ)空間中，A00的存儲(chǔ)地址是200，每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)字，則A62的存儲(chǔ)字地址是多少。A62的存儲(chǔ)字地址：322答案說(shuō)明：按行存儲(chǔ)時(shí)，計(jì)算Aij地址的公式為L(zhǎng)OC（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ǔ)地址為L(zhǎng)OC

19、（6,2）=200+（6*20+2）*1=322-1 ）和2. 已知一棵二叉樹(shù)的中序和后序序列如下，求該二叉樹(shù)的高度（假定空樹(shù)的高度為度為2、度為1及度為0的結(jié)點(diǎn)個(gè)數(shù)。c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a求解一下問(wèn)題:高度：4度為2的結(jié)點(diǎn)數(shù)：3度為1的結(jié)點(diǎn)數(shù)：3度為0的結(jié)點(diǎn)數(shù)：43.按次序把每個(gè)結(jié)點(diǎn)插入到初始為空的一假定一組記錄為(36,75,83,54,12,67,60,40)棵AVL樹(shù)中，請(qǐng)回答在插入時(shí)需進(jìn)行“左單旋轉(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ù)：0

20、先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù):先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù):不調(diào)整結(jié)點(diǎn)個(gè)數(shù)：64.已知一個(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)的最短路徑,在下面填寫(xiě)頂點(diǎn):路徑長(zhǎng)度:0161014252131對(duì)應(yīng)的路徑長(zhǎng)度。5.已知一個(gè)數(shù)據(jù)表為36,25,25*,62,40,53在進(jìn)行快速排序的過(guò)程中每次劃分后數(shù)據(jù)表的變化。(0)362525*624053(2)2

21、5*253662405325*253653406225*2536405362五、算法設(shè)計(jì)題1設(shè)有一個(gè)表頭first的單鏈表。試設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)按逆序鏈接。解答1template<classType>voidList<Type>:Tnerse()if(first=NULL)return;ListNode<Type>*p=firstlink;,*pr=NULL;While(p!=NULL)Firsttlink=pr;Pr=first;first=p;p=ptlink;first->link=pr;解答2template<

22、;classType>voidList<Type>:Tnerse()ListNode<Type>*p,*head=newListNode<Type>();While(first!=NULL)P=first;first=firsttlink;ptlink=headtlink;headtlink=p;first=headtlink;deletehead;數(shù)據(jù)結(jié)構(gòu)模擬卷C一、單項(xiàng)選擇題1 數(shù)據(jù)結(jié)構(gòu)是（D）。A. 種數(shù)據(jù)類(lèi)型B. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是（B）。A.

23、辨別數(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)算是（D）。A.插入B.刪除C. 排序4. 若進(jìn)棧序列為 1D.定位3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（B）。A. 3 ， 2，6，1，4，B.3， 41 ， 6， 5C. 1， 2，5，3，4，D.5， 62， 3 ， 15.設(shè)串sl="DataStructureswithJava" ,s2= it,則子串定位函數(shù)index （s1,s2 ）的值為（A.15B.16C.17D.186.二維數(shù)

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

25、入度C.圖中弧的條數(shù)11.A.無(wú)向圖C.稠密圖B.圖中每個(gè)頂點(diǎn)的出度D.圖中連通分量的數(shù)目圖的鄰接矩陣表示法適用于表示（B.有向圖D.稀疏圖12?在對(duì)n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過(guò)程中，每一趟都要從無(wú)序區(qū)選出最小關(guān)鍵字元素,則在進(jìn)行第i趟排序之前，無(wú)序區(qū)中關(guān)鍵字元素的個(gè)數(shù)為（D）。A.iB.i+1C.n-iD.n-i+1二、填空題1. .棧是特殊的線性表，其運(yùn)算遵循后進(jìn)先出的原則。2. 棧一是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3. 一個(gè)棧的輸入序列是：1,2,3則不可能的棧輸出序列是_3,1,24.二叉樹(shù)由一根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)_三個(gè)基本單元組成。5.在二叉樹(shù)中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是P->Lchild=NULL&&P->Rchild=NULL6.具有256個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為97.已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)有12仝葉子結(jié)點(diǎn)&若不考慮基數(shù)排序，則在排序過(guò)程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的和記錄的移動(dòng)_。則最省9 .分別采用堆排序，快速排序，冒泡排序和歸弁排序，對(duì)初態(tài)為有序的表一冒泡排序一算法，最費(fèi)時(shí)間的是一快速排序一算法。10 .不受待排序初始序列的影響，度為0(M)的排序算法是_選擇排序,在排序算法的最后一趟開(kāi)始之前，所有元素都可能不在其最終位置上的排序算法是