2018年文華學(xué)院普通專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

文華學(xué)院普通專升本2018年《數(shù)據(jù)結(jié)構(gòu)》考試大綱

第一部分 考試說(shuō)明

一、考試方法與考試時(shí)間

（1）答卷方式：閉卷，筆試

（2）答題時(shí)間：120分鐘

（3）題型：基本概念：約30%；
求解題：約60%；
算法設(shè)計(jì)：約10%

二、主要參考書(shū)目

嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.清華大學(xué)出版社.

第二部分 考試范圍、考試內(nèi)容及試卷結(jié)構(gòu)

第一章 緒論

一、學(xué)習(xí)目的與要求

通過(guò)本章學(xué)習(xí)，理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語(yǔ)，掌握算法的分析方法

二、考核知識(shí)點(diǎn)與考核目標(biāo)

（一）基本概念（次重點(diǎn)）

理解：數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容

識(shí)記：數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

（二）算法分析（重點(diǎn)）

理解：算法的基本特征

識(shí)記：算法分析的方法

第二三四五章 線性表，棧和隊(duì)列，串，數(shù)組

一、 學(xué)習(xí)目的與要求

通過(guò)本章學(xué)習(xí)，熟悉并掌握線性表、棧、隊(duì)列、串、數(shù)組的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的基本運(yùn)算；

二、考核知識(shí)點(diǎn)與考核目標(biāo)

（一）線性表、棧、隊(duì)列、串、數(shù)組的特征（一般）

識(shí)記：理解并掌握線性表、棧、隊(duì)列、串、數(shù)組的基本特點(diǎn)

（二）線性表的存儲(chǔ)方法和基本操作（重點(diǎn)）

識(shí)記：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，插入和刪除一些操作的實(shí)現(xiàn)

（三）棧，隊(duì)列（重點(diǎn)）

識(shí)記：棧的實(shí)現(xiàn)，循環(huán)隊(duì)列的實(shí)現(xiàn)，遞歸的應(yīng)用，懂得利用棧和隊(duì)列的思想實(shí)現(xiàn)算法

（四）串和數(shù)組（次重點(diǎn)）

理解：串和數(shù)組的特征

識(shí)記：串的簡(jiǎn)單模式匹配算法，數(shù)組存儲(chǔ)地址的運(yùn)算，稀疏矩陣的三元組表示法

第六章 樹(shù)和二叉樹(shù)

一、學(xué)習(xí)目的與要求

通過(guò)本章學(xué)習(xí)，了解樹(shù)和二叉樹(shù)的概念，理解二叉樹(shù)的表示方法，掌握二叉樹(shù)的存儲(chǔ)方法和遍歷算法的實(shí)現(xiàn)，掌握樹(shù)與二叉樹(shù)的相互轉(zhuǎn)換及哈夫曼樹(shù)的構(gòu)造。

二、考核知識(shí)點(diǎn)與考核目標(biāo)

（一）樹(shù)和二叉樹(shù)的概念（次重點(diǎn)）

理解：樹(shù)的概念及特征

識(shí)記：二叉樹(shù)的定、義術(shù)語(yǔ)和基本邏輯結(jié)構(gòu)特性；

識(shí)記：樹(shù)與二叉樹(shù)的相互轉(zhuǎn)換

（二）二叉樹(shù)的存儲(chǔ)和遍歷算法（重點(diǎn)）

識(shí)記：理解二叉樹(shù)的遍歷算法思想，掌握遞歸和非遞歸遍歷算法實(shí)現(xiàn)

（三）哈夫曼樹(shù)（重點(diǎn)）

理解：哈夫曼樹(shù)的特性

識(shí)記：哈夫曼樹(shù)的構(gòu)造

第七章 圖

一、學(xué)習(xí)目的與要求

通過(guò)本章學(xué)習(xí)，掌握?qǐng)D的基本概念，掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)，掌握?qǐng)D的遍歷算法，了解并掌握?qǐng)D的典型應(yīng)用，如最小生成樹(shù)、拓?fù)渑判?、關(guān)鍵路徑、最短路徑等。

二、考核知識(shí)點(diǎn)與考核目標(biāo)

（一）圖的概念（次重點(diǎn)）

理解：圖的邏輯結(jié)構(gòu)

識(shí)記：圖的一些基本術(shù)語(yǔ)，基本特征

（二）圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷算法（重點(diǎn)）

識(shí)記：理解并掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)；

識(shí)記：掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷算法；

（三）圖的典型應(yīng)用（重點(diǎn)）

識(shí)記：最小生成樹(shù)，拓?fù)渑判?，最短路?/span>

第八章 查找

一、 學(xué)習(xí)目的與要求

通過(guò)本章學(xué)習(xí)，理解靜態(tài)查找表和動(dòng)態(tài)查找表的特征，掌握常見(jiàn)幾種查找算法。

二、考核知識(shí)點(diǎn)與考核目標(biāo)

（一）靜態(tài)查找（重點(diǎn)）

識(shí)記：順序查找、折半查找、分塊查找；

（二）動(dòng)態(tài)查找表（重點(diǎn)）

識(shí)記：二叉排序樹(shù)

（三）哈希查找表（重點(diǎn)）

識(shí)記：掌握哈希表的概念和查找方法和哈希函數(shù)的構(gòu)造方法，解決沖突的基本方法

第九章 排序

一、 學(xué)習(xí)目的與要求

通過(guò)本章學(xué)習(xí)，掌握幾種常見(jiàn)的排序算法

二、考核知識(shí)點(diǎn)與考核目標(biāo)

（一）插入排序（重點(diǎn)）

識(shí)記：直接插入排序，希爾排序

（二）交換思想的排序（重點(diǎn)）

識(shí)記：冒泡排序，快速排序

（三）選擇排序（重點(diǎn)）

識(shí)記：簡(jiǎn)單選擇排序、堆排序；

（三）其他排序（重點(diǎn)）

識(shí)記：掌握其它排序算法如：歸并排序、基數(shù)排序；

識(shí)記：能夠?qū)Ω鞣N排序算法進(jìn)行分析比較

二、試卷結(jié)構(gòu)

（一）、單項(xiàng)選擇題

1．?dāng)?shù)據(jù)的最小單位是（ ）。

(A) 數(shù)據(jù)項(xiàng) (B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量

（二）、分析題

設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCDEFGHIJK，前序遍歷序列為EBADCFHGIKJ，要求畫(huà)出該二叉樹(shù)。

（三）、求解題

1．設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹(shù)，并求其哈夫曼編碼。

（四）、補(bǔ)充程序題

1.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。

typedefstruct node

{ intdata;

structnode *next;

}lklist;

void lklist create(_____________ *&head )

{

for(i=1;i<=n;i++)

{

p=(lklist*)malloc(sizeof(lklist));

scanf(“%d”,&(p->data));p->next=null;

if(i==1)

head=q=p;

else

{q->next=p;

____________;}

}

}

（五）、算法設(shè)計(jì)

給出一個(gè)高效算法，求出1,3,6………..n這串?dāng)?shù)中大于M小于N的數(shù)。（M和N是給定的數(shù)）



編輯推薦：

文華學(xué)院普通專升本2018年各專業(yè)科目考試大綱匯總

文華學(xué)院普通專升本2018年招生簡(jiǎn)章專業(yè)及報(bào)考流程