2017華科軟件專業(yè)課分享

P灰灰 · 發(fā)表于 2017-7-9 20:50

本帖最后由 as3652553 于 2017-11-30 21:13 編輯

2017年華中科技大學(xué)887數(shù)據(jù)結(jié)構(gòu)與算法分析

一．名詞解釋（25分，1個(gè)5分）
1.1堆分配存儲(chǔ)表示
1.2完全圖
1.3樹(shù)的結(jié)點(diǎn)層次
1.4拓?fù)渑判?br /> 1.5時(shí)間復(fù)雜度

二．選擇題（25分，1個(gè)5分）
2.1 折半查找的平均時(shí)間復(fù)雜度是（B）
A. 1                                                       B.logn
C. n                                                       D. n

2.2
int frog｛
if(n==0)
return 1;
else
return （n+frog（n-1）/2）;
｝
上述算法時(shí)間復(fù)雜度是多少（B）
A. logn                                              B.n
C.  nlogn                                     D. (n)`2

2.3一個(gè)算法的時(shí)間復(fù)雜度與什么有關(guān)（D）
A. 存儲(chǔ)器的大小                               B. 編程語(yǔ)言
C. 計(jì)算機(jī)的主頻                               D. 循環(huán)執(zhí)行的次數(shù)

2.4具有20個(gè)樹(shù)葉的二叉樹(shù)中只有1個(gè)孩子的結(jié)點(diǎn)個(gè)數(shù)是11，則這個(gè)二叉樹(shù)總的結(jié)點(diǎn)個(gè)數(shù)是多少（A）
A. 50                                              B.49
C. 51                                              D.52

2.5下列關(guān)于隊(duì)列說(shuō)話不正確的是（B）
A. 先進(jìn)先出                                     B.后進(jìn)先出
C. 插入刪除只能在端點(diǎn)             D. 插入刪除在不同點(diǎn)進(jìn)行

三．簡(jiǎn)答題（60分）

3.1｛1，2，3，4，5，6，7，8｝利用數(shù)組建成一個(gè)最大堆并使用堆排序?qū)⑵渑判蛭ㄒ粋€(gè)升序數(shù)組。要求畫(huà)出所有中間過(guò)程。

3.2 先序?yàn)?ABDFGHCE 中序 BFDHGACE 畫(huà)出該樹(shù)

3.3給出一個(gè)鄰接矩陣畫(huà)出克魯斯卡爾算法具體過(guò)程
00  4 4 2 1
4 00  1  00 2
4 1  00 5 3
2 00  5  00 4
1 2 3 4 00

3.4 13個(gè)權(quán)值為5， 18，12，13，4，6，7，9，28，16，20，30，2
給出哈夫曼樹(shù)并設(shè)計(jì)編碼

3.5給出輸出結(jié)果并說(shuō)明函數(shù)功能。
void Print(int w)
{
int i;
if (w!=0)
{
Print(w-1);
for(i=1:i<=w;i++)
printf(“%d, ”,w);
printf(“/n”);
}
}

四．算法設(shè)計(jì)（40分）（編碼困難可以寫(xiě)偽代碼，會(huì)適當(dāng)扣分）
4.1求二叉樹(shù)所有具有兩個(gè)子女的結(jié)點(diǎn)個(gè)數(shù)，如果根節(jié)點(diǎn)為空，則返回0。
typedef struct Bintreenode{
int data；
struct Bintreenode *right；
struct Bintreenode *left；
} *Bintreenode；
4.2 一個(gè)長(zhǎng)度為n數(shù)組由負(fù)數(shù) 0 正數(shù)組成，編寫(xiě)函數(shù)，將其重新排序?yàn)榍懊娑际秦?fù)數(shù)，中間都是0  .后面都是正數(shù)的結(jié)構(gòu)。要求時(shí)間復(fù)雜度為n。
關(guān)于2018華科軟院887復(fù)習(xí)八套卷
本套試題針對(duì)2018華科軟件887數(shù)據(jù)結(jié)構(gòu)與算法分析而制，內(nèi)容與往年大綱一致，鑒于15-17年題型難度趨于穩(wěn)定，本套卷將嚴(yán)格按照往年出題風(fēng)格，希望各位考生能考到理想的成績(jī)。

附2015-2017考研真題題型。
1名詞解釋（25分，1個(gè)5分）
5個(gè)名詞留一大段空白給出解釋。
例：完全圖（2017）

答：若一個(gè)圖的每一對(duì)不同頂點(diǎn)恰有一條邊相連，則稱為完全圖。完全圖是每對(duì)頂點(diǎn)之間都恰連有一條邊的簡(jiǎn)單圖。n個(gè)端點(diǎn)的完全圖有n個(gè)端點(diǎn)及n(n ? 1) / 2條邊。

范圍：數(shù)據(jù)結(jié)構(gòu)的概念，時(shí)間復(fù)雜度，線性表，棧隊(duì)列，樹(shù)，圖，排序算法，查找。
將總結(jié)出的算法解釋背誦即可。

2.選擇題（25分，1個(gè)5分）
選擇題中經(jīng)常出現(xiàn)關(guān)于時(shí)間復(fù)雜度的分析。（17年考了3道）
2.1 折半查找的平均時(shí)間復(fù)雜度是（B）
A. 1                                                       B.logn
C. n                                                       D. n

2.2
int frog｛
if(n==0)
return 1;
else
return （n+frog（n-1）/2）;
｝
上述算法時(shí)間復(fù)雜度是多少（B）
A. logn                                              B.n
C.  nlogn                                        D. (n)`2

2.3一個(gè)算法的時(shí)間復(fù)雜度與什么有關(guān)（D）
A. 存儲(chǔ)器的大小                               B. 編程語(yǔ)言
C. 計(jì)算機(jī)的主頻                               D. 循環(huán)執(zhí)行的次數(shù)
堆棧的概念，樹(shù)圖中的計(jì)算題。

3.簡(jiǎn)答題（60分）

5道題
樹(shù)的二道。（前中得后，中后得前，后序表達(dá)式，最優(yōu)二叉樹(shù)）
圖的一道。（給出圖，寫(xiě)出過(guò)程）普里姆，克魯斯卡爾，迪杰斯特拉
排序一道。近幾年經(jīng)?？缄P(guān)于堆排序得知識(shí)。
給出代碼，寫(xiě)出運(yùn)行結(jié)果。（一道）

4.算法設(shè)計(jì)（40分）（編碼困難可以寫(xiě)偽代碼，會(huì)適當(dāng)扣分）

基本上每年2道，一道線性表，一道樹(shù)的，圖的代碼沒(méi)考過(guò)。
例：求出鏈表L的倒數(shù)第N個(gè)結(jié)點(diǎn)的data。
先別急的寫(xiě)代碼
首先用注釋的形式寫(xiě)出代碼的大概過(guò)程

/*輸入：鏈表L，結(jié)點(diǎn)K
定義兩個(gè)結(jié)點(diǎn)指針p1，p2指向該鏈表的頭結(jié)點(diǎn)，利用p1遍歷整個(gè)鏈表，記下長(zhǎng)度n
然后再利用p2往后遍歷n-k個(gè)結(jié)點(diǎn)
輸出：結(jié)點(diǎn)K的data
異常：沒(méi)有第K個(gè)結(jié)點(diǎn)，輸入為空指針*/

之后再是代碼

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
｛
。。。。
｝
寫(xiě)代碼需要充分考慮所有的測(cè)試用例