數(shù)據(jù)結構03-04期末考試A答案

1、四川大學期末考試題解答(2003-2004學年第二學期)課程名: 數(shù)據(jù)結構(A) 計算機科學與技術專業(yè)適用 人數(shù):學院: 專業(yè): 教師姓名:姓名: 學號: 成績:一. 順序表的插入和刪除要求仍然保持各個元素原來的次序。設在等概率情形下, 對有127個元素的順序表進行插入, 平均需要移動多少個元素? 刪除一個元素, 又平均需要移動多少個元素?【解答】若設順序表中已有n = last+1個元素，last是順序表的數(shù)據(jù)成員，表明最后表項的位置。又設插入或刪除表中各個元素的概率相等，則在插入時因有n+1個插入位置(可以在表中最后一個表項后面追加)，每個元素位置插入的概率為1/(n+1)，但在刪除時只能

2、在已有n個表項范圍內刪除，所以每個元素位置刪除的概率為1/n。插入時平均移動元素個數(shù)AMN(Averagy Moving Number )為刪除時平均移動元素個數(shù)AMN為 二. 設A和B均為下三角矩陣，每一個都有n行。因此在下三角區(qū)域中各有n(n+1)/2個元素。另設有一個二維數(shù)組C，它有n行n+1列。試設計一個方案，將兩個矩陣A和B中的下三角區(qū)域元素存放于同一個C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉置后存放于C的上三角區(qū)域中。并給出計算A的矩陣元素aij和B的矩陣元素bij在C中的存放位置下標的公式?！窘獯稹坑嬎愎饺? 鐵路進行列車調度時, 常把

3、站臺設計成棧式結構的站臺，如右圖所示。試問：(1) 設有編號為1,2,3,4,5,6的六輛列車, 順序開入棧式結構的站臺, 則可能的出棧序列有多少種?(2) 若進站的六輛列車順序如上所述, 那么是否能夠得到, , 和的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出進?；虺鰲５男蛄??！窘獯稹?1) 可能的不同出棧序列有 種。(2) 不能得到和這樣的出棧序列。因為若在4, 3, 5, 6之后再將1, 2出棧，則1, 2必須一直在棧中，此時1先進棧，2后進棧，2應壓在1上面，不可能1先于2出棧。也是這種情況。出棧序列和可以得到。3562244 4411111111 3 3

4、2 32 325 325 3256 32564 5344122226 1 1 13 135 1354 13542 13542 四. 列出右圖所示二叉樹的葉結點、分支結點和每個結點的層次?！窘獯稹慷鏄涞娜~結點有、。分支結點有、。結點的層次為0；結點、的層次為1；結點、的層次為2；結點、的層次為3；結點的層次為4。五. 在結點個數(shù)為n (n1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結點？多少個分支結點？高度最大的樹的高度是多少？它有多少個葉結點？多少個分支結點？ 【解答】結點個數(shù)為n時，高度最小的樹的高度為1，有2層；它有n-1個葉結點，1個分支結點；高度最大的樹的高度為n-1，有n

5、層；它有1個葉結點，n-1個分支結點。六. 試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)?！窘獯稹烤哂?個結點的樹 具有3個結點的二叉樹七. 寫出向堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 14時，每加入一個數(shù)據(jù)后堆的變化?！窘獯稹恳宰钚《褳槔?224445552444238822223535533510648104864848614八. 給定一組權值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 試構造一棵具有最小帶權外部路徑長度的擴充4叉樹, 要求該4叉樹中所有內部結點的度都是4, 所有外部結點的度都是0。這棵擴充4

6、叉樹的帶權外部路徑長度是多少?【解答】權值個數(shù)n = 11，擴充4 叉樹的內結點的度都為4，而外結點的度都為0。設內結點個數(shù)為n4，外結點個數(shù)為n0，則可證明有關系n0 = 3 * n4 + 1。由于在本題中n0 = 113 * n4 +1，需要補2個權值為0的外結點。此時內結點個數(shù)n4 = 4。仿照霍夫曼樹的構造方法來構造擴充4叉樹，每次合并4個結點。6658524539332623151170000011 705239334518231526169826658375此樹的帶權路徑長度WPL = 375 + 82 + 169 + 18 = 644。畫出對其進行折半搜索時的二叉搜索樹, 并計算

7、搜索成功的平均搜索長度和搜索不成功的平均搜索長度?！窘獯稹?09677154897553275017908765612512503170094九. 給出右圖的鄰接矩陣、鄰接表和鄰接多重表表示。DA【解答】(1) 鄰接矩陣EBFC310 A1 B2 C3 D4 E5 F(2) 鄰接表42（出邊表）54140 A1 B2 C3 D4 E5 F（入邊表）30105312data fin fout(3) 鄰接多重表（十字鏈表）i j ilink jlink0 1 (A, B)0 A1 B2 C3 D4 E5 F0 3 (A, D)1 2 (B, C)1 4 (B, E)2 5 (C, F)3 1 (D

8、, B)3 4 (D, E)5 4 (F, E)十.對于如右圖所示的有向圖，試寫出：(1) 從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 【解答】(1) 以頂點為根的深度優(yōu)先生成樹（不唯一）： 或 (2) 以頂點為根的廣度優(yōu)先生成樹：十一.設在4地(A, B, C, D)之間架設有6座橋，如圖所示：ACDB要求從某一地出發(fā)，經(jīng)過每座橋恰巧一次，最后仍回到原地。(1) 試就以上圖形說明：此問題有解的條件什么？（3分）(2) 設圖中的頂點數(shù)為n，試用C或Pascal描述與求解此問題有關的數(shù)據(jù)結構并編寫一個算法，找出滿足要求的一條回路。

9、（7分）【解答】將下圖改為無向圖，城市為結點，橋為邊：ACDBBADC(1) 此為歐拉問題。有解的充要條件是每一個結點的度為偶數(shù)。（5分）EdgeNo AdjNo link(2) 數(shù)據(jù)結構采用鄰接表，每個邊結點有3個域，分別記錄相關邊號、鄰接頂點號和鏈指針。另外，設置一個邊的訪問標志數(shù)組visited ，當visitedi = 0表示第i條邊未訪問過，一旦訪問了第i條邊，即將visitedi改為1。1 A2 B3 C4 D 2 2 2 2 2 2 2 2 2 2 2 2 nodelist visitedstruct edgenode /頂點結點int edgeno;/相關邊號int adjve

10、rtex;/鄰接頂點號edgenode * link;/鏈接指針;struct vertex /頂點int city;/頂點數(shù)據(jù)edgenode * first;/出邊表指針;Typedef vertex * nodelist;/鄰接表數(shù)組下面給出按深度優(yōu)先搜索方法求解歐拉問題的遞歸算法。（5分）void dfs ( nodelist euler, int start, int n, int visited ) cout eulerstart.city ;/輸出頂點數(shù)據(jù)edgenode * p = eulerstart.first;/找第一條關聯(lián)的邊while ( p != NULL ) /有

11、int j = p-edgeno;/邊號if ( visitedj = 0 ) /未走過visitedj = 1;/作邊訪問標記dfs ( euler, p-adjvertex, n, visited ); /按鄰接頂點遞歸下去p = p-link;/查下一條關聯(lián)的邊主程序（5分）void main int count, n, i, j, k;cout n;nodelist euler= new vertexn;/創(chuàng)建鄰接表數(shù)組for ( int i = 0; i euleri.city; euleri.first = NULL;cout “輸入各條邊！” i j k ;/i是邊號碼，j, k是頂點while ( i != 0 ) /i為0, 表示輸入結束edgenode * p = new edgenode;/鏈入第j號鏈表p-edgeno = i; p-adjvertex = k;p-link = eulerj.first; eulerj.first = p;edgenode * p = new edgenode;/鏈入第k號鏈表p-edgeno = i; p-adjvertex = j;p-link = eulerk.first; eulerk.first = p;cin i j k ;count+;int *visited = new intcount;/創(chuàng)建訪問標志數(shù)組