2019年陕西师范大学硕士研究生考试大纲856-数据结构与程序设计.pdf

陕西师范大学硕士研究生招生考试“856-数据结构与程序设计”考试大纲本《数据结构与程序设计》考试大纲适用于陕西师范大学计算机学科各专业硕士研究生招生考试。数据结构与程序设计是大学计算机学科本科学生的核心课程而且也是其他理工专业的热门选修课。它的主要内容包括线性、树型、图型这些基本数据结构及其相关算法以及查找和排序的典型算法和算法的时间复杂度和空间复杂度分析。要求考生掌握基本的数据结构和经典算法具备对实际问题进行分析抽象出表达实际问题的数学模型设计出解决问题的算法能灵活运用程序设计技术实现相应算法具有分析问题、解决问题的能力。一、考试的基本要求要求考生比较系统地掌握数据结构与程序设计的基本概念和理论不仅能解答基础知识题且能综合运用所学的基本数据结构和程序设计技术给出相应实际问题的解决方案具备对实际问题进行分析抽象出计算机加工的数据对象及其间的关系能选择的合适的数据结构表达应用问题并选择合适的存储结构实现相应的程序设计解决实际应用问题。要求考生具有计算机专业学生的基本素质具有良好的程序设计风格能综合运用所学的基本数据结构和程序设计知识分析问题、解决问题。二、考试方法和考试时间数据结构与程序设计考试采用闭卷笔试形式试卷满分150分考试时间180分钟。三、考试内容（一）数据结构概述1．数据结构的基本概念以及相关术语；2．数据结构的抽象数据类型表示与实现；3．算法的基本概念及设计要求；4．算法的时间复杂度和空间复杂度分析。（二）线性表1．线性表的类型定义、基本算法以及集合运算等应用问题的解决方案；2．线性表的顺序表示和实现及集合运算等应用问题的解决方案的顺序表实现；3．线性表的链式表示和实现及集合运算等应用问题的解决方案的单链表实现；4．一元多项式的表示及相加即一元多项式的单链表加法算法实现。（三）栈和队列1．栈的类型定义；2．栈的顺序存储表示和栈的基本操作在顺序栈的实现；3．栈的链式存储表示和实现；4．队列的类型定义；5．队列的链式存储表示和实现；6．队列的顺序存储表示和实现。（四）串1．串的类型定义；2．串的表示和实现；3．串的模式匹配算法。（五）数组和广义表1．数组的定义；2．数组的顺序表示和实现；3．矩阵的压缩存储；4．广义表的定义；5．广义表的存储结构；6．m元多项式的表示；7．广义表的递归算法（六）树和二叉树1．树的定义和基本术语；2．二叉树的定义及性质；3．二叉树的二叉链表存储结构；4．遍历二叉树和线索二叉树；5．树的各种存储结构；6．树、森林与二叉树的转换；7．树和森林的遍历；8．哈夫曼树及其应用；9．回溯法与树的遍历；（七）图1．图的类型定义；2．图的存储结构；3．图的遍历；4．图的连通性问题；5．拓扑排序及关键路径；6．最短路径。（八）查找1．查找表的相关概念；2．顺序表的查找：算法与分析；3．有序表的查找：折半查找判定树及其查找分析等；4．索引顺序表的查找：算法与分析；5．动态查找表的类型定义：二叉排序树的构造、插入、删除等算法；6．平衡二叉树；7．哈希表：哈希函数与、处理冲突的方法查找分析。（九）内部排序1．排序的定义；2．排序方法的分类；3．插入排序；4．快速排序；5．选择排序；6．归并排序；7．基数排序；8．各种内部排序方法的比较。（十）程序设计1．顺序结构程序设计；2．选择结构程序设计；3．循环控制；4．指针、动态内存分配；5．数组、结构体；6．函数、类型定义等基本预编译命令。四、掌握重点（一）算法的时间复杂度和空间复杂度分析；（二）线性表、栈、队列、串、数组的表示、基本算法实现和应用；（三）串的模式匹配算法。