三、應(yīng)用題(本大題共5小題，每小題6分，共30分)
29．設(shè)一個鏈棧的輸入序列為X，Y，Z，試寫出出棧的所有可能的輸出序列及其操作步驟。
30．設(shè)二叉樹的先序遍歷序列為DCBAHEIFG，中序遍歷序列為ABCHDIEFG，試畫出該二叉樹并寫出后序遍歷序列。
31．已知連通帶權(quán)圖如題31圖所示，試?yán)闷绽锬罚≒rim）算法，從頂點(diǎn)A出發(fā)，構(gòu)造它的最小生成樹，畫出構(gòu)造過程。
32．給定表（28，15，55，3，71，75，10，22，56），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。
33．應(yīng)用直接選擇排序算法，對初始關(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個元素值小于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)樹的按層次遍歷。
