北京工商大學(xué)2024年考研初試大綱：818數(shù)據(jù)結(jié)構(gòu)

考研專業(yè)課大綱對(duì)備考具有重要價(jià)值。大綱可以幫助考生了解考試的整體結(jié)構(gòu)和考查重點(diǎn)，在備考過程中起到明確方向的作用。大綱所列出的考試范圍和知識(shí)要點(diǎn)，可以幫助考生建立知識(shí)體系，明確重難點(diǎn)，有針對(duì)性地進(jìn)行備考。同時(shí)，弄清大綱要求可以讓考生事先了解復(fù)習(xí)的時(shí)間分配和備考要求，避免在備考過程中盲目浪費(fèi)時(shí)間和精力。以下是北京工商大學(xué)2024年碩士研究生招生考試《818數(shù)據(jù)結(jié)構(gòu)》考試大綱具體內(nèi)容，報(bào)考該校計(jì)算機(jī)專業(yè)相關(guān)方向的考生可以根據(jù)考試大綱備考。

北京工商大學(xué)2024年碩士研究生初試考試大綱

818數(shù)據(jù)結(jié)構(gòu)考試大綱

一、考查目標(biāo)

1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。

2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。

3.能夠利用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解，具備采用C或C++語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。

二、考試形式和試卷結(jié)構(gòu)

1、試卷滿分及考試時(shí)間

本試卷滿分為150分，考試時(shí)間為180分鐘

2、答題方式

答題方式為閉卷、筆試

3、試卷題型結(jié)構(gòu)

單項(xiàng)選擇題

判斷題

簡(jiǎn)答題/填空題

綜合應(yīng)用題

算法設(shè)計(jì)題

三、考試范圍及基本要求

（一）緒論

【內(nèi)容】

數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，數(shù)據(jù)抽象，算法的描述和算法分析。

【要求】

掌握基本概念和術(shù)語，初步學(xué)會(huì)算法的分析度量。

（二）線性表

【內(nèi)容】

線性表的邏輯結(jié)構(gòu)，線性表的順序存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，循環(huán)鏈表，雙向鏈表。

線性表的應(yīng)用。

【要求】

1．了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的不同方法得到兩類不同的存儲(chǔ)結(jié)構(gòu)。

2．熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。

3．熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本操作：插入、刪除等算法。

（三）棧和隊(duì)列

【內(nèi)容】

棧的定義，棧的表示和實(shí)現(xiàn)，棧的順序存儲(chǔ)結(jié)構(gòu)，應(yīng)用舉例：表達(dá)式求值（*）。

隊(duì)列的定義，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)（和棧類似結(jié)構(gòu)及循環(huán)隊(duì)列），鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？偨Y(jié)線性表靜態(tài)及動(dòng)態(tài)的特點(diǎn)（包括棧和隊(duì)列），并舉例說明在實(shí)際工作中的應(yīng)用。

【要求】

1．掌握棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，懂得在什么樣的問題中應(yīng)該利用哪種結(jié)構(gòu)。

2．熟練掌握在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)棧的基本運(yùn)算，特別注意棧滿和?？盏臈l件及它們的描述。

3．熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算，特別注意隊(duì)滿和隊(duì)空的描述方法。

4．理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。

（四）樹和二叉樹

【內(nèi)容】

二叉樹的定義及基本操作，二叉樹的性質(zhì)，二叉樹的存儲(chǔ)結(jié)構(gòu)，二叉樹的遍歷。

樹的定義及存儲(chǔ)結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換，樹和森林的遍歷，哈夫曼樹及其應(yīng)用。

【要求】

1．熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。

2．了解幾種特殊形態(tài)的二叉樹。

3．熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。

4．遍歷二叉樹是二叉樹各種運(yùn)算的基礎(chǔ)，不僅要熟練掌握各種序遍歷的遞歸和非遞歸算法，還要了解遍歷過程中“?！钡臓顟B(tài)，并能靈活運(yùn)用遞歸遍歷算法實(shí)現(xiàn)二叉樹的其他各種運(yùn)算。

5．樹和森林(樹的存儲(chǔ)結(jié)構(gòu)、遍歷方法;森林與二叉樹的轉(zhuǎn)換方法)。

6．哈夫曼樹及哈夫曼編碼。

（五）圖

【內(nèi)容】

圖的定義和術(shù)語，圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷，深度優(yōu)先搜索，廣度優(yōu)先搜索，應(yīng)用舉例：人工

智能中的問題求解（*）。

無向圖的連通分量和生成樹，最小生成樹，有向無環(huán)圖及其應(yīng)用：最短路徑，拓?fù)渑判颍?），

關(guān)鍵路徑（*）。

【要求】

1．熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算

法有密切聯(lián)系。

2．熟練掌握?qǐng)D的遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與二叉樹的遍歷算法之間的類似和差異。

3．應(yīng)用圖的遍歷算法求解各種簡(jiǎn)單路徑問題。

4．理解參考書中討論的各種圖的算法，掌握其主要數(shù)據(jù)結(jié)構(gòu)的變化情況。

（六）查找

【內(nèi)容】

靜態(tài)查找表，二叉排序樹和平衡二叉樹（*），散列（Hash）表。

【要求】

1．順序表和有序表的查找方法及其平均查找長(zhǎng)度的計(jì)算方法。

2．靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系。

3．熟練掌握二叉排序樹的構(gòu)造和查找方法。

4．熟練掌握散列表的構(gòu)造方法，深刻理解散列表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。

6．掌握按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。

（七）內(nèi)部排序

【內(nèi)容】

冒泡排序，插入排序，快速排序，選擇排序，堆排序，歸并排序。

【要求】

1．了解排序的定義和各種排序方法的特點(diǎn)。熟悉各種方法的排序過程及其依據(jù)的原則。

2．掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能（*）。

3．理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。

原文鏈接：https://yjs.btbu.edu.cn/zsgz/sszs/a34836b0a6f54cdaad7a5f976a062a70.htm