數據結構導論試題和部分答案

1、全國2012年1月數據結構導論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)1 .結點按邏輯關系依次排列形成一條鎖鏈”的數據結構是()A.集合 B.線性結構C.樹形結構D.圖狀結構2 .下面算法程序段的時間復雜度為()for ( int i=0; i<m; i+)for ( int j=0; j<n; j+)a ijl =i*j；A. O(m2)B. O(n2)C. O(mn)D. O(m+n)3 .線性結構是()A.具有n (n>0個表元素的有窮序列B.具有n (n>Q個字符的有窮序列C.具有n (n>Q個結點的有窮序列D.具有

2、n (n>0個數據項的有窮序列4 .單鏈表中刪除由某個指針變量指向的結點的直接后繼，該算法的時間復雜度是()A. O(1)B. 0( . n )C. O(log 2n)D. O(n)5 .關于串的敘述，正確的是()A.串是含有一個或多個字符的有窮序列B.空串是只含有空格字符的串C.空串是含有零個字符或含有空格字符的串D.串是含有零個或多個字符的有窮序列6 .棧的輸入序列依次為1, 2, 3, 4,則不可能的出棧序列是 ()A.1243 B. 1432 C. 2134D.43127 .隊列是()A.先進先出的線性表B.先進后出的線性表C.后進先出的線性表D.隨意進出的線性表8.10階上三角

3、矩陣壓縮存儲時需存儲的元素個數為9 .深度為k (k>l)的二叉樹，結點數最多有 (10 .具有12個結點的二叉樹的二叉鏈表存儲結構中,()A.11B.56C.100D.101)A.2k 個B.(2k-1)個C.2k-1 個D.(2k+1)個空鏈域 NULL的個數為()A. 11B.13 C. 23 D.2511.具有n個頂點的無向圖的邊數最多為()A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)0 1 012.三個頂點V1,V2,V3的圖的鄰接矩陣為)A. 0 B. 1 C. 2 D.0 0 1 ，該圖中頂點V3的入度為(0 1 0313 .順序存儲的表格中有 6000

4、0個元素，已按關鍵字值升序排列，假定對每個元素進行查找的概率是相同的，且 每個元素的關鍵字值不相同。用順序查找法查找時，平均比較次數約為()A.20000 B.30000 C.40000D.6000014 .外存儲器的主要特點是()A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高15 .在待排數據基本有序的前提下，效率最高的排序算法是()A.直接插入排序 B.直接選擇排序C.快速排序D.歸并排序二、填空題(本大題共13小題，每小題2分，共26分)16 .數據的不可分割的最小標識單位是 ,它通常不具有完整確定的實際意義，或不被當作一個整體對待。17 .運算

5、分為加工型運算和引用型運算，讀取操作是 運算。18 .帶有頭結點的單向循環(huán)鏈表 L （L為頭指針）中，指針 p所指結點為尾結點的條件是19 .在雙鏈表中，前趨指針和后繼指針分別為prior和next。若使指針p往后移動兩個結點，則需執(zhí)行語句20 .元素S1,S2,S3,S4,S5,S6依次進入順序棧S,如果6個元素的退棧順序為S2,S3,S4,S6,S5,S1 ,則順序棧的容量至少為21 .稀疏矩陣一般采用的壓縮存儲方法是22.在一棵樹中,結點沒有雙親。1,23 .一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、自左至右給所有結點編號。設根結點編號為若編號為i的結點有父結點，那么其父結點的

6、編號為24 .二叉樹的二叉鏈表存儲結構中判斷指針p所指結點為葉子結點的條件是25.邊稀疏的無向圖采用存儲較省空間。26 .除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路，稱為27 .二分查找算法的時間復雜度是相互交換。28 .要將序列51 , 18, 23, 68, 94, 70, 73建成堆，則只需把 18與三、應用題（本大題共5小題，每小題6分，共30分）29 .將題29圖所示的一棵二叉樹轉換成對應的森林。題31圖題32圖30 .給定權值 3, 9, 13,5, 7,構造相應的哈夫曼（Huffman ）樹，并計算其帶權路徑長度。31 .寫出題31圖的鄰接矩陣和每個頂點的入度與出度。

7、32 .二叉排序樹的各結點的值依次為2028,請在題32圖中標出各結點的值。33 .用冒泡排序法對數據序列（55, 38, 65, 97, 76, 138, 27, 49）進行排序，寫出排序過程中的各趟結果。四、算法設計題（本大題共2小題，每小題7分，共14分）34 .設線性表A = （a1， a2,sm）, B= （b1，b2,b）,試寫一個按下列規(guī)則合并A, B為線性表C的算法,使得C= (a1，b1,，abm ,bm+1, ,b)當 m<n時;或者C= (a1, b1,，na,bn ,an+1,m) 當 m>n 時。線性表A,B和C均以帶頭結點的單鏈表作為存儲結構，且 C表利

8、用A表和B表中的結點空間構成。（注意：單鏈表的長度值 m和n均未顯式存儲。）35 .二叉樹的二叉鏈表類型定義如下:typedef struct btnode datatype data;struct btnode *lchild,*rchild; bitreptr;寫出后根遍歷根指針為 t的二叉樹的遞歸算法（void postorder （bitreptr *t）。全國2011年10月 數據結構導論試題課程彳弋碼:02142一、單項選擇題(本大題共15小題，每小題2分，共30分)1 .設棧S和隊列Q的初始狀態(tài)為空，元素 e1, e2, e3, e4, e5和e6依次通過棧S,元素退棧后即進入隊

9、列 Q, 若6個元素的出隊序列是 e2, e4, e3, e6, e5, e1,則棧S的容量至少為()A.2B.3C.4D.62 .設計一個判別表達式中左右括號是否配對出現的算法，采用的最佳數據結構為()A.線性表的順序存儲結構B.隊列C.線性表的鏈式存儲結構D.棧3 .下列程序段的時間復雜度為()i=0; s=0;while (s<n)i+ ; s=s+i; A.O (而)B.O(log2n)C.O(n)D.O(n2)4 .設A是nxn的對稱矩陣，將A的對角線及對角線上方的元素Aj(1 w i,j w n,i w j)以列優(yōu)先順序存放在一維數組元素B 1至B n(n+1)/2中，則元素

10、 Aj(iwj)在B中的位置為()A.i(i-l)/2+jB.j(j-l)/2+i C.j(-l)/2+i-1D.i(i-l)/2+j-15 .在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現的是()A.G中有弧<Vi, Vj>B.G中有一條從Vi到Vj的路徑C.G中沒有弧<Vi, Vj>D.G中有一條從Vj到Vi的路徑6 .下列序列中，由第一趟快速排序可得到的序列(排序的關鍵字類型是字符串)是()A. da,ax,eb,de,bbff ha,gcB. cd,eb,ax,daffha, gc,bbC. gc,ax,eb,cd,bbff da,haD

11、. ax,bb,cd,daffeb, gc,ha7 .不穩(wěn)定的排序方法是()A.直接插入排序B.冒泡排序C.堆排序D.二路歸并排序8 .設散列表表長 m=14,散列函數為h (k) =k%11 ,表中已有4個記錄，如果用二次探測法處理沖突，關鍵字為49的記錄的存儲位置是()01234567891011121315386184A.3B.5C.8D.99 .若元素1, 2, 3依次進棧，則退棧不可能出現的次序是()A.3 , 2, 1B.2 , 1, 3C.3, 1, 2D.1 , 3, 210 .直接插入排序的時間復雜度是( )A.O (n2)B.O (nlog2n) C.O (n)D.O (l

12、og2n)11 .稀疏矩B是指()A.元素少的矩陣B.有少量零元素的矩陣C.有少量非零元素的矩陣D.行數、列數很少的矩陣12 .深度為 k (k>1)的二叉樹，結點數最多有()A.2k B.2k-1C.2k-1D.2k-1-113 .由帶權為9, 2, 5, 7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為()A.23 B.37 C.44D.4614 .有n個頂點的有向完全圖的弧數為( )A.n2 B.2n C.n(n-1)D.2n (n+1)15 .圖的深度優(yōu)先搜索類似于二叉樹的()A.先根遍歷B.中根遍歷C.后根遍歷 D.層次遍歷二、填空題(本大題共13小題，每小題2分，共26

13、分)16 .下列程序段的時間復雜度為 。for(i=1;i<=n;i+)for(j=1;j<=n;j+) x+;17 .數據結構中結點按邏輯關系依次排列形成一條“鎖鏈”的結構是 。18 .在表長為n的順序表上做刪除運算，平均要移動的結點個數為 。19 .在帶有頭結點的單循環(huán)鏈表head中，指針p所指結點為尾結點的條件是 。20 .隊列又稱為 的線性表。21 .順序棧被定義為結構類型，含有兩個域：data和top,則對棧*sq進行初始化的操作是 。22 .對于任何一棵二叉樹 T,如果其終端結點數為n0,度為2的結點數為n2,則n2=。23 .一棵具有n個結點的二叉樹，采用二叉鏈表存儲

14、，則二叉鏈表中指向孩子結點的指針有 個。24 .若連通圖G的頂點個數為n,則圖G的生成樹的邊數為 。25 .一個具有n個頂點的無向圖的邊數最多為 。26 .中根遍歷二叉排序樹所得到的結點訪問序列是鍵值的 序列。27 .冒泡排序的平均時間復雜度為 。28 .將序列60, 20, 23, 68, 94, 70, 73建成堆，則只需把 20與 互相交換。三、應用題(本大題共5小題，每小題6分，共30分)29 .如題29圖所示，在棧的輸入端元素的輸入順序為A, B, C, D,進棧過程中可以退棧，寫出在棧的輸出端以A開頭和以B開頭的所有輸出序列。題29圖題30圖題31圖題32圖30 .一棵二叉樹如題3

15、0圖所示，寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。31 .將題31圖所示的一棵二叉樹轉換成森林。32 .對于有向無環(huán)圖：(1)敘述求拓撲排序算法的基本步驟；(2)對于題32圖，寫出它的4個不同的拓撲排序序列。33 .判別以下序列是否為堆。如果不是，則把它調整為堆。(1) (100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (2) (12, 70, 33, 65, 24, 56, 48, 92, 86, 33)。 四、算法設計題(本大題共2小題，每小題7分，共14分)34 .n個結點的完全二叉樹按結點編號將值順序存放在一維數組元素A 1至A n中

16、，試編寫算法實現將順序存儲結構轉換為二叉鏈表存儲結構，其中根結點由tree指向。35 .試寫出冒泡排序算法。全國2011年1月數據結構導論試題課程代碼：02142一、單項選擇題（本大題共15小題，每小題2分，共30分）1 .在順序表中查找第i個元素，時間效率最高的算法的時間復雜度為（）A.O（1）B.O（而）C.O（log2n）D.O（n）2 .樹形結構中，度為 0的結點稱為（）A.樹根 B.葉子C.路彳至D.二叉樹3 .已知有向圖 G=（V,E）,其中 V=V 1,V2,V3,V4,V5,V6,V7 , E=<V 1,V2> , <V1,V3> , <V1,V4

17、> , <V 2,V5> , <V3,V5>,<V3,V6>, <V4,V6>, <V5,V7>, 76丫7>,則圖 G 的拓撲序列是（）A.V 1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7 C.V 1,V3,V4,V5,V2,V 6,V7D.V 1,V2,V5,V3,V4,V6,V74 .有關圖中路徑的定義，表述正確的是 （）A.路徑是頂點和相鄰頂點偶對構成的邊所形成的序列B.路徑是不同頂點所形成的序列C.路徑是不同邊所形成的序列D.路徑是不同頂點和不同邊所形成的集合5 .串的長度是

18、指（）A.串中所含不同字母的個數 B.串中所含字符的個數C.串中所含不同字符的個數D.串中所含非空格字符的個數6 .組成數據的基本單位是（）A.數據項B.數據類型C.數據元素D.數據變量7 .程序段 i=n ; x=0 ;dox=x+5*i ; i-; while （i>0）;的時間復雜度為（ ）A.O （1） B.O （n） C.O （n2）D.O（n3）8 .與串的邏輯結構不回啊 數據結構是（） A.線性表 B.棧C.隊列D.樹9 .二叉樹的第i （i>1）層上所擁有的結點個數最多為（）A.2i B.2i C.2i-1D.2i-110 .設單鏈表中指針p指向結點A,若要刪除A的

19、直接后繼，則所需修改指針的操作為（）A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p11 .下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是（）A.堆排序B.冒泡排序C.直接插入排序D.快速排序12 .設字符串 S1 = ABCDEFG ，S2= PQRST',則運算S=CONCAT（SUBSTR（S1,2,LENGTH（S2）,SUBSTR（S1,LENGTH（S2）,2）后 S 的結果為（）A." BCQR" B. BCD

20、EF" C. BCDEFG " D. BCDEFEF "13 .在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A,并且A的左孩子的平衡因子為-1 ,右孩子的平衡因子為 0,則使其平衡的調整方法為（）A.LL 型 B.LR 型 C.RL 型 D.RR 型14 .如果結點A有3個兄弟結點，而且 B為A的雙親，則B的度為（）A.1B.3C.4D.515 .數據表A中每個元素距其最終位置較近，則最省時間的排序算法是（）A.堆排序B.插入排序C.直接選擇排序D.快速排序二、填空題（本大題共13小題，每小題2分，共26分）16 .下列程序段的時間復雜度為 。i

21、=1 ;while (i<n) i=i*2 ;個元素。17 .向一個長度為n的順序表中第i （1WiWn）個元素之前插入一個元素時，需向后移動18 .在循環(huán)雙鏈表中，刪除最后一個結點，其算法的時間復雜度為。19 .隊列的插入操作在隊列的部分進行。20 .一個棧的輸入序列是1, 2, 3,，n,輸出序列的第一個元素是 n,則第i個輸出元素為 。21 .一個10階對稱矩陣A,采用行優(yōu)先順序壓縮存儲下三角，ao0為第一個元素，其存儲地址為1,每個元素占有 1 個存儲地址空間，則a85 的地址為。22 .設字符串S=" ID AM DAD STUDENT "（其中口表示空格字

22、符），則S的長度為。23 .在樹形結構中，沒有后繼的結點是結點。24 .一棵深度為n（n>1）的滿二叉樹中共有 個結點。25 .在無向圖中，如果從頂點v到頂點v'有路徑，則稱 v和v'是。26 .無向完全圖G 采用 存儲結構較省空間。27 .在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個數沒有關系的查找方法是 。28 .快速排序最好情況下的時間復雜度為。三、應用題（本大題共5 小題，每小題6分，共 30 分 ）29 .稀疏矩陣A 如下，寫出矩陣A 的三元組表及矩陣A 的轉置矩陣的三元組表。030001000000 5-1 0 0 0 0 00

23、0040 -30 0 0 0 030 .一棵二叉樹的前根遍歷序列為ABCDEFG ，中根遍歷序列為CBDAEGF ，試構造出該二叉樹。31 .下述矩陣表示一個無向連通網，試畫出它所表示的連通網及該連通網的最小生成樹。1 12 51018912 82594102 432 .給定表（80， 90， 50， 70， 75， 60， 40， 100） ，試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。33 .試寫出一組鍵值（46， 58， 15， 45， 90， 18， 10， 62）應用直接插入排序算法從小到大排序后各趟的結果。四、算法設計題（本大題共2 小

24、題，每小題7 分，共 14 分 ）34 .試分別寫出二叉樹的先根遍歷和中根遍歷的遞歸算法。35 .試編寫以單鏈表為存儲結構實現直接選擇排序的算法。2011年1月全國自考數據結構導論參考答案2011年1月高等教育自學考試全國統(tǒng),一命題考試數據結構導論試題答案及評分參考（課程代碼 02142）一、單項選擇題（本大題共15小跋,每小題Z分.共30分）1. AZ-B3. A4, A5. BG. C7, B8. D生 C1G, A11.C12.1)'13, B14tCIt. B二、填空50；奉大題共13小益，每小建2分.共26分）16. CKh>&n)ni-118.0(1)19.隊

25、尾（或尾部）20. n-i4* 121+42ZZ. 1421葉于f卷羯24.25.連逋的28.鄰接矩陣2工散列查找2&. （Xnlog! n）二、底對黑；本人黑共5小段,耳小息6分，& 3!分） 29.稀疏用陣A.的三,元蛆我第下：（？分）11334._3. J2612rV31574一 3稀疏短降A的轉置矩陣訪三元組表卻下分）1tjV1515213231544611數據結構導論試鼠舉案及評分翡.名第】頁（共？頁30.解：（左子樹3分，石子樹3分）答30圖31.解，連通網為:獻小生成樹為;數據結構導論試題答案及評分參考第2頁（共3頁）32 一答能圖(注2左子期3分1右子樹三分)M

26、3.解;初始序列146, 5 fhi5*43矢1,10,62第趣上4£戶幻5T必需(j,1E,1O,MC1分)一二一山5,4彘5町.45 .蛇社gJ(M2(1分)第二的J15H55&5叼國。,】£門黑62(1分)第四趟：門 5,4516,58*90,卻 ,1362(1分)東直.口5,1孔席次;洱鈾。,鹿(1分)第六越；10,必,46.5機9口，鹿第七糖工16.1殖1%，品4/簫工2 .就(1步)四，算法諛計遢(本大翅共2小題,每小題¥分.共14分)力中 拓n "三川盧d-.W >*口4斛i無醉HL囚度戶丹西:Void preorSE“hit

27、i"邛trr) ifirJNUUJ visit(r>p pruorderCr >lchild)» pteorfler r- >rcliilcl)；)(3 分),根追加遞歸算法Vcid orcfcrCrjittptrr)< ifCrl-NULL) i.nordcr(i-> I child) visit(r ；inordertr-C>rchjltD j )«仍3友好void U nke dLisi_Se1 Mt_SoTt (Li nkTI_ k t & L) 單鏈.表上的玄拄逸擇排序克旅 (fottp Ljp >nEX

28、t->n總、Hp=p>n”t)tl 分)( q=pAnuxtjKNqAdata*Cl 分)"=烏福二世一 Aucxt打=rAn；Kt)/7在q后面尋找元素值最小的輔點 if(r>nexi - >data<xj (1 £ x= r> nesct-* > data ；r ；(1 分)if(s! =q)找到了值比q>das更小的結點=->n«t (p-AuE3tt=sAiwxt”一>nrtxi=q；Cl 分)t - q- >rKj*t«q->nexi.-"p -> nest

29、 >next； (1 分p>next-Augxil j/交換 q 和 s>riKt 的個結點(1 分)f" /JUnkedList_SelectScrt數娼結構導論試題答案及評分參考第3頁(共3頁)2010年10月數據結構導論試題課程代碼：02142、單項選擇題（本大題共15小題，每小題2分，共30分）1 下列描述中正確的是（）A. 數據元素是數據的最小單位B. 數據結構是具有結構的數據對象C. 數據結構是指相互之間存在一種或多種特定關系的數據元素的集合D. 算法和程序原則上沒有區(qū)別，在討論數據結構時兩者是通用的2歸并排序的時間復雜度是（）AO（n2）B.O（nlo

30、g2n）C.O（n）D.O（log2n）3二分查找的時間復雜度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）4順序存儲的表中有90000 個元素，已按關鍵字值升序排列，假設對每個元素進行查找的概率相同，且每個元素的關鍵字值皆不相同，用順序查找法查找時，需平均比較的次數為（ ）A 25000 B.30000 C.45000D.900005 .散列文件是一種（ ）A .順序文件B.索引文件 C.鏈接文件D.計算尋址文件6 .兩個矩陣 A : mxn, B: nXp 相乘，其時間復雜度為 （ ）A. O（n） B.O（mnp） C.O（n2） D.O （mp）7 .常用于函

31、數調用的數據結構是（ ）A.棧B.隊列C.鏈表 D.數組8 .二維數組 A n m以列優(yōu)先順序存儲，數組 A中每個元素占用1個字節(jié)，A 1 1為首元素，其地 址為 0,則元素 A i j的地址為（）A. （i-1） x m+（j-1）B.（j-1） Xn+（i-1）C.（j-1）Xn+I D.j x n+i9 .圖的廣度優(yōu)先搜索使用的數據結構是（ ）A.隊列 B.樹 C.棧 D.集合10序列（21,19,37,5,2）經冒泡排序法由小到大排序，在第一次執(zhí)行交換后所得結果為（）A （19， 21， 37， 5， 2） B.（21， 19， 5， 37， 2） C.（21， 19， 37， 2，

32、5）D.（2， 21， 19， 37， 5）11數據在計算機存儲器內表示時，根據結點的關鍵字直接計算出該結點的存儲地址，這種方法稱為（）A.索引存儲方法B.順序存儲方法C.鏈式存儲方法D.散列存儲方法12在單鏈表中，存儲每個結點有兩個域，一個是數據域，另一個是指針域，指針域指向該結點的（）A.直接前趨B.直接后繼C.開始結點D.終端結點13在已知頭指針的單鏈表中，要在其尾部插入一新結點，其算法所需的時間復雜度為（）A O（ 1）B.O（ log2n）C.O（ n）D.O（ n2）14在鏈隊列中執(zhí)行入隊操作，（）A.需判別隊是否空B.需判別隊是否滿C.限制在鏈表頭p進行D.限制在鏈表尾p進行15

33、 一整數序列26， 59， 77， 31， 51， 11， 19， 42， 以二路歸并排序從小到大排序，第一階段的歸并結果為（）A.31 ，51，11，42，26，77，59，19B.26，59，31，77，11，51 ，19，42C.11，19，26，31，42，59，51，77D.26，11，19，31，51，59，77，42二、填空題（本大題共13 小題，每小題2分，共 26 分 ）16下列程序段的時間復雜度為。i=0； s=0；while （ s<n） i+； s=s+i； 17數據的存儲結構被分為順序存儲結構、散列存儲結構和索引存儲結構4 種。18.從一個長度為n的順序表中刪除

34、第i個元素（iwiwn）時，需向前移動 個元素。19在單鏈表中，插入一個新結點需修改個指針。20在隊列結構中，允許插入的一端稱為。21稀疏矩陣采用的壓縮存儲方法是。22向一個棧頂指針為top 的鏈棧中插入一個新結點*p 時，應執(zhí)行p->next=top 和 操作。23有m 個葉結點的哈夫曼樹所具有的結點數為。24 .在一棵具有n個結點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結點編號。設根結點編號 為1。若編號為i的結點有右孩子，那么其右孩子的編號為 。25 .在一棵樹中， 結點沒有前驅結點。26 . 一個具有n個頂點的有向完全圖的弧數是 。27 . n個頂點的無向圖 G用鄰接

35、矩陣A n n存儲，其中第i列的所有元素之和等于頂點 Vi的。28 .選擇排序的平均時間復雜度為 。三、應用題（本大題共5小題，每小題6分，共30分）29 .在棧的輸入端元素的輸入順序為1, 2, 3, 4, 5, 6,進棧過程中可以退棧，則退棧時能否排成序列3, 2,5, 6, 4, 1和1, 5, 4, 6, 2, 3,若能，寫出進棧、退棧過程，若不能，簡述理由。（用push （x）表示x進棧，pop（x）表示x退棧）30 .已知一棵二叉樹的中根遍歷序列為CBEDFAGH ,后根遍歷序列為 CEFDBHGA ,畫出該二叉樹。31 .給定表（15, 11, 8, 20, 14, 13）,試按

36、元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹， 畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它 調整為平衡二叉排序樹。32 .如題32圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點 A為起點的深度優(yōu)先搜索頂點序列。33 .用冒泡排序法對數據序列（49, 38, 65, 97, 76, 134, 27, 49）進行排序，寫出排序過程。并說明冒泡排 序是否為穩(wěn)定排序。四、算法設計題（本大題共2小題，每小題7分，共14分）34 .編寫計算二叉樹中葉子結點數目的算法。35 .開散列表的類型定義如下：typedef struct tagnodekeytype key;struct tagnode*next;*pointer,node;typedef pointer openhash n;試寫出開散列表上的查找算法。2010年10月自考數據結構導論參考答案201