四川大学“精品课程” 计算机科学与技术专业（本科） 《数据结构与算法分析》课程 考试说明与模拟试卷 第一部分 考试说明 数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。由于本课程的主教材采用 C++语言描述算法，期末卷面考试也采用 C++语言描述，因而要求在做平时作业和上机实验操作时用 C++开发工具（如：Visual C++或 C++ Builder 或Borland C++）。 下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。 第一章 绪论 重点掌握的内容： 1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。 2. 集合结构、线 性 结构、树 结构和图结构的特 点。 3. 抽 象 数据类 型 的定 义 和表示方 法。 4. 一维 和二维 数组中元素 的按下标 和按地址 的访 问 方 式 以及相 互 转 换 ，元素 地址 和数组地址 的计算，元素 占 用存储空 间大小 和数组占 用存储空 间大小 的计算。 5. 普 通 函 数重载 和操作符 函 数重载 的含 义 ，定 义 格 式 和调 用格 式 。 6. 函 数定 义 中值 参 数和引 用参 数的说明格 式 及作用，函 数被 调 用执 行时对传 送 来 的实际 参 数的影 响 。 7. 算法的时间复杂 度 和空 间复杂 度 的概 念 ，计算方 法，数量 级 表示。 8. 一个 简 单 算法的最 好、最 差 和平均 这三 种情 况 的时间复杂 度 的计算。 对于本章的其 余 内容均 作一般 掌握。 第二章 线 性 表 重点掌握的内容： 1. 线 性 表的定 义 及判 别 和抽 象 数据类 型 的描述，线 性 表中每一种操作的功 能 ，对应的函 数名 、返 回 值 类 型 和参 数表中每个 参 数的作用。 2. 线 性 表的顺 序存储结构的类 型 定 义 ，即 List 类 型 的定 义 和每个 域 的定 义 及作用。 3. 线 性 表的每一种运算在顺 序存储结构上实现的算法，及相 应的时间复杂 度 。 4. 链 接 存储的概 念 ，线 性 表的单 链 接 和双 链 接 存储的结构，向 单 链 表中一个 结点之 后插入新结点或从单链表中删除一个结点的...
