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