想坚持每天学英语的必看

想坚持每天学英语的必看 2008年《数据结构与算法》期中复习提要 1. 考试时间和地点(再通知) 2. 考试题型 填空、辨析与简答、算法填空、算法设计和实现 注意: (1)算法语言无所谓，只要能看懂。考试用C++出题，但答题随意(可以用C/C++、Java、Pascal、自然语言等等，看得懂就可以)。 (2)如果要求自己独立地写算法(而不是填空)，请注意写算法思想，并加上足够的注释。 (3)对于算法中直接使用的类和函数(例如栈、队列的函数)，应该先写ADT，并简单说明算法中用到的重要函数的功能、入口参数、出口参数。 3. 考试范围和重点 各章节以下面的内容为复习重点，尤其是?标出部分为重中之重。考试时如果涉及到本大纲没有列出的内容，那么中会给出足够的定义和性质。 4. 考场安排和注意事项 1) 没有正式选课的旁听同学，请不要来考场。 2) 请随身带好您的学生证(或其他可以证明身份的证件)，笔和涂改工具参加考试。 3) 考试形式为闭卷，可以使用计算器。 4)考前10分钟，请大家把书包、课本、讲义、作业本、自带的草稿纸等放在教室前面的讲台和窗台上，只需要留下学生证(或其他可以证明身份的证件)，笔和涂改工具。教室清理干净后，可以提前5分钟发放试卷(带有草稿纸和答题纸，可以撕下来)，从前排向后排发放。注意在试卷纸和有效答题纸上写上姓名和学号，并且一定要在试卷纸的诚实答题宣言旁边的姓名和学号栏签名(否则，试卷计零分)。 5) 我们统一发草稿纸，不够可以随时举手要。 6) 请大家注意考场纪律，不要交头接耳，私下讨论。考试时对试题有疑问，可以举手，待监考老师来到旁边时，再请向监考老师询问。 7)考试时间为120分钟，中间不休息。提前15分钟提醒大家整理试卷，注意写好姓名和学号。 8) 监考老师宣布“考试时间到”以后，请大家停笔(不停笔的同学，监考老师有权没收试卷并宣布作废)，把草稿纸和答题纸 放在试卷上面，使姓名和学号朝外(诚实答题宣言旁边的姓名和学号朝向最外面)，对折以后放在桌面上。监考老师收卷清点无误，并宣布“全班同学都可以离开了”以后方可集体离开。注意，不要把试卷题带出考场，否则将计零分。 9) 提前交卷的同学，把试卷交到讲台上，并收拾好自己的东西，迅速离开考场。 第1章 概论 一. 重要概念 1. 数据类型 2. 抽象数据结构 3. 数据结构 4. 存储结构 5. 算法 6. 算法度量(时间代价、空间代价) ? 7. 数据结构的选择和评价 二. 方法 1. 根据二元组画出图示逻辑结构(注意边的方向) ? 2. 根据要求设计数据结构 3. 算法度量的大O表示法的简化法则(不要求掌握大Ω、大Θ表示法) 第2章 线性表 一. 概念 1. 线性表 2. 单链表 3. 双链表 4. 循环表 5. 栈 6. 队列 7. 循环队列 二. 方法 1. 线性表的运算(指针操作的正确性) ? 2. 循环队列队列的实现 ?3. 表达式求值(中缀表达式转后缀表达式的算法、后缀表达式求值算法) 4. 栈的性质，用栈来生成序列 第3章 字符串 一. 概念 1. 串 2. 模式匹配 二. 方法 1. 串的基本操作 2. 串的存储 ? 3. 串的KMP快速模式匹配算法，求特征向量数组(N数组)和利用N向量完成匹配的方法 第4章 二叉树 一. 概念 1. 二叉树 2.二叉树的前序、中序、后序周游 3. 二叉排序树 4. Huffman树、Huffman编码 5. 堆、堆排序 二. 方法 1(二叉树的链式存储 (1)二叉链表 (2)带父指针的三重链表 2. 二叉树的顺序存储 完全二叉树的顺序存储 ? 3. 二叉树的深度优先周游。要求自己能用递归解决二叉树应用问题，看得懂非递归二叉树周游框架、可以完成采用非递归算法设计的算法填空 4. 二叉检索树的插入与删除 ? 5. 构造Huffman树，利用Huffman树进行编码、解码 6. 堆排序的建堆过程 第5章 树 一. 概念 1. 树、森林 2. 树的先根周游、后根周游、层次周游 二. 方法 ? 1. 树林与二叉树相互转换 2(森林的链式存储 ? (1) 转换为相应的二叉树，用二叉链表表示 (2) 父指针表示法 (3) 子结点表表示法 (4)等价类和并查算法的应用 ? 3. 森林的深度优先周游(递归)，可能结合应用 ? 4. 森林的顺序存储 不必死记各种顺序存储方法，要了解原理。其本质是按照周游的性质，把顺序存储的森林信息反构造成森林(在内存中往往用二叉树来表示) 5. 二叉树和森林的层次周游(用队列)，可能结合应用