郑州轻工业大学

2019年硕士研究生入学考试初试科目考试大纲

数据结构(科目代码：822)

本考试大纲适用于报考郑州轻工业大学软件工程学科软件工程专业、软件工程技术与服务专业的硕士研究生的入学考试。

一、考试内容及基本要求

1.数据结构基本知识

(1) 掌握数据结构基本概念和术语

(2) 了解抽象数据类型的表示与实现

(3) 掌握算法基本概念和算法分析方法

2.线性结构

(1) 掌握线性表的类型定义

(2) 掌握线性表的顺序和链式表示与实现

(3) 掌握栈和队列的特点

(4) 理解栈与递归的关系

(5) 掌握栈和队列的常见应用

3.串、数组和广义表

(1) 掌握串的定义、存储，理解串的模式匹配算法

(2) 掌握数组的定义、存储、特殊矩阵的压缩存储方法

(3) 掌握广义表的定义和基本操作

4.树和二叉树

(1) 掌握树的定义和基本术语

(2) 掌握二叉树的定义、性质和存储结构、遍历操作

(3) 了解树和森林存储结构、遍历，掌握树和森林的转换

(4) 掌握哈夫曼树的基本概念、构造方法，掌握哈夫曼编码构造方法

5.图

(1) 掌握图的定义和基本术语

(2) 掌握图的邻接矩阵、邻接表存储结构

(3) 掌握图的遍历操作

(4) 掌握图的常见应用，包括最小生成树、最短路径、拓扑排序

6.查找

(1) 掌握查找的基本概念

(2) 掌握线性表的顺序查找、折半查找、分块查找算法

(3) 掌握二叉排序树、平衡二叉树的定义和基本操作

(4) 掌握散列表的基本概念、构造和查找方法以及处理冲突的常用方法

7.排序

(1) 掌握排序的基本概念和算法效率的评价指标，了解常见排序算法的基本性能

(2) 掌握直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序算法

(3) 掌握希尔排序、堆排序、二路归并排序、链式基数排序基本思想

二、试卷题型结构

主要题型：选择题、填空题、综合题、算法设计题，共150分。

三、试卷分值及考试时间

考试时间 180分钟，满分150分。