(研招考試主要考察考生分析問題與解決問題的能力,大綱所列內容為考生需掌握的基本內容,僅供復習參考使用,考試范圍不限于此)
一、 考察目標
834 數據結構、計算機組成原理要求考生比較系統地掌握上述專業基礎課程的基本概念、基本原理和基本方法,能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。
二、考試形式和試卷結構
1、 試卷滿分及考試時間:本試卷滿分為 150 分,考試時間為 180 分鐘
2、 答題方式:閉卷,筆試
3、 試卷內容結構:數據結構 75 分、計算機組成原理 75 分
三、考察范圍
數據結構:
【總體要求】
“數據結構”部分要求學生掌握常用數據結構的構造和實現方法,掌握基本的查找和排序方法,具備應用數據結構分析、設計和求解實際問題的能力,能夠對運算過程進行時間復雜度和空間復雜度分析,具備采用 C 或 C++或 Java 等編程語言設計與實現算法的能力。
(一)線性表
1)線性表的基本概念和基本操作
2)線性表的順序存儲及實現
3)線性表的鏈式存儲及實現
4)線性表的應用
(二)棧和隊列
1)棧和隊列的基本概念和基本操作
2)棧和隊列的存儲結構與實現
(1)棧的順序存儲及實現
(2)棧的鏈式存儲及實現
(3)隊列的鏈式存儲及實現
(4)循環隊列的定義及實現
3)棧和隊列的應用
(三)串
1)串的基本概念和基本操作
2)串的順序存儲、鏈式存儲及實現
3)串的模式匹配
(1)基本的模式匹配算法
(2) KMP 模式匹配算法(模式串的 next 函數計算)
(四)數組和廣義表
1)數組的基本概念和基本操作
2)數組的順序存儲
3)特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲及運算
4)廣義表的基本概念、存儲結構和基本運算
(五)樹與二叉樹
1)樹的基本概念
2)二叉樹
(1)二叉樹的定義及性質
(2)二叉樹的順序存儲和鏈式存儲
(3)二叉樹的先序、中序、后序遍歷和層序遍歷運算
(4)線索二叉樹的定義與基本運算
3)樹和森林
(1)樹的存儲結構
(2)樹(森林)與二叉樹的相互轉換
(3)樹和森林的遍歷
4)哈夫曼(Huffman)樹的構造方法與應用