微機原理與接口6

1、濟南鐵道職業(yè)技術(shù)學(xué)院專升本輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)試題(模 F)一、判斷題 (每小題 1分，共 15分)1.非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。( )2.數(shù)組是一種沒有插入與刪除操作的線性結(jié)構(gòu)。()3.稀疏矩陣中值為 0的元素分布有規(guī)律，因此可以采用三元組方法進行壓縮存儲。( )4.空串與由空格組成的串沒有區(qū)別。( )5.將 T在 S中首次出現(xiàn)的位置作為 T在 S中的位置的操作稱為串的模式匹配。( )6.深度為 h的非空二叉樹的第 i層最多有 2h-1 個結(jié)點。( )7.完全二叉樹就是滿二叉樹。( )8.已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。( )9.非空二叉排序

2、樹的任意一棵子樹也是二叉排序樹。( )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ù)據(jù)元素。( )A.n-i B.n+iC.n-i-1 D.n-i+12.

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

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

5、元素的操作時依次執(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.59.在初始為空的雜湊表中依次插入關(guān)鍵字序列(MONTUEWEDTHUFRISATSUN), 雜湊函數(shù)為 H(k)=iMOD 7，其中，i為關(guān)鍵字 k的第一個字

6、母在英文字母表中的序號，地址值域為0:9，采用線性再散列法處理沖突。插入后的雜湊表應(yīng)該如_所示。( )A. 0 1 2 3 4 5 6THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6TUE THU WED SUN SAT FRI MON10.從未排序序列中選擇一個元素，該元素將未排序序列分成前后兩個部分，前一部分中所有元素都小于等于所選元素。后一部分中所有元素都大于等于所選元素，而所選元

7、素處在排序的最終位置。這種排序方法稱為_排序法。( )A.插入B.謝爾(希爾) C.快速D.堆三、填空題 (每小題 2分，共 20分)1.已知具有 n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占 k個存儲單元，第一個元素的地址為LOC(a1)，那么，LOC(ai)=_。2.若一棵二叉樹有 10個葉結(jié)點，則該二叉樹中度為 2的結(jié)的點個數(shù)為_。3.具有 n個結(jié)點的非空二叉排序樹的最小深度為_。4.深度為 h且有_個結(jié)點的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點處在第 1層)。5.二叉樹的前序遍歷序列為 A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為 A，E，C，F(xiàn)，B，G，D，H，其后序遍歷序列為_。6.已

8、知序列(34764518265492)，按照逐點插入法建立一棵二叉排序列樹，該樹的深度是_。7.一個不帶有權(quán)的有向圖采用鄰接矩陣存儲方法，其鄰接矩陣是一個_。8.帶權(quán)連通圖 G=(V,E)，其中 V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v3)6，(v1,v4)9，(v2,v3)8，(v2,v4)4(v2,v5)4(v3,v4)6(v4,v5)2()G的最小生成樹的權(quán)值之和為_ 。9.在線性表中采用折半查找法（二分查找法）查找一個數(shù)據(jù)元素，線性表中元素應(yīng)該按值有序，并且采用_存儲方法。10.若對序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則第

9、三趟結(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:(v5,v7)9,a10:(v6,v7)6 ；(注：頂點偶對的右括號下方的數(shù)據(jù)表示該邊上的權(quán)值)。e1與 L1分別表示活動 a1的最早開始時間與最晚開始時間，請分別求

10、出 ei與 Li(1i10),填入下面的方格中。e1:10 l1:102.若對序列(7638139750采用堆積排序法(按照值的大小從小到大)進行排序，請分別在下表中寫出每一趟的結(jié)果：原始序列 76 38 65 13 97 27 50 49 寫出前八趟排序結(jié)果五、算法題 (共 25分)1.已知長度為 n的線性表 A采用順序存儲結(jié)構(gòu)，并且元素按值大小非遞減排列，下面的算法刪除線性表中多余的值相同的元素。請在算法的空白處填入適當內(nèi)容，使之能夠正常工作。(10分)procedure DEL (A,n)i1while _ doif (AiAi+1 thenii+1else / 查找滿足條件的元素 / for _ doAj-1Ajend / 刪除第 i+1個元素 (滿足條件的元素) /_ / 修改線性表的長度 /endend2.已知非空線性鏈表的鏈結(jié)點的構(gòu)造為 date|link，第一個鏈結(jié)點的指針為 list，下面的算法刪除鏈表的第 i個結(jié)點（設(shè) i0(15分)procedure DEL (list,i,item)_ / 給變量 q賦初值 /if (i=1