全國2007年1月高等教育自學考試數(shù)據(jù)結(jié)構(gòu)試題

1、全國 2007 年 1 月高等教育自學考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.抽象數(shù)據(jù)類型的三個組成部分分別為()A.數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作B.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C.數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型D.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型2.若算法中語句的最大頻度為T(n)=2006n+6nlogn+2910g2n,則其時間復雜度為()A.O(logn)B.O(n)C.O(nlogn)D.O(log2n)3 .若線性表的插入和刪除操作

2、頻繁地在表頭或表尾位置進行，則更適宜采用的存儲結(jié)構(gòu)為()5 .已知串s=aabacbabcaccab,串t1=abc,串t2=cba,函數(shù)index(s,t)的返回值為串t在串s中首次出現(xiàn)的位置， 則能求得串a(chǎn)bcacba的操作序列為()A.substr(s1,s,6,index(s,t1);substr(s2,s,index(s,t1),1);strcat(s1,s2);B.substr(s1,s,7,index(s,t1);substr(s2,s,index(s,t1),1);strcat(s2,s1);C.substr(s1,s,6,index(s,t2);substr(s2,s,ind

3、ex(s,t2),3);strcat(s1,s2);D.substr(s1,s,6,index(s,t2);substr(s2,s,index(s,t2),3);strcat(s2,s1);6 .對廣義表L=(a,b),(c,d),(e,f)執(zhí)行head(tail(head(tail(L)操作的結(jié)果是()D.(e,f)A.無頭結(jié)點的雙向鏈表C.無頭結(jié)點的單鏈表4.上溢現(xiàn)象通常出現(xiàn)在(A.順序棧的入棧操作過程中C.鏈棧的入棧操作過程中B.帶尾指針的循環(huán)鏈表D.帶頭指針的循環(huán)鏈表B.順序棧的出棧操作過程中D.鏈棧的出棧操作過程中C.(e)7.已知一棵完全二叉樹有64個葉子結(jié)點，則該樹可能達到的最大

4、深度為（）A.7B.8C.9D.108.若一棵二叉樹有11個葉子結(jié)點，則該二叉樹中度為2的結(jié)點個數(shù)是（）A.10B.11C.12D.不確定的9.對于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進行的操作為（）A.求一個頂點的鄰接點B.求一個頂點的度C.深度優(yōu)先遍歷D.廣度優(yōu)先遍歷10.若用鄰接矩陣表示帶權(quán)有向圖，則頂點i的入度等于矩陣中（）A.第i行非 8 元素之和B.第i列非 8 元素之和C.第i行非 8 兀素個數(shù)11.對關(guān)鍵字序列(5,1,4,3,7,2,A.(1,2,3,4,5,6,7,8)C.(2,1,4,3,5,7,8,6)12,卜列二叉樹中，不.平衡的二叉樹是A.FA)B.13.卜列

5、序列中，不.構(gòu)成堆的是(A.(1,2,5,3,4,6,7,8,9,1(B.(10,5,8,4,2,6,7,1,3)C.(10,9,8,7,3,5,4,6,2)D.(1,2,3,4,10,9,8,7,6,!14.主關(guān)鍵字能唯一標識()A.一個記錄C.一個類型15.稀疏索引是指在義件的索引表中(A.為每個字段設一個索引項D.第i列非 8 兀素個數(shù)8,6）進行快速排序時，以 A 個元素5為基準的一次劃分的結(jié)果為（）B.（1,4,3,2,5,7,8,6）D.（8,7,6,5,4,3,2,1）（）C.D.）0）5）B.一組記錄D.一個文件）B.為每個記錄設一個索引項2C.為每組字段設一個索引項D.為每組

6、記錄設一個索引項二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。16 .鏈式存儲結(jié)構(gòu)的特點是借助來表示數(shù)據(jù)元素之間的邏輯關(guān)系。17.假設帶頭結(jié)點的非空單循環(huán)鏈表中僅設尾指針L,則在第1個結(jié)點之前插入指針s所指結(jié)點的語句依次是;O18 .無表頭結(jié)點的鏈隊列Q為空的條件是。19,不含任何字符的串稱為。20.假設按行優(yōu)先順序?qū)⒁粋€20階的三對角矩陣A壓縮存儲在一維數(shù)組Q中，其中Q0存放矩陣的第1個元素a1,1,那么矩陣元素a3,4在Q中的存儲位置k=。21 .前序序列和中序序列不.相同的二叉樹的特征是。22 .在含有n個頂點的連通圖中，任意兩個不

7、同頂點之間的簡單路徑的最大長度為。23 .用排序方法對關(guān)鍵字序列（20,25,12,47,15,83,30,76）進行排序時，前三趟排序的結(jié)果為：20,12,25,15,47,30,76,8312,20,15,25,30,47,76,8312,15,20,25,30,47,76,8324 .哈希表常用的兩類解決沖突的方法是和。25 .倒排文件和多重表文件的主要區(qū)別在于的結(jié)構(gòu)不同。三、解答題（本大題共4小題，每小題5分，共20分）26 .已知主串為ccgcgccgcgcbcb,模式串為cgcgcb。下表所列為按照樸素的串匹配算法進行的前兩趟匹配。請繼續(xù)完成余下各趟匹配，直至結(jié)束。01234567

8、8910)11213i=0一CCgCgCCgCgCbCbCS，11C包0匕g1eb：，1:-:11!卜1-1-；-口；： ：ii:1Ir_-一.一:i:-L11:M8:315H1,dnF1r-：1r-111r1-；：H3!I1-1匹配失敗時j=l匹配失敗時j=527.已知帶權(quán)圖G如圖所示，畫出圖G的一棵最小生成樹。28.對于直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，堆排序和歸并排序等排序方法，分別寫出：(1)平均時間復雜度低于O(n2)的排序方法；(2)所需輔助空間最多的排序方法；(3)最好情況和最壞情況下的時間復雜度相同的排序方法。(1)(2)(3)29.已知一棵線索化的二叉

9、排序樹如圖所示。(1)說明該樹的線索化是基于何種遍歷次序的；(2)在該樹中插入元素值為53的結(jié)點并修改相應線索，畫出修改之后的樹。4四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.假設線性表采用順序存儲結(jié)構(gòu)，表中元素值為整型。閱讀算法f30,并回答下列問題:(1)設順序表L=(3,7,3,2,1,1,8,7,3),寫出執(zhí)行算法f30后的L;(2)簡述算法f30的功能。voidf30(SeqList*L)inti,j,k;k=0;for(i=0;ilength;i+)for(j=0;jdatai!=L-dataj;j+);if(j=k)if(k!=i)L-datak=L-datai;

10、k+;L-length=k;(2)31.閱讀算法f31,并回答下列問題：(1)設隊列Q=(1,3,5,2,4,6)。寫出執(zhí)行算法f31后的隊列Q;(2)簡述算法f31的功能。voidf31(Queue*Q)DataTypee;if(!QueueEmpty(Q)e=DeQueue(Q);f31(Q);EnQueue(Q,e);)(2)32.已知樹的存儲結(jié)構(gòu)為孩子兄弟鏈表，其類型定義如下：typedefstructCSTNodechardata;structCSTNodeleftmostchild,*rightsibling;CSTNode,*CSTree;閱讀函數(shù)f32,并回答下列問題：(1)對

11、于如圖所示樹，寫出函數(shù)調(diào)用f32(T)的返回值;(2)簡述樹T非空時函數(shù)f32返回值的含義。intf32(CSTreeT)intc;CSTreep;if(!T-leftmostchild)return1;elsec=0;for(p=T-leftmostchild;p;p=p-rightsibling)c+=f32(p);returnc;(2)33.已知數(shù)組R1.p-1中的元素序列為一個大根堆，函數(shù)(1)在函數(shù)Adjust的空缺處填入適當內(nèi)容， 使其成為一個完整的函數(shù);(2)簡述函數(shù)f33(R,n)的功能。voidAdjust(SeqListR,intp)inti,j;Adjust(R,p)將R1.p重新調(diào)整為一個大根堆。RecTypetemp=Rp;i=p；j=i/2;while(j=1&Rj.keytemp.key)Ri=Rj;i=j;CD;Ri=;voidf33(SeqListR,intn)intk;for(k=2;k=n;k+)Adjust(R,k);(2)五、算法設計題(本大題10分)34.已知有向圖的鄰接表表示的形式描述如下：#defineMaxNum50圖的最大頂點數(shù)typedefstructArcNodeintadjvex;鄰接點域structArcNode*nextArc;/鏈域ArcNode;/弧結(jié)點類型typedefstr