复习内容教材，教材作业，实验手册（上机实验、选择填空题），算法.doc

复习内容： 教材，教材作业，实验手册（上机实验、选择填空题），算法（要求的） ●算法的概念：解题方案的准确而完整的描述。 ●算法应具备的特性（详细解释） （1）可行性 （2）确定性 （3）有穷性 （4）拥有足够的情报 ●算法设计基本方法（举例说明）： 1. 列举法（穷举法、枚举法）（百钱买百鸡，水仙花数） 2. 枚举归纳法（波利亚归纳模式，通过观察得出规律，证明规律） 3. 递推（Fibonacci数列，牛顿迭代法求一个数的平方根） 4. 递归（典型问题：汉诺塔Tower of Hannoi） 5. 减半递推（二分法求方程的根，折半查找，矩阵相乘） 6. 回溯法（八皇后问题） 会按照算法，手工摆出n皇后问题的若干个解，如5皇后问题的第1个解是 1，3，5，2，4 …… ooooo ●算法的复杂度分析：时间的复杂度和空间的复杂度的概念 时间的复杂度：用算法在执行过程中所需基本运算（即主要运算）的次数来度量算法的工作量。 空间的复杂度：计算时所需内存容量。 掌握平均性态和最坏情况复杂度的分析方法，对以下两个问题会分析： （1）顺序查找 （2）求三个数的中间值 ●数据结构的定义：描述一组数据元素及元素之间的相互关系。数据结构的两个要素：数据元素的集合，数据集合上的关系。 关系的表示：二元组、图 ●逻辑结构：线性结构和非线性结构 ●物理存储结构：顺序存储结构和链式存储结构（实际使用时，往往两种结合使用，如图的邻接表表示，外链hash表，索引查找表） ●逻辑上的线性结构可以采用的顺序存储结构和链式存储结构（举例：线性表） 逻辑上的非线性结构可以采用链式存储结构，也可以采用的顺序存储结构和链式存储结构（举例：完全二叉树） 逻辑结构： 线性 非线性 存储结构： 顺序 链接 如：完全二叉树是非线性结构，但可以使用顺序存储 ●线性表：实验1.1 线性表的插入、删除算法（自然语言描述也可以） ●堆栈的概念及特点: 入栈，出栈操作 堆栈的物理实现：数组，链表。 应用: （1）函数递归及嵌套调用的实现 （2）简单表达式的处理，会画出处理表达式各步 OPS 栈和 OVS 栈的变化。 ●队列的概念及特点 队列的物理实现：数组，链表。 用数组实现循环队列：入队、退队的实现。 特点：rear指向队尾，front指向队首前一个元素。 问题：设循环队列的容量为50（序号从1到50），现经过一系列的入队与退队运算后，有： front=11, rear=22 front=26, rear=15 问在这两种情况下，循环队列中各有多少元素？ 答： 22-11 ＝ 11个元素 50－26＋15 ＝ 39个元素 ●线性链表：基本运算 创建链表 /* 教材 */ 插入元素 /* 教材 */ 删除元素 /* 教材 */ 释放链表 /* 教材 */ 逆转 /* 作业 */ 合并两个线性表 /* 作业 */ ●链表的应用：用循环链表实现的多项式的创建、相加算法 见实验1.3 ●数组：二维数组以行（或列）为主的顺序存放，物理上存储成一维数组。 逻辑：二维数组A， 物理：一维数组B 问题：给出i和j，如何从一维B数组中得到aij的值 aij —— b[k] 若A数组M行，N列，假定行号和列号都是从1开始，则k = (i-1)*N+j ●下三角矩阵和三对角线矩阵（带状矩阵）的压缩存储（按行存放） A[M][N] = B[ ] 同样的问题：给出i和j，如何从一维B数组中得到aij的值 aij --- b[ ? ] （1）下三角矩阵，公式： B[ (i-1)*i/2 + j ] j≤i 0 j＞i aij = 问题：若是按列存放，或上三角矩阵呢？ （2）三对角线矩阵（带状矩阵），公式： aij = B[2(i-1)+j] |i-j|≤1 0 其他 ●稀疏矩阵的表示，以下两种均为压缩存储方法，即只存储非0元素的值。 （1）三列两维数组B[ ] 要理解设置 NUM[ ] 和 POS[ ] 数组的含义。 目的：已知B[ ], i, j, NUM[ ], POS[ ]，求出A(i,j)的值。 写出访问A(i,j)的函数，参数是B[ ], i, j, NUM[ ], POS[ ]，返回值是A(i,j)。 取得aij元素值的过程：从B数组的POS[i]位置开始，顺序查找NUM[i]个元素，即顺序比较i和j的值是否等