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

1、數(shù)據(jù)結(jié)構(gòu)專升本考試試題（ 20XX 年 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；j<i ；j+) S；(A) n2(B) O(nlgn)(C) O(n)(D) O(n2)3折半查找法適用于（）。（A）有序順序表（B）有序單鏈表（C）有序順序表和有序單鏈表都可以（D）無(wú)限制4順序存儲(chǔ)結(jié)構(gòu)的優(yōu)勢(shì)是（）

2、。（A）利于插入操作（B）利于刪除操作（C）利于順序訪問（D）利于隨機(jī)訪問5深度為 k 的完全二叉樹，其葉子結(jié)點(diǎn)必在第（）層上。（ A） k-1（B）k（C）k-1 和 k（D）1 至 k6具有 60 個(gè)結(jié)點(diǎn)的二叉樹，其葉子結(jié)點(diǎn)有12 個(gè)，則度為 1 的結(jié)點(diǎn)數(shù)為（）。（A）11（B）13（C）48（D）377圖的 Depth-First Search(DFS)遍歷思想實(shí)際上是二叉樹（）遍歷方法的推廣。（A）先序（ B）中序（ C）后序（ D）層序8在下列鏈隊(duì)列 Q中，元素 a 出隊(duì)的操作序列為（）。frontabcd Qrear（ A） p=Q.front->next; p->ne

3、xt= Q.front->next;（ B） p=Q.front->next; Q.front->next=p->next;（ C） p=Q.rear->next; p->next= Q.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

4、）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)單性（ 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

5、-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，則棧的不可能輸出的序列是（）。（ 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） jin

6、g& （ 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）1620如果從無(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 線性表（a1,a 2,a n）的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)每個(gè)

7、單元的長(zhǎng)度為L(zhǎng)，元素 ai 的存儲(chǔ)地址 LOC(ai)為4已知一雙向鏈表如下 ( 指針域名為 next 和 prior)：xyqpe現(xiàn)將 p 所指的結(jié)點(diǎn)插入到x 和 y 結(jié)點(diǎn)之間，其操作步驟為：；5 n 個(gè)結(jié)點(diǎn)無(wú)向完全圖的的邊數(shù)為， n個(gè)結(jié)點(diǎn)的生成樹的邊數(shù)為。6已知一有向無(wú)環(huán)圖如下：BFDGACE任意寫出二種拓?fù)渑判蛐蛄校?、?已知二叉樹的中序遍歷序列為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哈夫

8、曼樹是其樹的帶權(quán)路徑長(zhǎng)度的二叉樹。12n個(gè)頂點(diǎn)的連通圖至少有條邊。三、應(yīng)用題（本大題共6 小題，共 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給定表（ 19,14,22,15,20,21,56,10）。（ 6 分）（1） 按元素在表中的次序，建立一棵二叉排序樹。（ 2） 對(duì) (1) 中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。3已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18） ,試寫出插入排序（升序）

9、過程。并指出具有 n 個(gè)元素的插入排序的時(shí)間復(fù)雜度是多少？(6 分)4已知二叉樹的先序遍歷序列為 ABCDEFGH，中序遍歷序列為 CBEDFAGH，畫出該二叉樹。（5 分）5已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)A 開始的最小生成樹。 (6 分 )A B CDE FA651B653C572D15764E366F2466已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(9 分，要有過程 ) 。（1）畫出對(duì)應(yīng)的 Huffman 樹。（2）計(jì)算帶權(quán)路徑長(zhǎng)度WPL。（3）求 A、B、C、D、E、F 的 Huff

10、man 編碼。四、程序分析填空題（本大題共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&&j<i)(1) ;+j;if(!p|j>i) return ERROR;*e=(2);return OK;2函數(shù) ListDelete_sq實(shí)現(xiàn)順序表刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int ListDelete_sq(Sqlist *L,int i)int k;if(i<1|i>L->length) return ERROR;for(k=i-1