计算机科学与技术考研 09计算机专业研究生入学考试：数据结构备考[2]

09计算机专业研究生入学考试：数据结构备考[2]  

　　二 知识点的重点和难点

　　在第一轮复习后 根据自己的理解 考生能体会到课程中知识点的重点和难点是下一轮成功复习的关键 笔者根据课程教学大纲的内容和往年部分高校数据结构考试题目的分析 对数据结构知识点的重点和难点进行了归纳 希望对复习备考的考生在复习的时候能起到引导作用

　　知识点的重点

　　①绪论部分的重点是算法时间复杂度和空间复杂度的度量;

　　②线性表部分的重点是线性表的插入 删除 逆置三个操作;

　　③栈和队列部分的重点是栈和队列的特点以及栈和队列的应用;

　　④字符串部分的重点是KMP匹配算法;

　　⑤数组和广义表在理解线性表的基本操作的基础上 重点以基本概念的掌握为主;

　　⑥树和二叉数的重点主要包含二叉树的五个性质 二叉树的排序 线索二叉树以及最优二叉树四个部分;

　　⑦图的重点主要包含图的 存储结构 图的遍历 图的最小生成树算法以及关键路径和最短路径算法;

　　⑧查找的重点是动态查找与哈希表 排序算法的重点主要是算法的思想 算法适宜的数据对象 算法的稳定性和算法的时间 空间复杂度

　　知识点的难点

　　①链表中的插入删除以及双向循环链表的操作;

　　②栈和递归的关系以及如何将递归算法改为非递归算法;

　　③迷宫求解栈和表达式求解算法;

　　④二叉树中相关的递归算法 如求二叉树的高度 交换二叉树的左右子树等递归算法;

　　⑤二叉树的非递归遍历算法的理解;

　　⑥已知二叉树的中序和另外一种遍历序列确定二叉树的步骤和相应的算法;

　　⑦图的最小生成树算法以及关键路径和最短路径算法;

　　⑧查找算法的平均查找长度以及平衡二叉树的调整方法 堆排序中建堆与堆调整的方法