考試科目代碼及名稱：822數據結構              學院名稱（公章）：信息科學與工程學院

一、考試的總體要求

《數據結構》是計算機類相關專業本科生的一門必修課程，是計算機程序設計的重要理論和實踐基礎。要求學生掌握軟件設計中經常遇到的線性表、棧、隊列、串、數組、樹和二叉樹、圖等典型數據結構的邏輯結構、存儲結構、基本操作的實現方法，以及各種典型的查找和排序算法的設計方法。在軟件設計中能夠比較準確地分析涉及到的數據結構的特性，選擇適當的邏輯結構、存儲結構及其相應的算法，并初步掌握算法的時間分析技術。

二、考試內容

一、概述 

1.熟悉數據結構相關術語的含義，掌握基本概念

2.掌握數據結構中邏輯結構、存儲結構以及兩者之間的關系  

3.了解抽象數據類型的定義和表示方法  

4.掌握計算語句頻度和估算算法時間復雜度的方法 

二、線性結構——線性表、棧、隊列和串  

1.理解線性表的邏輯結構定義  

2.熟悉抽象數據類型定義方式  

3.熟練掌握線性結構的順序和鏈式存儲結構  

4.掌握線性表、棧和隊列的應用，理解各種線性結構之間的關系  

5.熟悉串的邏輯結構和典型存儲方式，理解串的主要運算  

6.熟練掌握在順序和鏈式存儲結構上實現線性表、棧、隊列和串的相關操作 

三、數組和廣義表 

1.掌握數組的邏輯特征與存儲方式  

2.掌握矩陣的壓縮存儲方式及其特點  

3.理解廣義表的邏輯特征和存儲方式  

4.掌握廣義表的基本操作 

四、樹和二叉樹 

1.熟練掌握二叉樹的基本性質  

2.熟練掌握二叉樹的各種存儲結構的特點、適用范圍及實現  

3.熟練掌握二叉樹各種遍歷算法的遞歸實現  

4.熟練掌握基于遍歷策略的二叉樹操作及應用  

5.掌握樹（森林）與二叉樹的轉換關系 

6.掌握最優二叉樹的特性，熟練掌握構造哈夫曼樹和哈夫曼編碼的方法 

五、圖  

1.掌握圖的定義及其相關概念 

2.熟練掌握圖的存儲結構——鄰接矩陣、鄰接表

3.熟練掌握圖的遍歷方法——深度優先搜索、廣度優先搜索  

4.掌握最小生成樹算法  

5.掌握圖的最短路徑算法  

6.了解拓撲排序概念，了解關鍵路徑算法 

六、查找  

1.熟練掌握靜態查找表——順序表、有序表、索引表的查找算法；理解算法復雜性的分析過程；熟悉各算法特點及使用場景 

2.掌握動態查找表——二叉排序樹和平衡二叉樹的概念、基本操作及其實現  

3.了解B-樹的概念和特點  

4.熟練掌握哈希查找思想、哈希沖突解決方法、哈希查找性能 

七、排序 

1.掌握直接插入排序、希爾排序、冒泡排序、簡單選擇排序的思想及實現方法  

2.掌握快速排序、堆排序、歸并排序的思想和及實現方法  

3.了解基數排序的思想和實現方法

4.掌握算法復雜度及其分析方法；熟悉各算法特點及適用場景 

三、試卷題型及比例

一、單項選擇題（30分）

二、填空題（20分）

三、應用題（70分）

四、算法設計題（30分）

四、考試形式及時間    

閉卷，180分鐘

五、參考書目(須與專業目錄一致)(包括作者、書目、出版社、出版時間、版次)：

1.路瑩主編，《數據結構》，清華大學出版社，2013年7月，第一版

2.嚴蔚敏、吳偉民編、《數據結構（C語言版）》，清華大學出版社，1997年4月，第一版

 

添加大連工業大學學姐微信，或微信搜索公眾號“考研派小站”，關注【考研派小站】微信公眾號，在考研派小站微信號輸入【大連工業大學考研分數線、大連工業大學報錄比、大連工業大學考研群、大連工業大學學姐微信、大連工業大學考研真題、大連工業大學專業目錄、大連工業大學排名、大連工業大學保研、大連工業大學公眾號、大連工業大學研究生招生）】即可在手機上查看相對應大連工業大學考研信息或資源。