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

1、數(shù)據(jù)結(jié)構(gòu)專升本考試試題(2015 年 3 月)一、單項(xiàng)選擇題 ( 本大題共 20 小題 , 每小題 2 分, 共 40 分)1. 對(duì)于一個(gè)算法 , 當(dāng)輸入非法數(shù)據(jù)時(shí) , 也要能作出相應(yīng)的處理 , 這種要求稱為 ( ) 。(A)正確性(B)可行性(C)健壯性(D)輸入性2. 設(shè) S 為 C 語(yǔ)言的語(yǔ)句 , 計(jì)算機(jī)執(zhí)行下面算法時(shí) , 算法的時(shí)間復(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)路徑長(zhǎng)度WPL等于 ()(A) 除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之與(B)所有結(jié)點(diǎn)權(quán)值之與(C) 各葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之與(D)根結(jié)點(diǎn)的值10. 線索二叉鏈表就是利用 ( )域存儲(chǔ)后繼結(jié)點(diǎn)的地址。(A)lchild(B)data(C)rchild(D)root11. 研究數(shù)據(jù)結(jié)構(gòu)就就是研究()。(A)數(shù)據(jù)的邏輯結(jié)構(gòu)(B)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)(D)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本操作12. 算法分析的兩個(gè)主要方面就是()。(A)空間復(fù)雜度與時(shí)間復(fù)雜度(B) 正確性與簡(jiǎn)單

3、性(C)可讀性與文檔性(D)數(shù)據(jù)復(fù)雜性與程序復(fù)雜性13. 若一個(gè)線性表中最常用的操作就是取第 i 個(gè)元素與找第 i 個(gè)元素的前趨元素 , 則采用 ( )存儲(chǔ)方式最節(jié)省時(shí)間。(A) 順序表(B)單鏈表(C)雙鏈表(D)單循環(huán)鏈表14. 在一個(gè)長(zhǎng)度為 n 的順序表中 , 在第 i 個(gè)元素之前插入一個(gè)新元素時(shí) , 需向后移動(dòng) ( ) 個(gè)元素。(A) n-i(B) n-i+1(C)n-i-1(D)i15. 非空的循環(huán)單鏈表head 的尾結(jié)點(diǎn) p 滿足 ()。(A) p-next=head(B) p-next=NULL(C) p=NULL(D)p=head16. 一個(gè)棧的輸入序列為 :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 個(gè)字符開始的連續(xù) k 個(gè)字符組成的子串的操作 , 則對(duì)于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é)點(diǎn)總數(shù)為 ( ) 。(A)31(B)32(C)33(D)162

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

6、為 :;5.n個(gè) 結(jié)點(diǎn) 無(wú)向 完全 圖的的邊數(shù)為,n 個(gè)結(jié)點(diǎn)的生成樹的邊數(shù)為。6. 已知一有向無(wú)環(huán)圖如下 :BFADGCE任意寫出二種拓?fù)渑判蛐蛄?:、。7. 已知二叉樹的中序遍歷序列為BCA,后序遍歷序列為CBA,則該二叉樹的先序遍歷序列為,層序遍歷序列為。8. 數(shù) 據(jù) 的 存 儲(chǔ) 結(jié) 構(gòu) 可 用 四 種 基 本 的 存 儲(chǔ) 方 法 表 示 , 它 們 分 別 就是。9. 在圖形結(jié)構(gòu)中 , 每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)與后續(xù)結(jié)點(diǎn)數(shù)可以。10. 寫出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L 為空表的條件。11. 哈夫曼樹就是其樹的帶權(quán)路徑長(zhǎng)度的二叉樹。12.n 個(gè)頂點(diǎ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,要求用線性探測(cè)法處理沖突。 (8 分)(1) 構(gòu)造 HASH表。(2) 分別求查找成功與不成功時(shí)的平均查找長(zhǎng)度。（ 2） 對(duì) (1) 中所建立的二叉排序樹進(jìn)行中序遍歷, 寫出遍歷序列。3已知一維數(shù)組中的數(shù)據(jù)為 (18,12,25,53,18), 試寫出插入排序 ( 升序 ) 過程。并指出具有 n 個(gè)元素的插入排序的時(shí)間復(fù)雜度就是多少？ (6 分)4已知二叉樹的先序遍歷序列為 ABCDEFGH,中序遍歷序列為 CBEDFAGH,畫出該二叉樹。 (5 分)5已知一網(wǎng)絡(luò)

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

9、 分, 要有過程 ) 。(1) 畫出對(duì)應(yīng)的 Huffman 樹。(2) 計(jì)算帶權(quán)路徑長(zhǎng)度 WPL。2. 設(shè)順序表 va 中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法, 將 x 插入到順序表的適當(dāng)位置上, 以保持該表的有序性。(3) 求 A、 B、 C、 D、 E、 F 的 Huffman 編碼。四、程序分析填空題 ( 本大題共 2 小題 , 每小題 5 分, 共 10 分)1. 函數(shù) GetElem 實(shí)現(xiàn)返回單鏈表的第 i 個(gè)元素 , 請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。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