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

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

2、/ 結(jié)點(diǎn)后繼指針 ListNode ； (1) 已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè) 操作？ 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é)點(diǎn)(由 p 所指向)滿足： A. p-link = NULL ； B. p = NULL ； C. p-link = first ； D. p = first ； 三、 設(shè)有一個(gè)順

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

4、)。 (2) 采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于樹的(C )。 (3) 采用鄰接表存儲(chǔ)的圖的廣度優(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） 在用于表示有向圖的鄰接矩陣中， 對(duì)第 i 行的元素進(jìn)行累加， 可得到第 i 個(gè)頂 點(diǎn)的（ ）度， 而對(duì)第 j 列的元素進(jìn)行累加， 可得到第 j 個(gè)頂點(diǎn)的

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

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

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

8、 fromVex ， toVex ； / 邊的起點(diǎn)與終點(diǎn) int weight ； / 邊上的權(quán)值 TreeEdgeNode； typedef TreeEdgeNode MSTn-1 ； / 最小生成樹定義 void PrimMST （ AdjMatrix G ， MST T， int rt ） /從頂點(diǎn)rt出發(fā)構(gòu)造圖G的最小生成樹T, rt成為樹的根結(jié)點(diǎn) 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 / 圖不連通， 出錯(cuò)處 Tminpos ；Tminpos v = Tk.toVex ； for ( i = k+1 ； i T.toVex T.toVex ； ） / 修改候選邊集合 ） T.fromVex = v ； 參考答案 一、（1） 錯(cuò) （2） 錯(cuò) （ 3） 對(duì) 4） 錯(cuò) （5） 對(duì) 二、( 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é)點(diǎn)， 初始時(shí)指向第一個(gè)結(jié)點(diǎn) while （ s ！ = NULL ） / 處理所有結(jié)點(diǎn) pre = L ； p = L-lLink ； / 指針 p 指向待比較的結(jié)點(diǎn)， pre 是 p 的前驅(qū)指針 while （ p p-data ） / 循 lLink 鏈尋找結(jié)點(diǎn) *s 的插入位置 pre = p ； p = p-lLink s-lLink = p ； s = s-rLink ； / 結(jié)點(diǎn) *s 在 lLink 方向插入到 *pre 與 *p 之間 八、關(guān)鍵碼的輸入序列 55