2021沈阳化工大学817算法与数据结构研究生考试大纲及参考书目

沈阳化工大学学姐微信
为你答疑,送资源

    沈阳化工大学

    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