[自學(xué)考試密押題庫與答案解析]數(shù)據(jù)結(jié)構(gòu)自考題模擬13

1、自學(xué)考試密押題庫與答案解析數(shù)據(jù)結(jié)構(gòu)自考題模擬13自學(xué)考試密押題庫與答案解析數(shù)據(jù)結(jié)構(gòu)自考題模擬13數(shù)據(jù)結(jié)構(gòu)自考題模擬13一、單項選擇題問題:1. 為便于判別有向圖中是否存在回路，可借助于A.廣度優(yōu)先搜索算B.最小生成樹算法C.最短路徑算D.拓撲排序算法答案:D問題:2. 在頭指針為head的非空單循環(huán)鏈表中，指針p指向尾結(jié)點，下列關(guān)系成立的是A.pnext=headB.pnextNext=headC.pnext=NULLD.p=head答案:A解析 在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。故由題目中此單循環(huán)錨表的頭指針為

2、head，指針p指向尾結(jié)點，可得pnext=head。問題:3. 設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有 條邊才能確保是一個連通圖。A.5B.6C.7D.8答案:A問題:4. 若有序表的關(guān)鍵字序列為(b,c,d,e,f,g,q,r,s,t)，則在二分查找關(guān)鍵字b的過程中，先后進行比較的關(guān)鍵字依次為A.f,c,bB.f,d,bC.g,c,bD.g,d,b答案:A問題:5. 以下有關(guān)數(shù)據(jù)結(jié)構(gòu)的敘述，正確的是A.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)B.二叉樹的第i層上有2i-1個結(jié)點，深度為K的二叉樹上有2k-1個結(jié)點C.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表D.棧的操作方式是先進先出答案:C問題:6.

3、設(shè)rear是指向非空帶頭結(jié)點的循環(huán)單鏈表的尾指針，則刪除起始結(jié)點的操作可表示為A.s=rear;B.rear=rearnext; rear=rearnext; free(rear); free(s); C.rear=rearnextnext;D.s=rearnextnext; free(rear); rearnextnext=snext; free(s); 答案:D問題:7. 采用分治法進行排序的方法是A.快速排序B.插入排序C.堆排序D.希爾排序答案:A問題:8. 對長度為n的關(guān)鍵字序列進行堆排序的空間復(fù)雜度為A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)答案:B解析

4、由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為0(1)，但它是不穩(wěn)定的。問題:9. 在桶排序中，其平均時間復(fù)雜度是A.O(1)B.O(n)C.O(n2)D.O(1gn)答案:B問題:10. 森林T中有4棵樹，第一、二、三、四棵樹的結(jié)點個數(shù)分別是n1，n2，n3，n4，那么當把森林T轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點的左孩子上有 個結(jié)點。A.n1-1B.n1C.n1+n2+n3D.n2+n3+n4答案:A問題:11. 數(shù)據(jù)結(jié)構(gòu)是A.一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲結(jié)構(gòu)C.一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合答案:D問

5、題:12. 兩個字符串相等的條件是A.串的長度相等B.含有相同的字符集C.都是非空串D.串的長度相等且對應(yīng)的字符相同答案:D問題:13. 鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于于叉樹的A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷答案:A問題:14. 如果我們采用二分查找法查找一個長度為n的有序表，則查找每個元素的平均比較次數(shù) 對應(yīng)的判定樹的高度(假設(shè)樹高h2)。A.大于B.小于C.等于D.無法確定答案:B問題:15. 一個具有N個頂點的有向圖最多有 條邊。A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/2答案:B二、填空題問題:1. 在線性表的順序存儲中，元素

6、之間的邏輯關(guān)系是通過_決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_決定的。答案:相鄰位置 鏈接指針問題:2. 對于一個二維數(shù)組Amn，若按行序為主序存儲，則任一元素Aij相對于A00的地址為_。答案:ij+i全元素位置問題:3. 若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是_的。答案:穩(wěn)定問題:4. 對于數(shù)組，通常具有的基本操作有_種，它們分別是_。答案:兩 查找和修改問題:5. 如果我們定義一個長度為N的串空間，則它最多能放_個字符。答案:N1問題:6. 已知廣義表A=(a,b,c)，(d,e,f)，則運算head(head(tail(tail(A)=_。答

7、案:e問題:7. 若對關(guān)鍵字序列(43,02,80,48,26,57,15,73,21,24,66)進行一趟增量為3的希爾排序，則得到的結(jié)果為_。答案:15,02,21,24,26,57,43,66,80,48,73問題:8. 無向圖的鄰接矩陣是_，并且主對角線上的元素的值為_。答案:對稱零問題:9. 散列函數(shù)的作用是：_。答案:壓縮待處理的下標范圍，待處理的|u|個值減少到m個值，從而降低空間開銷問題:10. 在按照順序存儲方式存儲的數(shù)組中，元素aij的存儲地址應(yīng)該是數(shù)組的_加上排在aij前面的元素所占用的單元數(shù)。答案:基地址三、解答題問題:1. 對序列(48,37,63,96,22,31,

8、50,55,11)進行升序的堆排序，寫出構(gòu)建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。 初始堆： 第1趟： 第2趟： 答案:初始堆：(96,55,63,48,22,31,50,37,11) 第1趟：(63,55,50,48,22,3l,11,37,96) 第2趟：(55,48,50,37,22,31,11,63,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)。

9、 2.答案:head(tail(L1)3.答案:head(head(tail(head(L2)(1)畫出對表長為13的有序順序表進行二分查找的判定樹； (2)已知關(guān)鍵字序列為(12,14,16,21,24,28,35,43,52,67,71,84,99)，寫出在該序列中二分查找37時所需進行的比較次數(shù)。 4.答案:5.答案:3四、算法閱讀題假設(shè)學(xué)生成績按學(xué)號增序存儲在帶頭結(jié)點的單鏈表中，類型定義如下： typedef struct Node int id; /*學(xué)號*/ int score; /*成績*/ srruct Node*next; LNode,*LinkList; 閱讀算法f31，并

10、回答問題： (1)設(shè)結(jié)點結(jié)構(gòu)為，成績鏈表A和B如圖所示，畫出執(zhí)行算法f31(A,B)后A所指的鏈表； (2)簡述算法f31的功能。 void f31(LinkList A,LinkList B) LinkList p,q; p=Anext; q=Bnext; while(p else if(pidqid) q=qnext; else if(pscore60) if(qscore60) pscore=qscore; else pscore=60; p=pnext; q=qnext; 1.答案:2.答案:對于表A中成績低于60的學(xué)生，如果在表B中也有成績記錄，則將表A中的成績修改為其在表B中的成績

11、；但若其在表B中的成績高于60分，則只改為60分。閱讀下列算法，并回答問題： (1)無向圖G如圖所示，寫出算法f30( void DFS(Graph*g,int i); /*從頂點vi出發(fā)進行深度優(yōu)先搜索，訪問頂點vj時置visitedj為1*/ int f30(Graph*g) int i,k; for(i=0;igN;I+) 答案:34.答案:返回?zé)o向圖g中連通分量的個數(shù)。五、算法設(shè)計題問題:1. 對一個有t個非零值元素的mn矩陣，用B0.t,1.3的數(shù)組來表示，其中第0行的三個元素分別是m,n,t，從第一行開始到最后一行，每行表示一個非零元素，第一列為矩陣元素行號，第二列為其列號，第三列

12、為其元素量，對這樣的表示法，試編寫一個算法確定任意一個元素Aij的位置，并考慮若修改其元素值須用多少時間?(設(shè)B中第1列原行號是遞增的)答案:分析題意可得其算法思想為： 首先可在數(shù)組B中找到相應(yīng)的行，然后找到相應(yīng)的列，即可修改其元素值，可假定要修改的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表示mn矩陣*/ int p; p=1; while(Bp1!=1)(p=t) P+; if(pt)printf Chasn