考試科目代碼及名稱：822數(shù)據(jù)結(jié)構(gòu)              學(xué)院名稱（公章）：信息科學(xué)與工程學(xué)院

一、考試的總體要求

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)類相關(guān)專業(yè)本科生的一門必修課程，是計(jì)算機(jī)程序設(shè)計(jì)的重要理論和實(shí)踐基礎(chǔ)。要求學(xué)生掌握軟件設(shè)計(jì)中經(jīng)常遇到的線性表、棧、隊(duì)列、串、數(shù)組、樹和二叉樹、圖等典型數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、基本操作的實(shí)現(xiàn)方法，以及各種典型的查找和排序算法的設(shè)計(jì)方法。在軟件設(shè)計(jì)中能夠比較準(zhǔn)確地分析涉及到的數(shù)據(jù)結(jié)構(gòu)的特性，選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析技術(shù)。

二、考試內(nèi)容

一、概述 

1.熟悉數(shù)據(jù)結(jié)構(gòu)相關(guān)術(shù)語(yǔ)的含義，掌握基本概念

2.掌握數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及兩者之間的關(guān)系  

3.了解抽象數(shù)據(jù)類型的定義和表示方法  

4.掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法 

二、線性結(jié)構(gòu)——線性表、棧、隊(duì)列和串  

1.理解線性表的邏輯結(jié)構(gòu)定義  

2.熟悉抽象數(shù)據(jù)類型定義方式  

3.熟練掌握線性結(jié)構(gòu)的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  

4.掌握線性表、棧和隊(duì)列的應(yīng)用，理解各種線性結(jié)構(gòu)之間的關(guān)系  

5.熟悉串的邏輯結(jié)構(gòu)和典型存儲(chǔ)方式，理解串的主要運(yùn)算  

6.熟練掌握在順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線性表、棧、隊(duì)列和串的相關(guān)操作 

三、數(shù)組和廣義表 

1.掌握數(shù)組的邏輯特征與存儲(chǔ)方式  

2.掌握矩陣的壓縮存儲(chǔ)方式及其特點(diǎn)  

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

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

四、樹和二叉樹 

1.熟練掌握二叉樹的基本性質(zhì)  

2.熟練掌握二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)、適用范圍及實(shí)現(xiàn)  

3.熟練掌握二叉樹各種遍歷算法的遞歸實(shí)現(xiàn)  

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

5.掌握樹（森林）與二叉樹的轉(zhuǎn)換關(guān)系 

6.掌握最優(yōu)二叉樹的特性，熟練掌握構(gòu)造哈夫曼樹和哈夫曼編碼的方法 

五、圖  

1.掌握?qǐng)D的定義及其相關(guān)概念 

2.熟練掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)——鄰接矩陣、鄰接表

3.熟練掌握?qǐng)D的遍歷方法——深度優(yōu)先搜索、廣度優(yōu)先搜索  

4.掌握最小生成樹算法  

5.掌握?qǐng)D的最短路徑算法  

6.了解拓?fù)渑判蚋拍?，了解關(guān)鍵路徑算法 

六、查找  

1.熟練掌握靜態(tài)查找表——順序表、有序表、索引表的查找算法；理解算法復(fù)雜性的分析過程；熟悉各算法特點(diǎn)及使用場(chǎng)景 

2.掌握動(dòng)態(tài)查找表——二叉排序樹和平衡二叉樹的概念、基本操作及其實(shí)現(xiàn)  

3.了解B-樹的概念和特點(diǎn)  

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

七、排序 

1.掌握直接插入排序、希爾排序、冒泡排序、簡(jiǎn)單選擇排序的思想及實(shí)現(xiàn)方法  

2.掌握快速排序、堆排序、歸并排序的思想和及實(shí)現(xiàn)方法  

3.了解基數(shù)排序的思想和實(shí)現(xiàn)方法

4.掌握算法復(fù)雜度及其分析方法；熟悉各算法特點(diǎn)及適用場(chǎng)景 

三、試卷題型及比例

一、單項(xiàng)選擇題（30分）

二、填空題（20分）

三、應(yīng)用題（70分）

四、算法設(shè)計(jì)題（30分）

四、考試形式及時(shí)間    

閉卷，180分鐘

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

1.路瑩主編，《數(shù)據(jù)結(jié)構(gòu)》，清華大學(xué)出版社，2013年7月，第一版

2.嚴(yán)蔚敏、吳偉民編、《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，清華大學(xué)出版社，1997年4月，第一版

 

添加大連工業(yè)大學(xué)學(xué)姐微信，或微信搜索公眾號(hào)“考研派小站”，關(guān)注【考研派小站】微信公眾號(hào)，在考研派小站微信號(hào)輸入【大連工業(yè)大學(xué)考研分?jǐn)?shù)線、大連工業(yè)大學(xué)報(bào)錄比、大連工業(yè)大學(xué)考研群、大連工業(yè)大學(xué)學(xué)姐微信、大連工業(yè)大學(xué)考研真題、大連工業(yè)大學(xué)專業(yè)目錄、大連工業(yè)大學(xué)排名、大連工業(yè)大學(xué)保研、大連工業(yè)大學(xué)公眾號(hào)、大連工業(yè)大學(xué)研究生招生）】即可在手機(jī)上查看相對(duì)應(yīng)大連工業(yè)大學(xué)考研信息或資源。