三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

29．設(shè)一個(gè)鏈棧的輸入序列為X，Y，Z，試寫出出棧的所有可能的輸出序列及其操作步驟。

30．設(shè)二叉樹的先序遍歷序列為DCBAHEIFG，中序遍歷序列為ABCHDIEFG，試畫出該二叉樹并寫出后序遍歷序列。

31．已知連通帶權(quán)圖如題31圖所示，試?yán)�用普里姆（Prim）算法，從頂點(diǎn)A出發(fā)，構(gòu)造它的最小生成樹，畫出構(gòu)造過程。

32．給定表（28，15，55，3，71，75，10，22，56），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹。

33．應(yīng)用直接選擇排序算法，對(duì)初始關(guān)鍵字序列為48，35，61，98，82，18，29，48的記錄進(jìn)行從小到大排序，寫出排序過程和結(jié)果。

四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)

34.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：

typedef struct node

{ int data;

              struct node *next;

             }Node, *LinkList;

試編寫在帶頭結(jié)點(diǎn)的單鏈表head中查找第1個(gè)元素值小于x的結(jié)點(diǎn)的實(shí)現(xiàn)算法Node *GetLinklist(LinkList head，int x)，若找到，則返回指向該結(jié)點(diǎn)的指針，否則返回NULL。

35．假設(shè)樹采用孩子兄弟鏈表表示法，其結(jié)構(gòu)定義如下：

typedef struct tnode

{ DataType data;

  struct tnode *son, *brother;

}*Tree;

試編寫算法void leveltree(Tree root)實(shí)現(xiàn)樹的按層次遍歷。