沈陽化工大學

    2021年碩士研究Th入學考試初試自命題科目考試大綱科目代碼：817科目名稱：算法與數據結構

    一、考查目標與要求

    《算法與數據結構》在高等院校的教學計劃中是一門培養學生具備數據結構在計算機科學中最基本的應用課程，使學生具備在設計程序中選擇合適、恰當的數據結構模型的能力、對基本數據結構及其上基本運算的全面掌握能力和基本的分析解決現實世界問題的計算機模型化能力。該課程所論及的科學思想和方法，在計算機科學領域中具有廣泛的應用和強勁的活力，也是培養二十一世紀具有創新意識和創造性人才所必須的基本素質。本次考試出題根據我校計算機專業研究生培養的要求，著重考核學生對以下幾方面的知識的掌握情況：數據結構及相關的概念，數據的邏輯結構和物理結構，線性表、棧和隊列、數組與廣義表、樹與二叉樹、圖和網、查找和排序的順序和鏈式物理結構的定義以及在其上的運算和操作算。

    二、試卷結構

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

    2.判斷對錯題20分（每題2分共10題）

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

    4.簡答題40分（共3題）

    5.程序設計題50分（共4題）

    三、考試內容和范圍

    章節

    （按參考教材編排）考核知識點不考核知識點

    第1章緒論本章節全部內容均在考核范圍內，包括：

    1.1什么是數據結構

    1.2基本概念和術語

    1.3抽象數據類型的表示與實現無

    1.4算法和算法分析（及其子節）

    第2章線性表（重點2.1線性表的類型定義2.4一元多項式的表示

    考核）2.2線性表的順序表示和實現及相加

    2.3線性表的鏈式表示和實現（及

    其子節）

    第3章棧和隊列3.1棧3.2.3行編輯程序

    3.1.1抽象數據類型棧的定義3.2.4迷宮求解

    3.1.2棧的表示和實現3.3棧與遞歸的實現

    3.2棧的應用舉例3.4.2鏈隊列-隊列的鏈

    3.2.1數制轉換式表示和實現

    3.2.2括號匹配的檢驗3.5離散事件模擬

    3.2.5表達式求值

    3.4隊列

    3.4.1抽象數據類型隊列的定義

    3.4.3循環隊列-隊列的順序表示

    和實現

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

    4.2串的表示和實現示

    4.2.1定長順序存儲表示4.3串的模式匹配算法

    4.2.2堆分配存儲表示（及其子節）

    4.4串操作應用舉例（及

    其子節）

    第5章數組和廣義表5.1數組的定義5.3矩陣的壓縮存儲（及

    5.2數組的順序表示和實現其子節）

    5.4廣義表的定義5.6m元多項式的表示

    5.5廣義表的存儲5.7廣義表的遞歸算法

    （及其子節）

    第6章樹和二叉樹6.1樹的定義和基本術語6.3.2線索二叉樹

    （重點考核）6.2二叉樹（及其子節）6.5樹與等價問題

    6.3遍歷二叉樹和線索二叉樹6.7回溯法與樹的遍歷

    6.3.1遍歷二叉樹6.8樹的計數

    6.4樹和森林（及其子節）

    6.6哈夫曼樹及其應用（及其子節）

    第7章圖（重點考核）7.1圖的定義和術語7.2.3十字鏈表

    7.2圖的存儲結構7.2.4鄰接多重表

    7.2.1數組表示法7.4.4關節點的重連通

    7.2.2鄰接表分量

    7.3圖的遍歷（及其子節）7.6.2每一對頂點之間

    7.4圖的連通性問題的最短路徑

    7.4.1無向圖的連通分量和生成樹

    7.4.2有向圖的強連通分量

    7.4.3最小生成樹

    7.5有向無環圖及其應用（及其子

    節）

    7.6最短路徑

    7.6.1從某個源點到其余各頂點的最短路徑

    第8章動態存儲管理

    （不考核）無*本章所有內容均不在考

    核范圍內

    第9章查找9.1靜態查找表

    9.1.1順序表的查找

    9.1.2有序表的查找

    9.2動態查找表

    9.2.1二叉排序樹和平衡二叉樹

    9.3哈希表（及其子節）9.1.3靜態樹表的查找

    9.1.4索引順序表的查找

    9.2.2B-樹和B+樹

    9.2.3鍵樹

    第10章內部排序10.1概述

    10.2插入排序（及其子節）

    10.3快速排序（及其子節）

    10.4選擇排序（及其子節）

    10.5歸并排序（及其子節）

    10.7各種內部排序方法的比較討論10.6基數排序（及其子節）

    第11章外部排序無*本章所有內容均不在考

    核范圍內

    第12章文件無*本章所有內容均不在考

    核范圍內

    三、主要參考教材

    [1]《數據結構（C語言版）》，嚴蔚敏、吳偉民編著，清華大學出版社（2001以后版本。

    四、其它參考書目

    [1]《數據結構聯考復習指導》，王道論壇編著，電子工業出版社（2020年版）。[2]《數據結構高分筆記》，天勤計算機考研高分筆記系列，機械工業出版社（2020年版）。

    計算機科學與技術學院研究生命題組

    2020.7

添加沈陽化工大學學姐微信，或微信搜索公眾號“考研派小站”，關注【考研派小站】微信公眾號，在考研派小站微信號輸入【沈陽化工大學大學考研分數線、沈陽化工大學報錄比、沈陽化工大學考研群、沈陽化工大學學姐微信、沈陽化工大學考研真題、沈陽化工大學專業目錄、沈陽化工大學排名、沈陽化工大學保研、沈陽化工大學公眾號、沈陽化工大學研究生招生）】即可在手機上查看相對應沈陽化工大學考研信息或資源。