2023年山東省資料總結高階

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

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

//沿左分枝向下

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

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

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

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

}//結束longestpath

2、證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。

29. ① 試找出滿足下列條件的二叉樹

1）先序序列與後序序列相同 2）中序序列與後序序列相同

3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同

3、設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查詢方法用二分查詢，要求計算出查詢關鍵字62時的比較次數並計算出查詢成功時的平均查詢長度。

4、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。

2023年山東省資料總結高階

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

2023年山東省資料總結高階

r i x 3 兩棵空二叉樹或僅有根結點的二叉樹相似 對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。int similar bitree p,q 判斷二叉樹p和q是否相似 結束similar 4 在有向圖g中，如果r到g中的每個結點都有路徑可達，則稱結點r為g的根結點。編寫乙個演算法完成下列功...

2023年山東省資料總結高階

1 define maxsize 棧空間容量 void inouts int s maxsize s是元素為整數的棧，本演算法進行入棧和退棧操作。else s top x x入棧。else 讀入的整數等於 1時退棧。else printf 出棧元素是 d n s top 演算法結 2 設有一組初始記...