數據結構自考題-9

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

2、析在單鏈表中，將終端結點的指針域NULL改為指向表頭結點或開始結點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。故由題目中此單循環(huán)錨表的頭指針為head，指針p指向尾結點，可得 pnext=head。3. 設有 6 個結點的無向圖，該圖至少應有 （ ） 條邊才能確保是一個連通圖。A5 B6C7 D8(分數： 2.00 )A. VB.C.D.解析：，則在二分查找關鍵字 b 的過程中， 先后進行比較的關4. 若有序表的關鍵字序列為 (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(分數： 2.00 )A. VB.C.

3、D.解析：5. 以下有關數據結構的敘述，正確的是 ( )A. 線性表的線性存儲結構優(yōu)于鏈式存儲結構B. 二叉樹的第i層上有21個結點，深度為K的二叉樹上有 2個結點C. 二維數組是其數據元素為線性表的線性表D. 棧的操作方式是先進先出分數： 2.00 )A.B.C. VD.解析：6. 設 rear 是指向非空帶頭結點的循環(huá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);(分數： 2.00 )A.B.C.D. V解析：7. 采用分治法進行排序的方法是 ( )A. 快速排序B 插入排序C. 堆排序D 希爾排序(分數： 2.00 )A. VB.C.D.解析：8. 對長度為 n 的關鍵字序列進行堆排序的空間復雜度為 ( )AO(log 2n) B O(1)CO(n) D O(n*log 2n)分數： 2.00 )A.B. VC.D.解析： 解析 由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件

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

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

7、00 ）A.B. VC.D.解析：15. 一個具有N個頂點的有向圖最多有（）條邊。A. N（N-1）/2 B . N（N-1） C . N（N+1） D . N（N+1）/2分數： 2.00 )A.B. VC.D.解析：、 填空題 （ 總題數： 10，分數： 20.00）16. 在線性表的順序存儲中， 元素之間的邏輯關系是通過決定的； 在線性表的鏈接存儲中，元素之間的邏輯關系是通過 決定的 （分數： 2.00 ）填空項 1: （正確答案：相鄰位置 鏈接指針）解析：17. 對于一個二維數組 Amn ，若按行序為主序存儲，則任一元素 Aij 相對于 A00 的地址為 1（分數： 2.00 ）填空項

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

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

10、式存儲的數組中，元素aij 的存儲地址應該是數組的 1 加上排在 aij 前面的元素所占用的單元數。（分數： 2.00 ）填空項 1: （正確答案：基地址）解析：三、解答題 （總題數： 3，分數： 25.00）26. 對序列(48,37,63,96,22,31,50,55,11)進行升序的堆排序，寫出構建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。初始堆：第1趟：第2趟：(分數：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,其操作表達式為head(head(tail(L);分別寫岀從下列廣義表中分解得到b的操作表達式。(1) L1=(a,b,c,d);(2) L2=(a),(b),(c),(d)。(分數：10.00) 正確答案：(head(tail(L1)解析： 正確答案：(head(head(tail(head(L2)解析：(1)畫岀對表長為13的有序順序表進行二分查找的判定樹；已知關鍵字序列為(12,14,16,21,24,28,35,43,52,67,71,84,99)，寫出在該序列中二分查找 37時所

12、需進行的比較次數。（分數：10.00 ）正確答案：(II)解析：正確答案：(3)解析：四、算法閱讀題(總題數：2,分數：20.00)假設學生成績按學號增序存儲在帶頭結點的單鏈表中，類型定義如下:typedef struct Nodeint id; /* 學號 */int score; /* 成績 */srruct Node*next;LNode,*LinkList;閱讀算法f31，并回答問題：（1）設結點結構為成績鏈表A和B如圖所示，畫出執(zhí)行算法 f31（A,B）后A所指的鏈表;(2)簡述算法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;（分數：10.00） 正確答案：（）解析： 正確答案：（對于表A中成績低于6

14、0的學生，如果在表B中也有成績記錄，則將表 A中的成績修改為其在 表B中的成績；但若其在表 B中的成績高于60分，則只改為60分。）解析：閱讀下列算法，并回答問題：(1)無向圖G如圖所示，寫出算法f30(&G)的返回值；簡述算法f30的功能。#define MaxNum 20int visitedMaxNum;void DFS(Graph*g,int i);/*從頂點vi出發(fā)進行深度優(yōu)先搜索，訪問頂點vj時置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;分數： 10.00 ) 正確答案： (3)解析： 正確答案： (返回無向圖 g 中連通分量的個數。 )解析：五、算法設計題 ( 總題數： 1，分數： 10.00)27. 對一個有t個非零值元素的rrKn矩陣，用B0.t,1.3的數組來表示，其中第 0行的三個元素分別是m,n,t ，從第一行開始到最后一行，每行表示一個非零元素，第一列為矩陣元素行號，第二列為其列號，第 三列為其元素量，對這樣的表示法，試編寫一個算法確定任意一個元素Aij 的位置，并考慮若修改其元素值須用多少時間?(設B中第1列原行號是遞增的)分數： 10.00 ) 正確答案： ( 分析題意可得其算法思想為：首先可在數組B中找到相應的行，然后找到相應的列，即可修改其元素值，可假定要修改的Aij，原先就具有非零值。從而可將算法描述為：lorte(B,t,i,j,v) /*確定任意一個元素 Aij 的位置 */datatype B;/*B的桿標為 0.t和 1.3*/int t,i,j;float v; datatype A;/*A的下標為 1.m 和 1.n ， A 表示 rrKn 矩陣 */int p;p=1;while(Bp1!=1)&&(p< =t)P+;if(p >t)printf Chasn't ele