2017年遼寧工程技術大學數據結構和軟件工程考研初試大綱

考研專業課大綱來源：中國考研網 2016-11-28　相關院校：遼寧工程技術大學

初試《數據結構和軟件工程》科目考試大綱

一、考查目標

理解數據結構和軟件工程的基本概念及如何利用抽象數據類型進行程序設計；掌握線性表、棧和隊列、串、數組和廣義表、樹、圖等典型數據結構及相關算法，以及排序、查找等重要算法；掌握算法的時間分析和空間分析的技術；軟件工程基本思想和基本方法。具備分析和解決現實世界問題在計算機中如何表示和處理的能力，具有軟件開發的基本能力。

二、考試形式與試卷結構

（一）試卷滿分及考試時間
滿分為150分，考試時間為3小時。
（二）答題方式
閉卷、筆試。
（三）試卷內容結構
算法及其分析(5%)、線性表及其應用(10%)、棧和隊列及應用(20%)、樹及應用(20%)、圖及應用(20%)、查找排序(20%)、其他內容(10%)。
（四）試卷題型結構
作圖題、計算題（150分）。

三、考查內容

（一）算法及分析
掌握算法的時間復雜度及空間復雜度計算方法,從而分析算法優劣。
（二）線性表及其應用
主要內容為：
（1）線性表的邏輯結構定義及ADT。
（2）線性表的順序存儲結構及操作的實現。
（3）線性表的鏈式存儲結構及操作的實現。
（4）線性表的基本應用。
（三）棧和隊列及其應用
主要內容為：
（1）棧的邏輯結構及特點。
（2）棧的順序存儲結構及其基本操作的實現。
（3）棧的應用。
（4）隊列的邏輯結構及特點。
（5）隊列的鏈式存儲及其基本操作的實現。
（6）循環隊列的特點及操作的實現。
（7）隊列的應用。
（四）樹及應用
主要內容為：
（1）樹的基本概念及術語。
（2）二叉樹的定義、特性及二叉樹存儲。
（3）二叉樹遍歷的遞歸算法及非遞歸算法。
（4）樹的存儲。
（5）最優二叉樹——赫夫曼樹。
（五）圖及應用
主要內容為：
（1）圖的基本概念。
（2）圖的存儲——鄰接矩陣和鄰接表。
（3）圖的遍歷算法——深度優先算法，廣度優先算法。
（4）圖的應用——拓撲排序，關鍵路徑，最小生成樹，最短路徑。
（六）查找排序
主要內容為：
（1）靜態查找表——順序表的查找及折半查找。
（2）動態查找表——二叉排序樹和平衡二叉樹的構造、插入、刪除及查找過程。
（3）哈希表——哈希表的構造和查找，并計算平均查找長度。
（4）常見的內部排序過程及算法——直接插入排序、希爾排序、快速排序、隊排序、歸并排序。分析各算法優劣。
（七）其他內容
根據具體應用，能夠選擇合適的邏輯結構及存儲結構，并實現算法。
軟件工程基本思想和基本方法。