初試《數(shù)據(jù)結(jié)構(gòu)和軟件工程》科目考試大綱

1、初試數(shù)據(jù)結(jié)構(gòu)和軟件工程科目考試大綱一、考查目標理解數(shù)據(jù)結(jié)構(gòu)和軟件工程的基本概念及如何利用抽象數(shù)據(jù)類型進行程序設(shè)計；掌握線性表、棧和隊列、串、數(shù)組和廣義表、樹、圖等典型數(shù)據(jù)結(jié)構(gòu)及相關(guān)算法，以及排序、查找等重要算法；掌握算法的時間分析和空間分析的技術(shù)；軟件工程基本思想和基本方法。具備分析和解決現(xiàn)實世界問題在計算機中如何表示和處理的能力，具有軟件開發(fā)的基本能力。二、考試形式與試卷結(jié)構(gòu)（一）試卷滿分及考試時間滿分為150分，考試時間為3小時。（二）答題方式閉卷、筆試。（三）試卷內(nèi)容結(jié)構(gòu)算法及其分析(5%)、線性表及其應(yīng)用(10%)、棧和隊列及應(yīng)用(20%)、樹及應(yīng)用(20%)、圖及應(yīng)用(20%)、查找

2、排序 (20%)、其他內(nèi)容(10%)。（四）試卷題型結(jié)構(gòu)作圖題、計算題（150分）。三、考查內(nèi)容（一）算法及分析掌握算法的時間復(fù)雜度及空間復(fù)雜度計算方法,從而分析算法優(yōu)劣。（二）線性表及其應(yīng)用主要內(nèi)容為：（1）線性表的邏輯結(jié)構(gòu)定義及ADT。（2）線性表的順序存儲結(jié)構(gòu)及操作的實現(xiàn)。（3）線性表的鏈式存儲結(jié)構(gòu)及操作的實現(xiàn)。（4）線性表的基本應(yīng)用。（三）棧和隊列及其應(yīng)用主要內(nèi)容為：（1）棧的邏輯結(jié)構(gòu)及特點。（2）棧的順序存儲結(jié)構(gòu)及其基本操作的實現(xiàn)。（3）棧的應(yīng)用。（4）隊列的邏輯結(jié)構(gòu)及特點。（5）隊列的鏈式存儲及其基本操作的實現(xiàn)。（6）循環(huán)隊列的特點及操作的實現(xiàn)。（7）隊列的應(yīng)用。（四）樹及應(yīng)用主要

3、內(nèi)容為：（1）樹的基本概念及術(shù)語。（2）二叉樹的定義、特性及二叉樹存儲。（3）二叉樹遍歷的遞歸算法及非遞歸算法。（4）樹的存儲。（5）最優(yōu)二叉樹赫夫曼樹。（五）圖及應(yīng)用主要內(nèi)容為：（1）圖的基本概念。（2）圖的存儲鄰接矩陣和鄰接表。（3）圖的遍歷算法深度優(yōu)先算法，廣度優(yōu)先算法。（4）圖的應(yīng)用拓撲排序，關(guān)鍵路徑，最小生成樹，最短路徑。（六）查找排序主要內(nèi)容為：（1）靜態(tài)查找表順序表的查找及折半查找。（2）動態(tài)查找表二叉排序樹和平衡二叉樹的構(gòu)造、插入、刪除及查找過程。（3）哈希表哈希表的構(gòu)造和查找，并計算平均查找長度。（4）常見的內(nèi)部排序過程及算法直接插入排序、希爾排序、快速排序、隊排序、歸并排序。分析各算法優(yōu)劣。 （七）其他內(nèi)容 根據(jù)具體應(yīng)用，能夠選擇合適的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)，并實現(xiàn)算法。軟件