894程序設(shè)計(jì)

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

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

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

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