沈陽(yáng)化工大學(xué)

    2021年碩士研究Th入學(xué)考試初試自命題科目考試大綱科目代碼：817科目名稱：算法與數(shù)據(jù)結(jié)構(gòu)

    一、考查目標(biāo)與要求

    《算法與數(shù)據(jù)結(jié)構(gòu)》在高等院校的教學(xué)計(jì)劃中是一門培養(yǎng)學(xué)生具備數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中最基本的應(yīng)用課程，使學(xué)生具備在設(shè)計(jì)程序中選擇合適、恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)模型的能力、對(duì)基本數(shù)據(jù)結(jié)構(gòu)及其上基本運(yùn)算的全面掌握能力和基本的分析解決現(xiàn)實(shí)世界問(wèn)題的計(jì)算機(jī)模型化能力。該課程所論及的科學(xué)思想和方法，在計(jì)算機(jī)科學(xué)領(lǐng)域中具有廣泛的應(yīng)用和強(qiáng)勁的活力，也是培養(yǎng)二十一世紀(jì)具有創(chuàng)新意識(shí)和創(chuàng)造性人才所必須的基本素質(zhì)。本次考試出題根據(jù)我校計(jì)算機(jī)專業(yè)研究生培養(yǎng)的要求，著重考核學(xué)生對(duì)以下幾方面的知識(shí)的掌握情況：數(shù)據(jù)結(jié)構(gòu)及相關(guān)的概念，數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，線性表、棧和隊(duì)列、數(shù)組與廣義表、樹(shù)與二叉樹(shù)、圖和網(wǎng)、查找和排序的順序和鏈?zhǔn)轿锢斫Y(jié)構(gòu)的定義以及在其上的運(yùn)算和操作算。

    二、試卷結(jié)構(gòu)

    滿分150分，其中包含5種類型題目：1.選擇題20分（每題2分共10題）

    2.判斷對(duì)錯(cuò)題20分（每題2分共10題）

    3.程序填空20分（每空2分共10空）

    4.簡(jiǎn)答題40分（共3題）

    5.程序設(shè)計(jì)題50分（共4題）

    三、考試內(nèi)容和范圍

    章節(jié)

    （按參考教材編排）考核知識(shí)點(diǎn)不考核知識(shí)點(diǎn)

    第1章緒論本章節(jié)全部?jī)?nèi)容均在考核范圍內(nèi)，包括：

    1.1什么是數(shù)據(jù)結(jié)構(gòu)

    1.2基本概念和術(shù)語(yǔ)

    1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)無(wú)

    1.4算法和算法分析（及其子節(jié)）

    第2章線性表（重點(diǎn)2.1線性表的類型定義2.4一元多項(xiàng)式的表示

    考核）2.2線性表的順序表示和實(shí)現(xiàn)及相加

    2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（及

    其子節(jié)）

    第3章棧和隊(duì)列3.1棧3.2.3行編輯程序

    3.1.1抽象數(shù)據(jù)類型棧的定義3.2.4迷宮求解

    3.1.2棧的表示和實(shí)現(xiàn)3.3棧與遞歸的實(shí)現(xiàn)

    3.2棧的應(yīng)用舉例3.4.2鏈隊(duì)列-隊(duì)列的鏈

    3.2.1數(shù)制轉(zhuǎn)換式表示和實(shí)現(xiàn)

    3.2.2括號(hào)匹配的檢驗(yàn)3.5離散事件模擬

    3.2.5表達(dá)式求值

    3.4隊(duì)列

    3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義

    3.4.3循環(huán)隊(duì)列-隊(duì)列的順序表示

    和實(shí)現(xiàn)

    第4章串4.1串類型的定義4.2.3串的塊鏈存儲(chǔ)表

    4.2串的表示和實(shí)現(xiàn)示

    4.2.1定長(zhǎng)順序存儲(chǔ)表示4.3串的模式匹配算法

    4.2.2堆分配存儲(chǔ)表示（及其子節(jié)）

    4.4串操作應(yīng)用舉例（及

    其子節(jié)）

    第5章數(shù)組和廣義表5.1數(shù)組的定義5.3矩陣的壓縮存儲(chǔ)（及

    5.2數(shù)組的順序表示和實(shí)現(xiàn)其子節(jié)）

    5.4廣義表的定義5.6m元多項(xiàng)式的表示

    5.5廣義表的存儲(chǔ)5.7廣義表的遞歸算法

    （及其子節(jié)）

    第6章樹(shù)和二叉樹(shù)6.1樹(shù)的定義和基本術(shù)語(yǔ)6.3.2線索二叉樹(shù)

    （重點(diǎn)考核）6.2二叉樹(shù)（及其子節(jié)）6.5樹(shù)與等價(jià)問(wèn)題

    6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.7回溯法與樹(shù)的遍歷

    6.3.1遍歷二叉樹(shù)6.8樹(shù)的計(jì)數(shù)

    6.4樹(shù)和森林（及其子節(jié)）

    6.6哈夫曼樹(shù)及其應(yīng)用（及其子節(jié)）

    第7章圖（重點(diǎn)考核）7.1圖的定義和術(shù)語(yǔ)7.2.3十字鏈表

    7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.4鄰接多重表

    7.2.1數(shù)組表示法7.4.4關(guān)節(jié)點(diǎn)的重連通

    7.2.2鄰接表分量

    7.3圖的遍歷（及其子節(jié)）7.6.2每一對(duì)頂點(diǎn)之間

    7.4圖的連通性問(wèn)題的最短路徑

    7.4.1無(wú)向圖的連通分量和生成樹(shù)

    7.4.2有向圖的強(qiáng)連通分量

    7.4.3最小生成樹(shù)

    7.5有向無(wú)環(huán)圖及其應(yīng)用（及其子

    節(jié)）

    7.6最短路徑

    7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑

    第8章動(dòng)態(tài)存儲(chǔ)管理

    （不考核）無(wú)*本章所有內(nèi)容均不在考

    核范圍內(nèi)

    第9章查找9.1靜態(tài)查找表

    9.1.1順序表的查找

    9.1.2有序表的查找

    9.2動(dòng)態(tài)查找表

    9.2.1二叉排序樹(shù)和平衡二叉樹(shù)

    9.3哈希表（及其子節(jié)）9.1.3靜態(tài)樹(shù)表的查找

    9.1.4索引順序表的查找

    9.2.2B-樹(shù)和B+樹(shù)

    9.2.3鍵樹(shù)

    第10章內(nèi)部排序10.1概述

    10.2插入排序（及其子節(jié)）

    10.3快速排序（及其子節(jié)）

    10.4選擇排序（及其子節(jié)）

    10.5歸并排序（及其子節(jié)）

    10.7各種內(nèi)部排序方法的比較討論10.6基數(shù)排序（及其子節(jié)）

    第11章外部排序無(wú)*本章所有內(nèi)容均不在考

    核范圍內(nèi)

    第12章文件無(wú)*本章所有內(nèi)容均不在考

    核范圍內(nèi)

    三、主要參考教材

    [1]《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，嚴(yán)蔚敏、吳偉民編著，清華大學(xué)出版社（2001以后版本。

    四、其它參考書目

    [1]《數(shù)據(jù)結(jié)構(gòu)聯(lián)考復(fù)習(xí)指導(dǎo)》，王道論壇編著，電子工業(yè)出版社（2020年版）。[2]《數(shù)據(jù)結(jié)構(gòu)高分筆記》，天勤計(jì)算機(jī)考研高分筆記系列，機(jī)械工業(yè)出版社（2020年版）。

    計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院研究生命題組

    2020.7

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