2020年东北电力大学计算机学院初试

1、初试科目考试大纲“数据结构 ”考试大纲一、考试的学科范围数据结构课程教学（大纲）基本要求的所有内容。二、评价目标主要考查考生对数据结构课程的基础理论、基本知识掌握和运用的情况， 要求考生应掌握以下有关知识：1. 数据结构的基本概念：理解数据结构的基本概念和常用术语，掌握算法的 定义及特性，了解分析算法的时间复杂度和空间复杂度的方法。2. 线性表：理解线性表的基本概念；掌握顺序表的各种基本操作；掌握单链 表、双向链表的特点及各种基本操作；会运用线性表解决实际问题。3. 栈和队列：理解栈的定义及其基本运算；掌握顺序栈和链栈的特点及各种 操作实现；理解队列的定义及其基本运算；掌握循环队列的特点和各种

2、操作实 现；会运用栈和队列解决实际问题。4. 数组和广义表：理解数组和广义表的基本概念；掌握二维数组的存储结构 和稀疏矩阵的压缩存储方法。5. 树和二叉树：理解树和二叉树的概念；掌握二叉树的性质；掌握二叉树的 存储结构以及在该存储结构下各种基本操作的实现；掌握树、森林与二叉树之 间的转换关系；掌握哈夫曼树的定义与应用。6. 图：理解图的基本概念；掌握图的邻接矩阵和邻接表的存储结构；掌握图 的深度、广度优先搜索算法的基本思想；理解最小生成树的概念；掌握最短路 径算法的实现思想；掌握拓扑排序的概念及算法实现思想。7. 查找：理解查找的基本概念；掌握顺序查找、折半查找、分块查找的特点 和方法；掌握二

3、叉排序树的构造和查找方法；了解平衡二叉树的构造和查找方 法；掌握哈希表的构造和查找方法。8. 排序：理解内部排序、外部排序、稳定排序、不稳定排序等概念；掌握直 接插入排序、冒泡排序、直接选择排序等简单的排序方法和特点；掌握希尔排 序、快速排序、堆排序和归并排序等高效排序方法和特点；了解基数排序的基 本思想。三、试题主要类型1.答题时间： 180 分钟2. 试题主要类型：选择题，简答题，解答题，算法题四、考查要点（一）数据结构的基本概念：1. 数据结构的基本概念。2. 算法的概念3. 算法分析方法（算法的时间、空间复杂度）（二）线性表：1. 线性表的概念2. 线性表顺序存储结构特点及运算算法3.

4、 线性表链式存储结构特点及运算算法4. 线性表的典型应用（三）栈和队列：1. 栈的定义及基本运算算法2. 队列的定义及基本运算算法3. 栈的典型应用4. 队列的典型应用四）数组和广义表：1. 数组的顺序表示和实现2. 矩阵的压缩存储3. 广义表的定义及其存储结构（五）树和二叉树：1. 树的定义及基本术语2. 树的表示3. 树的存储结构4. 二叉树的定义及性质5. 二叉树的存储结构6. 二叉树的遍历算法7. 线索二叉树8. 树、森林与二叉树的转换9. 哈夫曼树的构造方法及应用（六）图：1. 图的定义及基本术语2. 图的存储结构3. 图的遍历方法4. 图的联通性5. 图的最短路径算法6.A0V网与

5、拓扑排序7.A0E网与关键路径（七）查找：1 .查找的基本概念2. 静态查找的顺序查找、折半查找、分块查找算法3. 动态查找表的基本概念4. 二叉排序树的构造方法及查找5. 平衡二叉树查找6. 哈希法查找（八）排序：1 .排序的基本概念2 .直接插入排序的基本思想和特点3 .希尔排序的基本思想和特点4. 折半插入排序的基本思想和特点5. 冒泡排序的基本思想和特点6 .快速排序的基本思想和特点7. 简单选择排序的基本思想和特点8. 堆排序的基本思想和特点9 .归并排序的基本思想和特点10. 基数排序的基本思想和特点11. 各类排序算法的时间空、间复杂度的比较五、主要参考书目1. 曲朝阳主编，数据

6、结构，北京：中国电力出版社2. 严蔚敏主编，数据结构，北京：清华大学出版社 2016“程序设计方法 ”考试大纲一、考试的学科范围程序设计方法课程考试的主要内容：数据类型及其运算、基本语句、顺序 程序设计、选择结构程序设计、循环结构程序设计、数组、函数、指针、结构 体、文件。二、评价目标主要考察C语言程序设计的基础知识，数据类型定义及使用，顺序程序设 计、选择结构程序设计和循环结构程序设计方法，数组定义及使用，函数定义 及调用，指针定义及使用，结构体以及文件操作。要求理解和掌握 C语言程序 设计的基本方法和基本技能，编写和调试程序的能力。要求考生应掌握以下有 关知识：1、介绍程序设计的基本思想、

7、基本要求，掌握算法的基本知识，数据类 型；2、掌握顺序结构程序的设计；3、掌握选择结构程序的设计；4、掌握循环结构程序的设计；5、掌握一维数组、二维数组的使用方法；6、掌握函数的定义、函数的调用方法；7、熟悉指针的含义，指针的重要性，学会数组指针的定义和使用方法；8、熟悉结构的定义、引用和初始化方法；指向结构体类型数据的指针的定义和 使用方法； 9、了解文件定义，文件操作命令，打开、关闭、读写、定位、出错 检测等。三、试题主要类型1、答题时间： 180 分钟2、程序设计方法试题类型：选择题、填空题、编程题四、考查要点（一）数据类型及其运算1. C的数据类型及其定义方法2. C运算符的种类、运算

8、优先级和结合性3. C 表达式类型（赋值表达式、算术表达式、关系表达式、逻辑表达式、条 件表达式、逗号表达式）（二）基本语句1. 表达式语句，空语句，复合语句2. 数据的输入与输出，输入输出函数的调用3. 顺序结构程序设计（三）选择结构程序设计1用if语句实现选择结构2. 用 switch 语句实现多分支选择结构3. 选择结构的嵌套4. 选择结构程序设计（四）循环结构程序设计1. for 循环结构2. while和do while循环结构3. 循环的嵌套4. 循环结构程序设计（五）数组的定义和引用1. 一维数组和二维数组的定义、初始化和引用2. 字符串与字符数组3. 数组的应用（六）函数1. 函数的定义方法2. 函数的类型和返回值3. 形式参数与实在参数，参数值的传递4. 函数的正确调用，嵌套调用，递归调用（七）指针1.指针与指针变量的概念，指针与地址运算符2.变量、数组、字符串、函数、结构体的指针以及指向变量、数组、字符串 指针变量3. 用指针作函数参数4. 指针应用（八）结构体1.结构体类型数据的定义方法和引用方法2.单向链表的建立、输出（九）