微機(jī)原理與接口7

1、濟(jì)南鐵道職業(yè)技術(shù)學(xué)院專升本輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)試題(模 G)第一部分 選擇題 (共 20分)一、單項(xiàng)選擇題 (本大題共 10小題，每小題 2分，共 20分)的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1.線性鏈表中各鏈結(jié)點(diǎn)之間的地址 A.連續(xù)與否都可以 B.部分地址必須連續(xù)C.一定不連續(xù) D.必須連續(xù)2.刪除非空雙向循環(huán)鏈表中由 q所指的鏈結(jié)點(diǎn)的過程是依次執(zhí)行以下三個(gè)動(dòng)作：rlink(llink(q)rlink(q),_,call RET(q)。 A.llink(q)q B.llink(rlink(q)qC.llink(rlink(q)llink(q) D.llink(q)rlink(q)3.在包含有 1000

2、個(gè)元素的線性表中實(shí)現(xiàn)如下四個(gè)操作，所需要的執(zhí)行時(shí)間最長的是 A.線性表采用順序存儲(chǔ)結(jié)構(gòu)，在第 10個(gè)元素后面插入一個(gè)新的元素B.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在第 10個(gè)元素后面插入一個(gè)新的元素C.線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除第 990個(gè)元素D.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除 p指的鏈結(jié)點(diǎn)4.因此在初始為空的隊(duì)列中插入元素 a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是 A.a B.bC.c D.d5.若不考慮結(jié)點(diǎn)的數(shù)據(jù)信息的組合情況，具有 3個(gè)結(jié)點(diǎn)的二叉樹共有_種形態(tài)。 A.2 B.3C.4 D.56.對(duì)任何一棵二叉樹，若n0n1n2分別是度為 012的結(jié)點(diǎn)的個(gè)數(shù)，則n0= A.n1+

3、1 B.n1+n2C.n2+1 D.2n1+17.維數(shù)組中，即ABCDFEGH，該二叉樹的中序遍歷序列為 A.G,D,B,A,F,H,C,E B.G,B,D,A,F,H,C,EC.B,D,G,A,F,H,C,E D.B,G,D,A,F,H,C,E8. 在 初 始 為 空 的 散 列 表 中 依 次 插 入 關(guān) 鍵 字 序 列(MON,TUE,WED,THU,FRI,SAT,SUN)，散列函數(shù)為 H(k)=i MOD 7，其中，i為關(guān)鍵字 k的第一個(gè)字母在英文字母表中的序號(hào)，地址值域?yàn)?0:6 ，采用線性再散列法處理沖突。插入后的散列表應(yīng)該如_ 所示。 A. 0 1 2 3 4 5 6THU T

4、UE 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 MON9.下面的序列中_是大頂堆積。 A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,110.在下述的排序方法中，不屬于內(nèi)排序方法的是是 A.插入排序法 B.選擇排序法C.拓?fù)渑判蚍?D.歸并排序法第二部分 非

5、選擇題 (共 80分)二、填空題 (本大題共 10小題，每空 2分，共 20分)請(qǐng)?jiān)诿啃☆}的空格上填上正確答案。錯(cuò)填、不填均無分。11.數(shù)據(jù)結(jié)構(gòu)課程討論的主要內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和_。12.若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_存儲(chǔ)結(jié)構(gòu)。13.若鏈結(jié)點(diǎn)的構(gòu)造為 data|next，那么，判斷由list所指的單向循環(huán)鏈表中只有一個(gè)結(jié)點(diǎn)的條件是_ _。14.求串 T在主串 S中首次出現(xiàn)的位置的操作是_。15.完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個(gè)名詞術(shù)語中，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)系的是_。16._。17.在序列(2,5,8,11,15,16,22,24,27,35

6、,50)中采用折半查找(二分查找)方法查找元素 24，需要進(jìn)行_次元素之間的比較。18.若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為 H(key)=key MOD ，與 18發(fā)生沖突的元素有_個(gè)。19.每一趟排序時(shí)從排好序的元素中挑出一個(gè)值最小的元素與這些未排小序的元素的第一個(gè)元素交換位置，這種排序方法成為_排序法。20.排序過程中所進(jìn)行的元素之間的比較次數(shù)與參加排序的序列的初始狀態(tài)無關(guān)的排序方法是_排序法。三、簡(jiǎn)答題 (本大題共 2小題，共 15分)21.(7分) 堆棧和隊(duì)列都是特殊線性表，其特殊性是什么？22.(8分) 在建散列表時(shí)，通常情況下，采用鏈地址法處理沖

7、突比采用開放地址法處理沖突的時(shí)間效率要高，為什么？四、問題求解題 (本大題共 2小題，每小題 10分，共 20分)23.折半查找過程可以利用一棵稱之為“判定樹”的二叉樹來描述，請(qǐng)畫出在長度為 13的表中進(jìn)行折半查找對(duì)應(yīng)的判定樹。24.若對(duì)序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小從小到大)進(jìn)行排序，請(qǐng)分別在下表中寫出每一趟排序的結(jié)果。原 始 序 列 49 38 27 13 97 76 50 65第 1趟的結(jié)果第 2趟的結(jié)果第 3趟的結(jié)果第 4趟的結(jié)果五、算法填空題 (本大題共 2小題，共 25分)25.(10分)已知線性表 A與線性表 B的長度分別為 n與

8、 m，并且都采用順序存儲(chǔ)結(jié)構(gòu)，下面的算法是在線性表A的第 i個(gè)位置插入線性表 B。約定：不考慮存儲(chǔ)空間溢出問題。請(qǐng)?jiān)谒惴ǖ目杖碧幪钊脒m當(dāng)內(nèi)容，使之能夠正常工作。procedure INSERT(A,n,B,m)for jn downto i doAAjend / 將 A中某些元素依次后移 m個(gè)位置 /for j1 to m doABjend / 從 A中第 i個(gè)位置開始依次插入 B中元素 /n / 修改插入以后 A的長度 /end26.(15分)已知不帶頭結(jié)點(diǎn)的非空線性鏈表的鏈結(jié)點(diǎn)的構(gòu)造為 data|link，第一個(gè)鏈結(jié)點(diǎn)的指針為 list，下面的算法將鏈表中數(shù)據(jù)域最大的那個(gè)鏈結(jié)點(diǎn)移到鏈表最后面。請(qǐng)?jiān)谒惴ǖ目杖碧幪钊脒m當(dāng)內(nèi)容，使之能夠正常工作。procedure REMOVE(list)p / p初始時(shí)指向鏈表第二個(gè)鏈結(jié)點(diǎn) /qlistrlistwhiledoif (data(p)data(q) then srqp rp / 將 p指向下一個(gè)結(jié)點(diǎn) /end / q指向值最大的那個(gè)鏈結(jié)點(diǎn)