一、 题型(填空 2*15 应用题 5*10 算法设计题 2*10)
算法设计题,包括书上定义的各类的方法,以及自己添加的类方法或调用类的外部函数。
有30分左右的英文题目,答题可全部用中文。
b) 书后习题及补充习题,特别是做过的习题,
课件和做过的习题答案已全部放在实验平台上可供下载192.168.131.161。
c) 实验题中的一些算法实现
1、计算某一条语句执行次数
2、时间复杂度计算。
3、hedge
1、栈的抽象数据类型定义和基本操作,ADT 定义的两个部分。
2、线性表和数组区别
3、 栈的特点、性质(LIFO, overflow, underflow, push, pop后栈的状态)、双栈共享空
间、利用栈的方法实现栈的其他操作的算法,如:copy_stack 等。
4、栈类定义及顺序实现(包括各个方法的具体实现)
5、逆波兰式计算器、括号匹配等应用
1、掌握队列的抽象数据类型定义和基本操作、扩展的队列操作。
2、队列的特点、性质(FIFO,入队、出队后不改变原序列)
3、队列的类定义及顺序实现,顺序队列产生的问题!如何解决?
4、利用循环队列产生的问题(队空队满条件相同的问题)?有哪些解决方案?
5、循环队列实现算法。(包括各个方法的具体实现)
2、 不使用safeguards的链栈(链队列,链表),可能会产生的一些问题剖析!如垃圾的累
积,破坏封装特性等问题!举例说明?P131-136,分析算法中的错误。
3、链栈类定义、具体实现(包括各个方法的具体实现)
4、链队列定义、具体实现(包括各个方法的具体实现)
1、什么是递归,递归的种类,栈与函数调用,什么是调用记录
2、汉诺塔算法实现过程
3、 两种单链表的方法实现。改进版中current,current_postion的作用,mutable的含义