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

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

3、在單鏈表中，已知 q指的結(jié)點(diǎn)是 P指的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若在 q和 p指的結(jié)點(diǎn)之間插入一個(gè)由 s指的結(jié)點(diǎn)，則需執(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所指的那個(gè)鏈結(jié)點(diǎn)前面插入一個(gè)由 p指的鏈結(jié)點(diǎn)的動(dòng)作對(duì)應(yīng)的語(yǔ)句依次為:rlink(p)q,llink(p)llink(q),llink(Q)p,_rlink(llink(p)_-p_條賦值語(yǔ)句）( )A.rlink(q)p B.rlink(llink(q)p C.

4、rlink(llink(p)p D.rlink(rlink(p)p4.為了節(jié)省存儲(chǔ)空間，將n階對(duì)稱矩陣 A中包括主對(duì)角線元素在內(nèi)的下三角部分的所有元素按照行序?yàn)橹餍蚍绞酱娣旁谝痪S數(shù)組 B1:n(n-1)/2中，對(duì)任意下三角部分的元素 aij(ij)在 B的下標(biāo) 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,下面的四個(gè)序列中，_不可能是它的輸出序列。( )A.a,c,b,d B.b,c,d,aC.d,c,a,b D.c,d,b,a6.若非空隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，front和 rear一個(gè)

5、元素的操作時(shí)依次執(zhí)行 pfront，_ ，call RET(P)。( )A.frontlink(rear) B.rearlink(p)C.rearlink(front) D.frontlink(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,d)的長(zhǎng)度為 ( )A.2 B.3 C.4 D.59.在初始為空的雜湊表中依次插入關(guān)鍵字序列(MONTUEWEDTHUFRISATSUN), 雜湊函數(shù)為 H(k)=iMOD 7，其中，i為關(guān)鍵字 k的第一個(gè)字

6、母在英文字母表中的序號(hào)，地址值域?yàn)?: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.從未排序序列中選擇一個(gè)元素，該元素將未排序序列分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素。后一部分中所有元素都大于等于所選元素，而所選元

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

8、知序列(34764518265492)，按照逐點(diǎn)插入法建立一棵二叉排序列樹(shù)，該樹(shù)的深度是_。7.一個(gè)不帶有權(quán)的有向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣是一個(gè)_。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的最小生成樹(shù)的權(quán)值之和為_(kāi) 。9.在線性表中采用折半查找法（二分查找法）查找一個(gè)數(shù)據(jù)元素，線性表中元素應(yīng)該按值有序，并且采用_存儲(chǔ)方法。10.若對(duì)序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則第

9、三趟結(jié)束后序列的狀態(tài)是_ 。四、問(wèn)題求解題 (每小題 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 ；(注：頂點(diǎn)偶對(duì)的右括號(hào)下方的數(shù)據(jù)表示該邊上的權(quán)值)。e1與 L1分別表示活動(dòng) a1的最早開(kāi)始時(shí)間與最晚開(kāi)始時(shí)間，請(qǐng)分別求

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