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

1、數(shù)據(jù)結(jié)構(gòu)自考題 -10( 總分： 100.00 ，做題時間： 90 分鐘 )一、 單項(xiàng)選擇題 ( 總題數(shù)： 15，分?jǐn)?shù)： 30.00)1. 當(dāng)初始序列已經(jīng)按鍵值有序時，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為( )A n2 B nlona n C log2 n D n-1（分?jǐn)?shù)：2.00 ）A.B.C.D.解析：2. 長度為 12 的按關(guān)鍵字有序的查找表采用順序組織方式。若采用二分查找方法，失敗時的 ASL 值是 ( )A 37/12 B 62/13 C 39/12 D 49/13則在等概率情況下，查找（分?jǐn)?shù)： 2.00 ）A.B. C.D.解析：3. 對廣義表 (a) ， (b) 進(jìn)行下面的

2、操作 head(head(a) ， (b) 后的結(jié)果是 ( ) A a B (a)C( ) D 不確定（分?jǐn)?shù)： 2.00 ）A. B.C.D.解析：4. 順序存儲結(jié)構(gòu) ( )A僅適合于靜態(tài)查找表的存儲B僅適合干動態(tài)查找表的存儲C既適合靜態(tài)又適合動態(tài)查找表的存儲D既不適合靜態(tài)又不適合動態(tài)查找表的存儲（分?jǐn)?shù)： 2.00 ）A.B.C. D.解析：5. 將含有 83 個結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號，根為編號，那么編號為41 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為( )1 號，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)A 42 B 40C 21 D20（分?jǐn)?shù)： 2.00 ）A.B.C.D. 解析：6. 非空的單循環(huán)鏈表

3、 L 的尾結(jié)點(diǎn) P，滿足 ( )AP.next=NULL; B P=NULL;CP.next=L; D P=L（分?jǐn)?shù)： 2.00 ）A.B.C. D.解析：7. 對長度為 n 的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為( )A O(log 2n) B O(1)C O(n) D O(n*log 2n)（分?jǐn)?shù)： 2.00 ）A.B. C.D.解析： 解析 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為0(1) ，但它是不穩(wěn)定的。8. 堆排序的最壞時間復(fù)雜度為 ( ) A O(n) B O(10g2n)C O(nlog 2 n) D O(n2 )（分?jǐn)?shù)：2

4、.00 ）A.B.C.D.解析：9. 在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是( )A插入B 刪除C 排序D 定位（分?jǐn)?shù)： 2.00 ）A.B.C.D. 解析：10. 深度為 k 的二叉樹，所含葉子的個數(shù)最多為( )A 2K BKC 2K-1 D 2K-1（分?jǐn)?shù)： 2.00 ）A.B.C. D.解析：11. 對關(guān)鍵字序列 (6,1,4,3,7,2,8,5)進(jìn)行快速排序時，以第1 個元素為基準(zhǔn)的一次劃分的結(jié)果為( )A (5,1,4,3,6,2,8,7) B (5,1,4,3,2,6,7,8)C (5,1,4,3,2,6,8,7) D (8,7,6,5,4,3,2,1)（分?jǐn)?shù)：

5、2.00 ）A.B.C. D.解析：12. 一個具有 N 個頂點(diǎn)的有向圖最多有 ( ) 條邊。A N(N-1)/2 BN(N-1) C N(N+1) D N(N+1)/2（分?jǐn)?shù)：2.00 ）A.B.C.D.解析：13. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等( )（分?jǐn)?shù)： 2.00 ）A.B. C.D.解析：14. 采用分治法進(jìn)行排序的方法是 ( ) A快速排序 B 插入排序C堆排序 D 希爾排序（分?jǐn)?shù)： 2.00 ）A. B.

6、C.D.解析：15. 下列說法中正確的是 ( )A二叉樹中任何一個結(jié)點(diǎn)的度都為2B二叉樹的度為2C任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為2D一棵二叉樹的度可以小于2（分?jǐn)?shù)： 2.00 ）A.B.C.D. 解析：二、 填空題 ( 總題數(shù)： 10，分?jǐn)?shù)： 20.00)16. 一個字符串相等的充要條件是 _和 _。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：兩個字符串的長度相等解析：17. 當(dāng)所有結(jié)點(diǎn)的權(quán)值都相等時，用這些結(jié)點(diǎn)構(gòu)造的二叉排序樹上只有對應(yīng)位置的字符相等）1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：右子樹）解析：18. 假設(shè)散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是

7、，當(dāng)需要插入新的記錄時，該桶中1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：已有m個同義詞的記錄( 或：已有 m個記錄；或：已滿) ）解析：19. 數(shù)組的長度是 _，線性表的長度是_。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：固定的可變的）解析：20. 對表長為 9000 的索引順序表進(jìn)行分塊查找，假設(shè)每一塊的長度均為15，且以順序查找確定塊，則在各記錄的查找概率均相等的情況下，其查找成功的平均查找長度為1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： 308.5 ）解析：21. 多維數(shù)組和廣義表是一種非常復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特點(diǎn)是1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng)

8、 1:_（正確答案：一個數(shù)據(jù)元素可能有多個直接前趨和多個直接后繼）解析：22. 假設(shè)以列優(yōu)先順序存儲二維數(shù)組A58 ，其中元素 A00 的存儲地址為 LOC(a00 ) ，且每個元素占 4個存儲單元，則數(shù)組元素Aij的存儲地址為1。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： LOC(a00)+4(5j+i)）解析：23. 一棵含 999 個結(jié)點(diǎn)的完全二叉樹的深度為1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： 10）解析：24. 控制區(qū)間和控制區(qū)域是 1 文件的邏輯存儲單位。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： VSAM）解析：25. 對于數(shù)組，通常具有的基本操作有

9、_種，它們分別是 _。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：兩查找和修改）解析：三、 解答題 ( 總題數(shù)： 4，分?jǐn)?shù)： 20.00)26. 對于下面用三元組表示的稀疏矩陣，請分別寫出它們所對應(yīng)的稀疏矩陣。（分?jǐn)?shù)： 5.00 ）_正確答案： ( 從三元組表還原稀疏矩陣時，首先根據(jù)表的第1 行得出稀疏矩陣的行數(shù)和列數(shù)，否則，我們無法確定所求的稀疏矩陣的維數(shù)，然后根據(jù)三元組表所提供的行號和列號在稀疏矩陣的對應(yīng)位置上寫上相應(yīng)的元素的值，在其他地方補(bǔ)零即可，根據(jù)上述原則，此題答案如圖(1) ，(2) 所示。)解析：27. 圖的鄰接表的類型定義如下所示：#define MaxVertexNum

10、50typedef struct nodeint adjvex;struct node*next;EdgeNode;typedef structVertexType vertex;EdgeNode*firstedge;VertexNode;typedef VertexNode A djListMaxVertexNum;typedef structAdjList adjiist;int n,e;ALGraph;為便于刪除和插入圖的頂點(diǎn)的操作，可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu)，兩種定義的存儲表示實(shí)例如下圖所示，請寫出重新定義的類型說明。（分?jǐn)?shù)： 5.00 ）_正確答案： (typeclef st

11、ruct ArcNodeVNode*adjvex; /該弧所指向的頂點(diǎn)的位置struct ArcNode*nextarc; /指向下一條弧的指針ArcNode;typedef struct VNodeVertexType data; /頂點(diǎn)信息struct VNode*nextVertex; /指向下一個頂點(diǎn)的指針ArcNode*firstarc; /指向第一條依附該頂點(diǎn)的弧VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：28. 假設(shè)有一個長度為 n 的有序序列， 在進(jìn)行查找時， 可以借助二叉樹來進(jìn)行， 請結(jié)合二

12、叉樹的性質(zhì)來分析二分查找的最壞性能和平均性能。（分?jǐn)?shù)： 5.00 ）_正確答案： ( 假設(shè)判定樹的內(nèi)部結(jié)點(diǎn)的總數(shù)為n=2h-1 。則判定樹是深度為 h=lg(n+1) 的滿二叉樹，樹中第 k層上的結(jié)點(diǎn)的個數(shù)為 2h-1 ，查找它們所需要比較的次數(shù)是k。則在等概率下，二分查找成功時的平均查找長度為：，如果 n 很大，則可以用如下近似公式：lg(n+1)-1 ，作為二分查找成功時的平均查找長度。二分查找在查找失敗時所需要比較的關(guān)鍵字的個數(shù)不超過判定樹的深度，在最壞情況下查找成功的比較次數(shù)也不超過判定樹的深度。因?yàn)榕卸渲卸葦?shù)小于2 的結(jié)點(diǎn)只可能在最下面的兩層上，所以n 個結(jié)點(diǎn)的判定樹的深度和 n

13、個結(jié)點(diǎn)的完全二叉樹的深度相同，即為lg(n+1) ，所以，二分查找的最壞性能和平均性能十分接近。 )解析：29. 某類物品的編號由一個大寫英文字母及 2 位數(shù)字 (0 9) 組成，形如 E32。運(yùn)用基數(shù)排序?qū)ο铝形锲肪幪栃蛄羞M(jìn)行按字典序的排序，寫出每一趟 ( 分配和收集 ) 后的結(jié)果。E13,A37,F43,B32,B47,E12,F37,B12第一趟：第二趟：第三耥：（分?jǐn)?shù)： 5.00 ）_正確答案： ( 第一趟： B32,E12,B12,E13,F43,A37,B47,F37第二趟： E12,B12,E13,B32,A37,F37,F43,B47第三趟： A37,B12,B32,B47,E

14、12,E13,F37,F43)解析：四、 算法閱讀題 ( 總題數(shù)： 3，分?jǐn)?shù)： 20.00)30. 求下面算法中變量 count 的值： ( 假設(shè) n 為 2 的乘冪，并且 n2) int Timeint n count=0;x=2; while(x n/2) x* =2;count+;return(count)（分?jǐn)?shù)： 5.00 ）_正確答案： (count=log2n)解析：31. 請將下面的程序改成遞歸的過程。voide ditui(int n)int i;i=n;while(i1)prinft(i-);（分?jǐn)?shù)： 5.00 ）_正確答案： ( 此遞推過程可以改寫成如下遞歸過程：voide

15、 dkui(int j)if(i1)prind(j);digui(j-1);)解析：閱讀下列算法，并回答問題：(1) 設(shè)串 s=OneWorldOneDream，t=One ，pos 是一維整型數(shù)組，寫出算法 f32(s,t,pos) 執(zhí)行之后得到的返回值和 pos 中的值；(2) 簡述算法 f32 的功能。int strlen(char*s); /*返回串 S 的長度 */int index(char*st，char*t);/* 若串 t 在串 st 中出現(xiàn)，則返回在串st 中首次出現(xiàn)的下標(biāo)值，否則返回-1*/int f32(char*s,char*t,int pos)int i,j,k,l

16、s,It;Is=strlen(s);lt=strlen(t);if(ls=0| It=0)return-1;k=0;i=0;doj=index(s+i,t);if(j=0)posk+=i+j;i+=j+it;while(i+it =is&j=0);return k;（分?jǐn)?shù)： 10.00 ）_正確答案： (2 ；pos0=0 ， pos1=8)解析：_正確答案： ( 返回串 t 在 S 中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos 中。 )解析：五、 算法設(shè)計(jì)題 ( 總題數(shù)： 1，分?jǐn)?shù)： 10.00)32. 有兩個磁盤文件 A、B，各存放一行字母，要求把這兩個文件中的信息按字母順序排列合

17、并，輸出到一個新文件 C 中。（分?jǐn)?shù)： 10.00 ）_正確答案： ( 可先分別將 A、B 文件的內(nèi)容讀出放到數(shù)組 C 中，再對數(shù)組 C 排序，最后再將數(shù)組內(nèi)容寫到文件 C 中，程序?yàn)椋?include stdio.hmain() /*合并 A、B 文件內(nèi)容到C 文件中 */ FILE*fp; int i,j,n,m; char c160,t,ch;if(fp=fopen(A,r)=Null) printf( 文件 A cant open/n); exit(0);else printf(/n文件 A 的內(nèi)容為 /n)for(i=0;(ch=fgetc(fp)!=EOF:i+) Ci=oh; putchar(C-i);fclose(fp);m=i;if(fp=fopen(B,r)=Null) printf(B 文件 cant open/n