數(shù)據(jù)結(jié)構(gòu)真題2012年10月

1、數(shù)據(jù)結(jié)構(gòu)真題2012 年 10 月( 總分： 100.00 ，做題時(shí)間： 90 分鐘 )一、 單項(xiàng)選擇題 ( 總題數(shù)： 15，分?jǐn)?shù)： 30.00)1. 一個(gè)算法的時(shí)間耗費(fèi)的數(shù)量級(jí)稱(chēng)為該算法的_（分?jǐn)?shù)： 2.00 ）A. 效率B. 難度C. 可實(shí)現(xiàn)性D. 時(shí)間復(fù)雜度 解析： 考點(diǎn) 算法的時(shí)間復(fù)雜度的概念 解析 一個(gè)算法的時(shí)間耗費(fèi)的數(shù)量級(jí)稱(chēng)為該算法的時(shí)間復(fù)雜度。2. 順序表便于 _（分?jǐn)?shù)： 2.00 ）A. 插入結(jié)點(diǎn)B. 刪除結(jié)點(diǎn)C. 按值查找結(jié)點(diǎn)D. 按序號(hào)查找結(jié)點(diǎn)解析： 考點(diǎn) 順序表的特征 解析 順序表便于按序號(hào)查找結(jié)點(diǎn)。3. 設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，指針變量 P 指向尾結(jié)點(diǎn)

2、的條件是 _（分?jǐn)?shù)： 2.00 ）A.p- next- next=headB.p- next=headC.p- next- next=NULLD.p- next=NULL解析： 考點(diǎn) 指針變量p 指向尾結(jié)點(diǎn)的判定條件 解析 單循環(huán)鏈表的指針變量p 指向尾結(jié)點(diǎn)的判定條件是p- next=head 。4. 設(shè)以數(shù)組 A0.m-1 存放循環(huán)隊(duì)列， front 指向隊(duì)頭元素， rear 指向隊(duì)尾元素的下一個(gè)位置，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為 _（分?jǐn)?shù)： 2.00 ）A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m解析： 考

3、點(diǎn) 隊(duì)列中元素個(gè)數(shù)的計(jì)算 解析 隊(duì)列中元素的個(gè)數(shù)為(rear-front+m)%m5. 下列關(guān)于順序棧的敘述中，正確的是_（分?jǐn)?shù)： 2.00 ）A. 入棧操作需要判斷棧滿，出棧操作需要判斷?？誃. 入棧操作不需要判斷棧滿，出棧操作需要判斷?？誄. 入棧操作需要判斷棧滿，出棧操作不需要判斷?？誅. 入棧操作不需要判斷棧滿，出棧操作不需要判斷?？战馕觯?考點(diǎn) 順序棧的性質(zhì)的判斷 解析 入棧操作需要判斷棧滿，出棧操作需要判斷?？铡?.A 是一個(gè) 1010 的對(duì)稱(chēng)矩陣，若采用行優(yōu)先的下三角壓縮存儲(chǔ)，第一個(gè)元素a 0， 0 的存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a 7 ， 5 的地址為 _（分?jǐn)?shù)：

4、2.00 ）A.25B.26C.33D.34解析： 考點(diǎn) 對(duì)稱(chēng)矩陣的元素的地址的計(jì)算 解析 若對(duì)稱(chēng)矩陣采用下三角壓縮存儲(chǔ)，根據(jù)其地址的計(jì)算公式，可得到所求元素的地址。7. 樹(shù)的后序遍歷等價(jià)于該樹(shù)對(duì)應(yīng)二叉樹(shù)的_（分?jǐn)?shù)： 2.00 ）A. 層次遍歷B. 前序遍歷C. 中序遍歷 D. 后序遍歷解析： 考點(diǎn) 樹(shù)的遍歷與二叉樹(shù)遍歷的關(guān)系 解析 樹(shù)的后序遍歷等價(jià)于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的中序遍歷。8. 使用二叉線索樹(shù)的目的是便于_（分?jǐn)?shù)： 2.00 ）A. 二叉樹(shù)中結(jié)點(diǎn)的插入與刪除B. 在二叉樹(shù)中查找雙親C. 確定二叉樹(shù)的高度D. 查找一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼 解析： 考點(diǎn) 二叉線索樹(shù)的使用目的 解析 二叉線索樹(shù)的

5、使用目的是便于查找一個(gè)結(jié)點(diǎn)的前趨和后繼。9. 設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為 n，則該圖邊的數(shù)目最多為 _（分?jǐn)?shù)： 2.00 ）A.n-1B.n(n-1)/2C.n(n+1)/2D.n2解析： 考點(diǎn) 無(wú)向圖的邊數(shù)的問(wèn)題 解析 無(wú)向圖的邊數(shù)最多為n(n-1)/2。10. 可進(jìn)行拓?fù)渑判虻膱D只能是 _（分?jǐn)?shù)： 2.00 ）A. 有向圖B. 無(wú)向圖C. 有向無(wú)環(huán)圖 D. 無(wú)向連通圖解析： 考點(diǎn) 拓?fù)渑判虻膱D的要求 解析 可進(jìn)行拓?fù)渑判虻膱D只能是有向無(wú)環(huán)圖。11. 下列排序方法中穩(wěn)定的是 _（分?jǐn)?shù)： 2.00 ）A. 直接插入排序B. 直接選擇排序C. 堆排序D. 快速排序解析： 考點(diǎn) 排序方法穩(wěn)定性的判斷 解

6、析 直接插入排序是穩(wěn)定的，直接選擇排序、堆排序以及快速排序是不穩(wěn)定的。12. 下列序列不為堆的是 _（分?jǐn)?shù)： 2.00 ）A.75 ， 45， 65， 30， 15， 25B.75 ， 65， 45， 30， 25， 15C.75 ， 65， 30， 15， 25， 45D.75 ， 45， 65， 25， 30， 15解析： 考點(diǎn) 堆的判斷 解析 根據(jù)堆的概念，可判斷出75，65，30，15，25，45 不為堆。13. 對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須是_（分?jǐn)?shù)： 2.00 ）A. 順序存儲(chǔ)B. 鏈?zhǔn)酱鎯?chǔ)C. 順序存儲(chǔ)且按關(guān)鍵字有序排列D. 鏈?zhǔn)酱鎯?chǔ)且按關(guān)鍵字有序排列解析： 考點(diǎn) 二分

7、查找對(duì)線性表的要求 解析 對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須是順序存儲(chǔ)且按關(guān)鍵字有序排列。14. 分別用以下序列生成二叉排序樹(shù)，其中三個(gè)序列生成的二叉排序樹(shù)是相同的，不同的序列是_（分?jǐn)?shù)： 2.00 ）A.(4 ， 1，2，3，5) B.(4 ， 2，3，1，5)C.(4 ， 5，2，1，3)D.(4 ， 2，1，5，3)解析： 考點(diǎn) 二叉排序樹(shù)的生成 解析 根據(jù)二叉排序樹(shù)的生成方法，不同的序列是A 選項(xiàng)。15. 下列關(guān)于 m階 B 樹(shù)的敘述中，錯(cuò)誤的是 _（分?jǐn)?shù)： 2.00 ）A. 每個(gè)結(jié)點(diǎn)至多有m個(gè)關(guān)鍵字B. 每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)C. 插入關(guān)鍵字時(shí)，通過(guò)結(jié)點(diǎn)分裂使樹(shù)高增加D. 刪除關(guān)

8、鍵字時(shí)通過(guò)結(jié)點(diǎn)合并使樹(shù)高降低解析： 考點(diǎn) B 樹(shù)的特征的判斷 解析 m 階 B 樹(shù)中，若樹(shù)非空，則根結(jié)點(diǎn)至少有一個(gè)關(guān)鍵字，最多有m-1 個(gè)關(guān)鍵字。二、 填空題 ( 總題數(shù)： 10，分?jǐn)?shù)： 20.00)16. 數(shù)據(jù)元素之間的邏輯關(guān)系稱(chēng)為數(shù)據(jù)的1 結(jié)構(gòu)。（分?jǐn)?shù)： 2.00 ）解析：邏輯 考點(diǎn) 數(shù)據(jù)的邏輯結(jié)構(gòu)的概念 解析 數(shù)據(jù)元素之間的邏輯關(guān)系稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)。17. 在線性表中，表的長(zhǎng)度定義為1 。（分?jǐn)?shù)： 2.00 ）解析：數(shù)據(jù)元素的個(gè)數(shù) 考點(diǎn) 線性表中表的長(zhǎng)度的計(jì)算 解析 在線性表中，表的長(zhǎng)度定義為數(shù)據(jù)元素的個(gè)數(shù)。18. 用 S 表示入棧操作，X 表示出棧操作，若元素入棧的順序?yàn)轫樞颍鄳?yīng)的

9、S 和 X 的操作序列為1 。1、2、3、 4，為了得到1、 3、 4、2 的出棧（分?jǐn)?shù)： 2.00 ）解析： SXSSXSXX 考點(diǎn) 棧的操作 解析 若元素入棧的順序?yàn)?、 2、 3、4，為了得到1、3、4、 2 的出棧順序，相應(yīng)的S 和 X 的操作序列為SXSSXSXX。19. 在二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最短的樹(shù)稱(chēng)為1 。（分?jǐn)?shù)： 2.00 ）解析：哈夫曼樹(shù) 考點(diǎn) 哈夫曼樹(shù)的概念 解析 在二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最短的樹(shù)稱(chēng)為哈夫曼樹(shù)。20. 已知廣義表 G，head(G) 與 tail(G) 的深度分別為 4 和 6，則 G的深度是 1 。（分?jǐn)?shù)：解析：62.00 ）考點(diǎn) 廣義表的深度 解析

10、若表尾深度大于表頭深度，那么線性表的深度為表尾的深度。21. 一組字符 (a ，b，c ，d) 在文中出現(xiàn)的次數(shù)分別為(7 ， 6， 3， 5) ，字符 d 的哈夫曼編碼的長(zhǎng)度為 1 。（分?jǐn)?shù)： 2.00 ）解析： 2 考點(diǎn) 哈夫曼編碼解析先構(gòu)造出相應(yīng)的哈夫曼樹(shù)，然后進(jìn)行編碼。22. 在一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要1條邊。（分?jǐn)?shù)： 2.00 ）解析： n-1 考點(diǎn) 連通無(wú)向圖的邊數(shù)的問(wèn)題解析在一個(gè)具有n 個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要n-1 條邊。23. 直接選擇排序算法的時(shí)間復(fù)雜度是1 。（分?jǐn)?shù)： 2.00 ）解析： O(n 2 ) 考點(diǎn) 直接選擇排序算法

11、的時(shí)間復(fù)雜度解析直接選擇排序算法的時(shí)間復(fù)雜度是O(n 2 ) 。24. 對(duì)于長(zhǎng)度為 81 的表，若采用分塊查找，每塊的最佳長(zhǎng)度為1 。（分?jǐn)?shù)： 2.00 ）解析： 9 考點(diǎn) 分塊查找解析對(duì)于長(zhǎng)度為81 的表，若采用分塊查找，每塊的最佳長(zhǎng)度為9。25. 用二叉鏈表保存有n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，則結(jié)點(diǎn)中有1 個(gè)空指針域。（分?jǐn)?shù)： 2.00 ）解析： n+1 考點(diǎn) 二叉鏈表中空指針域的個(gè)數(shù)解析用二叉鏈表保存有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，則結(jié)點(diǎn)中有n+1 個(gè)空指針域。三、 解答題 ( 總題數(shù)： 4，分?jǐn)?shù)： 20.00)26. 假設(shè) Q 是一個(gè)具有 11 個(gè)元素存儲(chǔ)空間的循環(huán)隊(duì)列( 隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位

12、置，隊(duì)頭指針指向隊(duì)頭元素 ) ，初始狀態(tài) Q.front=Q.rear=0；寫(xiě)出依次執(zhí)行下列操作后頭、尾指針的當(dāng)前值。a， b，c ，d， e，f 入隊(duì)， a， b， c ，d 出隊(duì)； (1)Q.front=_；Q.rear=_ 。g， h，i ，j ， k ，1 入隊(duì)， e， f ， g，h 出隊(duì)； (2)Q.front=_；Q.rear=_ 。M， n，o，P 入隊(duì)， i ，j ，k ， l ， m出隊(duì)； (3)Q.front=_； Q.rear=_ 。（分?jǐn)?shù)： 5.00 ）_正確答案：()解析： Q.front=4；Q.rear=6 。 Q.front=8；Q.rear=1 。 Q.fr

13、ont=2； Q.rear=5 。 考點(diǎn) 循環(huán)隊(duì)列的操作27. 已知一個(gè)無(wú)向圖如下圖所示， 以為起點(diǎn)， 用普里姆 (Prim) 算法求其最小生成樹(shù)， 畫(huà)出最小生成樹(shù)的構(gòu)造過(guò)程。（分?jǐn)?shù)： 5.00 ）_正確答案： ()解析：最小生成樹(shù)的生成過(guò)程如下： 考點(diǎn) Prim算法求最小生成樹(shù)的過(guò)程用歸并排序法對(duì)序列(98 ，36，-9 ，0，47，23，1， 8) 進(jìn)行排序，問(wèn)：（分?jǐn)?shù)：5.00 ）(1). 一共需要幾趟歸并可完成排序。（分?jǐn)?shù)：2.50 ）_正確答案： ()解析：需要 3 趟(2). 寫(xiě)出第一趟歸并后數(shù)據(jù)的排列次序。（分?jǐn)?shù)：2.50 ）_正確答案：()解析： (36 ，98，9，0，23，

14、47，1， 8) 考點(diǎn) 歸并排序法的應(yīng)用一組記錄關(guān)鍵字(55 ，76，44，32，64，82，20，16，43) ，用散列函數(shù)H(key)=key%11將記錄散列到散列表 HT_中去，用線性探測(cè)法解決沖突。（分?jǐn)?shù)：5.00 ）(1).畫(huà)出存入所有記錄后的散列表。（分?jǐn)?shù)：2.50 ）_正確答案： ()解析：存入所有記錄的散列表為：(2). 求在等概率情況下，查找成功的平均查找長(zhǎng)度。（分?jǐn)?shù)：2.50 ）_正確答案： ()解析： ASL 成功 =(1+2+6+1+2+1+1+4)/9=20/9考點(diǎn) 散列表的求解以及平均查找長(zhǎng)度的計(jì)算四、 程序閱讀題 ( 總題數(shù)： 4，分?jǐn)?shù)： 20.00)順序表類(lèi)型定

15、義如下：#define ListSize 100typedef structint dataListSize;int length;SeqList;閱讀下列算法，并回答問(wèn)題：void f30(SeqList *L)int i, j;i=0;while(iL- length)if(L-datai%2!=0)for(j=i+1; jL- length; j+L- dataj-1=L-dataj;L- length-;else i+ （分?jǐn)?shù)：5.00 ）(1).若 L- data中的數(shù)據(jù)為(22 ，4，63，0，15，29，34，42，3) ，則執(zhí)行上述算法后L- data中的數(shù)據(jù)以及L- leng

16、th的值各是什么?（分?jǐn)?shù)：2.50 ）_正確答案： ()解析： data=22，4，0， 34， 42 length=5。(2). 該算法的功能是什么?（分?jǐn)?shù)： 2.50 ）_正確答案： ()解析：刪除順序表中的奇數(shù)數(shù)據(jù)元素。 考點(diǎn)刪除順序表中的奇數(shù)數(shù)據(jù)元素的算法 解析 通過(guò)閱讀程序，可知其為刪除順序表中的奇數(shù)數(shù)據(jù)元素的操作，可得出data=22， 4，0， 34，42 ，length=5 。有向圖的鄰接矩陣類(lèi)型定義如下：#define MVN 100 /最大頂點(diǎn)數(shù)typedef int EType; /邊上權(quán)值類(lèi)型typedef structEType edgesMVNMVN; / 鄰接矩陣

17、，即邊表int n; /圖的頂點(diǎn)數(shù)MGraph; /圖類(lèi)型例如，一個(gè)有向圖的鄰接矩陣如下所示：閱讀下列算法，并回答問(wèn)題：Void f31(MGraph G)Int i, j, k=0;Step1;for(i=0; i G.n; i+)for(j=0; j G.n; j+)if(G.edgesij=1)k+;printf(%d/n, k);step2:for(j=0; j G.n; j+) k=0;for(i=0; i G.n; j+)if(G.edgesij=1)k+;printf(%d/n, k); （分?jǐn)?shù)： 5.00 ）(1).step1到 step2 之間的二重循環(huán)語(yǔ)句的功能是什么?（分

18、數(shù)： 2.50 ）_正確答案： ()解析：統(tǒng)計(jì)輸出圖中邊的數(shù)目。(2).step2之后的二重循環(huán)語(yǔ)句的功能是什么?（分?jǐn)?shù)：2.50 ）_正確答案： ()解析：統(tǒng)計(jì)輸出圖中每個(gè)結(jié)點(diǎn)的入度數(shù)。考點(diǎn) 圖的操作 解析 step1到step2之間的二重循環(huán)語(yǔ)句的功能是統(tǒng)計(jì)輸出圖中邊的數(shù)目；step2之后的二重循環(huán)語(yǔ)句的功能是統(tǒng)計(jì)輸出圖中每個(gè)結(jié)點(diǎn)的入度數(shù)。閱讀下列算法，并回答問(wèn)題：void f32(int r, int n)Int i, j;for(i=2; i n; i+) r0=ri; j=i-1;while(r0 rj) rj+1=rj; j=j-1;rj+1=r0; （分?jǐn)?shù)： 5.00 ）(1).

19、 這是哪一種插入排序算法?該算法是否穩(wěn)定 ?（分?jǐn)?shù)： 2.50 ）_正確答案： ()解析：直接插入排序，該算法是穩(wěn)定的。(2). 設(shè)置 r0的作用是什么 ?（分?jǐn)?shù)： 2.50 ）_正確答案： ()解析： r0的作用是監(jiān)視哨兵。 考點(diǎn)排序算法的判定解析根據(jù)算法，可知其為直接插入排序的算法，該算法是穩(wěn)定的。程序中r0 的作用是監(jiān)視哨兵。順序表類(lèi)型定義如下：typedef int SeqList100;閱讀下列算法，并回答問(wèn)題：void f33(SeqList r, int n) int a, b, i;if(r0r1)a=r0; b=r1;elsea=r1; b=r0; for(i=2; i n; i+)if(ria) a=ri;else if(rib) b=ri;printf(a=%d, b=%d。 /n, a,