2019浙江省資料結構考試高階

1、(1)p->rchild (2)p->lchild (3)p->lchild (4)addq(q,p->lchild) (5)addq(q,p->rchild)

25. (1)t->rchild!=null (2)t->rchild!=null (3)n0++ (4)count(t->lchild) (5)count(t->rchild)

26. .(1)top2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild

27. (1)*ppos // 根結點（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

2、設t是一棵滿二叉樹，編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。

3、請設計乙個演算法，要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表，表頭指標為head。二叉樹按二叉鍊錶方式儲存，鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。

4、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。

void translation（float *matrix，int n）

//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。

//for i

for(i=0; i

sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.

}//if

}//for i

free(p); //釋放p陣列.

}// translation

[演算法分析] 演算法中使用選擇法排序,比較次數較多,但資料交換(移動)較少.若用其它排序方法,雖可減少比較次數,但資料移動會增多.演算法時間複雜度為o(n2).

5、因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。

void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度

//沿左分枝向下

if(tag[top]==1) //當前結點的右分枝已遍歷

//保留當前最長路徑到l棧，記住最高棧頂指標，退棧

} else if(top>0) //沿右子分枝向下

}//while(p!=null||top>0)

}//結束longestpath

6、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。