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

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

第一部分 考試說明

一、考試方法與考試時間

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

（2）答題時間：120分鐘

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

二、主要參考書目

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

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

第一章 緒論

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

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

二、考核知識點與考核目標(biāo)

（一）基本概念（次重點）

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

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

（二）算法分析（重點）

理解：算法的基本特征

識記：算法分析的方法

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

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

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

二、考核知識點與考核目標(biāo)

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

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

（二）線性表的存儲方法和基本操作（重點）

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

（三）棧，隊列（重點）

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

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

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

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

第六章 樹和二叉樹

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

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

二、考核知識點與考核目標(biāo)

（一）樹和二叉樹的概念（次重點）

理解：樹的概念及特征

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

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

（二）二叉樹的存儲和遍歷算法（重點）

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

（三）哈夫曼樹（重點）

理解：哈夫曼樹的特性

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

第七章 圖

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

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

二、考核知識點與考核目標(biāo)

（一）圖的概念（次重點）

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

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

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

識記：理解并掌握圖的存儲結(jié)構(gòu)；

識記：掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法；

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

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

第八章 查找

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

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

二、考核知識點與考核目標(biāo)

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

識記：順序查找、折半查找、分塊查找；

（二）動態(tài)查找表（重點）

識記：二叉排序樹

（三）哈希查找表（重點）

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

第九章 排序

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

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

二、考核知識點與考核目標(biāo)

（一）插入排序（重點）

識記：直接插入排序，希爾排序

（二）交換思想的排序（重點）

識記：冒泡排序，快速排序

（三）選擇排序（重點）

識記：簡單選擇排序、堆排序；

（三）其他排序（重點）

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

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

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

（一）、單項選擇題

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

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

（二）、分析題

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

（三）、求解題

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

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

1.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(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è)計

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



編輯推薦：

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

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