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

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

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

3、) A.n-i B.n+i C.n-i-1 D.n-i+1 2.在單鏈表中，已知q指的結(jié)點是q指的結(jié)點的直接前驅(qū)結(jié)點，若在q和p指的結(jié)點之間插入一個由s指的結(jié)點，則需執(zhí)行_。( ) A.link(s)link(p)，link(p)s B.link(q)s，link(s)p C.link(p)link(s)，link(s)p D.link(p)s，link(s)q 3.在非空雙向循環(huán)鏈表中由q所指的那個鏈結(jié)點前面插入一個由p指的鏈結(jié)點的動作對應的語句依次為:rlink(p)q,llink(p)llink(q),llinkp,_。（空白處為一條賦值語句）( ) A.rlink(q)p B.rlin

4、k(llink(q)p C.rlink(llink(p)p D.rlink(rlink(p)p 4.為了節(jié)省存儲空間，將n階對稱矩陣A中包括主對角線元素在的下三角部分的所有元素按照行序為主序方式存放在一維數(shù)組B1:n(n-1)/2中，對任意下三角部分的元素aij(ij)在B的下標k是 ( ) A.i(i-1)/2+j B.(i(i-1)/2+j C.i(i+1)/2+j B.(i(i+1)/2+j 5.某堆棧的輸入序列為a,b,c,d,下面的四個序列中，_不可能是它的輸出序列。( ) A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a 6.若非空隊列采用鏈式存儲結(jié)構

5、，front和rear分別為隊頭元素與隊列尾元素的指針，刪除此時隊列的一個元素的*作時依次執(zhí)行pfront，_ ，call RET(P)。( ) A.frontlink(rear) B.rearlink(p) C.rearlink(front) D.frontlink(p) 7.中綴表達式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,d)的長度為 ( ) A.2 B.3 C.4 D.5 9.在初始為空的雜湊表中依次插入關鍵字序列(MON，TUE，WED，TH

6、U，F(xiàn)RI，SAT，SUN), 雜湊函數(shù)為H(k)=i MOD 7，其中，i為關鍵字k的第一個字母在英文字母表中的序號，地址值域為0:6，采用線性再散列法處理沖突。插入后的雜湊表應該如_所示。( ) A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON 10.從未排序序列中選擇一個元素，該元素

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

8、，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B，G?珼，H，其后序遍歷序列為_。 6.已知序列(34，76，45，18，26，54，92，65，)，按照逐點插入法建立一棵二叉排序列樹，該樹的深度是_。 7.一個不帶有權的有向圖采用鄰接矩陣存儲方法，其鄰接矩陣是一個_。8.帶權連通圖G=，其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6，(v1,v4)9，(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：頂點偶對右下角的數(shù)據(jù)為邊上的權值)，G的最小生成樹的權值之和為_ 。 9.在線性表中采用折半查找法（二分

9、查找法）查找一個數(shù)據(jù)元素，線性表中元素應該按值有序，并且采用_存儲方法。 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)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:(

10、v5,v7)9,a10:(v6,v7)6； (注：頂點偶對的右括號下方的數(shù)據(jù)表示該邊上的權值)。e與l分別表示活動a1的最早開始時間與最晚開始時間，請分別求出e與l(1i10),填入下面的方格中。 e1:10 l1:10 2.若對序列(76，38，65，13，97，27，50，49)采用堆積排序法(按照值的大小從小到大)進行排序，請分別在下表中寫出每一趟的結(jié)果： 原始序列 76 38 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é)構，并且元素按

11、值大小非遞減排列，下面的算法刪除線性表中多余的值一樣的元素。請在算法的空白處填入適當容，使之能夠正常工作。(10分) procedure DEL (A,n) i1 while _ do if (AAi+1 then ii+1 else / 查找滿足條件的元素 / for _ do Aj-1Aj end / 刪除第i+1個元素 (滿足條件的元素) / _ / 修改線性表的長度 / end end 2.已知非空線性鏈表的鏈結(jié)點的構造為 date | link，第一個鏈結(jié)點的指針為list，下面的算法刪除鏈表的第i個結(jié)點（設i0）。請在算法的空白處填入適當容，使之能夠正常工作。(15分) procedure DEL (list,i,item) _ / 給變量q賦初值 / if (i=1