1
2
3
4
《數據結構》考試大綱
一、 考查目標
1.掌握數據結構的基本概念、基本原理和基本方法。
2.掌握數據的邏輯結構、存儲結構及基本操作的實(shí)現，能夠對算法進(jìn)行基本的時(shí)間復雜度與空 間復雜度的分析。
3.能夠利用數據結構基本原理和方法進(jìn)行問(wèn)題的分析與求解，具備采用C 或 C++語(yǔ)言設計與實(shí)現 算法的能力。
二、 考試形式和試卷結構
1、試卷滿(mǎn)分及考試時(shí)間
本試卷滿(mǎn)分為 150 分，考試時(shí)間為 180 分鐘
2、答題方式
答題方式為閉卷、筆試
3、試卷題型結構
單項選擇題 判斷題
簡(jiǎn)答題/填空題 綜合應用題
算法設計題
三、 考試范圍及基本要求
(一) 緒論 【內容】
數據結構的基本概念和術(shù)語(yǔ)，數據抽象，算法的描述和算法分析。 【要求】
掌握基本概念和術(shù)語(yǔ)，初步學(xué)會(huì )算法的分析度量。
(二) 線(xiàn)性表 【內容】
線(xiàn)性表的邏輯結構，線(xiàn)性表的順序存儲結構，線(xiàn)性表的鏈式存儲結構，循環(huán)鏈表，雙向鏈表。 線(xiàn)性表的應用。
【要求】
了解線(xiàn)性表的邏輯結構特性是數據元素之間存在著(zhù)線(xiàn)性關(guān)系，在計算機中表示這種關(guān)系的 不同方法得到兩類(lèi)不同的存儲結構。
2. 熟練掌握這兩類(lèi)存儲結構的描述方法，以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。
3. 熟練掌握線(xiàn)性表在順序存儲結構上實(shí)現的基本操作：插入、刪除等算法。
(三) 棧和隊列 【內容】
棧的定義，棧的表示和實(shí)現，棧的順序存儲結構，應用舉例：表達式求值(*)。
隊列的定義，隊列的順序存儲結構(和棧類(lèi)似結構及循環(huán)隊列)，鏈式存儲結構?？偨Y線(xiàn)性表靜 態(tài)及動(dòng)態(tài)的特點(diǎn)(包括棧和隊列)，并舉例說(shuō)明在實(shí)際工作中的應用。
【要求】
1. 掌握棧和隊列這兩種數據結構的特點(diǎn),懂得在什么樣的問(wèn)題中應該利用哪種結構。
2. 熟練掌握在順序存儲結構上實(shí)現棧的基本運算,特別注意棧滿(mǎn)和?？盏臈l件及它們的描述。
3. 熟練掌握循環(huán)隊列和鏈隊列的基本運算,特別注意隊滿(mǎn)和隊空的描述方法。
4. 理解遞歸算法執行過(guò)程中棧的狀態(tài)變化過(guò)程。
(四) 樹(shù)和二叉樹(shù) 【內容】
二叉樹(shù)的定義及基本操作，二叉樹(shù)的性質(zhì)，二叉樹(shù)的存儲結構，二叉樹(shù)的遍歷。
樹(shù)的定義及存儲結構，森林與二叉樹(shù)的轉換，樹(shù)和森林的遍歷，哈夫曼樹(shù)及其應用。 【要求】
1. 熟練掌握二叉樹(shù)的結構特性,了解相應的證明方法。
2. 了解幾種特殊形態(tài)的二叉樹(shù)。
3. 熟悉二叉樹(shù)的各種存儲結構的特點(diǎn)及適用范圍。
4. 遍歷二叉樹(shù)是二叉樹(shù)各種運算的基礎,不僅要熟練掌握各種序遍歷的遞歸和非遞歸算法,還 要了解遍歷過(guò)程中“棧 ”的狀態(tài),并能靈活運用遞歸遍歷算法實(shí)現二叉樹(shù)的其他各種運算。
5. 樹(shù)和森林(樹(shù)的存儲結構、遍歷方法 ;森林與二叉樹(shù)的轉換方法)。
6. 哈夫曼樹(shù)及哈夫曼編碼。
(五) 圖 【內容】
圖的定義和術(shù)語(yǔ)，圖的存儲結構，圖的遍歷，深度優(yōu)先搜索，廣度優(yōu)先搜索，應用舉例：人工 智能中的問(wèn)題求解(*)。
無(wú)向圖的連通分量和生成樹(shù)，最小生成樹(shù)，有向無(wú)環(huán)圖及其應用：最短路徑，拓撲排序(*)， 關(guān)鍵路徑(*)。
【要求】
1. 熟悉圖的各種存儲結構及其構造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲結構和算 法有密切聯(lián)系。
2. 熟練掌握圖的遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學(xué)習中應注意圖 的遍歷算法與二叉樹(shù)的遍歷算法之間的類(lèi)似和差異。
3. 應用圖的遍歷算法求解各種簡(jiǎn)單路徑問(wèn)題。
4. 理解參考書(shū)中討論的各種圖的算法，掌握其主要數據結構的變化情況。
(六) 查找 【內容】
靜態(tài)查找表，二叉排序樹(shù)和平衡二叉樹(shù)(*)，散列(Hash)表。 【要求】
1. 順序表和有序表的查找方法及其平均查找長(cháng)度的計算方法。
2. 靜態(tài)查找樹(shù)的構造方法和查找算法,理解靜態(tài)查找樹(shù)和折半查找的關(guān)系。
3. 熟練掌握二叉排序樹(shù)的構造和查找方法。
4. 熟練掌握散列表的構造方法，深刻理解散列表與其它結構的表的實(shí)質(zhì)性的差別。
6. 掌握按定義計算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(cháng)度。
(七) 內部排序 【內容】
冒泡排序，插入排序，快速排序，選擇排序，堆排序，歸并排序。 【要求】
1. 了解排序的定義和各種排序方法的特點(diǎn)。熟悉各種方法的排序過(guò)程及其依據的原則。
2. 掌握各種排序方法的時(shí)間復雜度的分析方法。能從“關(guān)鍵字間的比較次數 ”分析排序算法 的平均情況和最壞情況的時(shí)間性能(*)。
3. 理解排序方法“穩定 ”或“不穩定 ”的含義，弄清楚在什么情況下要求應用的排序方法必 須是穩定的。
原標題：北京工商大學(xué)2025年碩士研究生招生考試（初試）參考書(shū)目、考試大綱
文章來(lái)源：https://yjs.btbu.edu.cn/zsgz/sszs/17491f7b380e487f9a41159d5da54ea6.htm
