2006年1月自考數據結構試題真題

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

2、插入和刪除操作頻繁地在表頭或表尾位置進行，則更適宜采用的存儲結構為B 帶尾指針的循環(huán)鏈表D.帶頭指針的循環(huán)鏈表B .順序棧的出棧操作過程中D .鏈棧的出棧操作過程中()A .無頭結點的雙向鏈表C.無頭結點的單鏈表4 上溢現象通常出現在()A 順序棧的入棧操作過程中C.鏈棧的入棧操作過程中5.已知串 s=" aabacbabcaccab',串 t仁"abc",串 t2= " cba",函數 index(s,t)的返回值為串 t在串s中首次出現的位置，則能求得串"abcacba"的操作序列為()Asubstr (s1,s

3、,6,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s1,s2);Bsubstr (s1,s,7,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s2,s1);Csubstr(s1 ,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s1,s2);Dsubstr(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í)行 hea

4、d(tail(head(tail(L) 操作的結果是()BeAdC (e)D(e,f )A 7B .8C.9D .108 若一棵二叉樹有11個葉子結點，則該二叉樹中度為2的結點個數是（）A.10B .11C.12D .不確定的9.對于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進行的操作為（)A.求一個頂點的鄰接點B .求一個頂點的度C.深度優(yōu)先遍歷D .廣度優(yōu)先遍歷10.若用鄰接矩陣表示帶權有向圖，則頂點i的入度等于矩陣中（)A.第i行非R兀素之和B .第i列非R兀素之和C.第i行非R兀素個數D .第i列非R兀素個數11.對關鍵字序列（5, 1, 4, 3,乙2,8,6）進行快速排序時，以第一

5、個兀素5為基準的一次劃分的結果為（）A.(1 , 2, 3, 4, 5, 6, 7, 8)B .(1, 4, 3, 2, 5, 7,8, 6)C.(2, 1, 4, 3, 5, 7, 8, 6)D .(8, 7, 6, 5, 4, 3,2, 1)12.下列二叉樹中，不 平衡的二叉樹是（)13.下列序列沖,不.構成堆的:是（)A.(1 ,2,5,3,4,6,乙8,9,10)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,乙6,5)14.主關鍵字能唯隹一標識()A .一個記錄B .一組記錄C. 一個類型D .一個文件1

6、5.稀疏索引是指在文件的索引表中（)A .為每個字段設一個索引項B.為每個記錄設一個索引項C.為每組字段設一個索引項D .為每組記錄設一個索引項二、填空題（本大題共 10 小題,每小題2 分,共 20 分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.鏈式存儲結構的特點是借助 來表示數據元素之間的邏輯關系。17假設帶頭結點的非空單循環(huán)鏈表中僅設尾指針L,則在第1個結點之前插入指針 s所指結點的語句依次是 ； 。18.無表頭結點的鏈隊列 Q為空的條件是 。19不含任何字符的串稱為。20假設按行優(yōu)先順序將一個 20 階的三對角矩陣 A 壓縮存儲在一維數組 Q 中，其中 Q0 存放矩陣的第

7、1個元素a1,1，那么矩陣元素 也4在Q中的存儲位置k=。21前序序列和中序序列不 相同的二叉樹的特征是 。22. 在含有n個頂點的連通圖中，任意兩個不同頂點之間的簡單路徑的最大長度為 。23. 用排序方法對關鍵字序列（20, 25, 12, 47, 15, 83, 30, 76）進行排序時， 前三趟排序的結果為：20,12,25,15,47,30,76,8312,20,15,25,30,47,76,8312,15,20,25,30,47,76,8324. 哈希表常用的兩類解決沖突的方法是 和。25. 倒排文件和多重表文件的主要區(qū)別在于 的結構不同。三、解答題（本大題共 4 小題,每小題 5分

8、,共 20分）26. 已知主串為"ccgcgccgcgcbcb"，模式串為"cgcgcb"。下表所列為按照樸素的串匹配 算法進行的前兩趟匹配。請繼續(xù)完成余下各趟匹配,直至結束。匹配失敗時j=l匹配失敗時j =50 I 2345678910 )1 12 1327.已知帶權圖 G如圖所示，畫出圖 G的一棵最小生成樹。28 對于直接插入排序，希爾排序，冒泡排序，快速排序，直接選擇排序，堆排序和歸并 排序等排序方法，分別寫出：(1) 平均時間復雜度低于 O (n2)的排序方法；(2) 所需輔助空間最多的排序方法；(3) 最好情況和最壞情況下的時間復雜度相同的排序

9、方法。(1)(2)(3)29 已知一棵線索化的二叉排序樹如圖所示。(1)說明該樹的線索化是基于何種遍歷次序的;(2)在該樹中插入元素值為 53的結點并修改相應線索，畫出修改之后的樹。(1)(2)t四、算法閱讀題(本大題共4小題，每小題5分，共20分)30 假設線性表采用順序存儲結構，表中元素值為整型。閱讀算法(1) 設順序表L=(3,7,3,2,1,1,8,7,3),寫出執(zhí)行算法f 30后的L;(2) 簡述算法f 30的功能。void f 30(SeqList *L) int i,j,k;k=0;for(i=0;i<L->le ngth;i+) for(j=0;j<k &am

10、p;& L->datai!=L->dataj;j+);f 30,并回答下列問題:if(j=k) if(k!=i)L->datak=L->datai; k+;L->le ngth=k;(1)31 閱讀算法f 31,并回答下列問題：(1) 設隊列Q= ( 1, 3, 5, 2, 4, 6)。寫出執(zhí)行算法f 31后的隊列Q;(2) 簡述算法f 31的功能。void f 31(Queue *Q)DataType e;if (!QueueEmpty(Q)e=DeQueue(Q);f 31(Q);En Queue(Q,e);(1)32已知樹的存儲結構為孩子兄弟鏈表，其

11、類型定義如下：typedef struct CSTNode char data;struct CSTNode leftmostchild ,* rightsibling; CSTNode, *CSTree;閱讀函數f 32,并回答下列問題：(1) 對于如圖所示樹，寫出函數調用 f 32(T)的返回值;(2) 簡述樹T非空時函數f 32返回值的含義。int f32(CSTree T) int c;CSTree p;if (!T->leftmostchild) retur n 1; else c=0;for(p=T->leftmostchild;p;p=p->rightsibli

12、 ng) c+=f32(p);return c;(1)33.已知數組 R1.p-1中的元素序列為一個大根堆，函數Adjust(R,p)將R1.p重新調整為一個大根堆。(1) 在函數Adjust的空缺處填入適當內容，使其成為一個完整的函數；(2) 簡述函數f33(R,n)的功能。void Adjust(SeqList R,i nt p) int i,j;RecType temp=Rp;i=p;j=i/2;while(j>=1 && Rj.key<temp.key) Ri=Rj;i=j;Ri=void f33(SeqList R,i nt n) int k;for(k=2;k<=n;k+)Adjust(R,k);(2)五、算法設計題(本大題 10 分)34已知有向圖的鄰接表表示的形式描述如下：#define MaxNum 50/圖的最大頂點數/鄰接點域/鏈域typedef struct ArcNode int adjvex; struct ArcNode *nextArc; ArcNode;/弧結點類型/頂點域/弧表頭指針/頂點表結點類型/鄰接表/