全國自考數據結構歷年試題及部分答案(2009--2013)

1、 全國2009年1月高等教育自學考試數據結構試題課程代碼：02331一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.下列程序段的時間復雜度為( )9 s=0； for(i=1；i<n；i+) for(j=1；j<n；j+) s+=i*j；A.O(1)B.O(n)C.O(2n)D.O(n2)2.假設某個帶頭結點的單鏈表的頭指針為head，則判定該表為空表的條件是( )22A.head=NULL；B.head->next=NULL；C.head!=NULL；D.h

2、ead->next=head；3.棧是一種操作受限的線性結構，其操作的主要特征是( )32A.先進先出B.后進先出C.進優(yōu)于出D.出優(yōu)于進4.假設以數組An存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數為( )A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n5.判斷兩個串大小的基本準則是( )52A.兩個串長度的大小B.兩個串中首字符的大小C.兩個串中大寫字母的多少D.對應的第一個不等字符的大小

3、6.二維數組A45按行優(yōu)先順序存儲，若每個元素占2個存儲單元，且第一個元素A00的存儲地址為1000，則數組元素A32的存儲地址為( )60A.1012B.1017C.1034D.1036a00a01a02a03a04a327.高度為5的完全二叉樹中含有的結點數至少為( )72A.16B.17C.31D.328.已知在一棵度為3的樹中，度為2的結點數為4，度為3的結點數為3，則該樹中的葉子結點數為( )A.5B.8C.11D.189.下列所示各圖中是中序線索化二叉樹的是( )81A10.已知含6個頂點(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如圖所示，則從頂點v0出發(fā)進行深度優(yōu)先

4、遍歷可能得到的頂點訪問序列為( )108A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)11.如圖所示有向圖的一個拓撲序列是( )A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列關鍵字序列中，構成大根堆的是( )A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，313.對長度為15的有序順序表進行二分查找，在各記錄的查找概率均相等的情況下，查找成功時所需進行的關鍵字

5、比較次數的平均值為( )172A.B.C.D.14.已知一個散列表如圖所示，其散列函數為H(key)=key11，采用二次探查法處理沖突，則下一個插入的關鍵字49的地址為( )d 19715.數據庫文件是由大量帶有結構的( )206A.記錄組成的集合B.字符組成的集合C.數據項組成的集合D.數據結構組成的集合二、填空題(本大題共10小題，每小題2分，共20分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.估算算法時間復雜度時考慮的問題規(guī)模通常是指算法求解問題的_。輸入量 817.在雙向循環(huán)鏈表中插入一個新的結點時，應修改_個指針域的值。4 2818.若進棧序列為a，b，c，且進棧和出

6、棧可以穿插進行，則可能出現_個不同的出棧序列。519.鏈串的結點大小定義為結點的_中存放的字符個數。數據域 5420.廣義表(a，(d，(c)的深度為_。3 6721.在含有3個結點a，b，c的二叉樹中，前序序列為abc且后序序列為cba的二叉樹有_棵。422.若用鄰接矩陣表示有向圖，則頂點i的入度等于矩陣中_。第i列非零元素的個數10723.對關鍵字序列(15，18，11，13，19，16，12，17，10，8)進行增量為5的一趟希爾排序的結果為_。 15，12，11，10，8，16，18，1724.索引順序查找的索引表由各分塊中的最大關鍵字及各分塊的_構成。起始位置17325.VSAM文件

7、的實現依賴于操作系統中的_存取方法的功能。分頁 215三、解答題(本大題共4小題，每小題5分，共20分)26.假設有一個形如的8×8矩陣，矩陣元素都是整型量(次對角線以上的元素都是0)。若將上述矩陣中次對角線及其以下的元素按行優(yōu)先壓縮存儲在一維數組B中，請回答下列問題：(1)B數組的體積至少是多少?(2)若a18存儲在B0中，a56存儲在Bk中，則k值為多少?(1) （1+8）*8/2=36 存放次對角線以上的零為37(2) 1227.對關鍵字序列(5，8，1，3，9，6，2，7)按從小到大進行快速排序。(1)寫出排序過程中前兩趟的劃分結果；(2)快速排序是否是穩(wěn)定的排序方法?(1)

8、第一趟劃分結果；(2，3，1)，5，(9，6，8，7)第二趟劃分結果；(1，2，3)，5，(9，6，8，7)第三趟劃分結果；(1，2，3)，5，(7，6，8，9)第四趟劃分結果； 1，2，3，5，6，7，8，9第一趟劃分過程2315968712359687 1235768912356789ji(5，8，1，3，9，6，2，7)1(2，8，1，3，9，6，5，7)2(2，5，1，3，9，6，8，7)3(2，3，1，5，9，6，8，7)4(2，3，1，5，9，6，8，7)第二趟劃分過程(2，3，1，5，9，6，8，7)1(1，2，3，5，7，6，8，9) (2)非穩(wěn)定231596871235576

9、8956789ji第一趟：（2，3，1）5 （9，6，8，7）第二趟： 1，2，3，5 （9，6，8，7）第三趟：1，2，3，5，（7，6，8），9第四趟：1，2，3，5，6，7，8，928.假設通信電文使用的字符集為a，b，c，d，e，f，g，h，各字符在電文中出現的頻度分別為：7，26，2，28，13，10，3，11，試為這8個字符設計哈夫曼編碼。要求：(1)畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值不大于右孩子結點的權值)； (2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個字符對應的編碼。(1)(2)29.已知3階B樹如圖所示，非根 【1，2】P184根 【1，2】(1)畫出將

10、關鍵字6插入之后的B樹；1,3695,8(2)畫出在(1)所得樹中插入關鍵字2之后的B樹。1,3695,81,2,3692,5,81,2,3695,81692,5,831692358四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.假設以帶頭結點的單鏈表表示線性表，單鏈表的類型定義如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;閱讀下列算法，并回答問題：(1)已知初始鏈表如圖所示，畫出執(zhí)行f30(head)之后的鏈表；題30圖(2)簡

11、述算法f30的功能。void f30( LinkList head) LinkList p,r, s; if (head - > next) r = head - > next; p = r->next; r - > next = NULL; while (p) s =p; p = p->next; if ( s - > data% 2 = = 0) s - > next = head - > next; head - > next = s; else s - > next = r - > next; r->next =

12、s; r =s; (1)2857(2)31.假設以二叉鏈表表示二叉樹，其類型定義如下：typedef struct node DataType data; struct node * lchild, * rchild; /左右孩子指針 * BinTree ;閱讀下列算法，并回答問題：(1)已知以T為根指針的二叉樹如圖所示， 寫出執(zhí)行f31(T)之后的返回值；(2)簡述算法f31的功能。int f31 ( BinTree T) int d; if ( ! T) return 0; d = f31 ( T - > lchild) + f31 ( T - > rchild) ; if (

13、T - > lchild && T - > rchild) return d + 1 ; else return d;(1)3(2)統計度為2的結點個數32.設有向圖鄰接表定義如下：typedef struct VertexNode adjlist MaxVertexNum ; int n，e； 圖的當前頂點數和弧數ALGraph； 鄰接表類型其中頂點表結點VertexNode邊表結點EdgeNode結構為：閱讀下列算法，并回答問題：(1)已知某有向圖存儲在如圖所示的鄰接 表G中，寫出執(zhí)行f32(G)的輸出；(2)簡述算法f32的功能。int visited Max

14、Num ;void DFS(ALGraph * G, int i) EdgeNode * p; visited i = TRUE ; if (G - > adjlist i. firstedge = = NULL) printf( "% c ", G - > adjlist i. vertex)； else p = G - > adjlist i. firstedge; while (p ! = NULL) if ( ! visitedp -> adjvex ) DFS( G, p - > adjvex) ; p = p->next;vo

15、id f32 ( ALGraph * G) int i; for (i = 0; i < G->n; i +) visited i = FALSE ; for (i = 0; i < G->n; i+) if ( ! visitedi ) DFS(G, i) ;(1)ABECD(2)圖的深度優(yōu)先搜尋ABCDE33.下列算法f33的功能是對記錄序列進行雙向冒泡排序。算法的基本思想為，先從前往后通過交換將關鍵字最大的記錄移動至后端，然后從后往前通過交換將關鍵字最小的記錄移動至前端，如此反復進行，直至整個序列按關鍵字遞增有序為止。請在空缺處填入合適的內容，使其成為完整的算法。

16、#define MAXLEN 100typedef int KeyType;typedef struct KeyType key; InfoType otherinfo; NodeType ;typedef NodeType SqList MAXLEN ;void f33 ( SqList R, int n) int i,j,k; NodeType t; i =0; j =n-l; while (i < j) for ( (1) ) k=i;k<j;k+ if (Rk.key > Rk +l.key) t = Rk; Rk = Rk +1; Rk +1 = t; j-; fo

17、r (k =j; k > i; k - ) if ( (2) ) Rk.key < Rk-l.key t = Rk; Rk = Rk-1; Rk-1 = t; (3) ; i+(1)(2)(3)五、算法設計題(本大題10分)34.假設以帶頭結點的單鏈表表示線性表，單鏈表的類型定義如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;編寫算法，刪除線性表中最大元素(假設最大值唯一存在)。函數原型為：void f34(LinkList hea

18、d) LinkNode *p,*max,*q;P=head->next;max=head->next;while(P)P=p->next;If(p->data>max->data) max=p;x=max->data;delete_L(Lnode *L,int i) Lnode *p,*q;int j;Elemtype x; P=L;j=0; While(p->next!=null&&j<=i-1) p=p->next;j+; If(! P->next|i<1) Printf("n刪除位置錯誤！&

19、quot;);return(-1); Elseq=p->next;x=q->data; P->next=q->next;free(q); Return(x);/*delete_L*/2009年10月全國自考數據結構真題一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.按值可否分解，數據類型通?？煞譃閮深悾鼈兪?)A.靜態(tài)類型和動態(tài)類型B.原子類型和表類型C.原子類型和結構類型D.數組類型和指針類型答案：C2.A.AB.BC.CD.D答案：C3.指針p、q

20、和r依次指向某循環(huán)鏈表中三個相鄰的結點，交換結點*q和結點*r在表中次序的程序段是()A.p->next=r；q->next=r->next；r->next=q；B.p->next=r；r->next=q；q->next=r->next；C.r->next=q；q->next=r->next；p->next=r；D.r->next=q；p->next=r；q->next=r->next；答案：A4.若進棧次序為a，b，c，且進棧和出?？梢源┎暹M行，則可能出現的含3個元素的出棧序列個數是()A.3B.

21、5C.6D.7答案：B5.假設以數組An存放循環(huán)隊列的元素，其頭指針front指向隊頭元素的前一個位置、尾指針rear指向隊尾元素所在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為()A.rear=frontB.(front+1)n=rearC.rear+1=frontD.(rear+1)n=front答案：D6.串的操作函數str定義為：A.3B.4C.5D.6答案：C7.二維數組A106采用行優(yōu)先的存儲方法，若每個元素占4個存儲單元，已知元素A34的存儲地址為1000，則元素A43的存儲地址為()A.1020B.1024C.1036D.1240答案：A8.對廣義表L= (a，

22、()執(zhí)行操作tail(L)的結果是()A.()B.()C.aD.(a)答案：B9.已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為()A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA答案：A10.已知森林F=T1，T2，T3，T4，T5，各棵樹Ti(i=1，2，3，4，5)中所含結點的個數分別為7，3，5，1，2，則與F對應的二叉樹的右子樹中的結點個數為()A.2B.3C.8D.11答案：D11.若非連通無向圖G含有21條邊，則G的頂點個數至少為()A.7B.8C.21D.22答案：B12.如圖所示的有向圖的拓撲序列是()A.c，d，b，a，eB.c，a，

23、d，b，eC.c，d，e，a，bD.c，a，b，d，e答案：B13.對關鍵字序列(6，1，4，3，7，2，8，5)進行快速排序時，以第1個元素為基準的一次劃分的結果為()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)答案：C14.分塊查找方法將表分為多塊，并要求()A.塊內有序B.塊間有序C.各塊等長D.鏈式存儲答案：B15.便于進行布爾查詢的文件組織方式是()A.順序文件B.索引文件C.散列文件D.多關鍵字文件答案：二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共

24、20分）請在每個空格中填上正確答案。錯填、不填均無分。1.數據的鏈式存儲結構的特點是借助_表示數據元素之間的邏輯關系。答案：指針2.如果需要對線性表頻繁進行_或_操作，則不宜采用順序存儲結構。答案：插入 刪除3.如圖所示，可以利用一個向量空間同時實現兩個類型相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則“棧滿”的判定條件是_。答案：top1>top2(或top2=top1-1或top1=top2+1)4.靜態(tài)存儲分配的順序串在進行插入、置換和_等操作時可能發(fā)生越界。答案：聯接5.廣義表L=（a，（b，( )）的深度為_。答案：36.任意一棵完全二叉樹中，

25、度為1的結點數最多為_。答案：17.求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中_的數目正相關。答案：邊8.在5階B樹中，每個結點至多含4個關鍵字，除根結點之外，其他結點至少含_個關鍵字。答案：29.若序列中關鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是_的。答案：穩(wěn)定10.常用的索引順序文件是_文件和_文件。答案：ISAM VSAM三、解答題(本大題共4小題，每小題5分，共20分)1.答案：2.由字符集s，t，a，e，i及其在電文中出現的頻度構建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據該哈夫曼樹進行譯碼，寫出原來的電文。答案

26、：eatst(說明：每個字母1分)（5分）3.已知無向圖G的鄰接表如圖所示，(1)畫出該無向圖；(2)畫出該圖的廣度優(yōu)先生成森林。(1)(2)答案：(1)(說明：每錯1個頂點或邊，扣0.5分，扣完3分為止)（3分）(2)(說明：每錯1個頂點或邊，扣0.5分，扣完2分為止)（2分）4.對序列(48，37，63，96，22，31，50，55，11)進行升序的堆排序，寫出構建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。初始堆：第1趟：第2趟：答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分）第1趟：（63，55，50，48，22，31，11，37，96）（2分）第2趟：

27、（55，48，50，37，22，31，11，63，96）（1分）四、算法閱讀題(本大題共4小題，每小題5分，共20分)1.閱讀下列算法，并回答問題：(1)無向圖G如圖所示，寫出算法f30(&G)的返回值；(2)簡述算法f30的功能。#define MaxNum 20int visitedMaxNum；void DFS(Graph *g，int i)；/*從頂點vi出發(fā)進行深度優(yōu)先搜索，訪問頂點vj時置visitedj為1*/int f30(Graph *g)int i，k；for (i=0； i<g->n； i+)*g->n為圖g的頂點數目*visitedi=0；fo

28、r (i=k=0； i<g->n; i+)if (visitedi=0)k+；DFS(g，i)；return k；(1)(2)答案：（1）3（3分）（2）返回無向圖g中連通分量的個數。（2分）2.假設學生成績按學號增序存儲在帶頭結點的單鏈表中，類型定義如下：typedef struct Node int id;/*學號*/int score；/*成績*/struct Node *next； LNode， *LinkList；閱讀算法f31，并回答問題：(2)簡述算法f31的功能。void f31(LinkList A, LinkList B)LinkList p, q;p=A-&g

29、t;next;q=B->next;while (p && q)if (p->id<q->id)p=p->next;else if (p->id >q->id)q=q->next;else if (p->score <60)if (q->score <60)p->score=q->score;else p->score=60;p=p->next;q=q->next;(1)(2)答案：3.閱讀下列算法，并回答問題：(1)設串s=OneWorldOneDream，t=One，p

30、os是一維整型數組，寫出算法f32(s，t，pos)執(zhí)行之后得到的返回值和pos中的值；(2)簡述算法f32的功能。int strlen(char*s)； /*返回串s的長度*/int index(char*st，char*t)；*若串t在串st中出現，則返回在串st中首次出現的下標值，否則返回-1*/int f32(char*s, char*t, int pos) int i, j, k, ls, lt;ls=strlen(s);lt=strlen(t);if (ls=0|lt=0) return-1;k=0;i=0;do j=index(s+i, t);if (j>=0) posk+

31、=i+j;i+=j+it;while(i+it<=is && j >=0);return k;(1)(2)答案：（1）2；pos0=0,pos1=8(說明：每個值1分)（3分）（2）返回串t在s中出現的次數，并將每次出現的位置依次存放在數組pos中。（2分）4.二叉排序樹的存儲結構定義為以下類型：typedef int KeyType;typedef struct node KeyType key;/*關鍵字項*/InfoType otherinfo;/*其它數據項*/struct node *lchild, *rchild;/*左、右孩子指針*/ BSTNode,

32、 *BSTree；閱讀算法f33，并回答問題：(1)對如圖所示的二叉排序樹T，寫出f33(T，8)返回的指針所指結點的關鍵字；(2)在哪些情況下算法f33返回空指針?(3)簡述算法f33的功能。BSTNode *f33(BSTree T, KeyType x) BSTNode *p;if (T=NULL) return NULL;p=f33(T->lchild, x);if (p!=NULL) return p;if (T->key >x) return T;return f33(T->rchild, x);(1)(2)(3)答案：（1）10（2分）（2）T是空樹或T中

33、所有結點的關鍵字均不大于給定值x時，返回空指針。（2分）（3）如果二叉排序樹T中存在含有關鍵字大于給定值x的結點，則返回指針指向它們中關鍵字最小的結點，否則返回空指針。（1分）五、算法設計題（本題10分）1.假設線性表采用順序存儲結構，其類型定義如下：#define ListSize 100typedef struct int dataListSize;int length; SeqList, *Table;編寫算法，將順序表L中所有值為奇數的元素調整到表的前端。答案：參考答案一：void f34(Table L)(或者參數說明為：SeqList *L,1分) int i,j,t;i=0;（初

34、始化，1分）j=L->length-1;while(i<j)(循環(huán)控制，1分) while(i<j&&L->datai%2)（1分）i+;while(i<j&&L->dataj%2=0)（1分）j-;if(i<j)(條件判斷，1分)t=L->datai;（交換，2分）L->datai=L->dataj;L->dataj=t;i+;(i和j,1分)j-;(其他，如“L->”表達，1分)參考答案二：void f34(SeqList*L)(或者參數說明為：Table L,1分) int i,j=0

35、,t;(初始化，1分)for(i=0;i<L->length;i+)(循環(huán)控制，2分)if(L->datai%2)/*奇數*/（奇數處理框架，1分） if(i!=j)(避免同一元素交換，1分) t=L->datai;(交換，2分)L->datai=L->dataj;L->dataj=t;j+;（1分）（其他，如“L->”表達，1分）全國2010年1月高等教育自學考試數據結構試題及參考答案課程代碼：02331一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯

36、選、多選或未選均無分。1若一個算法的時間復雜度用T(n)表示，其中n的含義是（ A ）A問題規(guī)模 B語句條數C循環(huán)層數 D函數數量2具有線性結構的數據結構是（ C ）A樹 B圖C棧和隊列 D廣義表3將長度為n的單鏈表連接在長度為m的單鏈表之后，其算法的時間復雜度為（ B ）AO(1) BO(m)CO(n)DO(m+n)4在帶頭結點的雙向循環(huán)鏈表中插入一個新結點，需要修改的指針域數量是（ C ）A2個 B3個 C4個D6個5假設以數組A60存放循環(huán)隊列的元素，其頭指針是front=47，當前隊列有50個元素，則隊列的尾指針值為（ B ）A3 B37C50 D976若棧采用鏈式存儲結構，則下列說法

37、中正確的是（ B ） A需要判斷棧滿且需要判斷?？?B不需要判斷棧滿但需要判斷棧空 C需要判斷棧滿但不需要判斷?？?D不需要判斷棧滿也不需要判斷?？?若串str=”Software”，其子串的數目是（ D ）A8 B9C36 D378設有一個10階的下三角矩陣A，采用行優(yōu)先壓縮存儲方式，all為第一個元素，其存儲地址為1000，每個元素占一個地址單元，則a85的地址為 （ C ）A1012 B1017C1032 D10399允許結點共享的廣義表稱為（ D ）A純表 B線性表C遞歸表 D再入表10下列數據結構中，不屬于二叉樹的是（ A ）AB樹 BAVL樹C二叉排序樹 D哈夫曼樹11對下面有向圖

38、給出了四種可能的拓撲序列，其中錯誤的是（ C ）A1，5，2，6，3，4 B1，5，6，2，3，4C5，1，6，3，4，2 D5，1，2，6，4，312以v1為起始結點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（ D ）Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6 Dv1，v2，v5，v6，v7，v3，v413下列排序算法中不穩(wěn)定的是（ A ）A快速排序 B歸并排序C冒泡排序 D直接插入排序14一個有序表為(1，3，9，12，32，41，45，62，75，77，82，95，100)，當采用折半查找方法查找值32時

39、，查找成功需要的比較次數是（ B ）A2 B3C4 D815采用ISAM組織文件的方式屬于（ D ）A鏈組織 B順序組織C散列組織 D索引組織二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。16數據元素及其關系在計算機存儲器內的表示稱為_存儲結構_。17長度為n的線性表采用單鏈表結構存儲時，在等概率情況下查找第i個元素的時間復雜度是_O（ n）_。18下面是在順序棧上實現的一個棧基本操作，該操作的功能是_。 typedef struct DataType data100； int top； SeqStack； DataType f18(S

40、eqStack*S) if(StackEmpty(S) Error(”Stack is empty”)； return S->dataS->top； 19在串匹配中，一般將主串稱為目標串，將子串稱為_模式串_。20已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)= _()_。21用6個權值分別為6、13、18、30、7和16的結點構造一棵哈夫曼(Huffman)樹，該樹的帶權路徑長度為_221_。 22已知有向圖如下所示，其中頂點A到頂點C的最短路徑長度是_35_。23對序列55，46，13，05，94，17，42進行基數排序，第一趟排序后的結果是_10,

41、42,12,94,55,01,46,17。24高度為3的3階B-樹最少的關鍵字總數是_13_。25VSAM通常作為大型索引順序文件的標準組織，其動態(tài)索引結構采用的是_B+_。三、解答題(本大題共4小題，每小題5分，共20分)26假設二叉樹的RNL遍歷算法定義如下： 若二叉樹非空，則依次執(zhí)行如下操作： (1)遍歷右子樹； (2)訪問根節(jié)點； (3)遍歷左子樹。已知一棵二叉樹如圖所示，請給出其RNL遍歷的結果序列。GCFABDC27已知一個無向圖G=(V，E)，其中V=A，B，C，D，E，F，鄰接矩陣表示如下所示。請回答下列問題：(1)請畫出對應的圖G。(2)畫出圖G的鄰接表存儲結構。28已知一組

42、待排記錄的關鍵字序列為(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，請給出初始建堆后的序列。29已知一棵二叉排序樹如圖所示。 請回答下列問題： (1)畫出插入元素23后的樹結構；(2)請畫出在原圖中刪除元素57后的樹結構。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30已知下列程序，Ls指向帶頭結點的單鏈表。 Typedefstruct node DataType data; struct node * next; * LinkList; void f30( LinkList Ls ) LinkList p, q; q = Ls->nex

43、t; if ( q && q->next ) Ls->next = q->next; p=q while ( p->next ) p = p->next; p->next = q; q->next = NULL;請回答下列問題：(1)當Ls指向的鏈表如下圖所示，請畫出執(zhí)行本函數之后的鏈表的結果。(2)請簡述算法的功能。31已知字符串處理函數f31程序如下。 int f31(char*strl，char*str2) while(*strl=*str2&&(*strl!=0) strl+； str2+； return(*st

44、rl-*str2 ? l0)； 請回答下列問題： (1)若調用語句是f31(”abcde”，”abcdf)，則函數的返回值是什么?若調用語句是 f31(”abcde”，”abcde”)，則函數的返回值是什么? (2)簡述該函數的功能。32數組A中存儲有n個整數，請閱讀下列程序。 void f32(intA，int n) inti，j，k，x； k=n-l； while(k>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 while return； 請回答

45、下列問題： (1)當A=10，8，2，4，6，7時，執(zhí)行f32(A，6)后，數組A中存儲的結果是什么? (2)說明該算法的功能。33下面程序實現二分查找算法。 Typedef struct KeyType key； InfoType otherinfo； SeqListN+1； int BinSearch(SeqList R, int n，KeyType K) int low=1，high=n； while( (1) ) mid=(1ow+high)2； if( (2) ) return mid； if(Rmidkey>K) high=mid-1； else (3) ； return O

46、； BinSearch 請在空白處填寫適當內容，使該程序功能完整。 (1) (2) (3)五、算法設計題(本題10分)34已知二叉樹采用二叉鏈表存儲，其結點結構定義如下： typedef struct Node ElmType data； struct Node *lchild，*rchild； *BiTree； 請編寫遞歸函數SumNodes(BiTree T)，返回二叉樹T的結點總數。32、下面程序實現插入排序算法。typedef struct int key; Info otherinof;Seqlist;void InsertSort(SeqList R, int n)/*待排序列保存在R1.n中*/ Seqlist x; int i,j,k,lo,hi,mi; for (i=2;i<=n;i+) x=Ri;lo=1;hi=i-1;/*用二分查找法找到待排序數據插入的位置*/while (lo<=hi) mi=(lo+hi)/2; if (Rmi.key=x.key) break; if (Rmi.key>x.key) hi=mi-1; else lo=m