2021東北石油大學820數據結構研究生考試大綱 正文

東北石油大學2021年碩士研究生招生考試初試
自命題科目考試大綱
 
命題單位：  計算機與信息技術學院    
考試科目代碼：        820           
考試科目名稱：    數據結構        
一、考試滿分及考試時間
    試卷滿分為150分，考試時間為180分鐘。
二、答題方式
    答題方式為閉卷、筆試。
三、答題內容結構
線性表25%，樹20%，圖20%，查找15%，排序20%。
四、試卷題型結構
1.單選題，共10小題，每題1分，共10分；
2.簡答題，共6小題，每題8分，共48分；
3.算法設計題，共5小題，分數分別為14分、16分、20分、20分、22分，共92分。
五、考試內容知識點說明
（一）線性表
考試內容：線性表的定義；線性表的抽象數據類型定義、數學表示及含義；線性表常用的基本運算；線性表的順序存儲結構及基本運算的實現；線性表的鏈式存儲結構及基本運算的實現。
考試要求：了解線性表的邏輯結構和常用的一些運算，掌握線性表的兩種存儲結構及其用法，掌握這兩種存儲結構各自的優缺點。在算法實現方面，要求能夠根據實際問題的需求來決定采用何種存儲結構并給出具體的算法，如：插入、刪除滿足條件的鏈表節點，在鏈表上排序等。
（二）棧和隊列
考試內容：棧的定義，邏輯結構和常用運算；棧的存儲結構；棧的實際應用；棧與遞歸的關系；隊列的定義及存儲結構；隊列的應用。
考試要求：了解棧和隊列的邏輯結構定義，掌握棧和隊列運算特點，掌握棧和遞歸的關系，掌握棧和隊列的順序存儲結構。在算法實現方面，要求可以熟練利用棧和隊列的順序存儲結構解決實際的問題，如：走迷宮問題、表達式括號匹配問題等。
（三）串
考試內容：串的存儲結構及基本運算的實現；串的模式匹配；KMP算法
考試要求：掌握字符串的兩種存儲結構，即定長存儲結構和堆存儲結構，能夠在兩中存儲結構上實現字符串的各種運算，掌握字符串的模式匹配運算及相應的改進算法。
（四）數組和廣義表
考試內容：數組的邏輯結構定義，數據的特點；數據的存儲結構；稀疏矩陣的壓縮存儲；廣義表的定義及存儲結構
考試要求：了解數組及廣義表的定義及特點，掌握數組的特點、存儲結構及廣義表的實際應用，掌握稀疏矩陣的壓縮存儲方法，能夠在壓縮存儲下實現矩陣的各種運算。
（五）樹和二叉樹
考試內容：樹和二叉樹的定義；二叉樹的性質；樹和二叉樹的存儲結構；二叉樹和樹的遍歷，線索二叉樹，二叉樹的層序遍歷；哈夫曼樹及其應用。
考試要求：了解樹的邏輯結構定義，掌握二叉樹的定義、性質、存儲結構和運算，掌握樹和二叉樹之間的關系。在算法實現方面，要求熟練掌握二叉樹的遞歸和非遞歸遍歷，并能夠用之解決實際問題，如：計算樹的層數、度，查找滿足條件的節點等。
（六）圖
考試內容：圖的定義及基本術語；圖的存儲結構；圖的兩種遍歷方法及算法；圖的連通性；拓撲排序和關鍵路徑；最短路徑；最小生成樹。
考試要求：了解圖的邏輯結構定義，掌握圖的術語、圖的兩種常用存儲結構，即鄰接矩陣和鄰接表。在算法實現方面，要求熟練掌握圖的兩種遍歷方法，并能夠根據圖的基本原理解決一些應用問題，如：判定圖的連通性、判定是否有環、計算特定路徑等。
（七）查找
考試內容：查找方法的分類；各類查找表常用的查找方法；典型查找方法的算法實現。
考試要求：了解動態查找表和靜態查找表的邏輯結構定義，掌握靜態查找表的三類查找方法的思想，對數據元素的要求、數據元素的存儲結構，平均查找長度。掌握二叉排序樹的定義及構造方法，二叉樹的平衡化處理。掌握散列表的定義及創建散列表的方法，以及查找散列表的方法。在算法實現方面，要求可以利用各種查找算法解決實際問題。
（八）內排序
考試內容：排序的基本概念，排序方法分類的依據；插入排序、快速排序、選擇排序、歸并排序、基數排序中各種常用的排序方法。
考試要求：了解排序的定義及術語，排序方法的評價方法，掌握的排序方法有：直接插入排序、shell插入排序，快速排序，堆排序，二路歸并排序，鏈式基數排序，要知道它們的排序思想，并能描述排序過程。在算法實現方面，要求可以利用各種排序算法解決實際問題。
六、參考書
1.嚴蔚敏，吳偉民. 數據結構(C語言版) [M].清華大學出版社，1997
 

東北石油大學

本文來源：http://m.btfokj.cn/dbsydx/cksm_407198.html