考研論壇
標(biāo)題: 華中科技大學(xué)軟件學(xué)院2011年研究生入學(xué)考試試題 [打印本頁(yè)]
作者: duck0135 時(shí)間: 2011-2-14 16:34
標(biāo)題: 華中科技大學(xué)軟件學(xué)院2011年研究生入學(xué)考試試題
華中科技大學(xué)軟件學(xué)院2011年研究生入學(xué)考試試題
數(shù)據(jù)結(jié)構(gòu)與算法
一.術(shù)語(yǔ)解釋：（25'）
1 線性表
2 樹的結(jié)點(diǎn)的層次
3 排序
4 完全圖
5 最小生成樹
二.單項(xiàng)選擇：（25'）
1 在數(shù)組{1，2，3，4，5，6，7，8，9，10}中折半查找5，需要的比較次數(shù)是（）
A 1 B 2 C 3 D 4
2 假定問題規(guī)模為N時(shí)，某遞歸算法的時(shí)間復(fù)雜度記為T（N），已知T(1)=1，
T(N)=2T(N/2)+N/2，用O表示的時(shí)間復(fù)雜度為（）
A O(N) B O(NlogN) C O(N2) D O(N2logN)
3 一棵二叉樹的先序遍歷輸出為ABCDEFGH，中序遍歷為CBEDAFHG，則其先序遍歷輸出為（）【此題的確問的是先序遍歷】
A CBDEAFGH B CBEDAFHG
C BCEDFAHG D 以上都不對(duì)
4 棧和隊(duì)列的共同點(diǎn)是（）
A 先進(jìn)先出 B 后進(jìn)先出
C 插入刪除只能在端點(diǎn)進(jìn)行 D 沒有共同點(diǎn)
5 起泡排序的時(shí)間復(fù)雜度是（C）【此題原試卷將答案附上了】
A O(N) B O(NlogN) C O(N2) D O(N2logN)
三.簡(jiǎn)答（60'）
1 用一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧，盡可能利用存儲(chǔ)空間，寫出兩個(gè)棧的插入、刪除操作算法。
2 已知一組關(guān)鍵字為{27、25、23、37、35、33、77、75、73、97、95、93、103}，按哈希函數(shù)H(key)=key Mod 11（表長(zhǎng)11），用連地址法處理沖突，畫出哈希表。
3 一個(gè)遞歸函數(shù)具有如下形式
Void func(int n)
{
if(n>0)
{
func(n/2);
printf("d%",n*n);
func(n/2);
}
return;
}
請(qǐng)依次寫出fun(1)，fun(2)，fun(3)，fun(5)執(zhí)行的結(jié)果，其時(shí)間復(fù)雜度為多少？
4 一個(gè)通信網(wǎng)絡(luò)中共有九中字符，其概率分別為0.14、0.23、0.15、0.03、0.18、0.1、0.02、0.11、0.04，畫出相應(yīng)的赫夫曼樹來設(shè)計(jì)其赫夫曼編碼。
5 V?→V?→V?→∧； V?→V?→V5→∧ ； V3→V5→V6→∧ ； V4→∧；
V5 →V7 →V8 →∧ ； V6→V8→∧； V7 →∧ ； V8→V9→∧ ； V9→∧，
畫出這個(gè)邏輯結(jié)構(gòu)的圖示，分別寫出從V?出發(fā)的深度優(yōu)先和廣度優(yōu)先搜索序列。
四.應(yīng)用編程題：（40'）
1 在一個(gè)整形數(shù)組a中既有負(fù)數(shù)又有正數(shù)，編寫一個(gè)算法將a中所有負(fù)數(shù)移到整數(shù)之前， 要求其時(shí)間復(fù)雜度為O(n)，n為數(shù)組長(zhǎng)度，并且只使用常數(shù)個(gè)輔助空間。
例如：a[ ]={1,2,3,4,-1,1,-2,-1,-4}執(zhí)行算法后的輸出為a[ ]={-4,-1,-2,-1,1,4,3,2,1}
2 編寫一個(gè)C函數(shù)，輸入一個(gè)二叉樹的根節(jié)點(diǎn)，返回這棵樹中所有值大于0的節(jié)點(diǎn)值之和，如果根為空，返回0。
二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)應(yīng)的C語(yǔ)言的結(jié)點(diǎn)類型定義如下：
typedef struct node{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTree;
說明：1.本試題為回憶版試題，某些題目的數(shù)值或者語(yǔ)言表述可能與原版不一致；
2.本試題僅供大家學(xué)習(xí)交流使用，嚴(yán)禁用于各類商業(yè)用途。
作者: hotsummer86 時(shí)間: 2011-2-14 21:57
專業(yè)課比中科大簡(jiǎn)單。。。最起碼知識(shí)點(diǎn)少很多很多。。
作者: magicyang112 時(shí)間: 2011-2-14 22:24
編程題出題點(diǎn)和北航的好像啊。。。我囧 不過這題量最多只有北航的70%吧。。。。3小時(shí)？。。。。
中科的數(shù)據(jù)結(jié)構(gòu)確實(shí)很難 很多很生的出題點(diǎn)。。。
作者: zzfxjk 時(shí)間: 2011-2-15 22:37
LZ.計(jì)算機(jī)不是全國(guó)統(tǒng)考啊!是不是有些院校還是自主考試啊?這是怎么回事啊?12年的求教....
作者: ffwwd456 時(shí)間: 2011-2-16 18:02
雖然我不是這個(gè)專業(yè)的........這個(gè)很像二級(jí)里的公共基礎(chǔ)[qq:13]
作者: ewlwl 時(shí)間: 2011-2-16 18:14
想了解華科軟院的同學(xué)可以論壇短信我，愿意回答各種有關(guān)問題[qq:20]
作者: rocdevil 時(shí)間: 2011-4-6 14:42
謝謝
作者: 沫小蝸 時(shí)間: 2011-9-22 23:21
分享哈皮
| 歡迎光臨 考研論壇 (http://www.5522pp.com/) |
Powered by Discuz! X3.2 |