全國(guó)1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題及答案

1、全國(guó) 2010 年 1 月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題（課程代碼：02331）一、單項(xiàng)選擇題（ 本大題共15 小題，每小題2 分，共 30 分 ）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1 若一個(gè)算法的時(shí)間復(fù)雜度用T（n） 表示，其中n 的含義是（）A.問題規(guī)模B.語句條數(shù)C.循環(huán)層數(shù)D.函數(shù)數(shù)量2具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（）A.樹B.圖C.棧和隊(duì)列D.廣義表3.將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為 m的單鏈表之后，其算法的時(shí)間復(fù)雜度為（）AO（1）BO（m）CO（n）DO（m+n）4在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改

2、的指針域數(shù)量是（）A2 個(gè)B3 個(gè) C4 個(gè)D6 個(gè)5假設(shè)以數(shù)組A60 存放循環(huán)隊(duì)列的元素，其頭指針是front=47 ，當(dāng)前隊(duì)列有50 個(gè)元素，則隊(duì)列的尾指針值為（）A 3B 37C 50D 976若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說法中正確的是（）A 需要判斷棧滿且需要判斷?？誃 不需要判斷棧滿但需要判斷棧空C 需要判斷棧滿但不需要判斷?？誅 不需要判斷棧滿也不需要判斷棧空7若串str= ” Software ”，其子串的數(shù)目是（ ）A 8B 9C 36D 378 .設(shè)有一個(gè)10階的下三角矩陣 A,采用行優(yōu)先壓縮存儲(chǔ)方式，an為第一個(gè)元素，其存儲(chǔ)地址為1000，每個(gè)元素占一個(gè)地址單元，則a85

3、的地址為（）A 1012B 1017D. 1039C. 10329 .允許結(jié)點(diǎn)共享的廣義表稱為（A.純表B.線性表C.遞歸表D.再入表10.下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（A. B樹B. AVL 樹的是（D. 5, 1,2,3A. 1, 5,6, 4,C.二叉排序樹11.對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄?D.哈夫曼樹 其中錯(cuò)誤C. 5, 1, 6, 3, 4, 212.以v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（VIv6,B.v1, v2, v5,v7v7,v6v6D.v1, v2, v5,v7,v413.下列排序算法中不穩(wěn)定的是A.快速排序B.歸并排序C.冒泡排序D.直接

4、插入排序14. 一個(gè)有序表為（1 , 3, 9,12,32,41,45, 62, 75, 77,82,95,100),當(dāng)采用折半查找方法查找值32時(shí)，查找成功需要的比較次數(shù)是（A. 2B. 3C. 4D. 815 .采用ISAM組織文件的方式屬于（A.鏈組織B.順序組織C.散列組織D.索引組織二、填空題（本大題共10小題，每小題2分，共20分） 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16 .數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱為17. 長(zhǎng)度為n的線性表采用單鏈表結(jié)構(gòu)存儲(chǔ)時(shí)，在等概率情況下查找第i個(gè)元素的時(shí)間復(fù)雜度是18. 下面是在順序棧上實(shí)現(xiàn)的一個(gè)?；静僮?，該操作的功能是ty

5、pedef structDataType data100;int topSeqStack ;DataType f18(SeqStack*S)if(StackEmpty(S)Error( " Stack is empty ");return S->dataS->top19.20.在串匹配中，一般將主串稱為目標(biāo)串，將子串稱為 已知廣義表 C=(a(b , c) , d),則：tail(head(tail(C)=21.用6個(gè)權(quán)值分別為6、13、18、30、7和16的結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長(zhǎng)度為22.已知有向圖如下所示，其中頂點(diǎn)A到頂點(diǎn)C

6、的最短路徑長(zhǎng)度是23.24.高度為3的3階B-樹最少的關(guān)鍵字總數(shù)是25.26.VSAMB常作為大型索引順序文件的標(biāo)準(zhǔn)組織，其動(dòng)態(tài)索引結(jié)構(gòu)采用的是 解答題(本大題共4小題，每小題5分，共20分) 假設(shè)二叉樹的 RNL1歷算法定義如下：若二叉樹非空，則依次執(zhí)行如下操作:(2)遍歷右子樹;訪問根節(jié)點(diǎn);遍歷左子樹。已知一棵二叉樹如圖所示，請(qǐng)給出其對(duì)序列55 , 46, 13, 05, 94, 17, 42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果27.已知一個(gè)無向圖 G=(V, E),其中V=A,B,C,D, E, F,鄰接矩陣表示如下所示。請(qǐng)回答下列問題:(1)請(qǐng)畫出對(duì)應(yīng)的圖 G(2)畫出圖G的鄰接表存儲(chǔ)結(jié)構(gòu)

7、。28.已知一組待排記錄的關(guān)鍵字序列為29.-01010Q0100011 1 00 I 00101010 01010(16,12, 18,60, 15, 36, 14, 18, 25, 85),用堆排序方法建小根堆，請(qǐng)給出初始建堆后的序列。已知一棵二叉排序樹如圖所示O請(qǐng)回答下列問題:(1)畫出插入元素23后的樹結(jié)構(gòu)；20分)(2)請(qǐng)畫出在原圖中刪除元素57后的樹結(jié)構(gòu)。四、算法閱讀題(本大題共4小題，每小題5分，共30 .已知下列程序，Ls指向帶頭結(jié)點(diǎn)的單鏈表。Typedefstruct node DataType data;struct node * next; * LinkList;void

8、 f30( LinkList Ls ) LinkList p, q;q = Ls->next;if ( q && q->next ) Ls->next = q->next;p=q while ( p->next )p = p->next;p->next = q;q->next = NULL;請(qǐng)回答下列問題：(1)當(dāng)Ls指向的鏈表如下圖所示，請(qǐng)畫出執(zhí)行本函數(shù)之后的鏈表的結(jié)果。(2)請(qǐng)簡(jiǎn)述算法的功能。31 .已知字符串處理函數(shù)f31程序如下。int f31(char*strl , char*str2) while(*strl=*str

9、2&&(*strl!= ' 0' )strl+;str2+;return(*strl-*str2 ? l： 0);請(qǐng)回答下列問題：(1) 若調(diào)用語句是f31(" abcde"，" abcdf'),則函數(shù)的返回值是什么？若調(diào)用語句是f31( " abcde" , " abcde"),則函數(shù)的返回值是什么？(2) 簡(jiǎn)述該函數(shù)的功能。32 .數(shù)組A口中存儲(chǔ)有n個(gè)整數(shù)，請(qǐng)閱讀下列程序。void f32(intA , int n) inti , j , k, x;k=n-l ;while(k&g

10、t;0)i=k ;k=0 ;for(j=O ; j<i ; j+)if(Aj>Aj+1)x=Aj ;Aj=Aj+l；Aj+1=x;k=j ；/ end of if /end of whilereturn ;請(qǐng)回答下列問題：(1)當(dāng)A尸10 , 8, 2, 4, 6, 7時(shí)，執(zhí)行f32(A , 6)后，數(shù)組A中存儲(chǔ)的結(jié)果是什么？(2)說明該算法的功能。33 .下面程序?qū)崿F(xiàn)二分查找算法。Typedef structKeyType key ;InfoType otherinfo ;SeqListN+1 ;int BinSearch(SeqList R, int n, KeyType K)

11、 int low=1 , high=n ;while( (1) J mid=(1ow+high)/2;if( (2)_Jreturn mid;if(Rmid . key>K) high=mid-1;else (3); return O ;/ BinSearch請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使該程序功能完整。(1)(2)(3)五、算法設(shè)計(jì)題(本題10分)34 .已知二叉樹采用二叉鏈表存儲(chǔ)，其結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct Node ElmType data ;struct Node *lchild, *rchild ;*BiTree ;請(qǐng)編寫遞歸函數(shù)SumNodes(BiTree

12、 T),返回二叉樹T的結(jié)點(diǎn)總數(shù)。全國(guó)2010年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題答案(課程代碼:02331) 一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)1. A2. C3. B4. C5. B6. B7. D8. C9. D10. A11. C12. D13. A14. B15. D二、填空題（本大題共10小題，每小題2分，共20分）16 .存儲(chǔ)結(jié)構(gòu)（或物理結(jié)構(gòu)）17 . O（n）18 .取棧頂元素（或StackTop或GetTop）19 .模式（或模式串）20 . （c）21.21922. 3523. 42, 13, 94, 55, 05,46,1724.725 . B+ 樹 三

13、、解答題（本大題共 4小題，每小題5分，共20分）26 .該樹的RNL遍歷結(jié)果序列為：GCFABD【評(píng)分參考】錯(cuò)一個(gè)字符扣1分，扣完5分為止。27 . （1）如下圖（2分）（2）如下圖（3分）001【評(píng)分參考】以上答案不惟一，只要圖形等價(jià)正確即可給分。28 .初始堆序列是（12, 15, 14, 18, 16, 36, 18, 60, 25, 85）【評(píng)分參考】錯(cuò)一個(gè)數(shù)扣1分，扣完5分為止。29, Cl）如下圖【評(píng)分參考】以上（2）中答案不惟一，給出的兩個(gè)圖都是對(duì)的，只要給出其中之一即可。四、算法閱讀題（本大題共 4小題，每小題5分，共20分）30 . 口 K+0EHIEM3HHEHEW1E（ 3 分）【評(píng)分參考】錯(cuò)一個(gè)結(jié)點(diǎn)扣 1分，扣完3分為止。（2）將單鏈表的首結(jié)點(diǎn)（第一個(gè)結(jié)點(diǎn)）移到鏈尾（作為最后一個(gè)結(jié)點(diǎn)）?；?qū)㈡滎^元素移到鏈尾。（2分）31 . （1）1 , 0（2 分）（2）判斷兩個(gè)字符串是否相等。若串相等，則返回O,否則返回1。（3分）32 .（1）A尸2,4,6,7,8,10）（ 3 分）（2）該算法實(shí)現(xiàn)了對(duì)數(shù)組A進(jìn)行冒泡排序。（2分）33 .（1） low<=high（2 分）（2） Rmid.key=K（2 分）（3） low=mid+l（1 分）五、算法設(shè)計(jì)題(本題10分)34