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

1、數(shù)據(jù)結(jié)構(gòu)專升本考試試題(2015 年 3 月)專升本試題數(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) 正確性與簡單性(C)可讀性與文檔性(D)數(shù)據(jù)復(fù)雜性與程序復(fù)雜性13. 若一個線性表中最常用的操作就是取第i 個元素與找第 i 個元素的前趨元素 , 則采用 ()一、單項選擇題 ( 本大題共 20 小題 , 每小題 2 分, 共 40 分)1.對于一個算法 , 當(dāng)輸入非法數(shù)據(jù)時 ,也要能作出相應(yīng)的處理 , 這種要求稱為 () 。(A)正確性 (B)

2、可行性(C)健壯性(D)輸入性2.設(shè) S 為 C 語言的語句 , 計算機(jī)執(zhí)行下面算法時 , 算法的時間復(fù)雜度為 ( )。for(i=n-1;i>=0;i-)for(j=0;j<i;j+)S;(A) n2(B) O(nlgn)(C) O(n)(D) O(n2)3.折半查找法適用于 () 。(A) 有序順序表(B)有序單鏈表(C) 有序順序表與有序單鏈表都可以 (D) 無限制4. 順序存儲結(jié)構(gòu)的優(yōu)勢就是 ( ) 。(A) 利于插入操作(B)利于刪除操作(C) 利于順序訪問(D)利于隨機(jī)訪問5.深度為 k 的完全二叉樹 , 其葉子結(jié)點必在第 ( )層上。(A)k-1 (B)k (C)k-

3、1與 k (D)1至 k6.具有 60 個結(jié)點的二叉樹 , 其葉子結(jié)點有12 個 , 則度為 1 的結(jié)點數(shù)為 ( )。(A)11(B)13(C)48(D)377.圖的 Depth-First Search(DFS)遍歷思想實際上就是二叉樹 ( )遍歷方法的推廣。(A) 先序 (B) 中序 (C)后序 (D) 層序8.在下列鏈隊列 Q中 , 元素 a 出隊的操作序列為 ()。frontabcd Qrear(A)p=Q、 front->next; p->next= Q、front->next;(B)p=Q、 front->next; Q、front->next=p-&

4、gt;next;(C)p=Q、 rear->next; p->next= Q、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)就就是研究()。存儲方式最節(jié)省時間。(A) 順序表(B)單鏈表(C)雙鏈表(D)單循環(huán)鏈表14.在

5、一個長度為 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,則棧的不可能輸出的序列就是 () 。(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 個字符

6、組成的子串的操作 , 則對于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)1620.如果從無向圖的任一頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點, 則該圖一定就是() 。(A) 完全圖(B) 連通圖(C) 有回路(D) 一棵樹二、填空題 ( 本大題共 20 個空 , 每空 2 分, 共 40

7、分)1 邏輯結(jié)構(gòu)決定了算法的,而存儲結(jié)構(gòu)決定了算法的。2 棧與隊列都就是一種的線性表 , 棧的插入與刪除只能在進(jìn)行。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é)點之間 , 其操作步驟為 :;5.n個 結(jié)點 無向 完全 圖的的邊數(shù)為,n 個結(jié)點的生成樹的邊數(shù)為。專升本試題數(shù)據(jù)結(jié)構(gòu)6. 已知一有向無環(huán)圖如下 :BFADGCE（ 2） 對 (1) 中所建立的二叉排序樹進(jìn)行中序遍歷, 寫出遍歷序列。任意寫出

8、二種拓?fù)渑判蛐蛄?:、。7. 已知二叉樹的中序遍歷序列為BCA,后序遍歷序列為CBA,則該二叉樹的先序遍歷序列為,層序遍歷序列為。8. 數(shù) 據(jù) 的 存 儲 結(jié) 構(gòu) 可 用 四種 基 本 的 存 儲 方 法 表 示 ,它 們 分 別 就3已知一維數(shù)組中的數(shù)據(jù)為 (18,12,25,53,18),試寫出插入排序 ( 升序 ) 過程。并指出具有 n是。個元素的插入排序的時間復(fù)雜度就是多少？(6 分)9. 在圖形結(jié)構(gòu)中 , 每個結(jié)點的前驅(qū)結(jié)點數(shù)與后續(xù)結(jié)點數(shù)可以。10. 寫出帶頭結(jié)點的雙向循環(huán)鏈表L 為空表的條件。11. 哈夫曼樹就是其樹的帶權(quán)路徑長度的二叉樹。12.n 個頂點的連通圖至少有條邊。三、應(yīng)

9、用題 ( 本大題共 6 小題 , 共 40 分)1. 設(shè)散列函數(shù)H(k)=k % 13, 設(shè)關(guān)鍵字系列為 22,12,24,6,45,7,8,13,21,要求用線性探測法處理沖突。 (8分)4已知二叉樹的先序遍歷序列為 ABCDEFGH,中序遍歷序列為 CBEDFAGH,畫出該二叉樹。(1) 構(gòu)造 HASH表。(5 分)(2)分別求查找成功與不成功時的平均查找長度。5已知一網(wǎng)絡(luò)的鄰接矩陣如下, 求從頂點 A 開始的最小生成樹。 (6 分)A B CDE FA651B653C572D15764E366F2462給定表 (19,14,22,15,20,21,56,10)。(6 分)（1） 按元素在

10、表中的次序 , 建立一棵二叉排序樹。專升本試題數(shù)據(jù)結(jié)構(gòu)L->slistk= (1) ;(2);return OK;6. 已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表:五、算法設(shè)計題 ( 本大題共 2 小題 , 每小題 10 分, 共 20 分)1.編寫算法 , 實現(xiàn)帶頭結(jié)點單鏈表的逆置算法。ABCDEF0、 150、150、 10、10、20、 3把這些字母與頻率作為葉子結(jié)點及權(quán)值, 完成如下工作 (9 分, 要有過程 ) 。(1) 畫出對應(yīng)的 Huffman 樹。(2) 計算帶權(quán)路徑長度WPL。2. 設(shè)順序表 va 中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法 , 將 x 插入到順序表的適保持表的有序性。(3) 求 A、 B、 C、 D、 E、 F 的 Huffman 編碼。四、程序分析填空題 ( 本大題共 2 小題 , 每小題 5 分, 共 10 分)1. 函數(shù) GetElem 實現(xiàn)返回單鏈表的第 i 個元素 , 請在空格處將算法補(bǔ)充完整。int GetElem(LinkList L,int i,Elemtype *e) LinkList p;int j;p=L->next;j=1; while(p&&j<i)(1) ;+j;if(!p|j>i) return ERROR; *e= (2)