一、 题型（填空2*15 应用题5*10 算法设计题2*10）
算法设计题，包括书上定义的各类的方法，以及自己添加的类方法或调用类的外部函数。
有30分左右的英文题目，答题可全部用中文。
二、 复习素材
a) 课件
b) 书后习题及补充习题，特别是做过的习题，
课件和做过的习题答案已全部放在实验平台上可供下载192.168.131.161。
c) 实验题中的一些算法实现
d) 本复习提纲
需下载的同学请至实验平台下载第7章“作业”。
第一章
1、计算某一条语句执行次数
2、时间复杂度计算。
3、hedge
第二章 栈
1、 栈的抽象数据类型定义和基本操作，ADT定义的两个部分。
2、 线性表和数组区别
3、 栈的特点、性质（LIFO, overflow, underflow, push, pop后栈的状态）、双栈共享空间、利用栈的方法实现栈的其他操作的算法，如：copy_stack等。
4、 栈类定义及顺序实现（包括各个方法的具体实现）
5、 逆波兰式计算器、括号匹配等应用
第三章 队列
1、 掌握队列的抽象数据类型定义和基本操作、扩展的队列操作。
2、 队列的特点、性质（FIFO,入队、出队后不改变原序列）
3、 队列的类定义及顺序实现，顺序队列产生的问题！如何解决？
4、 利用循环队列产生的问题（队空队满条件相同的问题）？有哪些解决方案？
5、循环队列实现算法。（包括各个方法的具体实现）
第四章 链栈和链队列
1、 链表结点类定义 p 123
2、 不使用safeguards的链栈（链队列，链表），可能会产生的一些问题剖析！如垃圾的累积，破坏封装特性等问题！举例说明？P131-136，分析算法中的错误。
3、 链栈类定义、具体实现（包括各个方法的具体实现）
4、 链队列定义、具体实现（包括各个方法的具体实现）
第五章 递归
1、 什么是递归，递归的种类，栈与函数调用，什么是调用记录
2、 汉诺塔算法实现过程
3、 递归算法递归树的画法
第六章 线性表和串
1、 线性表的概念和基本操作
2、 顺序线性表的类定义和实现。
3、 两种单链表的方法实现。改进版中current,current_postion的作用，mutable
的含义等。
4、 双向链表的实现算法。
5、 顺序存储和链式结构的优缺点比较和适用场合，如何在多种结构中选择？
6、 掌握串的概念、串的类定义和基本操作。P236-240,各构造函数的实现和调用时机，利用c串实现strcat，strncpy, strstr等操作。
第七章 查找
1、各种查找算法（顺序查找，带sentinel的顺序查找，2种二分查找）的递归算法和非递归算法实现
2、画比较树，利用查找树分析成功以及不成功时的平均比较次数（平均查找长度，Average Search Length, ASL ），时间复杂度分析和比较。
3、以关键字比较为基础的查找算法的最好性能O(lgn) Lower Bounds p300
第6章算法例题分析
1、 假设用带头结点、不带current指针的单链表作为线性表list的存储结构，为list添加一个成员函数，删除线性表中所有值为x的元素。
请按以下函数原型进行设计，其中count返回被删除的元素的个数。
template int List :: remove_all_x(const List_entry &x){Node *p,*q;int count=0;
p=head;
while (p->next)
{if (p->next->entry==x)
{q=p->next;
p->next=q->next;
delete q;
count++;
}
else
p=p->next;
return count;
}
假设用普通单链表作为线性表的存储结构，编写一线性表的方法，以判断该线性表的元素是否按值非递减有序排列。
