894程序設計

1、2011年北師大教育技術初試真題年北師大教育技術初試真題一、選擇題（12道5分）。1、有幾道讀程序題，C語言中的遞歸、數(shù)組指針、十六進制。2、用數(shù)組表示平衡二叉樹，廣義表表示的二叉樹然后后序遍歷這顆二叉樹。3、計算二分查找的平均查找長度，選擇正確的關于鏈表的程序。二、簡答題。（5道12分）1、平衡二叉樹插入一個數(shù)后的結構。2、快速排序一個序列。3、用堆排序一個序列。4、用靜態(tài)列表表示一個基數(shù)排列的分配和收集。5、讀一段漢諾塔程序，寫出結

2、果，4層遞歸。三、操作題（2道15分）。1、構造一顆哈弗曼樹，算出它的路徑長度。2、一個AOE網(wǎng)，填寫事件和活動的最早開始時間和最晚開始時間的表格，最后寫出關鍵路徑的頂點。題型：選擇題（12道）、簡答題（5道）、操作題（5道）選擇題每道題5分，簡單題每道題6分，操作題每道12分。1、選擇題考察的是C語言的基礎知識，比如數(shù)組指針；還考了數(shù)據(jù)結構中一些線性表的操作，有一個是問稀疏矩陣的稀疏因子，廣義表里面考了個選擇題。2、簡答題考察的是（1

3、）靜態(tài)鏈表存儲結構算法描述；（2）單鏈表的插入操作、刪除操作；（3）KMP算法的應用：next數(shù)組值推導；（4）哈夫曼樹；（5）快速排序。5給定權值｛8，12，4，5，26，16，9｝，構造一個哈夫曼樹，并計算其帶權路徑長度。四、編寫程序（15分）建立線形表，（a1a2a3….an）的單鏈表存儲，并實現(xiàn)其就地逆置為（anan1…a2.a1）。五、編寫程序（10分）在中序線索樹中，要找出Ｘ結點的前驅結點，請寫出相關函數(shù)定義。LtagLcD

4、ataRtagRc六、編寫算法（20分）已知有Ｎ個結點的無向圖，采用鄰接表結構存儲，要求對每個連通子圖中一個生成樹中的各條邊逐層輸出，邊的輸出格式為（kikj）。七、編寫算法（25分）1寫出建立二叉樹，二叉鏈表存儲結構的算法。（10分）2已知二叉樹采用二叉鏈表方式存放，要求對二叉樹從１開始進行連續(xù)編號，要求每個結點的編號大于其左右孩子的編號，同一結點的左右孩子中，左孩子編號小于右孩子編號。給出在二叉樹中結點的數(shù)據(jù)域部分填寫，實現(xiàn)如上要求