一、考查目標
考查學生掌握數值計算問題在計算機中進行處理的基本原理和方法，掌握常用數據結構的基本概念及其不同的實現方法；在技能方面，能夠在不同存儲結構上實現不同邏輯結構的運算，并能解決相關的實際問題，對算法設計的方式和技巧有所體會，有較好的分析處理數據的能力。
二、考試形式與試卷結構
（一）試卷滿分及考試時間
滿分為100分，考試時間為2小時。
（二）答題方式
閉卷、筆試。
（三）試卷內容結構
內容結構為各部分知識點在試卷中所占的比例。
1 數據結構基本概念（10%左右）
2 線性結構（25%左右）
3 樹狀結構（25%左右）
4 圖（15%左右）
5 查找（10%左右）
6 內部排序（15%左右）
（四）試卷題型結構
客觀題：選擇題20%左右，判斷題20%左右；
算法設計30%左右；
算法綜合應用30%左右
三、考查內容
（一）緒論
1 掌握數據、數據元素、數據對象、數據結構、存儲結構和數據類型的概念和術語的含義；
2 理解算法五要素的確切含義；
3 掌握算法設計的基本要求以及計算語句頻度和估算算法時間復雜度的方法。
（二）線性表
1 掌握線性表的邏輯結構特性是數據元素之間存在著的線性關系；
2 熟練掌握線性表的順序存儲結構和鏈式存儲結構的描述方法及循環鏈表, 雙向鏈表的特點；
3 熟練掌握線性表在順序存儲結構和各種鏈表結構上的查找、插入和刪除的算法；
4 能夠從時間和空間復雜度的角度綜合比較兩種存儲結構的不同特點及其適用的場合。
（三）棧和隊列
1 熟練掌握棧和隊列的結構特性----操作受限的線性表；
2 熟練掌握棧類型在兩種存儲結構表示時的基本操作實現方法；
3 熟練掌握循環隊列和鏈隊列的基本操作實現算法；
4 熟練掌握棧和隊列的滿和空的條件和它們的描述方法；
5 熟悉棧和隊列的典型應用，如：數制轉換、表達式求值等。
（四）串
1 掌握串的結構特性----數據元素為字符的線性表；
2 熟悉串的七種基本操作;
（五）數組
1 掌握高維數組存在一維數組中的兩種存儲表示方法及以行為主(低下標優先)的存儲結構中的地址計算, 特別注意下標是從0開始或從1開始；
2 掌握對特殊矩陣(對稱矩陣,下三角矩陣等) 進行壓縮存儲時的下標變換公式；
3 了解稀疏矩陣的三元組壓縮存儲表示方法及適用范圍。
（六） 樹和二叉樹
1 熟悉樹的基本定義及其相關的術語的含義（如孩子、兄弟,深度、度等概念）；
2 熟練掌握二叉樹的結構特性，了解相應的證明方法, 理解常見的二叉樹（如滿二叉樹，完全二叉樹，Huffman樹，平衡二叉樹，排序二叉樹和判定樹）有關理論結論；
3 熟悉二叉樹的二叉鏈和線索二叉樹存儲結構特點及適用范圍；
4 熟悉三種遍歷二叉樹的遞歸算法（先序, 中序和后序）；
5 掌握二叉樹線索化的實質及線索化的過程；
6 掌握樹和森林與二叉樹的轉換, 及其各自遍歷的對應關系；
7 了解實現樹的各種操作的算法；
8 掌握最優樹的特性，掌握Huffman樹及其應用。
（七） 圖
1 掌握圖的定義和術語（如頂點，邊，度及其相互之間的數量關系,連通性與生成樹等）；
2 掌握圖的兩種存儲結構：數組表示法（鄰接矩陣）、鄰接表，了解實際問題的求解效率與采取何種存儲結構和算法有密切關系；
3 掌握圖的兩種遍歷策略：深度優先搜索和廣度優先搜索；圖的遍歷和樹的遍歷之間的類似與差異；
4 熟悉圖的最小生成樹的生成方法（Prim方法和Kruskal方法）；
（八）查找
1 熟練掌握順序表和有序表的查找方法（順序查找和二分查找）；
2 掌握查找效率的計算方法-----平均查找長度；
3 熟練掌握二叉排序樹的構造和查找方法；
4 了解平衡二叉樹的維護平衡的方法。
（九）內部排序
1 掌握排序的定義和各種排序方法的基本思想及其特點；
2 了解各種排序方法的排序過程及其依據的原則，基于“關鍵字間的比較”進行排序的方法可以分為插入排序、交換排序、選擇排序、歸并排序和基數排序；
3 熟練掌握快速排序和堆排序等方法的實例排序過程；
4 能夠進行各種排序方法的時間復雜性(平均情況與最壞情況)估計或分析；
5 一般了解排序方法“穩定”的含義。
四、考試用具說明
黑色筆答題，無需攜帶計算器、直尺、三角板、量角器、圓規等特殊用具。
點擊查看：同等學力加試數據結構
原文標題：2018年信息學院碩士研究生招生考試復試大綱
原文鏈接：http://grs.sjzu.edu.cn/info/1020/1994.htm
