自考數(shù)據(jù)結構02331歷年試題及答案(2009--2015個人整理版).doc

自考數(shù)據(jù)結構02331歷年試題及答案(2009-2015個人整理版)全國2009年1月自學考試數(shù)據(jù)結構試題一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.下列程序段的時間復雜度為( )9 s=0； for(i=1；in；i+) for(j=1；jnext=NULL；C.head!=NULL；D.head-next=head；3.棧是一種操作受限的線性結構，其操作的主要特征是( )32A.先進先出B.后進先出C.進優(yōu)于出D.出優(yōu)于進4.假設以數(shù)組An存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數(shù)為( )A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n5.判斷兩個串大小的基本準則是( )52A.兩個串長度的大小B.兩個串中首字符的大小C.兩個串中大寫字母的多少D.對應的第一個不等字符的大小6.二維數(shù)組A45按行優(yōu)先順序存儲，若每個元素占2個存儲單元，且第一個元素A00的存儲地址為1000，則數(shù)組元素A32的存儲地址為( )60A.1012B.1017C.1034D.1036a00a01a02a03a04a327.高度為5的完全二叉樹中含有的結點數(shù)至少為( )72A.16B.17C.31D.328.已知在一棵度為3的樹中，度為2的結點數(shù)為4，度為3的結點數(shù)為3，則該樹中的葉子結點數(shù)為( )A.5B.8C.11D.189.下列所示各圖中是中序線索化二叉樹的是( A )81A10.已知含6個頂點(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如圖所示，則從頂點v0出發(fā)進行深度優(yōu)先遍歷可能得到的頂點訪問序列為( )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的有序順序表進行二分查找，在各記錄的查找概率均相等的情況下，查找成功時所需進行的關鍵字比較次數(shù)的平均值為( )172A.B.C.D.14.已知一個散列表如圖所示，其散列函數(shù)為H(key)=key11，采用二次探查法處理沖突，則下一個插入的關鍵字49的地址為( D )d 19715.數(shù)據(jù)庫文件是由大量帶有結構的( )206A.記錄組成的集合B.字符組成的集合C.數(shù)據(jù)項組成的集合D.數(shù)據(jù)結構組成的集合二、填空題(本大題共10小題，每小題2分，共20分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.估算算法時間復雜度時考慮的問題規(guī)模通常是指算法求解問題的_輸入量_。 817.在雙向循環(huán)鏈表中插入一個新的結點時，應修改_4_個指針域的值。 2818.若進棧序列為a，b，c，且進棧和出?？梢源┎暹M行，則可能出現(xiàn)_5_個不同的出棧序列。519.鏈串的結點大小定義為結點的_數(shù)據(jù)域_中存放的字符個數(shù)。 5420.廣義表(a，(d，(c)的深度為_3 _。6721.在含有3個結點a，b，c的二叉樹中，前序序列為abc且后序序列為cba的二叉樹有_4_棵。422.若用鄰接矩陣表示有向圖，則頂點i的入度等于矩陣中_。第i列非零元素的個數(shù)10723.對關鍵字序列(15，18，11，13，19，16，12，17，10，8)進行增量為5的一趟希爾排序的結果為_。 15，12，11，10，8，16，18，1724.索引順序查找的索引表由各分塊中的最大關鍵字及各分塊的_起始位置_構成。17325.VSAM文件的實現(xiàn)依賴于操作系統(tǒng)中的_分頁_存取方法的功能。 215三、解答題(本大題共4小題，每小題5分，共20分)26.假設有一個形如的88矩陣，矩陣元素都是整型量(次對角線以上的元素都是0)。若將上述矩陣中次對角線及其以下的元素按行優(yōu)先壓縮存儲在一維數(shù)組B中，請回答下列問題：(1)B數(shù)組的體積至少是多少?(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)第一趟劃分結果；(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)定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.假設通信電文使用的字符集為a，b，c，d，e，f，g，h，各字符在電文中出現(xiàn)的頻度分別為：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)畫出將關鍵字6插入之后的B樹；1,3695,8(2)畫出在(1)所得樹中插入關鍵字2之后的B樹。1,2,3695,81,3695,81,2,3692,5,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)簡述算法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 = 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 (T - lchild & T - rchild) return d + 1 ; else return d;(1)3(2)統(tǒng)計度為2的結點個數(shù)32.設有向圖鄰接表定義如下：typedef struct VertexNode adjlist MaxVertexNum ; int n，e； 圖的當前頂點數(shù)和弧數(shù)ALGraph； 鄰接表類型其中頂點表結點VertexNode邊表結點EdgeNode結構為：閱讀下列算法，并回答問題：(1)已知某有向圖存儲在如圖所示的鄰接 表G中，寫出執(zhí)行f32(G)的輸出；(2)簡述算法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 - adjvex) ; p = p-next;void f32 ( ALGraph * G) int i; for (i = 0; i n; i +) visited i = FALSE ; for (i = 0; i n; i+) if ( ! visitedi ) DFS(G, i) ;(1)ABECD(2)圖的深度優(yōu)先搜尋ABCDE33.下列算法f33的功能是對記錄序列進行雙向冒泡排序。算法的基本思想為，先從前往后通過交換將關鍵字最大的記錄移動至后端，然后從后往前通過交換將關鍵字最小的記錄移動至前端，如此反復進行，直至整個序列按關鍵字遞增有序為止。請在空缺處填入合適的內容，使其成為完整的算法。#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 Rk +l.key) t = Rk; Rk = Rk +1; Rk +1 = t; j-; for (k =j; k i; k - ) if ( (2) ) Rk.key next;max=head-next;while(P)P=p-next;If(p-datamax-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&jnext;j+; If(! P-next|inext;x=q-data; P-next=q-next;free(q); Return(x);/*delete_L*/全國2009年10月自學考試數(shù)據(jù)結構真題一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是(c)A.靜態(tài)類型和動態(tài)類型B.原子類型和表類型C.原子類型和結構類型D.數(shù)組類型和指針類型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)鏈表中三個相鄰的結點，交換結點*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行，則可能出現(xiàn)的含3個元素的出棧序列個數(shù)是()A.3B.5C.6D.7答案：B5.假設以數(shù)組An存放循環(huán)隊列的元素，其頭指針front指向隊頭元素的前一個位置、尾指針rear指向隊尾元素所在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為()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)先的存儲方法，若每個元素占4個存儲單元，已知元素A34的存儲地址為1000，則元素A43的存儲地址為()A.1020B.1024C.1036D.1240答案：A8.對廣義表L= (a，()執(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)中所含結點的個數(shù)分別為7，3，5，1，2，則與F對應的二叉樹的右子樹中的結點個數(shù)為()A.2B.3C.8D.11答案：D11.若非連通無向圖G含有21條邊，則G的頂點個數(shù)至少為()A.7B.8C.21D.22答案：B12.如圖所示的有向圖的拓撲序列是()A.c，d，b，a，eB.c，a，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.多關鍵字文件答案：D二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）請在每個空格中填上正確答案。錯填、不填均無分。1.數(shù)據(jù)的鏈式存儲結構的特點是借助_指針_表示數(shù)據(jù)元素之間的邏輯關系。2.如果需要對線性表頻繁進行_插入_或_刪除_操作，則不宜采用順序存儲結構。3.如圖所示，可以利用一個向量空間同時實現(xiàn)兩個類型相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則“棧滿”的判定條件是_ top1top2(或top2=top1-1或top1=top2+1)。4.靜態(tài)存儲分配的順序串在進行插入、置換和_聯(lián)接_等操作時可能發(fā)生越界。5.廣義表L=（a，（b，( )）的深度為_3_。6.任意一棵完全二叉樹中，度為1的結點數(shù)最多為_1_。7.求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中_邊_的數(shù)目正相關。8.在5階B樹中，每個結點至多含4個關鍵字，除根結點之外，其他結點至少含_2_個關鍵字。9.若序列中關鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是_穩(wěn)定_的。10.常用的索引順序文件是_ ISAM _文件和_ VSAM _文件。三、解答題(本大題共4小題，每小題5分，共20分)1.答案：2.由字符集s，t，a，e，i及其在電文中出現(xiàn)的頻度構建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據(jù)該哈夫曼樹進行譯碼，寫出原來的電文。答案：eatst(說明：每個字母1分)（5分）3.已知無向圖G的鄰接表如圖所示，(1)畫出該無向圖；(2)畫出該圖的廣度優(yōu)先生成森林。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趟：（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； in； i+)*g-n為圖g的頂點數(shù)目*visitedi=0；for (i=k=0； in; i+)if (visitedi=0)k+；DFS(g，i)；return k；(1)(2)答案：（1）3（3分）（2）返回無向圖g中連通分量的個數(shù)。（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-next;q=B-next;while (p & q)if (p-idid)p=p-next;else if (p-id q-id)q=q-next;else if (p-score score score=q-score;else p-score=60;p=p-next;q=q-next;(1)(2)答案：3.閱讀下列算法，并回答問題：(1)設串s=OneWorldOneDream，t=One，pos是一維整型數(shù)組，寫出算法f32(s，t，pos)執(zhí)行之后得到的返回值和pos中的值；(2)簡述算法f32的功能。int strlen(char*s)； /*返回串s的長度*/int index(char*st，char*t)；*若串t在串st中出現(xiàn)，則返回在串st中首次出現(xiàn)的下標值，否則返回-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=0return k;(1)(2)答案：（1）2；pos0=0,pos1=8(說明：每個值1分)（3分）（2）返回串t在s中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos中。（2分）4.二叉排序樹的存儲結構定義為以下類型：typedef int KeyType;typedef struct node KeyType key;/*關鍵字項*/InfoType otherinfo;/*其它數(shù)據(jù)項*/struct node *lchild, *rchild;/*左、右孩子指針*/ BSTNode, *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中所有結點的關鍵字均不大于給定值x時，返回空指針。（2分）（3）如果二叉排序樹T中存在含有關鍵字大于給定值x的結點，則返回指針指向它們中關鍵字最小的結點，否則返回空指針。（1分）五、算法設計題（本題10分）1.假設線性表采用順序存儲結構，其類型定義如下：#define ListSize 100typedef struct int dataListSize;int length; SeqList, *Table;編寫算法，將順序表L中所有值為奇數(shù)的元素調整到表的前端。答案：參考答案一：void f34(Table L)(或者參數(shù)說明為：SeqList *L,1分) int i,j,t;i=0;（初始化，1分）j=L-length-1;while(ij)(循環(huán)控制，1分) while(idatai%2)（1分）i+;while(idataj%2=0)（1分）j-;if(idatai;（交換，2分）L-datai=L-dataj;L-dataj=t;i+;(i和j,1分)j-;(其他，如“L-”表達，1分)參考答案二：void f34(SeqList*L)(或者參數(shù)說明為：Table L,1分) int i,j=0,t;(初始化，1分)for(i=0;ilength;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-”表達，1分）全國2010年1月自學考試數(shù)據(jù)結構試題一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1若一個算法的時間復雜度用T(n)表示，其中n的含義是（ A ）A問題規(guī)模 B語句條數(shù)C循環(huán)層數(shù) D函數(shù)數(shù)量2具有線性結構的數(shù)據(jù)結構是（ C ）線性結構有：順序表、棧和隊列、串A樹 B圖C棧和隊列 D廣義表3將長度為n的單鏈表連接在長度為m的單鏈表之后，其算法的時間復雜度為（ B ）AO(1) BO(m)CO(n)DO(m+n)插入到長度為m的單鏈表，需找到表尾，時間復雜度為o(m)，連接的時間復雜度為0(1),所以總的時間復雜度為0(m)4在帶頭結點的雙向循環(huán)鏈表中插入一個新結點，需要修改的指針域數(shù)量是（ C ）A2個 B3個 C4個D6個void DInsertBefore(DListNode *p,DataType x)/在帶頭結點的雙鏈表中，將值為x的新結點插入結點*p之前，設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ù)組A60存放循環(huán)隊列的元素，其頭指針是front=47，當前隊列有50個元素，則隊列的尾指針值為（ B ）A3 B37C50 D97對于循環(huán)向量中的循環(huán)隊列，寫出通過隊頭隊尾指針表示的隊列長度公式。（front指向實際隊頭，rear指向實際隊尾的下一元素位置。）當rearfront時，隊列長度L=rear-front；當rearfront時，L=m+(rear-front)。這兩種情況可統(tǒng)一為L=(m+(rear-front)%m，這里m為向量的大小。本題中m=606若棧采用鏈式存儲結構，則下列說法中正確的是（ B ） A需要判斷棧滿且需要判斷?？?B不需要判斷棧滿但需要判斷棧空 C需要判斷棧滿但不需要判斷?？?D不需要判斷棧滿也不需要判斷棧空因為鏈棧中的結點是動態(tài)分配的，可以不考慮上溢，所以無需定義stackFull運算。7若串str=”Software”，其子串的數(shù)目是（ D ）A8 B9C36 D378設有一個10階的下三角矩陣A，采用行優(yōu)先壓縮存儲方式，all為第一個元素，其存儲地址為1000，每個元素占一個地址單元，則a85的地址為 （ C ）A1012 B1017C1032 D1039在n階方陣A這個下三角矩陣中，第i（i從0開始）行（0in）有i+1個元素，元素總數(shù)為：n(n+1)/2，并將元素放在一個向量sa0. n(n+1)/2-1中。若ij，則aij在左下三角矩陣中，sak與aij的對應關系是k=i(i+1)/2+j。若idataS-top； 19在串匹配中，一般將主串稱為目標串，將子串稱為_模式串_。20已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)= _()_。21用6個權值分別為6、13、18、30、7和16的結點構造一棵哈夫曼(Huffman)樹，該樹的帶權路徑長度為_221_。 WPL=301+182+163+134+65+75=30+36+48+52+30+35=23122已知有向圖如下所示，其中頂點A到頂點C的最短路徑長度是_35_。23對序列55，46，13，05，94，17，42進行基數(shù)排序，第一趟排序后的結果是_42,13,94,55,05,46,17。24高度為3的3階B-樹最少的關鍵字總數(shù)是_5_。P182一顆m（m3）階的B-樹，每個非根結點中所包含的關鍵字個數(shù)j滿足： m/2 -1jm-1。即每個非根結點至少應有 m/2 -1個關鍵字，至多有m-1個關鍵字。（注： m/2 是指不小于（即大于等于）m/2的最小整數(shù)。）一顆高度為h的m階B-樹中最少可容納的關鍵字總數(shù)為： m/2 h-1，最少可容納的結點總數(shù)為 m/2 h-1 m/2 -1以h=3，m=3為例，相應的B-樹最少可容納的關鍵字總數(shù)為 m/2 h-1=23-1=7個。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(xiàn)，鄰接矩陣表示如下所示。請回答下列問題：(1)請畫出對應的圖G。(2)畫出圖G的鄰接表存儲結構。28已知一組待排記錄的關鍵字序列為(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-next; 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í)行本函數(shù)之后的鏈表的結果。(2)請簡述算法的功能。刪除單鏈表的中間結點和尾結點。31已知字符串處理函數(shù)f31程序如下。 int f31(char*strl，char*str2) while(*strl=*str2&(*strl!=0) strl+； str2+； return(*strl-*str2 ? l0)； 請回答下列問題： (1)若調用語句是f31(”abcde”，”abcdf)，則函數(shù)的返回值是什么?若調用語句是 f31(”abcde”，”abcde”)，則函數(shù)的返回值是什么?由于e 對應的ASCII碼是101，f對應的ASCII碼是102，則e f=101102=-1 函數(shù)的返回值是1。函數(shù)的返回值是0。 (2)簡述該函數(shù)的功能。答：如果兩個字符串結點*strl和*strl中的字符相等，且字符串結點*strl中的字符不等于字符串結束標識0，則兩個字符串結點*strl和*strl中的字符指針自加運算。如果條件不滿足，則字符串結點*strl和*strl中的字符相減。若邏輯表達式的值為非零，則條件表達式的值等于1；若邏輯表達式的值為零，則條件表達式的值等于0。32數(shù)組A中存儲有n個整數(shù)，請閱讀下列程序。 void f32(intA，int n) inti，j，k，x； k=n-l； while(k0) i=k； k=0； for(j=O；jAj+1) x=Aj； Aj=Aj+l； Aj+1=x； k=j； end of if end of while return； 請回答下列問題： (1)當A=10，8，2，4，6，7時，執(zhí)行f32(A，6)后，數(shù)組A中存儲的結果是什么?答：數(shù)組A