Ⅰ. 考試內容及考試要求
一、數(shù)據(jù)結構的基本概念、算法及算法分析方法
【考試內容】1、 合適的數(shù)據(jù)結構在解決實際應用問題中的關鍵性；學習《數(shù)據(jù)結構》的意義。
2、 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構等基本概念。
3、 數(shù)據(jù)結構的四種邏輯結構和兩種存儲結構表示方法。
4、 抽象數(shù)據(jù)類型的表示和實現(xiàn)。
5、 算法的五個特點。
6、 算法、算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。
7、 算法描述和算法分析的方法，對于一般算法能分析出時間復雜度。
【考試要求】
1、數(shù)據(jù)結構的基本概念和術語（識記）
（1）數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結構等基本概念。
（2）數(shù)據(jù)結構的邏輯結構、存儲結構及數(shù)據(jù)操作的含義及其相互關系。
（3）數(shù)據(jù)結構的四種邏輯結構和兩種常用的存儲表示方法。
2、數(shù)據(jù)結構在軟件系統(tǒng)中的作用（識記）。
（1）數(shù)據(jù)結構在各種軟件系統(tǒng)中所起的作用。
（2）選擇合適的數(shù)據(jù)結構是解決應用問題的關鍵步驟。
3、算法的描述和分析（領會）
（1）算法、算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。
（2）算法的時間復雜度不僅僅依賴于問題的規(guī)模，也取決于輸入實例的初始狀態(tài)。
（3）算法描述和算法分析的方法，對于一般算法能分析出時間復雜度。
（4）O符號的含義及求解漸進時間復雜度的方法。
二、線性表
【考試內容】1、線性表的類型定義。
2、順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析。
3、鏈式表示和實現(xiàn)，單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。
4、單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法及其時間復雜度。
5、循環(huán)鏈表及雙向鏈表的定義和相關算法。
6、順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優(yōu)的時空性能。
【考試要求】
1、線性表的邏輯結構（識記）
（1）線性表的邏輯結構特征。
（2）線性表上定義的基本操作，并能利用基本操作構造出較復雜的操作。
2．線性表的順序存儲結構——順序表（綜合應用）
（1） 順序表的含義及特點，即順序表如何反映線性表中元素之間的邏輯關系。
（2）順序表上的插入、刪除操作及其平均時間性能分析。
（3）利用順序表設計算法解決簡單的應用問題。
3．線性表的鏈式存儲結構——鏈表（綜合應用）
（1）鏈表如何表示線性表中元素之間的邏輯關系。
（2）鏈表中頭指針和頭結點的使用。
（3）單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。
（4）單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法，并分析其時間復雜度。
（5）單循環(huán)鏈表以及單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。
（6）雙鏈表的定義及其相關的算法。
（7）利用鏈表設計算法解決簡單的應用問題。
4、順序表和鏈表的比較（領會）
（1）順序表和鏈表的主要優(yōu)缺點。
（2）針對線性表上所需要執(zhí)行的主要操作，知道選擇順序表還是鏈表作為其存儲結構才能取得較優(yōu)的時空性能。
三、棧和隊列
【考試內容】1、棧的抽象數(shù)據(jù)類型的定義。
2、棧的表示和實現(xiàn)。
3、棧的簡單應用。
4、抽象數(shù)據(jù)類型隊列的定義。
5、隊列的鏈式表示和實現(xiàn)。
6、隊列的順序表示和實現(xiàn)。
【考試要求】
1、棧的邏輯結構、存儲結構及其相關算法（綜合應用）
（1）棧的邏輯結構特點，棧與線性表的異同。
