專升本試題數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)專升本考試試題(2015 年 3 月)一、單項選擇題 ( 本大題共 20 小題 , 每小題 2 分, 共 40 分)1. 對于一個算法 , 當(dāng)輸入非法數(shù)據(jù)時 , 也要能作出相應(yīng)的處理 , 這種要求稱為 ( ) 。(A)正確性(B)可行性(C)健壯性(D)輸入性2. 設(shè) S 為 C 語言的語句 , 計算機執(zhí)行下面算法時 , 算法的時間復(fù)雜度為 ()。for(i=n-1;i=0;i-)for(j=0;jnext; p-next= Q、front-next;(B)p=Q、 front-next; Q、front-next=p-next;(C)p=Q、 rear-next; p-next= Q

2、、rear-next;(D)p=Q-next; Q-next=p-next;9. Huffman 樹的帶權(quán)路徑長度WPL等于 ()(A) 除根結(jié)點之外的所有結(jié)點權(quán)值之與(B)所有結(jié)點權(quán)值之與(C) 各葉子結(jié)點的帶權(quán)路徑長度之與(D)根結(jié)點的值10. 線索二叉鏈表就是利用 ( )域存儲后繼結(jié)點的地址。(A)lchild(B)data(C)rchild(D)root11. 研究數(shù)據(jù)結(jié)構(gòu)就就是研究()。(A)數(shù)據(jù)的邏輯結(jié)構(gòu)(B)數(shù)據(jù)的存儲結(jié)構(gòu)(C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)(D)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作12. 算法分析的兩個主要方面就是()。(A)空間復(fù)雜度與時間復(fù)雜度(B) 正確性與簡單

3、性(C)可讀性與文檔性(D)數(shù)據(jù)復(fù)雜性與程序復(fù)雜性13. 若一個線性表中最常用的操作就是取第 i 個元素與找第 i 個元素的前趨元素 , 則采用 ( )存儲方式最節(jié)省時間。(A) 順序表(B)單鏈表(C)雙鏈表(D)單循環(huán)鏈表14. 在一個長度為 n 的順序表中 , 在第 i 個元素之前插入一個新元素時 , 需向后移動 ( ) 個元素。(A) n-i(B) n-i+1(C)n-i-1(D)i15. 非空的循環(huán)單鏈表head 的尾結(jié)點 p 滿足 ()。(A) p-next=head(B) p-next=NULL(C) p=NULL(D)p=head16. 一個棧的輸入序列為 :a,b,c,d,e

4、, 則棧的不可能輸出的序列就是 ( ) 。(A)a,b,c,d,e(B)d,e,c,b,a(C)d,c,e,a,b(D)e,d,c,b,a17. 設(shè) SUBSTR(S,i,k) 就是求 S 中從第 i 個字符開始的連續(xù) k 個字符組成的子串的操作 , 則對于S=Beijing&Nanjing ,SUBSTR(S,4,5)=()。(A) ijing(B) jing& (C) ingNa(D) ing&N18. 廣義表 (a),a)的表尾就是 ()。(A) a(B) (a)(C) ()(D)(a)19. 在一棵具有 5 層的滿二叉樹中結(jié)點總數(shù)為 ( ) 。(A)31(B)32(C)33(D)162

5、0. 如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點, 則該圖一定就是()。(A) 完全圖(B) 連通圖(C) 有回路(D) 一棵樹二、填空題 ( 本大題共 20 個空 , 每空 2 分, 共 40 分)1 邏輯結(jié)構(gòu)決定了算法的,而存儲結(jié)構(gòu)決定了算法的。2 棧與隊列都就是一種的線性表 , 棧的插入與刪除只能在進行。3 線性表 (a 1,a 2, ,a n) 的順序存儲結(jié)構(gòu)中 , 設(shè)每個單元的長度為L, 元素 ai 的存儲地址 LOC(ai)為4已知一雙向鏈表如下 ( 指針域名為 next 與 prior):xyqpe現(xiàn)將 p 所指的結(jié)點插入到x 與 y 結(jié)點之間 , 其操作步驟

6、為 :;5.n個 結(jié)點 無向 完全 圖的的邊數(shù)為,n 個結(jié)點的生成樹的邊數(shù)為。6. 已知一有向無環(huán)圖如下 :BFADGCE任意寫出二種拓?fù)渑判蛐蛄?:、。7. 已知二叉樹的中序遍歷序列為BCA,后序遍歷序列為CBA,則該二叉樹的先序遍歷序列為,層序遍歷序列為。8. 數(shù) 據(jù) 的 存 儲 結(jié) 構(gòu) 可 用 四 種 基 本 的 存 儲 方 法 表 示 , 它 們 分 別 就是。9. 在圖形結(jié)構(gòu)中 , 每個結(jié)點的前驅(qū)結(jié)點數(shù)與后續(xù)結(jié)點數(shù)可以。10. 寫出帶頭結(jié)點的雙向循環(huán)鏈表L 為空表的條件。11. 哈夫曼樹就是其樹的帶權(quán)路徑長度的二叉樹。12.n 個頂點的連通圖至少有條邊。三、應(yīng)用題 ( 本大題共 6

7、小題 , 共 40 分)1. 設(shè)散列函數(shù) H(k)=k % 13, 設(shè)關(guān)鍵字系列為 22,12,24,6,45,7,8,13,21,要求用線性探測法處理沖突。 (8 分)(1) 構(gòu)造 HASH表。(2) 分別求查找成功與不成功時的平均查找長度。（ 2） 對 (1) 中所建立的二叉排序樹進行中序遍歷, 寫出遍歷序列。3已知一維數(shù)組中的數(shù)據(jù)為 (18,12,25,53,18), 試寫出插入排序 ( 升序 ) 過程。并指出具有 n 個元素的插入排序的時間復(fù)雜度就是多少？ (6 分)4已知二叉樹的先序遍歷序列為 ABCDEFGH,中序遍歷序列為 CBEDFAGH,畫出該二叉樹。 (5 分)5已知一網(wǎng)絡(luò)

8、的鄰接矩陣如下, 求從頂點 A 開始的最小生成樹。 (6 分)A B CDE FA651B653C572D15764E366F2462給定表 (19,14,22,15,20,21,56,10)。(6 分)（1） 按元素在表中的次序 , 建立一棵二叉排序樹。6. 已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表:L-slistk=(1);(2);return OK;五、算法設(shè)計題 ( 本大題共 2 小題 , 每小題 10 分, 共 20 分)1. 編寫算法 , 實現(xiàn)帶頭結(jié)點單鏈表的逆置算法。ABCDEF0、 150、150、 10、10、20、 3把這些字母與頻率作為葉子結(jié)點及權(quán)值, 完成如下工作 (9

9、 分, 要有過程 ) 。(1) 畫出對應(yīng)的 Huffman 樹。(2) 計算帶權(quán)路徑長度 WPL。2. 設(shè)順序表 va 中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法, 將 x 插入到順序表的適當(dāng)位置上, 以保持該表的有序性。(3) 求 A、 B、 C、 D、 E、 F 的 Huffman 編碼。四、程序分析填空題 ( 本大題共 2 小題 , 每小題 5 分, 共 10 分)1. 函數(shù) GetElem 實現(xiàn)返回單鏈表的第 i 個元素 , 請在空格處將算法補充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p;int j;p=L-next;j=1;while(p&ji) return ERROR;*e=(2);r