中山大学南方学院2017年插本数据结构与算法.docxVIP

2017年中山大学南方学院专插本《数据结构与算法》专业课程考试大纲考试科目名称：数据结构与算法一、考试性质普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。该考生所包含的内容将大致稳定，试题形式多种，具有对学生把握本课程程度的较强识别、区分能力。二.考试内容及要求一、考试基本要求通过数据结构与算法理论的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术;配合算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，对理论和实践的操作使学生得到全面的领会和深刻的认识。二、考核知识点及考核要求本大纲的考核中，按照“识记”、“领会”、“简单应用”和“综合应用”等四个层次规定应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是：识记：要求考生知道有关的名词、概念、原理、知识的含义，并能正确认识或识别。领会：要求在识记的基础上，能把握相关的基本概念、基本原理和基本方法，掌握有关概念、原理、方法的区别与联系。简单应用：要求在领会的基础上，运用所掌握的基本概念、基本原理和基本方法中的少量知识点，分析和解决一般的理论问题或实际问题。综合应用：要求在简单应用的基础上，运用学过的多个知识点，综合分析和解决比较复杂的实际问题。第1章绪论一、考核知识点1、数据结构的基本概念2、抽象数据类型的表示和实现3、算法的概念和特性4、算法时间复杂度和空间复杂度分析二、考核要求1、识记(1)数据结构的研究内容2、领会(1)抽象数据类型的表示和实现(2)算法的定义和特性(3)评价算法优劣的基本标准3、简单应用(1)简单数据结构的程序设计(2)简单数据结构程序的时间复杂度和空间复杂度分析4、综合应用(1)数据结构的一些基本概念(2)算法的时间复杂度分析第2章线性表一、考核知识点1、线性表的类型定义2、线性表的顺序表示和实现3、线性表的链式表示和实现4、线性表的应用二、考核要求1、识记(1)线性表的定义(2)线性表的特点2、领会(1)线性表的抽象数据类型定义3、简单应用(1)线性表的顺序存储和基本操作实现(2)单链表的存储和基本实现(3)双链表的存储和基本实现(4)一元多项式的表示和基本运算4、综合应用(1)一般线性表的合并(2)有序表的合并第3章栈和队列一、考核知识点1、栈的类型定义2、栈的存储结构表示和实现3、栈与递归的实现4、队列的类型6、队列的存储结构标识和实现二、考核要求1、识记(1)栈的类型定义(2)队列的类型定义2、领会(1)栈的存储结构表示和实现(2)队列的存储结构标识和实现3、简单应用(1)表达式求值(2)打印杨晖三角形(3)迷宫求解问题(4)模拟汽车加油站问题第4章串、数组和广义表一、考核知识点1、串的表示和实现2、数组的存储方法3、特殊存储结构4、广义表的逻辑结构和存储结构二、考核要求1、识记(1)串的表示和实现(2)数组的存储方法2、领会(1)特殊结构的存储方法(2)广义表的逻辑结构和存储结构3、综合应用(1)古典的模式匹配算法第5章树和二叉树一、考核知识点1、二叉树的定义和术语2、二叉树的性质，特殊的二叉树3、二叉树的存储结构，顺序存储和二叉链表4、二叉树的遍历(前序、中序、后序、层次)5、树和森林的定义，树的存储6、树、森林与二叉树的转换、7、树的应用，哈夫曼树和哈夫曼编码8、线索化二叉树二、考核要求1、识记(1)二叉树的定义(2)树和森林的定义2、领会(1)二叉树的术语(2)特殊的二叉树3、简单应用(1)二叉树的存储结构(2)线索化二叉树(3)树、森林和二叉树的转换4、综合应用(1)二叉树的性质(2)二叉树的遍历方法(3)哈夫曼编码第6章图一、考核知识点1、图的定义和术语2、图的存储结构(邻接表和邻接矩阵)3、图的遍历(深度优先和广度优先)4、构造最小生成树的短发5、拓扑排序和关键路径6、求最短路径问题二、考核要求1、识记(1)图的定义和术语2、领会(1)图的邻接矩阵表示法(2)图的邻接表表示法3、简单应用(1)图的遍历方法：深度优先遍历、广度优先遍历3、综合应用(1)最小生成树算法：普里姆算法、克鲁斯卡尔算法(2)拓扑排序和关键路径(3)最短路径问题算法：迪杰斯特拉算法、佛洛依德算法第7章查找一、考核知识点1、查找的基本概念2、基于线性表的查找3、基于树表的查找4、散列表二、考核要求1、识记(1)查找的基本概念(2)散列表的基本概念2、简单应用(1)顺序查找(2)折半查找(3)二叉排序树、平衡二叉树3、综合应用(1)散列函数的构造方法(2)处理冲突的方法(3)散列表的查找和分析第8章排序一、考核知识点1、排