澳门皇家赌场 > 考试 > <转>数据结构的复习

原标题:<转>数据结构的复习

浏览次数:85 时间:2019-11-20

一、数据结构部分

cr.http://m.sohu.com/n/412398598/

考点1. 算法复杂度分析问题:能够给出特定算法用大O表示的时间或空间复杂度

线性表这一章里面的知识点不多,但要做到深刻理解,能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点,诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。

考点2. 线性表的存储结构对比问题:链式存储和顺序存储的优缺点对比,各使用于那种应用场合

栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的,是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点,进栈出栈序列的问题常出现在选择题中。其次,是栈和队列的顺序和链式存储结构,这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作,特别是循环队列判满和判空的2种判断方法。再次,是特殊矩阵的压缩存储,这个考点复习的重点可以放在二维矩阵与一维数组相互转换时,下标的计算方法,比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后,各个数据点相应的下标的计算。这一章可能的大题点,在于利用堆栈或队列的特性,将它们作为基础的数据结构,支持实际问题求解算法的设计,例如用栈解决递归问题,用队列解决图的遍历问题等等。

考点3. 树、二叉树和森林的相互转换问题:树<->二叉树<->森林之间的转换问题,注意树的左孩子右兄弟表示法

树和二叉树:这一章中我们从顺序式的数据结构,转向层次式的数据结构,要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树),重点要熟练掌握的,是森林、树以及二叉树的前中后三种遍历方式,要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点,复习时要特别关注。一些常见的选择题考点包括:满二叉树、完全二叉树节点数的计算,由树、二叉树的示意图给出相应的遍历序列,依据二叉树的遍历序列还原二叉树,线索化的实质,计算采用不同的方法线索化后二叉树剩余空指针域的个数,平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括:二叉树的遍历算法,遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等),判断某棵二叉树是否二叉排序树,以上这些都要求能用递归的和非递归的算法解决,特别要重视非递归的算法,线索化后二叉树的遍历算法,如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。

考点4. 二叉树的构造与遍历问题:给定二叉树,能给出相应的前中后序遍历序列;给定一个中序遍历序列,再给出一个前序或后序遍历序列,构造出二叉树

图:在这一章中需要识记的是图以及基于图的各种定义,存储方式。要熟练掌握图的深度遍历和广度遍历算法,这是用图来解决应用问题时常用的算法基础。需要掌握基于图的多个算法,能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象,会成为下列问题:最小生成树求解(PRIM算法和KRUSKAL算法,两种方法思想都很简单,但要注意不要混淆这两种方法),拓扑排序问题(这里会用到数组实现的链表,可以注意一下),关键路径问题(数据结构的较大难点,要把概念理解透,能做出表格找出关键路径),最短路径问题(有重要的应用背景,也是贪心法不多的能给出最优解的典型问题之一)。

考点5. Huffman树的构造与Huffman编码:节点的权值,根到叶子节点的路径长度;给定一组数据的出现频率,构造相应的Huffman码

查找:这一章,需要识记关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度ASL的概念念及在各种查找算法中的计算方法和计算结果,特别是一些典型结构的ASL值,B-树的概念和基本操作冲突解决方法的选择和冲突处理过程的描述,B+树的概念(新增考点),特别要注意B-树和B+树概念的对比,以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法,特别要注意顺序查找、二分查找的适用条件(比如链表上用二分查找就不合适)和算法复杂度。

考点6. 图相关的定义问题:有向图,无向图,连同,强连通等概念的对比

排序:最新的大纲将去年的内部排序范围扩展为排序,排序既是重点,又是难点。排序算法众多,今年大纲还加上了外部排序,总共10种,各种不同算法还有相应的一些概念定义需要记住。选择题常见的问题包括:给定数列要求给出某种特定排序方法运行一轮后的排序结果,或者给出初始数列和一轮排序结果要求选择采用的排序算法,给定时间、空间复杂度要求以及数列特征要求选择合适的排序算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考查。

考点7. 图的最小生成树问题:Prim算法和Kruskal算法的具体步骤,给定一个图,能使用给定的算法构造相应的最小生成树

数据结构的复习要紧扣参考书,把书认真看几遍,深入理解大纲相关的知识点。

考点8. 图的关键路径问题:给定一个图,能求出相应的关键路径,并且能给出求关键路径所需的中间表格

考点9. 二分查找算法的基本方法:给定一组数据和需要查找的关键字,能够给出二分查找经过的节点序列

考点10. 排序算法的特征问题:给定一组数据的初始状态和经过若干论排序后的状态,能推断出所使用的排序算法

二、计算机组成原理部分

考点1. 计算机硬件系统与冯诺依曼体系结构:五大件、存储执行、顺序执行、数据与操作有相同存储方式

考点2. 补码运算:补码的加减乘除法;给定两个数,能给出相应的计算过程和结果

考点3. ALU的结构与并行进位加法:并行进位加法公式的推导等

考点4. DRAM的刷新问题:三种刷新方式刷新效率的计算

考点5. Cache替换算法与写方法:各种不同替换算法的原理,写直达与写回

考点6. Cache与虚存的效率问题:使用Cache和虚存对存取效率提高的比率计算

考点7. 常见的寻址方式:各种寻址方式的寻址过程,使用到的硬件设备

考点8. 时序系统:三级时序系统之间相互的关系

考点9. I/O设备相关指标及计算问题:访问速率,存储容量,访问周期等指标的计算

澳门皇家赌场,考点10. 指令执行过程与CPU控制信号传输过程:取指令,分析指令,执行指令,不同指令指令周期中各个微操作以及相应的微指令序列

三、操作系统部分

本文由澳门皇家赌场发布于考试,转载请注明出处:<转>数据结构的复习

关键词:

上一篇:名师解析考研调剂成功的关键技巧【澳门皇家赌

下一篇:没有了