[研究生入学考试]2009计算机考研数据结构解析2.pdf

今后考试走向与应试指导 根据2009年考试分析和历年考试经验，可以对今后考 试走向作一个简单的预测： 单项选择题覆盖了考试大纲所列出的所有各章，主 要考查对各个数据结构的定义和特点的理解， 以及相应延伸的概念。 综合应用题分为两个部分：算法分析题和算法设计 题（编程题），主要考查分析问题和解决问题 的能力。算法分析题的重点在图、查找、排序 部分，算法设计题的重点在线性表、树与二叉 树、排序部分。 清航教育 建议复习参考教材 清航教育 建议复习参考教材 清航教育 各个章节的复习重点： 线性表 线性表的定义和特点：由数据元素组成，惟一直接 前驱与后继。 线性表的基本操作：查找、定位、遍历、插入、删 除。 线性表的存储表示：顺序存储、链表存储 顺序表的定义及基本运算（算法设计和算法分 析） 单链表的定义及基本运算（算法设计和算法分 析） 清航教育 特殊链表的定义和基本运算 线性表的特殊链接表示 循环链表的特殊遍历方式 双向链表的方向性：每个结点处于两个循环链 表（前驱、后继）中 线性表的应用 掌握使用线性表基本操作实现应用算法 一维数组中数组元素的原地逆置或非零元素压 缩 递归计算一维数组的长度、一维数组中所有元 素的和及平均值 清航教育 在顺序表中查找值为x的元素，在有序顺序表中 查找值为x的元素 在有序顺序表中插入新元素x到第i个位置 在有序顺序表中删除第i个元素 两个有序顺序表的合并，m 个有序顺序表的合 并 单链表的迭代求解算法及性能，包括 统计链表结点个数 在链表中寻找与给定值x 匹配的结点 在链表中寻找第i 个结点 在链表中第i 个位置插入新结点 清航教育 删去第i个结点 单链表各结点顺序逆转算法，在单链表中按 从左到右和从右到左的顺序遍历的逆转链 算法 带表头结点的单链表的迭代算法，包括 统计链表结点个数 在链表中寻找与给定值x 匹配的结点 在链表中寻找第i 个结点 在链表中第i个位置插入新结点 删去第i个结点 连续删除链表中含有x 值的结点 两个有序链表的合并。 清航教育 单链表的递归算法，包括 统计链表结点个数 在链表中寻找与给定值x 匹