濟(jì)南鐵道職業(yè)技術(shù)學(xué)院專升本輔導(dǎo)

1、濟(jì)南鐵道職業(yè)技術(shù)學(xué)院專升本輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)試題(模A)一、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案,將其代號(hào)(A,B,C,D)寫在下表中,答題寫在其它地方無效；每小題1分,共11分)題號(hào)1234567891011答案1.數(shù)據(jù)的不可分割的基本單位是_。 A.元素 B.結(jié)點(diǎn) C.數(shù)據(jù)類型 D.數(shù)據(jù)項(xiàng)2.下列算法suanfa2的時(shí)間復(fù)雜度為_。int suanfa2(int n) int t=1； while(t<=n) t=t*2；return t； A.O(log2n) B.O(2n) C.O(n2) D.O(n)3._又稱為FIFO表。A.隊(duì)列 B.散列表 C.棧 D.哈希表 4

2、.若6行8列的數(shù)組以列序?yàn)橹餍蝽樞虼鎯?chǔ),基地址為1000,每個(gè)元素占2個(gè)存儲(chǔ)單元,則第5行第3列的元素(假定無第0行第0列)的地址是_。 A.1086 B.1032 C.1068 D.答案A,B,C都不對5.廣義表(a,(b,( ),c),(d,(e)的深度是_。 A.5 B.4 C.3 D.26.有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是_。 A.élog2(n)ù B.élog2(n)+1ù C.ëlog2(n+1)û D.ëlog2(n)+1û 7.與中綴表達(dá)式a+b*c-d等價(jià)的前綴表達(dá)式是_。 A.+

3、a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*- 8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次 與表中元素_進(jìn)行比較,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,379.對長度為10的表作選擇(簡單選擇)排序,共需比較_次關(guān)鍵字。 A.45 B.90 C.55 D.11010.對n個(gè)元素的表作快速排序,在最壞情況下,算法的時(shí)間復(fù)雜度為_。 A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n ) 11.對長度為10的表作2_路歸并排序,共需

4、移動(dòng)_次(個(gè))記錄。 A.20 B.45 C.40 D.30二、填空(每空1分,共11分)1.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱為 _。2.線性表中 _ 稱為表的長度。3.棧中元素的進(jìn)出原則為 _ 。4.設(shè)數(shù)組A1.10,1.8的基地址為2000,每個(gè)元素占2個(gè)存儲(chǔ)單元,若以行序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A4,5的存儲(chǔ)地址為_；若以列序?yàn)橹餍蝽樞虼鎯?chǔ),則元素A4,5的存儲(chǔ)地址為_。5.一棵深度為6的滿二叉樹有_個(gè)非終端結(jié)點(diǎn)。6.若一棵二叉樹中有8個(gè)度為2的結(jié)點(diǎn),則它有_個(gè)葉子。7.順序查找n個(gè)元素的順序表,當(dāng)使用監(jiān)視哨時(shí),若查找成功,比較關(guān)鍵字的次數(shù)至少為_次, 最多為_次；若查找失敗,比較關(guān)

5、鍵字的次數(shù)為_次。8.對長度為400的表采用分塊(區(qū))查找,最理想的塊長為_。三、回答下列問題 (每小題5分,共10分)1.線性表的存儲(chǔ)結(jié)構(gòu),在什么情況下采用順序結(jié)構(gòu)? 為什么?2.二叉樹有哪幾種基本形態(tài)? 畫圖說明之。四、試畫出下列存儲(chǔ)結(jié)構(gòu)圖(每小題4分,共20分)1.數(shù)組A1.2,0.2 的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)。 2.依次將元素 A,C,D,B 插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏！?.二叉樹的順序存儲(chǔ)結(jié)構(gòu): 4.圖的鄰接矩陣: 5.有向圖的逆鄰接表: 五、求解下列問題 (每小題6分,共24分)1.給定30個(gè)字符組成的電文: D D D D D A A A

6、B E E A A F C D A A C A B B C C C B A A D D試為字符 A、B、C、D、E、F 設(shè)計(jì)哈夫曼(Huffman)編碼。 (1)畫出相應(yīng)的哈夫曼樹； (2)分別列出 A、B、C、D、E、F 的哈夫曼碼；(3)計(jì)算該樹的帶權(quán)路徑長度WPL。 2.試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹中, 使之仍是一棵二叉排序樹。 (1)試畫出插入完成之后的二叉排序樹； (2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小? (3)假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹的平均查找長度 AS

7、L。 (4)對該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。3.試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹。 T1 T2 T3 T44.找出下面網(wǎng)絡(luò)的最小生成樹。 六、填空題(在算法中有下劃線_的位置填空,使之成為完整、正確的算法)算法說明:已知r1.n是n個(gè)記錄的遞增有序表,用折半查找法查找關(guān)鍵字為k的記錄,若查找失敗,則輸出”Failure”,返回零；否則輸出”Success”,并返回該記錄的序號(hào)值。(共8分)算法(C函數(shù)): int bin_search(struct arecord r,int n,k:keytype) /* r1.n為n個(gè)記錄的遞增有序表,k為關(guān)鍵字 */ int low, mid, hig ； low=1； hig=n ； /* 各變量初始化 */ while( _ ) mid=_ ； if(k<rmid.key) _ ； else if(k=rmid.key) _ ； _ ； else _ ； _ ； _ ； 七、算法設(shè)計(jì)(算法中必須有注釋,每小題8分,共16分)1.設(shè)n個(gè)元素的線性表順序存儲(chǔ)在一維數(shù)組s