數據結構與程序設計考試大綱
江蘇自動化研究所碩士研究生入學考試
《數據結構與程序設計》考試大綱
一、命題范圍及考查的知識點
（一）、數據結構部分
1、概述
（1）數據的邏輯結構與存儲結構的基本概念；
（2）算法的定義、基本性質以及算法分析的基本概念，包括采用大O形式表示時間或空間復雜度。
2、線性表
（1）線性關系、線性表的定義，線性表的基本操作；
（2）線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理；
(3)在以上兩種存儲結構的基礎上對線性表實施的基本操作，包括順序表的插入和刪除、鏈表的建立、插入和刪除、檢索等操作對應的算法設計(含遞歸算法的設計)。
3、堆棧與隊列
(1)堆棧與隊列(含循環隊列)的基本概念、基本操作；
(2)堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理；
(3)在不同存儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作。
4、樹與二叉樹
(1)樹與二叉樹的基本概念，基本特征、名詞術語；
(2)完全二叉樹、滿二叉樹的概念、二叉樹的基本性質；
(3)二叉樹的順序存儲結構與二叉鏈表存儲結構的構造原理、二叉樹的前序遍歷、中序遍歷、后序遍歷和按層次遍歷算法(重點為非遞歸算法)以及利用遍歷解決有關二叉樹的其它操作；
(4)線索二叉樹的基本概念以及構造原理；
(5)二叉排序樹的基本概念、建立(插入)和查找，在二叉排序樹中查找結點的平均查找長度ASL。
5、圖
(1)圖的基本概念、名詞術語；
(2)鄰接矩陣存儲方法和鄰接表存儲方法的基本構造原理與特點；
(3)圖的深度優先搜索和廣度優先搜索的過程，圖的遍歷的基本作用；
(4)最小生成樹及最短路徑的特點、求解過程，拓撲排序及其目的。
6、文件及查找
(1)順序查找法、折半查找法以及查找過程對應的“判定樹”的構造；
(2)索引文件的基本概念；
(3)B-樹與B+樹的構造以及構造上異同，B-樹的插入和查找；
(4)散列文件的特點，散列函數和散列沖突的概念，處理散列沖突的方法以及散列文件的查找。
7、內排序
插入排序、選擇排序、泡排序、快速排序、堆積排序(大頂堆積)和二路歸并排序法等排序方法的排序原理、規律和特點。
（二）、C語言程序設計部分
1、C語言基本知識
（1）C語言的特點以及C語言程序的組成；
（2）數據類型，包括整型、實型、字符型等常量與變量和變量的賦值；用typedef定義類型；
（3）各種類型數據之間的混合運算；
（4）各類運算符的運算規則和優先級；條件運算符；
（5）算術表達式、關系表達式和邏輯表達式，逗號運算符和逗號表達式，表達式sizeof的含義。
2、語句
（1）賦值語句(含條件賦值語句)、條件語句(含if、if-else、switch)、循環語句(含while、do-while、for語句，包括循環嵌套和break語句)；
（2）輸入/輸出語句，包括整型、實型、字符型(含字符串)等類型數據的格式輸入函數scanf和格式輸出函數printf。
3、數組
（1）一維數組與二維數組的定義，數組元素的引用，數組的初始化；
（2）字符數組的定義，字符數組的初始化，字符數組的引用，字符數組的輸入與輸出，字符串和字符串處理函數。
4、函數
（1）函數的定義，函數參數(形參和實參)與函數的返回值；
（2）函數的調用，包括函數的嵌套調用和遞歸函數的遞歸調用；
（3）命令行參數的概念（帶參數的主函數）。
5、宏定義
（1）帶參數的宏定義；
（2）包含文件的處理。
6、指針
（1）指針的概念，變量的指針與指向變量的指針變量，包括定義、引用以及指針變量作為函數參數；
（2）數組的指針，包括指向數組的指針變量的定義與賦值、通過指針引用數組元素、數組名作為函數參數；
（3）字符串的指針與指向字符串的指針變量。
7、結構體
（1）結構體的基本概念和特點，結構體的初始化與引用；
（2）結構體數組。
8、文件
（1）文本文件的基本概念，文本文件的類型指針FILE以及文本文件的使用方式；
（2）文本文件的打開(fopen函數)、文本文件的關閉(fclose函數)；
（3）文本文件的狀態，包括feof函數和ferror函數；
（4）文本文件的讀寫，包括fputc函數和fgetc函數、fgets函數和fputs函數等；
（5）文本文件的輸入函數fscanf和輸出函數fprintf。
二、考試說明
1、總分滿分：150分
2、考試時間：3小時
3、考試方式：筆試
4、考試題型：
填空題（20分）
選擇題（20分）
分析計算題（30分）
簡答題（30分）
綜合應用編程題（50分）
5、數據結構和C語言程序設計分別占75分。
三、主要參考書
1、《數據結構》C語言版） 嚴蔚敏，清華大學出版社，2007年；
2、《C程序設計》（第四版） 譚浩強，清華大學出版社2010年；