自考數(shù)據(jù)結(jié)構(gòu)歷年試題及答案?jìng)€(gè)人整理

1、自考數(shù)據(jù)結(jié)構(gòu)02331歷年試題及答案(2009-2015個(gè)人整理版)全國(guó)2009年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1.下列程序段的時(shí)間復(fù)雜度為( )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.假設(shè)某個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則判定該表為空表的條件是( )22A.head=NULL；B.head->next=NU

2、LL；C.head!=NULL；D.head->next=head；3.棧是一種操作受限的線(xiàn)性結(jié)構(gòu)，其操作的主要特征是( )32A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)于出D.出優(yōu)于進(jìn)4.假設(shè)以數(shù)組An存放循環(huán)隊(duì)列的元素，其頭、尾指針?lè)謩e為front和rear。若設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為( )A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n5.判斷兩個(gè)串大小的基本準(zhǔn)則是( )52A.兩個(gè)串長(zhǎng)度的大小B.兩個(gè)串中首字符的大小C.兩個(gè)串中大寫(xiě)字

3、母的多少D.對(duì)應(yīng)的第一個(gè)不等字符的大小6.二維數(shù)組A45按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占2個(gè)存儲(chǔ)單元，且第一個(gè)元素A00的存儲(chǔ)地址為1000，則數(shù)組元素A32的存儲(chǔ)地址為( )60A.1012B.1017C.1034D.1036a00a01a02a03a04a327.高度為5的完全二叉樹(shù)中含有的結(jié)點(diǎn)數(shù)至少為( )72A.16B.17C.31D.328.已知在一棵度為3的樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為4，度為3的結(jié)點(diǎn)數(shù)為3，則該樹(shù)中的葉子結(jié)點(diǎn)數(shù)為( )A.5B.8C.11D.189.下列所示各圖中是中序線(xiàn)索化二叉樹(shù)的是( A )81A10.已知含6個(gè)頂點(diǎn)(v0，v1，v2，v3，v4，v5)的無(wú)向圖的鄰接

4、矩陣如圖所示，則從頂點(diǎn)v0出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的頂點(diǎn)訪問(wèn)序列為( )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.如圖所示有向圖的一個(gè)拓?fù)湫蛄惺? )A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列關(guān)鍵字序列中，構(gòu)成大根堆的是( )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.對(duì)長(zhǎng)度為15的有序順序表進(jìn)行二分查找，在各記錄的查找概率

5、均相等的情況下，查找成功時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)的平均值為( )172A.B.C.D.14.已知一個(gè)散列表如圖所示，其散列函數(shù)為H(key)=key11，采用二次探查法處理沖突，則下一個(gè)插入的關(guān)鍵字49的地址為( D )d 19715.數(shù)據(jù)庫(kù)文件是由大量帶有結(jié)構(gòu)的( )206A.記錄組成的集合B.字符組成的集合C.數(shù)據(jù)項(xiàng)組成的集合D.數(shù)據(jù)結(jié)構(gòu)組成的集合二、填空題(本大題共10小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16.估算算法時(shí)間復(fù)雜度時(shí)考慮的問(wèn)題規(guī)模通常是指算法求解問(wèn)題的_輸入量_。 817.在雙向循環(huán)鏈表中插入一個(gè)新的結(jié)點(diǎn)時(shí)，應(yīng)修改_4_個(gè)指針域的

6、值。 2818.若進(jìn)棧序列為a，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)_5_個(gè)不同的出棧序列。519.鏈串的結(jié)點(diǎn)大小定義為結(jié)點(diǎn)的_數(shù)據(jù)域_中存放的字符個(gè)數(shù)。 5420.廣義表(a，(d，(c)的深度為_(kāi)3 _。6721.在含有3個(gè)結(jié)點(diǎn)a，b，c的二叉樹(shù)中，前序序列為abc且后序序列為cba的二叉樹(shù)有_4_棵。422.若用鄰接矩陣表示有向圖，則頂點(diǎn)i的入度等于矩陣中_。第i列非零元素的個(gè)數(shù)10723.對(duì)關(guān)鍵字序列(15，18，11，13，19，16，12，17，10，8)進(jìn)行增量為5的一趟希爾排序的結(jié)果為_(kāi)。 15，12，11，10，8，16，18，1724.索引順序查找的索引表由各分塊中

7、的最大關(guān)鍵字及各分塊的_起始位置_構(gòu)成。17325.VSAM文件的實(shí)現(xiàn)依賴(lài)于操作系統(tǒng)中的_分頁(yè)_存取方法的功能。 215三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)有一個(gè)形如的8×8矩陣，矩陣元素都是整型量(次對(duì)角線(xiàn)以上的元素都是0)。若將上述矩陣中次對(duì)角線(xiàn)及其以下的元素按行優(yōu)先壓縮存儲(chǔ)在一維數(shù)組B中，請(qǐng)回答下列問(wèn)題：(1)B數(shù)組的體積至少是多少?(2)若a18存儲(chǔ)在B0中，a56存儲(chǔ)在Bk中，則k值為多少?(1) （1+8）*8/2=36 存放次對(duì)角線(xiàn)以上的零為37(2) 1227.對(duì)關(guān)鍵字序列(5，8，1，3，9，6，2，7)按從小到大進(jìn)行快速排序。(1)寫(xiě)出排序

8、過(guò)程中前兩趟的劃分結(jié)果；(2)快速排序是否是穩(wěn)定的排序方法?(1)第一趟劃分結(jié)果；(2，3，1)，5，(9，6，8，7)第二趟劃分結(jié)果；(1，2，3)，5，(9，6，8，7)第三趟劃分結(jié)果；(1，2，3)，5，(7，6，8，9)第四趟劃分結(jié)果； 1，2，3，5，6，7，8，9第一趟劃分過(guò)程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)第二趟劃分過(guò)程(2，3，1，5，9，6，8，7)1(1，2，3

9、，5，7，6，8，9) (2)非穩(wěn)定2315968712355768956789ji第一趟：（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.假設(shè)通信電文使用的字符集為a，b，c，d，e，f，g，h，各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，試為這8個(gè)字符設(shè)計(jì)哈夫曼編碼。要求：(1)畫(huà)出你所構(gòu)造的哈夫曼樹(shù)(要求樹(shù)中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值)； (2)按左分支為0和右分支為1的規(guī)則，分別寫(xiě)出與每個(gè)字符對(duì)應(yīng)的編碼。(1)(2)29.已知3

10、階B樹(shù)如圖所示，非根 【1，2】P184根 【1，2】(1)畫(huà)出將關(guān)鍵字6插入之后的B樹(shù)；1,3695,8(2)畫(huà)出在(1)所得樹(shù)中插入關(guān)鍵字2之后的B樹(shù)。1,2,3695,81,3695,81,2,3692,5,81692,5,831692358四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線(xiàn)性表，單鏈表的類(lèi)型定義如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;閱讀下列算法，并回答問(wèn)題：(1)已知初始鏈

11、表如圖所示，畫(huà)出執(zhí)行f30(head)之后的鏈表；題30圖(2)簡(jiǎn)述算法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 - > ne

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

13、) + f31 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else return d;(1)3(2)統(tǒng)計(jì)度為2的結(jié)點(diǎn)個(gè)數(shù)32.設(shè)有向圖鄰接表定義如下：typedef struct VertexNode adjlist MaxVertexNum ; int n，e； 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph； 鄰接表類(lèi)型其中頂點(diǎn)表結(jié)點(diǎn)VertexNode邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為：閱讀下列算法，并回答問(wèn)題：(1)已知某有向圖存儲(chǔ)在如圖所示的鄰接 表G中，寫(xiě)出執(zhí)行f32(G)

14、的輸出；(2)簡(jiǎn)述算法f32的功能。int visited MaxNum ;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 -

15、 > adjvex) ; p = p->next;void 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的功能是對(duì)記錄序列進(jìn)行雙向冒泡排序。算法的基本思想為，先從前往后通過(guò)交換將關(guān)鍵字最大的記錄移動(dòng)至后端，然后從后往前通過(guò)交換將關(guān)鍵字最小的記錄移動(dòng)至前端，如此反復(fù)進(jìn)行，直至整個(gè)序列按

16、關(guān)鍵字遞增有序?yàn)橹埂Ｕ?qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。#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 =

17、Rk; Rk = Rk +1; Rk +1 = t; j-; for (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)五、算法設(shè)計(jì)題(本大題10分)34.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線(xiàn)性表，單鏈表的類(lèi)型定義如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;編寫(xiě)算法，刪除線(xiàn)性表中最大元素(假設(shè)最大值

18、唯一存在)。函數(shù)原型為：void f34(LinkList head) 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->ne

19、xt|i<1) Printf("n刪除位置錯(cuò)誤！");return(-1); Elseq=p->next;x=q->data; P->next=q->next;free(q); Return(x);/*delete_L*/全國(guó)2009年10月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)真題一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1.按值可否分解，數(shù)據(jù)類(lèi)型通?？煞譃閮深?lèi)，它們是(c)A.靜態(tài)類(lèi)型和動(dòng)態(tài)類(lèi)型B.原子類(lèi)型和表類(lèi)型C.原子類(lèi)型和結(jié)構(gòu)類(lèi)型D.數(shù)組

20、類(lèi)型和指針類(lèi)型2. A.A f(n)是0(g(n)B.B g(n)是0(f(n)C.C h(n)是0(nlogn)D.D h(n)是0(n2)答案：C3.指針p、q和r依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)*q和結(jié)點(diǎn)*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

21、=r；q->next=r->next；答案：A4.若進(jìn)棧次序?yàn)閍，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的含3個(gè)元素的出棧序列個(gè)數(shù)是()A.3B.5C.6D.7答案：B5.假設(shè)以數(shù)組An存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素的前一個(gè)位置、尾指針rear指向隊(duì)尾元素所在的存儲(chǔ)位置，則在少用一個(gè)元素空間的前提下，隊(duì)列滿(mǎn)的判定條件為()A.rear=frontB.(front+1)n=rearC.rear+1=frontD.(rear+1)n=front答案：D6.串的操作函數(shù)str定義為：A.3B.4C.5D.6答案：C7.二維數(shù)組A106采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)

22、元素占4個(gè)存儲(chǔ)單元，已知元素A34的存儲(chǔ)地址為1000，則元素A43的存儲(chǔ)地址為()A.1020B.1024C.1036D.1240答案：A8.對(duì)廣義表L= (a，()執(zhí)行操作tail(L)的結(jié)果是()A.()B.()C.aD.(a)答案：B9.已知二叉樹(shù)的中序序列和后序序列均為ABCDEF，則該二叉樹(shù)的先序序列為()A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA答案：A10.已知森林F=T1，T2，T3，T4，T5，各棵樹(shù)Ti(i=1，2，3，4，5)中所含結(jié)點(diǎn)的個(gè)數(shù)分別為7，3，5，1，2，則與F對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)為()A.2B.3C.8D.11答案：D11

23、.若非連通無(wú)向圖G含有21條邊，則G的頂點(diǎn)個(gè)數(shù)至少為()A.7B.8C.21D.22答案：B12.如圖所示的有向圖的拓?fù)湫蛄惺?)A.c，d，b，a，eB.c，a，d，b，eC.c，d，e，a，bD.c，a，b，d，e答案：B13.對(duì)關(guān)鍵字序列(6，1，4，3，7，2，8，5)進(jìn)行快速排序時(shí)，以第1個(gè)元素為基準(zhǔn)的一次劃分的結(jié)果為()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.塊內(nèi)有序B.塊間有序C.各塊等長(zhǎng)D.鏈?zhǔn)酱鎯?chǔ)答案：B15.便

24、于進(jìn)行布爾查詢(xún)的文件組織方式是()A.順序文件B.索引文件C.散列文件D.多關(guān)鍵字文件答案：D二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）請(qǐng)?jiān)诿總€(gè)空格中填上正確答案。錯(cuò)填、不填均無(wú)分。1.數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助_指針_表示數(shù)據(jù)元素之間的邏輯關(guān)系。2.如果需要對(duì)線(xiàn)性表頻繁進(jìn)行_插入_或_刪除_操作，則不宜采用順序存儲(chǔ)結(jié)構(gòu)。3.如圖所示，可以利用一個(gè)向量空間同時(shí)實(shí)現(xiàn)兩個(gè)類(lèi)型相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則“棧滿(mǎn)”的判定條件是_ top1>top2(或top2=top1-1或top1=top2+1)。4

25、.靜態(tài)存儲(chǔ)分配的順序串在進(jìn)行插入、置換和_聯(lián)接_等操作時(shí)可能發(fā)生越界。5.廣義表L=（a，（b，( )）的深度為_(kāi)3_。6.任意一棵完全二叉樹(shù)中，度為1的結(jié)點(diǎn)數(shù)最多為_(kāi)1_。7.求最小生成樹(shù)的克魯斯卡爾(Kruskal)算法耗用的時(shí)間與圖中_邊_的數(shù)目正相關(guān)。8.在5階B樹(shù)中，每個(gè)結(jié)點(diǎn)至多含4個(gè)關(guān)鍵字，除根結(jié)點(diǎn)之外，其他結(jié)點(diǎn)至少含_2_個(gè)關(guān)鍵字。9.若序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱(chēng)該排序算法是_穩(wěn)定_的。10.常用的索引順序文件是_ ISAM _文件和_ VSAM _文件。三、解答題(本大題共4小題，每小題5分，共20分)1.答案：2.由字符集s，t，a，e，i及其在電文

26、中出現(xiàn)的頻度構(gòu)建的哈夫曼樹(shù)如圖所示。請(qǐng)根據(jù)該哈夫曼樹(shù)進(jìn)行譯碼，寫(xiě)出原來(lái)的電文。答案：eatst(說(shuō)明：每個(gè)字母1分)（5分）3.已知無(wú)向圖G的鄰接表如圖所示，(1)畫(huà)出該無(wú)向圖；(2)畫(huà)出該圖的廣度優(yōu)先生成森林。4.對(duì)序列(48，37，63，96，22，31，50，55，11)進(jìn)行升序的堆排序，寫(xiě)出構(gòu)建的初始(大根)堆及前兩趟重建堆之后的序列狀態(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趟：（55，48，50，37，22，31，11，63，96）（1分）四、

27、算法閱讀題(本大題共4小題，每小題5分，共20分)1.閱讀下列算法，并回答問(wèn)題：(1)無(wú)向圖G如圖所示，寫(xiě)出算法f30(&G)的返回值；(2)簡(jiǎn)述算法f30的功能。#define MaxNum 20int visitedMaxNum；void DFS(Graph *g，int i)；/*從頂點(diǎn)vi出發(fā)進(jìn)行深度優(yōu)先搜索，訪問(wèn)頂點(diǎn)vj時(shí)置visitedj為1*/int f30(Graph *g)int i，k；for (i=0； i<g->n； i+)*g->n為圖g的頂點(diǎn)數(shù)目*visitedi=0；for (i=k=0； i<g->n; i+)if (vis

28、itedi=0)k+；DFS(g，i)；return k；(1)(2)答案：（1）3（3分）（2）返回?zé)o向圖g中連通分量的個(gè)數(shù)。（2分）2.假設(shè)學(xué)生成績(jī)按學(xué)號(hào)增序存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表中，類(lèi)型定義如下：typedef struct Node int id;/*學(xué)號(hào)*/int score；/*成績(jī)*/struct Node *next； LNode， *LinkList；閱讀算法f31，并回答問(wèn)題：(2)簡(jiǎn)述算法f31的功能。void f31(LinkList A, LinkList B)LinkList p, q;p=A->next;q=B->next;while (p &

29、& 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.閱讀下列算法，并回答問(wèn)題：(1)設(shè)串s=OneWorldOneDream，t=One，pos是一維整型數(shù)組，寫(xiě)出算法f32(s，t，pos)執(zhí)行之后得到的返

30、回值和pos中的值；(2)簡(jiǎn)述算法f32的功能。int strlen(char*s)； /*返回串s的長(zhǎng)度*/int index(char*st，char*t)；*若串t在串st中出現(xiàn)，則返回在串st中首次出現(xiàn)的下標(biāo)值，否則返回-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+=i+j;i+=j+it;while(i+it<=is &am

31、p;& j >=0return k;(1)(2)答案：（1）2；pos0=0,pos1=8(說(shuō)明：每個(gè)值1分)（3分）（2）返回串t在s中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos中。（2分）4.二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)定義為以下類(lèi)型：typedef int KeyType;typedef struct node KeyType key;/*關(guān)鍵字項(xiàng)*/InfoType otherinfo;/*其它數(shù)據(jù)項(xiàng)*/struct node *lchild, *rchild;/*左、右孩子指針*/ BSTNode, *BSTree；閱讀算法f33，并回答問(wèn)題：(1)對(duì)如圖所示的二叉排序

32、樹(shù)T，寫(xiě)出f33(T，8)返回的指針?biāo)附Y(jié)點(diǎn)的關(guān)鍵字；(2)在哪些情況下算法f33返回空指針?(3)簡(jiǎn)述算法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是空樹(shù)或T中所有結(jié)點(diǎn)的關(guān)鍵字均不大于給定值x時(shí)，返回空指針。（2分）（3）如果二叉排

33、序樹(shù)T中存在含有關(guān)鍵字大于給定值x的結(jié)點(diǎn)，則返回指針指向它們中關(guān)鍵字最小的結(jié)點(diǎn)，否則返回空指針。（1分）五、算法設(shè)計(jì)題（本題10分）1.假設(shè)線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，其類(lèi)型定義如下：#define ListSize 100typedef struct int dataListSize;int length; SeqList, *Table;編寫(xiě)算法，將順序表L中所有值為奇數(shù)的元素調(diào)整到表的前端。答案：參考答案一：void f34(Table L)(或者參數(shù)說(shuō)明為：SeqList *L,1分) int i,j,t;i=0;（初始化，1分）j=L->length-1;while(i<j)

34、(循環(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->”表達(dá)，1分)參考答案二：void f34(SeqList*L)(或者參數(shù)說(shuō)明為：Table L,1分) int i,j=0,t;(初始化，1分)for(i=0;i<L->length

35、;i+)(循環(huán)控制，2分)if(L->datai%2)/*奇數(shù)*/（奇數(shù)處理框架，1分） if(i!=j)(避免同一元素交換，1分) t=L->datai;(交換，2分)L->datai=L->dataj;L->dataj=t;j+;（1分）（其他，如“L->”表達(dá)，1分）全國(guó)2010年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是（ A ）A問(wèn)題規(guī)模 B語(yǔ)句條數(shù)C

36、循環(huán)層數(shù) D函數(shù)數(shù)量2具有線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ C ）線(xiàn)性結(jié)構(gòu)有：順序表、棧和隊(duì)列、串A樹(shù) B圖C棧和隊(duì)列 D廣義表3將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m的單鏈表之后，其算法的時(shí)間復(fù)雜度為（ B ）AO(1) BO(m)CO(n)DO(m+n)插入到長(zhǎng)度為m的單鏈表，需找到表尾，時(shí)間復(fù)雜度為o(m)，連接的時(shí)間復(fù)雜度為0(1),所以總的時(shí)間復(fù)雜度為0(m)4在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是（ C ）A2個(gè) B3個(gè) C4個(gè)D6個(gè)void DInsertBefore(DListNode *p,DataType x)/在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x的新結(jié)點(diǎn)插入結(jié)點(diǎn)*p之

37、前，設(shè)pNULL DListNode *s=malloc(sizeof(ListNode);s->data=x;s->prior=p->prior; s->next=p;p->prior->next=s;p->prior=s; 5假設(shè)以數(shù)組A60存放循環(huán)隊(duì)列的元素，其頭指針是front=47，當(dāng)前隊(duì)列有50個(gè)元素，則隊(duì)列的尾指針值為（ B ）A3 B37C50 D97對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫(xiě)出通過(guò)隊(duì)頭隊(duì)尾指針表示的隊(duì)列長(zhǎng)度公式。（front指向?qū)嶋H隊(duì)頭，rear指向?qū)嶋H隊(duì)尾的下一元素位置。）當(dāng)rearfront時(shí)，隊(duì)列長(zhǎng)度L=rear-front；

38、當(dāng)rear<front時(shí)，L=m+(rear-front)。這兩種情況可統(tǒng)一為L(zhǎng)=(m+(rear-front)%m，這里m為向量的大小。本題中m=606若棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則下列說(shuō)法中正確的是（ B ） A需要判斷棧滿(mǎn)且需要判斷?？?B不需要判斷棧滿(mǎn)但需要判斷?？?C需要判斷棧滿(mǎn)但不需要判斷?？?D不需要判斷棧滿(mǎn)也不需要判斷?？找?yàn)殒湕Ｖ械慕Y(jié)點(diǎn)是動(dòng)態(tài)分配的，可以不考慮上溢，所以無(wú)需定義stackFull運(yùn)算。7若串str=”Software”，其子串的數(shù)目是（ D ）A8 B9C36 D378設(shè)有一個(gè)10階的下三角矩陣A，采用行優(yōu)先壓縮存儲(chǔ)方式，all為第一個(gè)元素，其存儲(chǔ)地址為100

39、0，每個(gè)元素占一個(gè)地址單元，則a85的地址為 （ C ）A1012 B1017C1032 D1039在n階方陣A這個(gè)下三角矩陣中，第i（i從0開(kāi)始）行（0i<n）有i+1個(gè)元素，元素總數(shù)為：n(n+1)/2，并將元素放在一個(gè)向量sa0. n(n+1)/2-1中。若ij，則aij在左下三角矩陣中，sak與aij的對(duì)應(yīng)關(guān)系是k=i(i+1)/2+j。若i<j，則aij在右上三角矩陣中，sak與aij的對(duì)應(yīng)關(guān)系是k=j(j+1)/2+i。若all為第一個(gè)元素， a85與a00為第一個(gè)元素時(shí)的a(85-(11-00)= a74位置一樣，k=7*8/2+4=32，則a85的地址=1000+3

40、2=1032；若a44為第一個(gè)元素， a85與a00為第一個(gè)元素時(shí)的a(85-(44-00)= a41位置一樣，k=4*5/2+1=11，則a85的地址=1000+11=1011；9允許結(jié)點(diǎn)共享的廣義表稱(chēng)為（ D ）A純表 B線(xiàn)性表C遞歸表 D再入表10下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹(shù)的是（ A ）AB樹(shù) B樹(shù)是一種平衡的多叉樹(shù)BAVL樹(shù) AVL樹(shù)是自平衡二叉查找樹(shù)C二叉排序樹(shù) D哈夫曼樹(shù) 哈夫曼樹(shù)是最優(yōu)二叉樹(shù)11對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄校渲绣e(cuò)誤的是（ 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為起始結(jié)點(diǎn)對(duì)下圖

41、進(jìn)行深度優(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，v4深度優(yōu)先遍歷類(lèi)似于樹(shù)的前序遍歷。其特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。13下列排序算法中不穩(wěn)定的是（ A ）A快速排序 B歸并排序C冒泡排序 D直接插入排序穩(wěn)定：直接插入、冒泡、歸并、基數(shù) 不穩(wěn)定：直接選擇、希爾、快速、堆14一個(gè)有序表為(1，3，9，12，32，41，45，62，75，77，82，95，100)，當(dāng)采用折半查找方法查找值32時(shí)，查找成功需要的比較次數(shù)是（ B ）mi

42、d1=45，mid2=9，mid3=32A2 B3C4 D815采用ISAM組織文件的方式屬于（ D ）A鏈組織 B順序組織C散列組織 D索引組織二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱(chēng)為_(kāi)存儲(chǔ)結(jié)構(gòu)_。17長(zhǎng)度為n的線(xiàn)性表采用單鏈表結(jié)構(gòu)存儲(chǔ)時(shí)，在等概率情況下查找第i個(gè)元素的時(shí)間復(fù)雜度是_O（ n）_。18下面是在順序棧上實(shí)現(xiàn)的一個(gè)棧基本操作，該操作的功能是_取棧頂_。 typedef struct DataType data100； int top； SeqStack； DataType

43、 f18(SeqStack*S) if(StackEmpty(S) Error(”Stack is empty”)； return S->dataS->top； 19在串匹配中，一般將主串稱(chēng)為目標(biāo)串，將子串稱(chēng)為_(kāi)模式串_。20已知廣義表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)樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為_(kāi)221_。 WPL=30×1+18×2+16×3+13×4+6×5+7×5=30+36+48+52+

44、30+35=23122已知有向圖如下所示，其中頂點(diǎn)A到頂點(diǎn)C的最短路徑長(zhǎng)度是_35_。23對(duì)序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是_42,13,94,55,05,46,17。24高度為3的3階B-樹(shù)最少的關(guān)鍵字總數(shù)是_5_。P182一顆m（m3）階的B-樹(shù)，每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)j滿(mǎn)足： m/2 -1jm-1。即每個(gè)非根結(jié)點(diǎn)至少應(yīng)有 m/2 -1個(gè)關(guān)鍵字，至多有m-1個(gè)關(guān)鍵字。（注： m/2 是指不小于（即大于等于）m/2的最小整數(shù)。）一顆高度為h的m階B-樹(shù)中最少可容納的關(guān)鍵字總數(shù)為： m/2 h-1，最少可容納的結(jié)點(diǎn)總數(shù)為 m/2 h-1

45、m/2 -1以h=3，m=3為例，相應(yīng)的B-樹(shù)最少可容納的關(guān)鍵字總數(shù)為 m/2 h-1=23-1=7個(gè)。25VSAM通常作為大型索引順序文件的標(biāo)準(zhǔn)組織，其動(dòng)態(tài)索引結(jié)構(gòu)采用的是_B+_。三、解答題(本大題共4小題，每小題5分，共20分)26假設(shè)二叉樹(shù)的RNL遍歷算法定義如下： 若二叉樹(shù)非空，則依次執(zhí)行如下操作： (1)遍歷右子樹(shù)； (2)訪問(wèn)根節(jié)點(diǎn)； (3)遍歷左子樹(shù)。已知一棵二叉樹(shù)如圖所示，請(qǐng)給出其RNL遍歷的結(jié)果序列。GCFABDC27已知一個(gè)無(wú)向圖G=(V，E)，其中V=A，B，C，D，E，F(xiàn)，鄰接矩陣表示如下所示。請(qǐng)回答下列問(wèn)題：(1)請(qǐng)畫(huà)出對(duì)應(yīng)的圖G。(2)畫(huà)出圖G的鄰接表存儲(chǔ)結(jié)構(gòu)。2

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

47、>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)回答下列問(wèn)題：(1)當(dāng)Ls指向的鏈表如下圖所示，請(qǐng)畫(huà)出執(zhí)行本函數(shù)之后的鏈表的結(jié)果。(2)請(qǐng)簡(jiǎn)述算法的功能。刪除單鏈表的中間結(jié)點(diǎn)和尾結(jié)點(diǎn)。31已知字符串處理函數(shù)f31程序如下。 int f31(char*strl，char*str2) while(*strl=*str2&&(*strl!=0) st

48、rl+； str2+； return(*strl-*str2 ? l0)； 請(qǐng)回答下列問(wèn)題： (1)若調(diào)用語(yǔ)句是f31(”abcde”，”abcdf)，則函數(shù)的返回值是什么?若調(diào)用語(yǔ)句是 f31(”abcde”，”abcde”)，則函數(shù)的返回值是什么?由于'e '對(duì)應(yīng)的ASCII碼是101，'f'對(duì)應(yīng)的ASCII碼是102，則'e ''f'=101102=-1 函數(shù)的返回值是1。函數(shù)的返回值是0。 (2)簡(jiǎn)述該函數(shù)的功能。答：如果兩個(gè)字符串結(jié)點(diǎn)*strl和*strl中的字符相等，且字符串結(jié)點(diǎn)*strl中的字符不等于字符串結(jié)束標(biāo)識(shí)'0'，則兩個(gè)字符串結(jié)點(diǎn)*strl和*strl中的字符指針自加運(yùn)算。如果條件不滿(mǎn)足，則字符串結(jié)點(diǎn)*strl和*strl中的字符相減。若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于1；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于0。32數(shù)組A中存儲(chǔ)有n個(gè)整數(shù)，請(qǐng)閱讀下列程序。 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