|
華中科技大學軟件學院2011年研究生入學考試試題 數據結構與算法 一.術語解釋：（25'） 1 線性表 2 樹的結點的層次 3 排序 4 完全圖 5 最小生成樹 二.單項選擇：（25'） 1 在數組{1，2，3，4，5，6，7，8，9，10}中折半查找5，需要的比較次數是（） A 1 B 2 C 3 D 4 2 假定問題規模為N時，某遞歸算法的時間復雜度記為T（N），已知T(1)=1， T(N)=2T(N/2)+N/2，用O表示的時間復雜度為（） A O(N) B O(NlogN) C O(N2) D O(N2logN) 3 一棵二叉樹的先序遍歷輸出為ABCDEFGH，中序遍歷為CBEDAFHG，則其先序遍歷輸出為（）【此題的確問的是先序遍歷】 A CBDEAFGH B CBEDAFHG C BCEDFAHG D 以上都不對 4 棧和隊列的共同點是（） A 先進先出 B 后進先出 C 插入刪除只能在端點進行 D 沒有共同點 5 起泡排序的時間復雜度是（C）【此題原試卷將答案附上了】 A O(N) B O(NlogN) C O(N2) D O(N2logN) 三.簡答（60'） 1 用一個數組實現兩個棧，盡可能利用存儲空間，寫出兩個棧的插入、刪除操作算法。 2 已知一組關鍵字為{27、25、23、37、35、33、77、75、73、97、95、93、103}，按哈希函數H(key)=key Mod 11（表長11），用連地址法處理沖突，畫出哈希表。 3 一個遞歸函數具有如下形式 Void func(int n) { if(n>0) { func(n/2); printf("d%",n*n); func(n/2); } return; } 請依次寫出fun(1)，fun(2)，fun(3)，fun(5)執行的結果，其時間復雜度為多少？ 4 一個通信網絡中共有九中字符，其概率分別為0.14、0.23、0.15、0.03、0.18、0.1、0.02、0.11、0.04，畫出相應的赫夫曼樹來設計其赫夫曼編碼。
5 V?→V?→V?→∧； V?→V?→V5→∧ ； V3→V5→V6→∧ ； V4→∧； V5 →V7 →V8 →∧ ； V6→V8→∧； V7 →∧ ； V8→V9→∧ ； V9→∧， 畫出這個邏輯結構的圖示，分別寫出從V?出發的深度優先和廣度優先搜索序列。 四.應用編程題：（40'） 1 在一個整形數組a中既有負數又有正數，編寫一個算法將a中所有負數移到整數之前， 要求其時間復雜度為O(n)，n為數組長度，并且只使用常數個輔助空間。 例如：a[ ]={1,2,3,4,-1,1,-2,-1,-4}執行算法后的輸出為a[ ]={-4,-1,-2,-1,1,4,3,2,1} 2 編寫一個C函數，輸入一個二叉樹的根節點，返回這棵樹中所有值大于0的節點值之和，如果根為空，返回0。
二叉樹的鏈式存儲結構對應的C語言的結點類型定義如下：
typedef struct node{
ElemType data; struct node *lchild; struct node *rchild;
}BTree;
說明：1.本試題為回憶版試題，某些題目的數值或者語言表述可能與原版不一致；
2.本試題僅供大家學習交流使用，嚴禁用于各類商業用途。
| 
發表于 2011-2-14 16:34
收藏
分享
支持
反對
