【正文】 f(%c,amp。ch)。 if (ch == 39。39。) T = NULL。 else { T = (BiTNode *)malloc(sizeof(BiTNode))。 Tdata = ch。 CreateBT(Tlchild)。 CreateBT(Trchild)。 }}//交換二叉樹中結(jié)點(diǎn)的左右孩子void ExchangeBT(BiTree T){ BiTree temp。 if(T) { temp=Tlchild。 Tlchild=Trchild。 Trchild=temp。 ExchangeBT(Tlchild)。 ExchangeBT(Trchild)。 }}//先序遍歷二叉樹void PreOrderTraverse(BiTree T){ if(T) { printf(%c , Tdata)。 PreOrderTraverse(Tlchild)。 PreOrderTraverse(Trchild)。 }}//查找值為x的結(jié)點(diǎn)BiTree SearchTree(BiTree T,char X){ BiTree bt。 if(T) { if(Tdata==X) return T。 bt=SearchTree(Tlchild,X)。 if(bt==NULL) bt=SearchTree(Trchild,X)。 return bt。 } return NULL。}//統(tǒng)計(jì)以T為根的子樹中葉子結(jié)點(diǎn)數(shù)int LeafCount1 (BiTree T){ static int count。if ( T ) { if ((Tlchild==NULL)amp。amp。 (Trchild==NULL)) count++。 else { count=LeafCount1( Tlchild)。 count=LeafCount1( Trchild)。 } } return count。} void LeafCount2 (BiTree T, int amp。count){ if ( T ) { if ((Tlchild==NULL)amp。amp。 (Trchild==NULL)) count++。 LeafCount2( Tlchild, count)。 LeafCount2( Trchild, count)。 } } //按樹狀打印輸出二叉樹的元素,level表示結(jié)點(diǎn)的層次void DispBiTree(BiTree T,int level){ int i。 if(T){ DispBiTree(Trchild, level + 1)。 for(i = 0。 i level。i++) printf()。 printf(%c\n,Tdata)。 DispBiTree(Tlchild, level + 1)。 }}void main(){ BiTree T,SubT。 char Subch。 int countl=0。 printf(輸入先序序列建立二叉樹：\n)。 CreateBT(T)。 printf(\n二叉樹的先序序列：)。 PreOrderTraverse(T)。 printf(\n二叉樹為：\n)。 DispBiTree(T,0)。 printf(交換結(jié)點(diǎn)的左右孩子\n)。 ExchangeBT(T)。 printf(\n此時(shí)二叉樹為：\n)。 DispBiTree(T,0)。 printf(輸入要統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)的子樹的根：)。 fflush(stdin)。 scanf(%c,amp。Subch)。 SubT=SearchTree(T,Subch)。 //countl=LeafCount1(SubT)。 LeafCount2(SubT, countl)。 printf(葉子結(jié)點(diǎn)數(shù)為：%d\n,countl)。}作業(yè)4. 圖l 非編程作業(yè):1． 已知帶權(quán)有向圖如圖所示，畫出該圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)。2aafbdgcheA69783251302421參考答案：2． 無向圖鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示：(1) 畫出該無向圖；(2) 寫出在該鄰接表上，從頂點(diǎn)1出發(fā)所得到的深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)序列。參考答案：13247586DFS：1，3，4，7，8，6，5，2 BFS：1，3，2，4，7，6，5，8 作業(yè)5. 查找、排序l 非編程作業(yè)：1． 對(duì)下標(biāo)為1～9的有序表進(jìn)行折半查找，畫出折半查找的判定樹；并計(jì)算在等概率情況下查找成功的平均查找長度ASL。參考答案：2． 設(shè)有關(guān)鍵字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列表長12，散列函數(shù)為h(key)=key%11，用線性探查再散列、鏈地址法處理沖突，請(qǐng)分別畫出散列表，并計(jì)算。參考答案：線性探查再散列處理沖突：鏈地址法處理沖突：3． 已知待排序序列為{50，86，72，41，45，93，57，46}，請(qǐng)寫出按下列排序方法進(jìn)行升序排序時(shí)的第一趟排序結(jié)果：① 直接插入排序；② 冒泡排序；③ 簡單選擇排序；④ 堆排序初建堆序列。參考答案：第一趟直接插入排序：50，86，72，41，45，93，57，46第一趟冒泡排序： 50，72，41，45，86，57，46，93第一趟簡單選擇排序：41，86，72，50，45，93，57，46堆排序初建堆序列 ： 93，86，72，46，45，50，57，414． 設(shè)計(jì)一種方法，以少于2n3次的比較在順序存儲(chǔ)的n(n=2)個(gè)數(shù)中同時(shí)找出最大和最小值。參考答案：方法1：從n個(gè)數(shù)中找出最大值放在下標(biāo)為0的位置——(n1)次比較； 再在剩余的n1個(gè)數(shù)中找到最小值——(n2)次比較； 總比較次數(shù)為2n3。方法2：將n個(gè)數(shù)兩兩比較，比較的過程中將小的數(shù)放在前面，大的數(shù)放在后面——()次比較； 之后在偶數(shù)下標(biāo)的數(shù)中找到最小值（下標(biāo)從0開始）——()次比較； 在奇數(shù)下標(biāo)的數(shù)中找到最大值——()次比較； ，當(dāng)n=2時(shí)小于2n3。