考研计算机专业课的复习难点解读

　　从计算机统考大纲数据结构部分及其相关知识点可以看出来，数据结构占了45分，和计算机组成原理部分同一个比重。小编为大家精心准备了考研计算机复习要点分析，欢迎大家前来阅读。

考研计算机专业课的复习难点解读

　　考研计算机复习重点解析

　　一、重难点解析和复习建议

　　统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。

　　当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。

　　下面我们来解析一下知识点：

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

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

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

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

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

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

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

　　计算机考研常见的疑问总结

　　问题1：请结合往年的计算机专业课试题谈一下四门专业课所占的比例么?

　　答：计算机考研专业课在2009年年初实行了第一次统考，统考科目包括四门计算机专业课：数据结构、计算机组成原理、操作系统和计算机网络，这四门课程合在一起称为计算机科学专业基础综合，共150分。四门专业课在试卷中所占的分数分别为：数据结构45分，计算机组成原理45分，操作系统35分，计算机网络25分。从09年初考过的真题情况来看，计算机专业基础综合考试一共有两种题型：单选题和综合应用题。第一种题型是单选题，共40道题，每题2分，满分80分。其中1-10题是数据结构部分，11-22题是计算机组成原理部分，23-32题是操作系统部分，33-40题是计算机网络部分;第二种题型是综合应用题，共7道大题，满分70分。按题目编号来说，41题、42题是数据结构题，分值各为10分和15分，43和44题是计算机组成原理题，各占8分和13分，45题和46题是操作系统题，各占7分和8分，47题是计算机网络题，分值为9分。

　　问题2：数据结构的考试内容有哪些?考生应该如何复习?怎样把握重点和难点?

　　答：数据结构的考试内容包括：线性表、栈、队列和数组、树和二叉树、图、查找和内部排序。考生复习时首先要深刻理解数据结构的三要素：逻辑结构、存储结构以及在其上定义的各种基本操作，要把复习的重点放在掌握常用数据结构的这三个要素上面。举例来说，栈这种数据结构有两种实现方式(即存储方式)：顺序栈和链式栈，经过一到两轮的复习之后，考生应该能够比较熟练地使用C语言(当然也可以用C++等高级语言)写出这两种方式下栈的定义以及初始化、进栈、出栈、返回栈顶元素等各种阿基本操作的算法实现，有条件的同学，可以上机调试算法。也就是说，对于每一种常用的数据结构，在掌握了它的逻辑结构和存储结构后，一定要亲自动手，自己写出各种基本操作的算法实现，这个过程需要认真体会和反复琢磨。只有熟练掌握了这些基本算法以后，才能在此基础上对常用的数据结构进行比较灵活的运用，而对于数据结构的灵活运用，正是这门课程的难点所在。把握重点和难点的最主要的一条，就是多动手，勤思考。

　　问题3：计算机组成原理的考试内容有哪些?考生应该如何复习?

　　答：计算机组成原理的考试内容包括：计算机系统概述、数据的表示和运算、存储器层次结构、指令系统、中央处理器、总线、输入/输出系统。考生在复习时，首先要重点掌握单处理机计算机系统中各个部件的组成结构和基本工作原理。全部复习完后再把这些组成部件形成一个完整的系统，各部件之间是通过什么联系起来的、是怎样联系的，最好在头脑中有一个比较清晰的认识。随着复习的深入，这种认识要不断加深，这样就不会“只见树木，不见森林”，并且复习过的内容不容易遗忘。

　　问题4：计算机操作系统的考试内容有哪些?考生复习时重点放在哪儿?难点是什么?

　　答：计算机操作系统的考试内容主要包括：操作系统概述、进程管理、内存管理、文件管理和输入/输出管理。考生复习时重点应该放在掌握基本概念和基本原理上，包括一些常用的算法，如：并发和并行的概念、进程的概念与状态及相互转化、信号量和P、V操作、死锁及其预防、避免、检测与解除、页式、段式和段页式存储管理、磁盘调度算法、设备管理等。难点主要是运用操作系统的基本原理来分析和解决具体问题，如：运用P、V操作实现进程之间的同步和互斥。

　　问题5：计算机网络涉及到哪些内容?这门课有什么特点?考生应该如何复习?

　　答：计算机网络的考试内容主要围绕TCP/IP协议层次的具体展开，包括以下内容：物理层、数据链路层、网络层、传输层、应用层。计算机网络这门课的特点是：在考研专业课中所占分数最少，但是涉及到的具体的知识点最多。考生复习时要注意按照层进行知识点的复习和总结。对于每一层，重点把握这一层的协议有哪些、引入这些协议的原因、涉及到哪些重要算法、算法的内容、每一层和上下层之间的关系、每一层用到的硬件设备及作用等，也就是说，学习完一层时一定要用系统的方法将具体的知识点串连在一起，不要局限于孤立地理解和掌握每个细节的知识点。

　　问题6：四门专业课的内容之间有什么联系?有没有交叉?考生复习时是否需要按照一定的顺序?四门课的复习时间怎样分配比较合适?

　　答：这四门专业课之间有一定的内在联系，数据结构和组成原理是操作系统的先修课程，计算机网络相对来说比较独立，或者说不需要先修课程。内容的交叉有一些，主要表现在组成原理和操作系统这两门专业课之间，二者都包含了存储系统和输入/输出系统的内容，如：内存管理的各种页面置换算法、虚拟存储器等。如果不是跨专业考生，也就是说这些专业课以前都系统的学习过，那么复习时可以不按顺序。但如果是初学者，必须先学习完数据结构和组成原理后再学习操作系统，否则有些概念和原理难以理解。四门课的复习时间应该合理分配，重点放在数据结构和组成原理上，尤其数据结构更要多花一些时间;操作系统和计算机网络的很多知识点需要在理解的基础上进行记忆，相对来说容易一些。当然难易程度是相对的`，具体情况也要因人而异，灵活安排。