《算法与数据结构实践教学考试大纲》.doc

算法与数据结构实践教学考试大纲算法与数据结构实践教学考试大纲第一部分第一部分 课程性质与设置目的课程性质与设置目的一、课程性质与特点一、课程性质与特点算法与数据结构（实践） 课程是与算法与数据结构课程所对应的一 门实践课。通过本课程的学习，使应考者能够全面理解算法与数据结构在实际 应用中的地位和作用，熟练掌握算法设计与分析中的基本概念和基本设计与分 析方法，熟练掌握运用数据结构进行程序设计的基本方法和基本技能，培养将 原理应用于实际的能力，提高软件设计、算法应用、编程及调试的综合素质， 为今后的应用软件编程打下坚实的基础。二、课程目标与基本要求二、课程目标与基本要求本课程设置目的是使学生学会合理地组织数据、有效地表示数据和有效地 处理数据，培养和训练学生能够根据实际问题的要求选择和设计合适的数据结 构，编写质量高、风格好的应用程序，并具有初步的算法设计分析能力。 本课程的基本要求及达到如下目标： （1）掌握线性结构、树形结构和图形结构等基本数据结构及算法的应用； （2）掌握分治技术、贪心技术、回溯和分支限界等经典算法设计技术及应 用； （3）熟练掌握搜索算法和排序算法的应用； （4）具备应用算法与数据结构开发简单应用软件的能力。三、与本专业其他课程的关系三、与本专业其他课程的关系本课程是计算机科学与技术专业必修课，它对提高学生的程序设计和算法 设计与分析能力具有十分重要的作用。本课程的先修课程有高级语言程序设计、 离散数学等。第二部分第二部分 考核内容与考核目标考核内容与考核目标一、学生应达到的实验能力和标准一、学生应达到的实验能力和标准（1）学会数值计算与非数值计算中的抽象数据类型：表、栈、队列、串、 树、图及其相关的操作； （2）掌握排序和查找算法以及算法的简单分析，并能在计算机上实现有关 的算法； （3）掌握常用的数据结构，掌握合理地组织数据结构和表示数据的方法； （4）掌握有效地处理数据的方法；掌握评价算法性能的基本方法。二、考核知识点与考核目标二、考核知识点与考核目标实验一实验一 顺序表的应用顺序表的应用（一）实验内容 1. 创建和销毁顺序表存储结构。2. 实现顺序表的基本操作，如插入、删除、查找和遍历等。 3. 顺序表的简单应用，如分数统计、有序表的查找与合并、字典比较等。 （二）考核知识点及考核要求 1. 创建和销毁顺序表存储结构，要求达到“熟练掌握”层次。 2. 实现顺序表的基本操作，要求达到“熟练掌握”层次。 3. 顺序表的简单应用，要求达到“基本掌握”层次。实验二实验二 链表的应用链表的应用（一）实验内容 1. 创建和销毁链表存储结构。 2. 实现链表的基本操作，如插入、删除、查找和遍历等。 3. 链表的简单应用，如约瑟夫环、集合求并、一元多项式相加等。 （二）考核知识点及考核要求 1. 创建和销毁链表存储结构，要求达到“熟练掌握”层次。 2. 实现链表的基本操作，要求达到“熟练掌握”层次。 3. 链表的简单应用，要求达到“基本掌握”层次。实验三实验三 栈和队列的应用栈和队列的应用（一）实验内容 1. 创建和销毁栈和队列的存储结构。 2. 实现栈和队列的基本操作，如入栈、出栈、入队、出队、取栈顶和队头 元素等。 3. 栈和队列的简单应用，如停车场管理、配对问题、算术表达式求值、迷 宫问题等。 （二）考核知识点及考核要求 1. 创建和销毁栈和队列的存储结构，要求达到“熟练掌握”层次。 2. 实现栈和队列的基本操作，要求达到“熟练掌握”层次。 3. 栈和队列的简单应用，要求达到“基本掌握”层次。实验四实验四 树和二叉树的应用树和二叉树的应用（一）实验内容 1. 创建和销毁二叉树的存储结构。 2. 实现二叉树的基本操作，如查找和遍历等。 3. 二叉树的简单应用，如线索二叉树、哈夫曼树和表达式树等。 4. 树转化为二叉树的存储结构的创建和销毁。 5. 树与森林的遍历算法。 6. 树的简单应用，如因特网查询等。 （二）考核知识点及考核要求 1. 创建和销毁二叉树的存储结构，要求达到“熟练掌握”层次。 2. 实现二叉树的基本操作，要求达到“熟练掌握”层次。 3. 二叉树的简单应用，要求达到“熟练掌握”层次。 4. 树转化为二叉树的存储结构的创建和销毁，要求达到“基本掌握”层次。5. 树与森林的遍历算法，要求达到“基本掌握”层次。6. 树的简单应用，要求达到“基本掌握”层次。实验五实验五 图的应用图的应用（一）实验内容 1. 图的邻接表和邻接矩阵存储结构的创建和销毁。 2实现图的基本操作，如查找和遍历等。 3图的应用，如最小生成树、单源最短路径、拓扑排序等。 （二）考核知识点及考核要求 1. 图的邻接表和邻接矩阵存储结构的创建和销毁，要求达到“熟练掌握” 层次。 2实现图的基本操作，要求达到“熟练掌握”层次。 3图的应用，要求达到“基本掌握”层次。实验六实验六 散列表的应用散列表的应用（一）实验内容 1. 散列表存储结构的创建和销毁。 2实现散列表的基本操作，如插入、删除和查找等。 3解决散列冲突方法的应用，如开放地址法和链地址法等。 （二）考核知识点及考核要求 1. 散列表存储结构的创建和销毁，要求达到“熟练掌握”层次。 2实现散列表的基本操作，要求达到“熟练掌握”层次。 3解决散列冲突方法的应用，要求达到“基本掌握”层次。实验七实验七 排序的应用排序的应用（一）实验内容 1插入排序的应用，如直接插入排序、有序表排序等。 2交换排序的应用，如冒泡排序、快速排序等。 3选择排序的应用，如直接选择排序、堆排序等。 4归并排序的应用，如二路归并排序等。 （二）考核知识点及考核要求 1插入排序的应用，要求达到“熟练掌握”层次。 2交换排序的应用，要求达到“熟练掌握”层次。 3选择排序的应用，要求达到“熟练掌握”层次。 4归并排序的应用，要求达到“熟练掌握”层次。实验八实验八 典型算法的应用典型算法的应用（一）实验内容 1分治算法的应用，如静态二分查找、顺序统计和二叉排序树等。 2贪心算法的应用，如会议日程安排、0/1 背包问题等。 3动态规划算法的应用，如最长公共子序列、关键路径等。 4回溯与分支限界算法的应用，如迷宫问题、旅行售货员问题等。 （二）考核知识点及考核要求 1分治算法的应用，要求达到“基本掌握”层次。 2贪心算法的应用，要求达到“基本掌握”层次。3动态规划算法的应用，要求达到“基本掌握”层次。 4回溯与分支限界算法的应用，要求达到“基本掌握”层次。第三部分第三部分 有关说明与实施要求有关说明与实施要求一、指定教材一、指定教材数据结构与算法 黄国兴 等 编著 机械工业出版社 2004 年版二、自学方法指导二、自学方法指导（1）在开始阅读教材之前，先翻阅大纲中有关的考核知识点及对知识点的 能力层次要求和考核目标。 （2）学习教材时，要逐段细读，逐句推敲，集中精力，吃透每一个知识点， 对基本概念必须深刻理解，对基本理论必须彻底弄清，对基本方法必须牢固掌 握。 （3）在自学过程中，既要思考问题，也要做好阅读笔记，把教材中的基本 概念、原理、方法等加以整理，这可从中加深对问题的认知、理解和记忆，以 利于突出重点，并涵盖整个内容，可以不断提高自学能力。 （4）完成书后作业和适当的辅导练习是理解、消化和巩固所学知识，培养 分析问题、解决问题及提高能力的重要环节，在练习过程中对所学知识进行合 理的回顾与发挥，注重理论联系实际和具体问题具体分析，解题时应注意培养 逻辑性，针对问题围绕相关知识点进行层次（步骤）分明的论述或推导，明确 各层次（步骤）间的逻辑关系。三、考核要求三、考核要求本课程的考核分为中期考核和期末考核，中期要求达到对所学内容的初步 掌握，要求能够写出实验报告，并能对所学的内容进行较全面的论述和简单的 计算。 期末考核要求进行系统的应用和综合性的计算。四、题型示例四、题型示例（一）简单应用题 应用循环队列编写一个打印二项式系数表（即杨辉三角形）的算法。（二）综合应用题 设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77 采用哈希函数 H（key）=key MOD 13，并采用开放地址的线性探测再散列 方法解决冲突，试编程实现在 018 的散列地址空间中对该关键字序列构造哈 希表（要求有计算过程） ，并求出在等概率情况下，查找成功时的平均查找长度。