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

1、濟南鐵道職業(yè)技術(shù)學(xué)院專升本輔導(dǎo)數(shù)據(jù)結(jié)構(gòu)試題(模A)、單項選擇題(從下列各題四個備選答案中選出一個正確答案，將其代號(A,B,C,D)寫在下表中,答題寫在其它地方無效；每小題 1分,共11分)題號1234567891011答案1.數(shù)據(jù)的不可分割的基本單位是A.元素 B.結(jié)點 C.數(shù)據(jù)類型 D.數(shù)據(jù)項2. 下列算法suanfa2的時間復(fù)雜度為 。int sua nfa2(i nt n) int t=1；while(t0)個結(jié)點的完全二叉樹的深度是 。A. log 2(n)B. log 2(n)+1C. Hjog 2(n+1) D.log2(n)+17. 與中綴表達式a+b*c-d等價的前綴表達式是

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

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

4、多為 次；若查找失敗 , 比較關(guān)鍵字的次數(shù)為 次。8.對長度為400的表采用分塊（區(qū)）查找,最理想的塊長為 。三、回答下列問題 （ 每小題 5 分， 共 10 分）1. 線性表的存儲結(jié)構(gòu) ， 在什么情況下采用順序結(jié)構(gòu) ? 為什么 ?2. 二叉樹有哪幾種基本形態(tài) ? 畫圖說明之。四、試畫出下列存儲結(jié)構(gòu)圖 （ 每小題 4 分， 共 20 分）1. 數(shù)組 A1.2，0.2的以列序為主序的順序存儲結(jié)構(gòu)。2. 依次將元素 A，C，D，B 插入一個初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?， 試畫出所有插入完成之后的鏈 式棧。3. 二叉樹的順序存儲結(jié)構(gòu)4.圖的鄰接矩陣5.有向圖的逆鄰接表五、求解下列問題(每小題6分，共24

5、分)1. 給定30個字符組成的電文：D D D D D A A A 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è)計哈夫曼(Huffman)編碼。(1) 畫出相應(yīng)的哈夫曼樹；分別列出A、B C D E、F的哈夫曼碼；(3)計算該樹的帶權(quán)路徑長度WPL2.試按表(10,8,9,12,20,5,6,15,19,25 )中元素的排列次序?qū)⑺性夭迦胍豢贸跏紴榭盏亩媾判驑渲校怪允且豢枚媾判驑洹?1) 試畫出插入完成之后的二叉排序樹；(2) 若查找元素17,它將依次與二叉排序樹中哪些元素比較大小ASL。(3) 假設(shè)每個

6、元素的查找概率相等，試計算該樹的平均查找長度(4) 對該樹進行中序遍歷，試寫出中序遍歷序列。T1 T2 T3 T44.找出下面網(wǎng)絡(luò)的最小生成樹。六、填空題（在算法中有下劃線_的位置填空，使之成為完整、正確的算法）算法說明：已知r1.n是n個記錄的遞增有序表，用折半查找法查找關(guān)鍵字為k的記錄，若查找失敗,則輸出” Failure ” ,返回零；否則輸出” Success” ,并返回該記錄的序號值。（共 8分）算法（C函數(shù)）:int bin _search（struct arecord r,i nt n ,k:keytype）/* r1.n 為n個記錄的遞增有序表,k為關(guān)鍵字*/ int low, mid, hig；low=1 ； hig=n ； /* 各變量初始化 */ while( ) mid= ；if(krmid.key) else if(k=rmid.key) ；else 七、算法設(shè)計 （算法中必須有注釋 ,每小題 8分,共 16分）1. 設(shè) n 個元素的線性表順序存儲在一維數(shù)組st1.maxlen 的前 n 個位置上 , 試將新元素 e插入表中第 i-1 個和第