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

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

第一部分 考試說明

一、考試方法與考試時間

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

（2）答題時間：120分鐘

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

二、主要參考書目

嚴蔚敏.數(shù)據(jù)結構（C語言版）.清華大學出版社.

第二部分 考試范圍、考試內容及試卷結構

第一章 緒論

一、學習目的與要求

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

二、考核知識點與考核目標

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

理解：數(shù)據(jù)結構研究的內容

識記：數(shù)據(jù)結構的邏輯結構和物理結構

（二）算法分析（重點）

理解：算法的基本特征

識記：算法分析的方法

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

一、 學習目的與要求

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

二、考核知識點與考核目標

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

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

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

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

（三）棧，隊列（重點）

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

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

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

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

第六章 樹和二叉樹

一、學習目的與要求

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

二、考核知識點與考核目標

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

理解：樹的概念及特征

識記：二叉樹的定、義術語和基本邏輯結構特性；

識記：樹與二叉樹的相互轉換

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

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

（三）哈夫曼樹（重點）

理解：哈夫曼樹的特性

識記：哈夫曼樹的構造

第七章 圖

一、學習目的與要求

通過本章學習，掌握圖的基本概念，掌握圖的存儲結構，掌握圖的遍歷算法，了解并掌握圖的典型應用，如最小生成樹、拓撲排序、關鍵路徑、最短路徑等。

二、考核知識點與考核目標

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

理解：圖的邏輯結構

識記：圖的一些基本術語，基本特征

（二）圖的存儲結構，圖的遍歷算法（重點）

識記：理解并掌握圖的存儲結構；

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

（三）圖的典型應用（重點）

識記：最小生成樹，拓撲排序，最短路徑

第八章 查找

一、 學習目的與要求

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

二、考核知識點與考核目標

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

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

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

識記：二叉排序樹

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

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

第九章 排序

一、 學習目的與要求

通過本章學習，掌握幾種常見的排序算法

二、考核知識點與考核目標

（一）插入排序（重點）

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

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

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

（三）選擇排序（重點）

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

（三）其他排序（重點）

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

識記：能夠對各種排序算法進行分析比較

二、試卷結構

（一）、單項選擇題

1．數(shù)據(jù)的最小單位是（ ）。

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

（二）、分析題

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

（三）、求解題

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

（四）、補充程序題

1.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內容。

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;

____________;}

}

}

（五）、算法設計

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



編輯推薦：

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

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