數(shù)據(jù)結(jié)構(gòu)工程碩士試題

1、數(shù)據(jù)結(jié)構(gòu)工程碩士試題 注： 1、除第九題外，其他各題每題10 分，第九題 20分。 2、所有試題的答案寫在答題紙上。 一、判斷下列敘述的對錯。 (1) 線性表的邏輯順序與物理順序總是一致的。 ( 2) 線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎尽?(3) 線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。 (4) 二維數(shù)組是其數(shù)組元素為線性表的線性表。 (5) 每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運算：插入、刪除和搜索。 二、設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為 typedef struct node / 鏈表結(jié)點定義 ElemType data ； / 數(shù)據(jù) struct node * Link ；

2、/ 結(jié)點后繼指針 ListNode ； (1) 已知指針p所指結(jié)點不是尾結(jié)點，若在*p之后插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個 操作？ A. s-link = p ； p-link = s ； B. s-link = p-link ； p-link = s ； C. s-link = p-link ； p = s ； D. p-link = s ； s-link = p ； ( 2) 非空的循環(huán)單鏈表 first 的尾結(jié)點(由 p 所指向)滿足： A. p-link = NULL ； B. p = NULL ； C. p-link = first ； D. p = first ； 三、 設(shè)有一個順

3、序棧S，元素si， s2， s3， s4， s5， s6依次進(jìn)棧，如果 6個元素 的出棧順序為 s2， s3 ， s4 ， s6 ， s5 ， s1 ，則順序棧的容量至少應(yīng)為多少？ 四、一棵具有 n 個結(jié)點的理想平衡二叉樹 (即除離根最遠(yuǎn)的最底層外其他各層都是滿的， 最底層有若干結(jié)點)有多少層？若設(shè)根結(jié)點在第0層，則樹的高度h如何用n來表示(注意 n 可能為 0)？ 五、從供選擇的答案中選擇與下面有關(guān)圖的敘述中各括號相匹配的詞句，將其編號填入 相應(yīng)的括號內(nèi)。 (1) 對于一個具有 n 個結(jié)點和 e 條邊的無向圖，若采用鄰接表表示，則頂點表的大小 為( A )，所有邊鏈表中邊結(jié)點的總數(shù)為( B

4、)。 (2) 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于樹的(C )。 (3) 采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于樹的(D )。 (4) 判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用(E )。 供選擇的答案 A：n n+1 n-1n+e B：e/2e 2e n+e CD中根遍歷先根遍歷 后根遍歷 按層次遍歷 E：求關(guān)鍵路徑的方法求最短路徑的Dijkstra 方法 深度優(yōu)先遍歷算法 廣度優(yōu)先遍歷算法 六、填空題 （1） 在用于表示有向圖的鄰接矩陣中， 對第 i 行的元素進(jìn)行累加， 可得到第 i 個頂 點的（ ）度， 而對第 j 列的元素進(jìn)行累加， 可得到第 j 個頂點的

5、（ ）度。 （2）一個連通圖的生成樹是該圖的（ ）連通子圖。若這個連通圖有 n 個頂點， 則 它的生成樹有（ ）條邊。 （3）給定序列 100， 86， 48， 73， 35， 39， 42， 57， 66， 21 ， 按堆結(jié)構(gòu)的 定義， 則它一定（ ）堆。 （ 4） 在進(jìn)行直接插入排序時， 其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ ）關(guān)；而在進(jìn) 行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列（ ）關(guān)。 （5）利用關(guān)鍵碼分別為 10， 20 ， 30 ， 40 的四個結(jié)點，能構(gòu)造出（ ）種不同的 二叉搜索樹。 七、設(shè)帶表頭結(jié)點的雙向鏈表的定義為 typedef int ElemType ； type

6、def struct dnode / 雙向鏈表結(jié)點定義 ElemType data ； / 數(shù)據(jù) struct dnode * lLink ， * rLink ； / 結(jié)點前驅(qū)與后繼指針 DblNode； typedef DblNode * DblList ； / 雙向鏈表 試設(shè)計一個算法，改造一個帶表頭結(jié)點的雙向鏈表，所有結(jié)點的原有次序保持在各個結(jié) 點的右鏈域 rLink 中，并利用左鏈域 lLink 把所有結(jié)點按照其值從小到大的順序連接起來。 八、設(shè)有一個關(guān)鍵碼的輸入序列 55 ， 31， 11， 37， 46， 73， 63， 02， 07 ， （ 1） 從空樹開始構(gòu)造平衡二叉搜索樹，畫

7、出每加入一個新結(jié)點時二叉樹的形態(tài)。 若發(fā)生不 平衡， 指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。 （2） 計算該平衡二叉搜索樹在等概率下的查找成功的平均查找長度和查找不成功的平 均查找長度。 九、下面是求連通網(wǎng)絡(luò)的最小生成樹的 Prim 算法的實現(xiàn)， 中間有 5 個地方缺失， 請閱讀 程序后將它們補(bǔ)上。 const int MaxInt = INT_MAX ； /INT_MAX 的值在中 const int n = 6 ； / 圖的頂點數(shù)， 應(yīng)由用戶定義 typedef int AdjMatrixnn ； / 用二維數(shù)組作為鄰接矩陣表示 typedef struct / 生成樹的邊結(jié)點 int

8、 fromVex ， toVex ； / 邊的起點與終點 int weight ； / 邊上的權(quán)值 TreeEdgeNode； typedef TreeEdgeNode MSTn-1 ； / 最小生成樹定義 void PrimMST （ AdjMatrix G ， MST T， int rt ） /從頂點rt出發(fā)構(gòu)造圖G的最小生成樹T, rt成為樹的根結(jié)點 TreeEdgeNode e ； int i ， k = 0 ， min ， minpos ， v ； for （ i = 0 ； i .fromVex = rt ； Tk.toVex = I ； Tk+.weight = Grt ； fo

9、r （ k = 0 ; k n-1; k+ ） / 依次求 MST的候選邊 min = MaxInt ； for ( i = k ； i n-1 ； i+ ) / 遍歷當(dāng)前候選邊集合 if ( T.weight ； Tk = e ； ！ endl ；exit (1) ； e / 圖不連通， 出錯處 Tminpos ；Tminpos v = Tk.toVex ； for ( i = k+1 ； i T.toVex T.toVex ； ） / 修改候選邊集合 ） T.fromVex = v ； 參考答案 一、（1） 錯 （2） 錯 （ 3） 對 4） 錯 （5） 對 二、( 1) B ( 2) C

10、 三、 3 四、h = elog2 (n+1)u-1 五、A. B. C. D. E. 六、出入極小n-1 是（最小） 有 無 14 七、算法如下 void sort ( DblNode * L ) DblNode * s = L-rlink ； / 指針 s 指向待插入結(jié)點， 初始時指向第一個結(jié)點 while （ s ！ = NULL ） / 處理所有結(jié)點 pre = L ； p = L-lLink ； / 指針 p 指向待比較的結(jié)點， pre 是 p 的前驅(qū)指針 while （ p p-data ） / 循 lLink 鏈尋找結(jié)點 *s 的插入位置 pre = p ； p = p-lLink s-lLink = p ； s = s-rLink ； / 結(jié)點 *s 在 lLink 方向插入到 *pre 與 *p 之間 八、關(guān)鍵碼的輸入序列 55