算法课件复习课

1、数据结构与算法复习课王昭信息学院wangzhaoi要求时间:（三） 上午8：3010：30地点： 二教105wangzhao题型填空题（满分20分，超出20分按20分计）判断题（满分15分，超出15分按15分计）1.5分及1分两种题型选择题（满分15分，超出15分按15分计）问答题（18分）算法分析（功能或者对错分析）+算法填空（16分）算法设计题（16分）还未出题，以上只是参考，以实际为准wangzhao成绩考核“学生成绩=平时成绩(50%)+期末成绩(50%)”平时作业（一定要按时交）20%平时成绩50%随堂测验+考勤10%（由助教负责）上机20%期末成绩50%注重综合能力的考评，平时表现

2、突出、上机能力较强的(如完成附加题)可以得到加分，不超过5分。“优秀率(85分以上)原则上不超过30%，不及格率(60分以下)不超过15%。”4wangzhao答疑时间五）上午9：0011：30一）下午2：305：306月10日（6月13日（答疑地点：理科1号楼1530E也可以发邮件和在课程上答疑wangzhao第一章绪论学目：了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法教学重点：了解数据结构的逻辑结构、存储结构及数据的运算面的概念及相互关系教学难点：算法复杂度的分析方法。wangzhao知识点数据结构？数据、数据元素、数据对象四种逻辑结构四种结构注意各种算法？结构的主要特征算法

3、的五个重要特性？算法的设计要求。算法的时间效率、空间效率度量。时间效率的度量方法（基本操作的执行次数）空间效率的度量方法（额外辅助空间的数量）wangzhao第二章线性表教学目的：介绍线性表的逻辑结构和各种表示方法，以及定义在逻辑结构上的各种基本运算及其在结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的结构设计出相应的有效算法，解决与线性表有关的实际问题。教学重点：熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析教学难能够使用本章所学到的基本知识设计有效算法解决与线性表有关的应用问题。8wangzhao知识点线性结构特点顺序表顺

4、序表特点顺序表各种基本操作的实现、删除、查找、取值链表、删除等算法的时间效率度量链表的特点单链表的各种基本操作的实现、删除等算法的时间效率度量、删除、查找、取值和不结点的链表操作的不同循环、双向链表的、删除等操作的实现顺序表与链表的比较 优点、缺点9wangzhao第三章字符串教学目的：介绍字符串的概念、实现。表示以及基本运算的教学重点：字符串在顺序结构和结构中基本操作的实现。10wangzhao知识点字符串是一种线性结构，它是零或多个字符组成的有限序列。常用方式：顺序、结构；字符串在顺序结构和结构中基本操作的实现。模式匹配的概念和时间复杂度分析。朴素模式匹配算法简单，但由于回溯操作使得算法效

5、率低O(n*m)。wangzhao第四章栈与队列教学目的：是介绍栈和队列的逻辑结构定义及在两种结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下选择使用栈或队列。教学重点：是掌握栈和队列在两种运算教学难点：循环队列中对边界条件的处理。结构上实现的基本12wangzhao知识点栈、队列的操作受到什么限制？栈、队列的操作规则是什么？栈、队列的、删除等基本操作的实现顺序栈、链栈顺序队列环形队列、链队列 各种栈、队列的判空、判满条件、删除操作的实现等环形队列的、删除操作13wangzhao栈与递归问题函数调用函数的过程调用、返回递归如何实现的？栈结构在递归中如何应

6、用的？栈的应用：表达式的计算数制转换扩号匹配14wangzhao第五章树与二叉树教学目的：介绍树的定义、结构、遍历，二叉树的定义、性质、结构、遍历，树和森林与二叉树的转换，树及编码等内容。教学重点：要求在熟悉这些内容的基础上，重点掌握二叉树的遍历算法及其有关应用。教学难：使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。wangzhao知识点树结构的特点树与森林的遍历方法树的表达方法 双亲、孩子、孩子-兄弟二叉树结构的特点二叉树的8个重要性质二叉树的表达方法 顺序表示中如何确定孩子、双亲？堆二叉、三叉链表wangzhao二叉树的三种深度优先遍历方法（DLR, LDR, L

7、RD)和广度优先遍历方法递归二叉树的生成树、二叉树之间的转换Huffman树及其Huffman编码wangzhao第六七章字典与检索教学目的：是介绍字典的线性表表示、二叉树表示和散列表表示。教学重点：要求在熟悉这些内容的基础上，重点掌握顺序查找、二分查找，二叉排序树上查找以及散列表上查找的基本算法实现。和教学难点：是二叉排序树的删除算法。wangzhao检索算法效率的度量标准静态字典与动态字典顺序表检索各种检索方法的、算法、效率顺序检索（不等概率情况下，如何提高顺序检索效率？）二分法检索用于有序顺序表分块检索（检索思、过程以及块内采用不同检索下的时间效率）wangzhao散列表检索常用的散列函

8、数与散列函数的选择散列表的构造与检索碰撞的处理方法检索效率与那些有关？二叉排序树 特点，检索、删除算法 最佳二叉排序树,基本概念,等概的情况wangzhao 各种检索方法的应用范围 各种检索方法的ASL 哪种检索方法与问题规模n无关？ 分块检索如何实现的，块索引如何建立的？块间采用顺序检索和二分法检索最后的ASL值分别是多少？如何分块效率最高？ 不等概率下，如何提高顺序检索的效率？ 二叉排序树为动态字典的合适表达？wangzhao第八章排序教学目的:是介绍五类排序方法的基本、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。教学重点:要求在熟悉这些内容的基础上，重点掌握快速

9、排序、堆排序、归并排序和分配排序的基本程教学难点:本章难点是这四个排序算法的实现。wangzhao及排序过知识点、算法、时间效率度量（注意最好、以及实现排序、平均等）、S直接直接、折半排序中、表排序的比较、移动，特点。排序的改进，如何改进的？其它都是对直接选择排序 直接选择、堆排序（时如何调整？）堆，初始堆如何建立？非堆wangzhao交换排序 起泡排序的、算法、时间效率分析； 快速排序如何改进起泡的，分配排序情况如何改进？基数排序什么情况下，效率高？归并排序（两个有序表合并的应用）两组归并一趟归并归并wangzhao排序算法之间的比较主要考虑以下几个方面算法的时间复杂度算法的辅助空间排序的稳

10、定性算法结构的复杂性 参加排序的数据的规模 和初始状态的相关性wangzhao特别注意各种排序方法的选择：思考的例题哪种排序方法的比较次数与初始状态无关？哪些排序方法可以不用各趟排序完成后就知道前面最大或最小的若干个排序码？待排序的哪种？序列基本有序时，效率最高的排序方法是给定一组排序码，写出前面12躺的排序结果。各种排序方法对内存的要求空间效率各种排序方法的稳定性下列各种情况，直接正序；逆序；排序至少需要多少次比较？wangzhaowangzhao排序方法平均时间复杂度辅助空间稳定性直接排序O(n2)O(1)稳定的二分法排序O(n2)O(1)稳定的表排序O(n2)O(n)稳定的S排序O(n1.3)O 1不稳定的直接选择排序O(n2)O(1)不稳定的堆排序O(nlog2n)O(1)不稳定的起泡排序O(n2)O(1)稳定的快速排序O(nlog2n)O(log2n)不稳定的基数排序O(d(n+r)O(r+n)稳定的归并排序O(nlog2n)O(n)稳定的第九章图教学目的：是介绍图的基本概念、两种常用的用算法。结构、两种遍历算法以及图的应教学重点：掌握在图的两种现的遍历算法。结构上实wangzhao知识点无向、有向图图中顶点个数、边（弧）数、