計算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)模擬卷

1、計算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)模擬試題07 月 14 日 22:00一、判斷題 ( 每小題 1分，共 15 分)1. 非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個 直接前驅(qū)元素。 ( )2. 數(shù)組是一種沒有插入與刪除 * 作的線性結(jié)構(gòu)。 ( )3. 稀疏矩陣中值為 0的元素分布有規(guī)律， 因此可以采用三元組方法進(jìn)行壓縮存 儲。 ()4. 空串與由空格組成的串沒有區(qū)別。 ( )5. 將T在S中首次出現(xiàn)的位置作為 T在S中的位置的*作稱為串的模式匹配。( )6. 深度為 h 的非空二叉樹的第 i 層最多有 2h-1 個結(jié)點。 ()7. 完全二叉樹就是滿二叉樹。 ( )8. 已知一棵二叉樹的前序序列和中序序列可以唯

2、一地構(gòu)造出該二叉樹。 ()9. 非空二叉排序樹的任意一棵子樹也是二叉排序樹。 ()10. 有向圖是一種非線性結(jié)構(gòu)。 ( )11. 帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之 和。 ( )12. AOE 網(wǎng)是一種帶權(quán)的無環(huán)連通圖。 ( )13. 折半查找方法適用于按值有序的線性鏈表的查找。 ( )14. 哈希表的查找效率主要取決于所選擇的哈希函數(shù)與處理沖突的方法。 ( )15. 選擇排序過程中元素之間的比較次數(shù)與原始序列的狀態(tài)無關(guān)。 ( )二、單項選擇題 ( 每小題 2 分，共 20分)1. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，刪除它的第i數(shù)據(jù)元素之前，需要先依次向前移動個數(shù)

3、據(jù)元素。 ()A. n-iB. n+iC. n-i-1D. n-i+12. 在單鏈表中，已知q指的結(jié)點是q指的結(jié)點的直接前驅(qū)結(jié)點，若在q和p指的結(jié)點之間插入一個由 s 指的結(jié)點，則需執(zhí)行 。 ()A. link(s)jlink(p), link(p)JsB. link(q)Js, link(s) JpC. link(p)jlink(s)， link(s)jpD. link(p)Js， link(s) Jqp 指的鏈結(jié)點空白處為3. 在非空雙向循環(huán)鏈表中由 q 所指的那個鏈結(jié)點前面插入一個由 的動作對應(yīng)的語句依次為 :rlink(p)Jq,llink(p)Jllink(q),llink J p,

4、一條賦值語句)()A. rlink(q)JpB. rl ink(llink(q)JpC. rlink(llink(p)JpD. rlink(rlink(p)Jp4. 為了節(jié)省存儲空間，將n階對稱矩陣A中包括主對角線元素在內(nèi)的下三角部分的所有元素按 照行序為主序方式存放在一維數(shù)組 B1:n(n-1)/2 中， aij(i >j)在 B的下標(biāo) k 是 ( )A. i(i-1)/2+jB. (i(i-1)/2+jC. i(i+1)/2+jB. (i(i+1)/2+j5. 某堆棧的輸入序列為 a,b,c,d, 下面的四個序列中， 的輸出序列。 ()A. a,c,b,dB. b,c,d,aC. d

5、,c,a,bD. c,d,b,a對任意下三角部分的元素不可能是它6. 若非空隊列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)， front 和 rear 分別為隊頭元素與隊列尾元素的指針，刪除此時隊列的一個元素的*作時依次執(zhí)行pjfront , , callRET(P)。()A. front jlink(rear)B. rear jlink(p)C. rear jlink(front)D. front jlink(p)7. 中綴表達(dá)式 A-(B+C)*D/E 的后綴形式是 。 ()A. ABC+-D*E/B. ABC+D*-E/C. ABC+D-*E/D. ABC+D*E/-8. 廣大義表 A=(),(a),(b,(c,

6、d)的長度為 ()A. 2B. 3C. 4D. 59. 在初始為空的雜湊表中依次插入關(guān)鍵字序列 (MON，TUE，WED，THU，F(xiàn)RI，SAT， SUN), 雜湊函數(shù)為H(k)=i MOD,其中，i為關(guān)鍵字k的第一個字母在英文字母表中的序 號，地址值域為0:6 ,采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如 所示。 ( )A. 0123456THU TUE WED FRI SUN SAT MONB. 0123456TUE THU WED FRI SUN SAT MONC. 0123456TUE THU WED FRI SAT SUN MOND. 0123456TUE THU WED SUN

7、 SAT FRI MON10. 從未排序序列中選擇一個元素，該元素將未排序序列分成前后兩個部分，前一部分中所有元素都小于等于所選元素。 后一部分中所有元素都大于等于所選元素， 而所選元素處在排序的最終位置。這種排序方法稱為 排序法。 ( )A. 插入B. 謝爾C. 快速D. 堆積三、填空題 ( 每小題 2分，共 20 分)1. 已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)， 每個元素占k個存儲單元，第一個元素的地址為 L0C(a1),那么，LOC(ai)二。2. 若一棵二叉樹有 10 個葉結(jié)點，則該二叉樹中度為 2 的結(jié)的點個數(shù)為。3. 具有 n 個結(jié)點的非空二叉排序樹的最小深度為 。4. 深度

8、為h且有 結(jié)點的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點處在第 1 層)5. 二叉樹的前序遍歷序列為 A, B, C, E, F, D, G, H,中序遍歷序列為 A, E,C， F， B， G?珼，H,其后序遍歷序歹H為 。6. 已知序列 (34 , 76, 45, 18, 26, 54, 92, 65, ) ,按照逐點插入法建立一棵二叉排序列樹,該樹的深度是 。7. 一個不帶有權(quán)的有向圖采用鄰接矩陣存儲方法,其鄰接矩陣是一個8. 帶權(quán)連通圖 G=<V,E> 其中 V二v1,v2,v3,v4,v5,E二(v1,v2)7,(v1,v4)6(v1,v4)9 ，(v2,v3)8 ，(v2,v4)

9、4 ，(v2,v5)4 ，(v3,v4)6 ，(v4,v5)2 ，(注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值),G的最小生成樹的權(quán)值之和為 。9. 在線性表中采用折半查找法 (二分查找法) 查找一個數(shù)據(jù)元素， 線性表中元 素應(yīng)該按值有序，并且采用 存儲方法。10. 若對序列 (49，38，65，97，76，13，27，50)采用選擇排序法排序，則第三趟結(jié)束后序列的狀態(tài)是 。四、問題求解題 ( 每小題 10 分，共 20 分)1.已知AOE網(wǎng)為G=(V,E)，其中，V =v1,v2,v3,v4,v5,v6,v7,E = a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a1:(v1,v2

10、)3,a2:(v1,v3)2,a3:(v2,v4)1,a4:(v2,v5)8,a5:(v3,v4)3,a6:(v3,v6)7,a7:(v4,v5)4,a8:(v4,v6)2,a9:(v5,v7)9,a10:(v6,v7)6 ；( 注：頂點偶對的右括號下方的數(shù)據(jù)表示該邊上的權(quán)值) 。 e 與 l 分別表示活動 a1 的最早開始時間與最晚開始時間，請分別求出e與1(1 <i < 10),填入下面的方格中。e1:10l1:102.若對序列（76，38，65，13，97，27，50，49）采用堆積排序法 （按照值的大 小從小到大）進(jìn)行排序，請分別在下表中寫出每一趟的結(jié)果：原始序列 76 3

11、8 65 13 97 27 50 49第 1 趟結(jié)果第 2 趟結(jié)果第 3 趟結(jié)果第 4 趟結(jié)果第 5 趟結(jié)果第 6 趟結(jié)果第 7 趟結(jié)果第 8 趟結(jié)果五、算法題 （ 共 25 分）1.已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，并且元素按值大小非遞減排列,面的算法刪 除線性表中多余的值相同的元素。 請在算法的空白處填入適當(dāng)內(nèi)容， 常工作。（10分）procedure DEL （A,n）i 1while doif （A 半 Ai+1 theni i+1else滿足條件的元素 / for doAj- 1 Ajend使之能夠正/ 查找/ 刪除第i+1個元素（滿足條件的元素）/ / 修改線性表的長度 /endend2. 已知非空線性鏈表的鏈結(jié)點的構(gòu)造為 date | link ，第一個鏈結(jié)點的指針為 list ，下面的算法刪除鏈表的第 i 個結(jié)點(設(shè) i>0 )。請在算法的空白處填入適當(dāng)內(nèi)容，使之 能夠正常工作。(15 分 )procedure DEL (list,i,item) / 給變量 q 賦初值