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

1、數(shù)據(jù)結(jié)構(gòu)自考題 -3( 總分： 100.00 ，做題時(shí)間： 90 分鐘 )一、單項(xiàng)選擇題 ( 總題數(shù)： 15，分?jǐn)?shù)： 30.00)1. 采用分治法進(jìn)行排序的方法是 ( )A. 快速排序B 插入排序C.堆排序D 希爾排序(分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：2. 圖的鄰接矩陣表示法適用于表示 ( )A. 無向圖B .有向圖C .稠密圖D .稀疏圖(分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：3. 假設(shè)有一個(gè)數(shù)組，它的行號(hào)從 0到 8，列號(hào)從 0到 10，數(shù)組中每個(gè)元素所占的存儲(chǔ)空間為3個(gè)單元，則現(xiàn)在將此數(shù)組從某一個(gè)地址開始連續(xù)存放在一個(gè)存儲(chǔ)器中，試問至少需要 ( ) 個(gè)存儲(chǔ)單元才能完

2、全將此數(shù)組 存放進(jìn)去。A. 240 B . 297C. 270 D . 300分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：4. 順序存儲(chǔ)結(jié)構(gòu) ( )A. 僅適合于靜態(tài)查找表的存儲(chǔ)B. 僅適合干動(dòng)態(tài)查找表的存儲(chǔ)C. 既適合靜態(tài)又適合動(dòng)態(tài)查找表的存儲(chǔ)D. 既不適合靜態(tài)又不適合動(dòng)態(tài)查找表的存儲(chǔ)分?jǐn)?shù)： 2.00 )A.B.D.解析：5. 對(duì)關(guān)鍵字序列 (6,1,4,3,7,2,8,5) 進(jìn)行快速排序時(shí)，以第 1個(gè)元素為基準(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)

3、(分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：6. 若進(jìn)棧次序?yàn)?a,b,e ，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的含 3個(gè)元素的出棧序列個(gè)數(shù)是 ( ) A3 B5C6 D7分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：7. 在一棵具有 5 層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為 ( ) 個(gè)A33 B32 C31 D30(分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：8. 設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵高度為 h 的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是 ( )A2h B 2h-1 C 2h-1 D2h+1-1(分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：9. 下面關(guān)于線性表的敘述錯(cuò)誤的是 ( )A. 線性表采用順

4、序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B. 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C. 線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D. 線性袁采用鏈接存儲(chǔ)，不便于插入和刪除操作（分?jǐn)?shù):2.00 ）A. VB.C.D.解析：10. 數(shù)據(jù)結(jié)構(gòu)是（）A. 種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合（分?jǐn)?shù)：2.00 ）A.B.C.D. V解析：11. 設(shè)有一個(gè)用線性探測法解決沖突得到的散列表:散列函數(shù)為H（k）=Kmod 11若要查找元素14，探測的次數(shù)（比較的次數(shù)）是A. 8 B . 9 C . 3 D . 6（分?jǐn)?shù)：2.

5、00 ）A.B.C.D. V解析：12. 二維數(shù)組Mi,j的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4,列 下標(biāo)j的范圍從0到5。M按行存儲(chǔ)時(shí)元素 M3,5的起始地址與 M按列存儲(chǔ)時(shí)元素（）的起始地址相同。A. M2,4 B . M3,4 C . M3,5 D . M4,4（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：13. 樹最適合用來表示（）A.有序數(shù)據(jù)元素 B .無序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D 元素之間無聯(lián)系的數(shù)據(jù)（分?jǐn)?shù):2.00 ）A.B.C. VD.解析：14. 若進(jìn)棧序列為1,2,3,4,5,6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)

6、的出棧序列為（）A. 3,2,6,1,4,5 B . 3,4,2,1,6,5 C . 1,2,5,3,4,6 D . 5,6,4,2,3,1（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：15. 如圖所示二叉樹的中序遍歷序列是（）A. a b c d g e f B. d f e b a g cC. d b a e f c g D. d e f b a g c（分?jǐn)?shù)：2.00 ）A.B.C. VD.解析：二、填空題（總題數(shù)：10,分?jǐn)?shù)：20.00）16. 若二叉樹的一個(gè)葉子是某子樹的中序遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是孩子樹的后序遍歷序中的1個(gè)結(jié)點(diǎn)。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1: （正確答案：第

7、一）解析：17. 1與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1: （正確答案：數(shù)據(jù)的邏輯結(jié)構(gòu)）解析：18. 具有N個(gè)頂點(diǎn)的無向完全圖的邊為，具有N個(gè)頂點(diǎn)無向完全圖的弧為（分?jǐn)?shù)：2.00 ）填空項(xiàng) 解析：1: (正確答案： n(n-1)/2 n(n-1) )19. 數(shù)組 A1.10 ，-2.6 ，2.8 以行優(yōu)先順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是 100 ，每個(gè)元素占 3 個(gè)存儲(chǔ) 長度的存儲(chǔ)空間，則元素 A5,0,7 的存儲(chǔ)地址為 1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 913 ）解析：進(jìn)行一趟增量為 3的希爾排序， 則得到的結(jié)果為20. 若對(duì)關(guān)鍵字序列 （43,

8、02,80,48,26,57,15,73,21,24,66） 1。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 15,02,21,24,26,57,43,66,80,48,73 ）解析：21. 多維數(shù)組和廣義表是一種非常復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特點(diǎn)是 1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前趨和多個(gè)直接后繼）解析：22. 由權(quán)值為 1,2,3,4,5,6 的六個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)的路徑的長度為 1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： 55）解析：23. 在分塊查找法中，首先查找 1 ，然后再查找相應(yīng)的 2（分?jǐn)?shù)：

9、2.00 ）（正確答案：索引表塊）1 條邊。填空項(xiàng) 1:解析：24. N 個(gè)頂點(diǎn)的連通圖，至少有（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： N 1）解析：25. n 個(gè)頂點(diǎn)且含有環(huán)路的無向連通圖中，至少含有 1 條邊 （分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： n）解析： 解析 n 個(gè)頂點(diǎn)的無向連通圖有環(huán)路且邊最少時(shí)，此圖僅有一個(gè)環(huán)路且所有頂點(diǎn)均在此環(huán)路中，此 時(shí)邊數(shù)為 n 。三、解答題 （總題數(shù)： 3，分?jǐn)?shù)： 20.00）26. 已知有一關(guān)鍵字序列為 97,86,53,108,72,34,215,146,11,68 ，如果我們采用直接選擇排序方法對(duì)此序 列進(jìn)行排序 ( 按照升序排

10、列 ) ，請(qǐng)給出每一趟的排序結(jié)果。分?jǐn)?shù)： 5.00 )正確答案：(直接選擇排序的過程為：從第 i趟開始時(shí)，當(dāng)前的有序區(qū)和無序區(qū)分別為R1i和R1n(1 < -1<n-1)，則在該趟排序是從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄RK，將它與無序區(qū)中的第1個(gè)記錄Ri交換，使R1i和Ri+1n分別變成新的有序區(qū)和新的無序區(qū)，每次排序都使有序區(qū) 增加一個(gè)記錄，無序區(qū)減少一個(gè)記錄，按照以上規(guī)則，我們得到各趟結(jié)果如下：初始： 97,86,53,108,72,34,215,232,11,68第 1 趟： 1186,53,108,72,34,215,232,97,68第 2 趟： 11,3453,108

11、,72,86,215,232,97,68第 3 趟： 11,34,531108,72,86,215,232,97,68第 4 趟： 11,34,53,6872,86,215,232,97,108第 5 趟： 11,34,53,68,7286,215,232,97,108第 6 趟： 11,34,53,68,72,86215,232,97,108第 7 趟： 11,34,53,68,72,86,97232,215,108第 8 趟： 11,34,53,68,72,86,97,108215,232第 9 趟： 11,34,53,68,72,86,97,108,215,232)解析：利用廣義表的 h

12、ead 和 tail 操作，可從廣義表L=(a,b) ， (c,d)中分解得到原子 c ，其操作表達(dá)式為head(head(tail(L);分別寫出從下列廣義表中分解得到 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) 解析：27. 圖的鄰接表的類型定義如下所示： #define MaxVertexNum 50 typedef struct node int adjvex;struct node*next; Ed

13、geNode;typedef struct VertexType vertex;EdgeNode*firstedge; VertexNode;typedef VertexNode A djListMaxVertexNum; typedef structAdjList adjiist;int n,e;ALGraph;為便于刪除和插入圖的頂點(diǎn)的操作，可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu)，兩種定義的存儲(chǔ)表示實(shí)例如 下圖所示，請(qǐng)寫岀重新定義的類型說明。（分?jǐn)?shù)：5.00 ） 正確答案：(typeclef struct ArcNodeVNode*adjvex; / 該弧所指向的頂點(diǎn)的位置struct Arc

14、Node*nextarc; / 指向下一條弧的指針ArcNode;typedef struct VNodeVertexType data; / 頂點(diǎn)信息 struct VNode*nextVertex; /指向下一個(gè)頂點(diǎn)的指針ArcNode*firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：四、算法閱讀題(總題數(shù)：2,分?jǐn)?shù)：20.00)28. 求下面算法中變量count的值：(假設(shè)n為2的乘冪，并且n >2)int Timeint ncount=0;x=2;w

15、hile(x < n/2) x*=2;count+;return(count)（分?jǐn)?shù)：5.00 ） 正確答案：(count=log 2n)解析：二叉排序樹的存儲(chǔ)結(jié)構(gòu)定義為以下類型：typedef int KeyType;typedef struct nodeKeyType key; /* 關(guān)鍵字項(xiàng) */InfoType otherinfo; /*其它數(shù)據(jù)項(xiàng) */struet node*lchild,*rchild; /*左、右孩子指針 */BSTNode,*BSTree;閱讀算法f33，并回答問題: 對(duì)如圖所示的二叉排序樹T,寫出f33(T,8)返回的指針?biāo)附Y(jié)點(diǎn)的關(guān)鍵字;在哪些情況下算

16、法f33返回空指針？簡述算法f33的功能。BSTNode*f33(BSTreeKeyType x)BSTNode*P;if(T=NULL)return NULL;p=f33(T > lehild,x);if(p!=NULL)return p;if(T > key > x)return T;return f33(T> rchild,x);(分?jǐn)?shù)：15.00 )填空項(xiàng)1: (正確答案：10)解析：正確答案：仃是空樹或T中所有結(jié)點(diǎn)的關(guān)鍵字均不大于給定值X時(shí)，返回空指針。)解析： 正確答案：(如果二叉排序樹T中存在含有關(guān)鍵字大于給定值 X的結(jié)點(diǎn)，則返回指針指向它們中關(guān)鍵字最小

17、的結(jié)點(diǎn)，否則返回空指針。)解析：五、算法設(shè)計(jì)題(總題數(shù)：1,分?jǐn)?shù)：10.00)29. 寫岀向某個(gè)有序文件中插入一個(gè)記錄的程序。(分?jǐn)?shù)：10.00 )正確答案：(所謂有序文件是指文件的記錄按關(guān)鍵字由小到大(或由大到小)順序存放。為方便起見，可設(shè)文件的每一個(gè)記錄是一個(gè)整數(shù)，文件上數(shù)據(jù)是按由小到大順序存放。設(shè)插入數(shù)據(jù)是命令行的第3個(gè)參數(shù)，且設(shè)為d。若原文件中沒有數(shù)據(jù)，則 d寫入文件；若有數(shù)據(jù)，則找到第 1個(gè)比d大的數(shù)據(jù)i，先寫入d，再將 i和其后各數(shù)據(jù)寫回文件中，可通過調(diào)用fseek函數(shù)采實(shí)現(xiàn)插入。相應(yīng)程序?yàn)椋?include < stdio.h >#include < stdli

18、b.h >#include < io.h >#include < fcntl.h >#define LEN sizeof(int)void main(int argi,char*argc) int fp,i,d;if(argi < 3) printf("filename int/11")exit(0);d=atoi(argc2);fp=open(argc1,O_GREAT| 0_RDWRI O_BINARY,s_IREAD| S_IWRITE);while(1) if( read(fp,&I ,LEN)!=LEN)write(fp，&d,LEN):