數(shù)據(jù)結(jié)構(gòu)自考題-9

1、數(shù)據(jù)結(jié)構(gòu)自考題 -9（ 總分： 105.00 ，做題時(shí)間： 90 分鐘 ）一、 單項(xiàng)選擇題 （ 總題數(shù)： 15，分?jǐn)?shù)： 30.00）1. 為便于判別有向圖中是否存在回路，可借助于 （ ）A. 廣度優(yōu)先搜索算 B 最小生成樹(shù)算法C.最短路徑算D 拓?fù)渑判蛩惴ǎǚ謹(jǐn)?shù)： 2.00 ）A.B.C.D. V解析：2. 在頭指針為 head 的非空單循環(huán)鏈表中，指針 p 指向尾結(jié)點(diǎn)，下列關(guān)系成立的是 （ ）A. p> next=head B . p> next > Next=headC. p> next=NULL D . p=head（分?jǐn)?shù)： 2.00 ）A.B.C.D.解析：V解

2、析在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱為單循環(huán)鏈表。故由題目中此單循環(huán)錨表的頭指針為head，指針p指向尾結(jié)點(diǎn)，可得 pnext=head。3. 設(shè)有 6 個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有 （ ） 條邊才能確保是一個(gè)連通圖。A5 B6C7 D8(分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：，則在二分查找關(guān)鍵字 b 的過(guò)程中， 先后進(jìn)行比較的關(guān)4. 若有序表的關(guān)鍵字序列為 (b,c,d,e,f,g,q,r,s,t) 鍵字依次為 ( )A f,c,b B f,d,b C g,c,b D g,d,b(分?jǐn)?shù)： 2.00 )A. VB.C.

3、D.解析：5. 以下有關(guān)數(shù)據(jù)結(jié)構(gòu)的敘述，正確的是 ( )A. 線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B. 二叉樹(shù)的第i層上有21個(gè)結(jié)點(diǎn)，深度為K的二叉樹(shù)上有 2個(gè)結(jié)點(diǎn)C. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表D. 棧的操作方式是先進(jìn)先出分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：6. 設(shè) rear 是指向非空帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，則刪除起始結(jié)點(diǎn)的操作可表示為( )A. s=rear; B . rear=rear > next;rear=rear > next; free(rear);free(s);Crear=rear >next > next; D s=rea

4、r > next > next;free(rear); rear > next > next=s > next;free(s);(分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：7. 采用分治法進(jìn)行排序的方法是 ( )A. 快速排序B 插入排序C. 堆排序D 希爾排序(分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：8. 對(duì)長(zhǎng)度為 n 的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為 ( )AO(log 2n) B O(1)CO(n) D O(n*log 2n)分?jǐn)?shù)： 2.00 )A.B. VC.D.解析： 解析 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件

5、。堆排序是就地 排序，輔助空間為 0(1) ，但它是不穩(wěn)定的。9. 在桶排序中，其平均時(shí)間復(fù)雜度是 ( )2A O(1) B O(n) C O(n2) D O(1gn)(分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：10. 森林T中有4棵樹(shù)，第一、二、三、四棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別是m, n2,仇，帀，那么當(dāng)把森林 T轉(zhuǎn)換成一棵二叉樹(shù)后，其根結(jié)點(diǎn)的左孩子上有 ( ) 個(gè)結(jié)點(diǎn)。An1-1 B n1 Cn1+n2+n3 Dn2+n3+n4(分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：11. 數(shù)據(jù)結(jié)構(gòu)是 ( )A. 種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或

6、多種特定關(guān)系的數(shù)據(jù)元素的集合(分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：12. 兩個(gè)字符串相等的條件是 ( )A.串的長(zhǎng)度相等B 含有相同的字符集C.都是非空串D 串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同(分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：13. 鄰接表存儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于于叉樹(shù)的A.先序遍歷B 中序遍歷C 后序遍歷D 按層遍歷（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：14. 如果我們采用二分查找法查找一個(gè)長(zhǎng)度為 n 的有序表，則查找每個(gè)元素的平均比較次數(shù) （ ） 對(duì)應(yīng)的判定 樹(shù)的高度（假設(shè)樹(shù)高h(yuǎn)>2）。A.大于B .小于C 等于D .無(wú)法確定（分?jǐn)?shù)： 2.

7、00 ）A.B. VC.D.解析：15. 一個(gè)具有N個(gè)頂點(diǎn)的有向圖最多有（）條邊。A. N（N-1）/2 B . N（N-1） C . N（N+1） D . N（N+1）/2分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：、 填空題 （ 總題數(shù)： 10，分?jǐn)?shù)： 20.00）16. 在線性表的順序存儲(chǔ)中， 元素之間的邏輯關(guān)系是通過(guò)決定的； 在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò) 決定的 （分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：相鄰位置 鏈接指針）解析：17. 對(duì)于一個(gè)二維數(shù)組 Amn ，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素 Aij 相對(duì)于 A00 的地址為 1（分?jǐn)?shù)： 2.00 ）填空項(xiàng)

8、1: （正確答案：i xj+i 全元素位置）解析：18. 若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是1 的分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：穩(wěn)定）解析：19. 對(duì)于數(shù)組，通常具有的基本操作有 種，它們分別是 （分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：兩 查找和修改）解析：20. 如果我們定義一個(gè)長(zhǎng)度為 N 的串空間，則它最多能放 1 個(gè)字符（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： N 1）解析：21. 已知廣義表 A=(a,b,c) ， (d,e,f) ，則運(yùn)算 head(head(tail(tail(A)= 1（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1

9、: （正確答案： e）解析：22. 若對(duì)關(guān)鍵字序列 （43,02,80,48,26,57,15,73,21,24,66）進(jìn)行一趟增量為 3的希爾排序， 則得到的結(jié)果為1。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 15,02,21,24,26,57,43,66,80,48,73 ）解析：23. 無(wú)向圖的鄰接矩陣是 1 ，并且主對(duì)角線上的元素的值為 2。分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:（正確答案：對(duì)稱零）解析：24. 散列函數(shù)的作用是：1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng)1: （正確答案：壓縮待處理的下標(biāo)范圍，待處理的|u|個(gè)值減少到m個(gè)值，從而降低空間開(kāi)銷） 解析：25. 在按照順序存儲(chǔ)方

10、式存儲(chǔ)的數(shù)組中，元素aij 的存儲(chǔ)地址應(yīng)該是數(shù)組的 1 加上排在 aij 前面的元素所占用的單元數(shù)。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：基地址）解析：三、解答題 （總題數(shù)： 3，分?jǐn)?shù)： 25.00）26. 對(duì)序列(48,37,63,96,22,31,50,55,11)進(jìn)行升序的堆排序，寫(xiě)出構(gòu)建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。初始堆：第1趟：第2趟：(分?jǐn)?shù)：5.00) 正確答案：(初始堆：(96,55,63,48,22,31,50,37,11)第 1 趟：(63,55,50,48,22,31,11,37,96)第 2 趟：(55,48,50,37,22,31,11,63

11、,96)解析：利用廣義表的head和tail操作，可從廣義表L=(a,b) ，(c,d)中分解得到原子c,其操作表達(dá)式為head(head(tail(L);分別寫(xiě)岀從下列廣義表中分解得到b的操作表達(dá)式。(1) L1=(a,b,c,d);(2) L2=(a),(b),(c),(d)。(分?jǐn)?shù)：10.00) 正確答案：(head(tail(L1)解析： 正確答案：(head(head(tail(head(L2)解析：(1)畫(huà)岀對(duì)表長(zhǎng)為13的有序順序表進(jìn)行二分查找的判定樹(shù)；已知關(guān)鍵字序列為(12,14,16,21,24,28,35,43,52,67,71,84,99)，寫(xiě)出在該序列中二分查找 37時(shí)所

12、需進(jìn)行的比較次數(shù)。（分?jǐn)?shù)：10.00 ）正確答案：(II)解析：正確答案：(3)解析：四、算法閱讀題(總題數(shù)：2,分?jǐn)?shù)：20.00)假設(shè)學(xué)生成績(jī)按學(xué)號(hào)增序存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表中，類型定義如下:typedef struct Nodeint id; /* 學(xué)號(hào) */int score; /* 成績(jī) */srruct Node*next;LNode,*LinkList;閱讀算法f31，并回答問(wèn)題：（1）設(shè)結(jié)點(diǎn)結(jié)構(gòu)為成績(jī)鏈表A和B如圖所示，畫(huà)出執(zhí)行算法 f31（A,B）后A所指的鏈表;(2)簡(jiǎn)述算法f31的功能。 void f31(LinkList A,LinkList B) LinkList p,

13、q;p=A> next; q=B> next;while(p&&q)if(p > id<Q > id) p=p> next;else if(p > id >q> id) q=q> next;else if(p > score < 60) if(q > score < 60) p> score=q > score; else p > score=60; p=p> next;q=q> next;（分?jǐn)?shù)：10.00） 正確答案：（）解析： 正確答案：（對(duì)于表A中成績(jī)低于6

14、0的學(xué)生，如果在表B中也有成績(jī)記錄，則將表 A中的成績(jī)修改為其在 表B中的成績(jī)；但若其在表 B中的成績(jī)高于60分，則只改為60分。）解析：閱讀下列算法，并回答問(wèn)題：(1)無(wú)向圖G如圖所示，寫(xiě)出算法f30(&G)的返回值；簡(jiǎn)述算法f30的功能。#define MaxNum 20int visitedMaxNum;void DFS(Graph*g,int i);/*從頂點(diǎn)vi出發(fā)進(jìn)行深度優(yōu)先搜索，訪問(wèn)頂點(diǎn)vj時(shí)置visitedj 為1*/int f30(Graph*g)int i,k;for(i=0;i <g> N;I+)visitedi=0;if(visitedi=0)k+;

15、DFS(g,i);return k;分?jǐn)?shù)： 10.00 ) 正確答案： (3)解析： 正確答案： (返回?zé)o向圖 g 中連通分量的個(gè)數(shù)。 )解析：五、算法設(shè)計(jì)題 ( 總題數(shù)： 1，分?jǐn)?shù)： 10.00)27. 對(duì)一個(gè)有t個(gè)非零值元素的rrKn矩陣，用B0.t,1.3的數(shù)組來(lái)表示，其中第 0行的三個(gè)元素分別是m,n,t ，從第一行開(kāi)始到最后一行，每行表示一個(gè)非零元素，第一列為矩陣元素行號(hào)，第二列為其列號(hào)，第 三列為其元素量，對(duì)這樣的表示法，試編寫(xiě)一個(gè)算法確定任意一個(gè)元素Aij 的位置，并考慮若修改其元素值須用多少時(shí)間?(設(shè)B中第1列原行號(hào)是遞增的)分?jǐn)?shù)： 10.00 ) 正確答案： ( 分析題意可得其算法思想為：首先可在數(shù)組B中找到相應(yīng)的行，然后找到相應(yīng)的列，即可修改其元素值，可假定要修改的Aij，原先就具有非零值。從而可將算法描述為：lorte(B,t,i,j,v) /*確定任意一個(gè)元素 Aij 的位置 */datatype B;/*B的桿標(biāo)為 0.t和 1.3*/int t,i,j;float v; datatype A;/*A的下標(biāo)為 1.m 和 1.n ， A 表示 rrKn 矩陣 */int p;p=1;while(Bp1!=1)&&(p< =t)P+;if(p >t)printf Chasn't ele