1、更多優質自考資料盡在百度貼吧 自考樂園 俱樂部 （ ）歡迎？加入.歡迎？交流.止不住的驚喜等著你 2004年下半年全國自考數據結構真題一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項 中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均 無分。1.A. AB. BC. CD. D答案：D2. 若要在單鏈表中的結點*p之后插入一個結點*s,則應執行的語句是（）A. s->next=p->next;p->next=s;B. p->next=s;s->next=p->next;C. p->next=s-

2、>next;s->next=p;D. s->next=p;p->next=s->next;答案：A3. 若要在O （1）的時間復雜度上實現兩個循環鏈表頭尾相接，則應對兩個循環鏈表各設置一 個指針，分別指向（）A. 各自的頭結點B. 各自的尾結點C. 各自的第一個元素結點D. 一個表的頭結點，另一個表的尾結點答案：B4. 棧的兩種常用存儲結構分別為（）A. 順序存儲結構和鏈式存儲結構B. 順序存儲結構和散列存儲結構C. 鏈式存儲結構和索引存儲結構D. 鏈式存儲結構和散列存儲結構答案：A5. 已知循環隊列的存儲空間為數組data 21，且當前隊列的頭指針和尾指針的值分

3、別為8和3, 則該隊列的當前長度為（）A. 5B. 6C. 16D. 17答案：C6. 已知在如下定義的鏈申結點中，每個字符占1個字節，指針占4個字節，則該鏈申的存儲密度為 typedef struct node (char data 8;struct node *next; LinkStrNode;()A. 1/4B. 1/2C. 2/3D. 3/4答案：C7. 應用簡單的匹配算法對主串 s=" BDBABDABDA由子串t= " BDA'進行模式匹配，在匹配成 功時，進行的字符比較總次數為()A. 7B. 9C. 10D. 12答案：C8. 二維數組A 20 1

4、0采用列優先的存儲方法，若每個元素占2個存儲單元，且第1個元素 的首地址為200,則元素A 8 9的存儲地址為()A. 574B. 576C. 578D. 580答案：B9. 對廣義表L=(a,b),c,d)進行操作tail(head(L)的結果是()A. (c,d)B. (d)C. bD. (b)答案：D10. 已知一棵樹的前序序列為ABCDEF后序序列為CEDFBA則對該樹進行層次遍歷得到的序列 為()A. ABCDEFB. ABCEFDC. ABFCDED. ABCDFE答案：D11. 一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂 點出度的時間復雜度為

5、（）A. AB. BC. CD. D答案：A12. 在關鍵字序列（12 ,23,34,45,56,67,78,89,91）中二分查找關鍵字為 45、89和12的結點時，所需進行的比較次數分別為（）A. 4, 4, 3B. 4, 3, 3C. 3, 4, 4D. 3, 3, 4答案：B13. 下歹0排序方法中，最好與最壞時間復雜度不相同的排序方法是（）A. 冒泡排序B. 直接選擇排序C. 堆排序D. 歸并排序答案：A14. 已知含10個結點的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成 功的平均查找長度等于（）A. 1.0B. 2.9C. 3.4D. 5.5答案：B15. 在下

6、列各種文件中，不能進行順序查找的文件是（）A.順序文件B. 索引文件C. 散列文件D. 多重表文件答案：C二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答 案。錯填、不填均無分。1. 抽象數據類型是指數據邏輯結構及與之相關的 。答案：操作2. 已知在結點個數大于1的單循環鏈表中，指針p指向表中某個結點，則下列程序段執行結束時，指針q指向結點*p的結點。q=p；while （q->next!=p） q=q->next;答案：前驅3. 假設拚日X分別表示進棧和出棧操作，由輸入序列“ABC得到輸出序列“BCA的操作序列為SSXSXX則由“a*b+c/d ”

7、得到“ab*cd/+ ”的操作序列為。答案：SXSSXXSSXSSXXX4. 在文本編輯程序中查找某一特定單詞在文本中出現的位置，可以利用申的運算。答案：子申定位（或模式匹配）5. 假設以行優先順序將一個n階的5對角矩陣壓縮存儲到一維數組 ，則數組Q勺大小至少為0答案：5n-66. 在含100個結點的完全二義樹中，葉子結點的個數為 。答案：507. 在無向圖中，若從頂點a到頂點b存在，則稱a與b之間是連通的。答案：路徑8. 如果排序過程不改變之間的相對次序，則稱該排序方法是穩定的。答案：關鍵字相同的記錄9. 索引順序查找適宜對 的順序表進行查找。答案：分塊有序或有序10. 文件的檢索操作可按檢

8、索條件不同分為下列四種詢問，它們是簡單詢問、范圍詢問、函數 詢問及 。答案：布爾詢問（或組合詢問）三、解答題（本大題共4小題，每小題5分，共20分）1.畫出下圖所示二義樹的中序線索鏈表的存儲表示答案：說明：線索指針或標志域每錯2個扣1分，扣完5分為止2.已知圖G= (V, E)，其中：V= a,b,c,d,e,E= (a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)(1) 畫出圖G;(2) 畫出圖G勺鄰接表。答案：3. 已知自頂向下的二路歸并排序的算法如下所示，按此算法對關鍵字序列(55, 28, 73, 91, 37, 64, 19, 82, 46)進行排序，

9、列出算法執行過程中前 5次調用Merge函數 進行歸并之后的關鍵字序歹0。void MergeSortDC(SeqList R,int low,int high)( /用分治法對R low.high 進行二路歸并排序int mid;if (low<high)( /區間長度大于1mid=(low+high)/2; / 分解MergeSortDC(R,low,mid); /遞歸地對 R low.mid 排序MergeSortDC(R,mid+1,high); /遞歸地對 R mid+1.high 排序Merge(R,low,mid,high); /組合，將兩個有序區歸并為一個有序區 / Me

10、rgeSortDC答案：第1次調用Merge®行歸并之后的關鍵字序列為：(28, 55, 73, 91, 37, 64, 19, 82, 46) (1 分)第2次調用Merge®行歸并之后的關鍵字序列為：(28, 55, 73, 91, 37, 64, 19, 82, 46) (1 分)第3次調用Merge®行歸并之后的關鍵字序列為：(28, 55, 73, 37, 91, 64, 19, 82, 46) (1 分)第4次調用Merge®行歸并之后的關鍵字序列為：(28, 37, 55, 73, 91, 64, 19, 82, 46) (1 分)第5次調

11、用Merge®行歸并之后的關鍵字序列為：(28, 37, 55, 73, 91, 19, 64, 82, 46) (1 分)4. 由于元素的插入先后次序不同，所構成的二義排序樹可能有多種形態。請畫出4棵含1, 2, 3, 4, 5, 6六個元素且以1為根、深度為4的二義排序樹。答案：說明：畫出其中4棵二義樹即得5分。反之，每畫錯1棵二義樹扣1分。4棵二義樹都畫錯 ,則不得分。四、算法閱讀題(本大題共4小題，每小題5分，共20分)1. L為一個帶頭結點的循環鏈表。函數f30的功能是刪除L中數據域data的值大于c的所有結點 ，并由這些結點組建成一個新的帶頭結點的循環鏈表，其頭指針作為函

12、數的返回值。請在 處 填入合適的內容，使其成為一個完整的算法。LinkList f30(LinkList L,int c)(LinkList Lc,p,pre;pre=L;P=(_;Lc=(LinkList)malloc(sizeof(ListNode);Lc->next=Lc;while (p!=L)if(p->data>c)(pre->next=p->next;(_;Lc->next=p;p=pre->next;else(pre=p;(_;)return Lc;)答案：L->next(或 pre->next)(1 分)p->nex

13、t=Lc->next(2 分)p=p->next(或p=pre->next)(2 分)2. 設棧S=(1,2,3,4,5,6,7),其中7為棧頂元素。(1) 寫出調用f31(&S)后的S;(2) 簡述函數f31中第1個循環語句的功能。void f31 (Stack *S)Queue Q;Stack T;int i=0;InitQueue(&Q);InitStack(&T);while(!StackEmpty(S)if (i=!i)!=0) Push(&T,Pop(S);else EnQueue(&Q,Pop(S);while (!Sta

14、ckEmpty(&T)Push(S,Pop(&T);while(!QueueEmpty(&Q)Push(S,DeQueue(&Q);)答案：(1)S=(1,3,5,7,6,4,2),其中2為棧頂元素；(3分)(2)將棧S中的元素依次出棧，同時將第奇數次出棧的元素入棧T,第偶數次出棧的元素入隊列Q。(2 分)3. 圖的鄰接矩陣表示描述如下：#define MaxNum20/圖的最大頂點數typedef structchar vexs MaxNum ; H字符類型的頂點表int edges MaxNum MaxNum ; /鄰接矩陣int n,e; /圖的頂點數和邊

15、數MGraph; /圖的鄰接矩陣結構描述閱讀下歹0算法，并回答問題：(1) 對于下列圖G勺鄰接矩陣，寫出函數調用f32(&G,3)的返回值；(2) 簡述函數f32的功能；(3) 寫出函數f32的時間復雜度。int f32(MGraph *G,int i)(int d=0,j;for (j=0;j<G->n;j+)(if (G->edges i j ) d+;if (G->edges:j : : i : ) d+;return d;答案：1) 5(2分)(2) 求有向圖中頂點vi的入度和出度的和(或有向圖中某頂點的度)(或關聯于有向圖中頂點 vi的邊的數目)(2分

16、)(3) O(n)(1 分)4. 閱讀下列算法并回答問題：(1) 設數組L 1.8 的初值為(4, -3 , 7, -1 , -2 , 2, 5, -8 ),寫出執行函數調用f33(L,8)之后的L 1.8 中的元素值；(2) 簡述函數f33的功能。void f33(int R 口 ,int n)(int x=R 1;int low=1,high=n;while (low<high)(while (low<high && Rhigh >=0)high -;if (low<high)(R low+ =R high ;while (low<high &

17、amp;& Rlow <0)low+;R high- =R low;更多優質自考資料盡在百度貼吧 自考樂園 俱樂部( )歡迎？加入.歡迎？交流.止不住的驚喜等著你 )R low =x;答案：(1)(-8,-3,-2,-1,4,2,5,7)(3 分)(2)將數組R中所有負數均調整到前端，同時將所有非負數調整到后端(2分)五、算法設計題(本題共10分)1.假設以二義鏈表作為二義樹的存儲結構，其結點結構為：依照如下給定的函數f34的原型，編寫求二義樹T中葉子結點所在的最小層次與最大層次的函數。其中，參數level為函數執行過程中T當前所指結點的層次，其初值為1 ； *lmin與*lmax分別為葉 子結點的最小層次與最大層次，它們的初值均為0。void f34(BinTree T, int level, int *lmin, int *lmax);答案：void f34(BinTree T,int level,int *lmin,int *lmax)if (T) (1分)if (!T->lchild && !T->rchid)(1