2010数据结构考研真题(2010计算机考研真题及讲解)

2010年计算机统一考试大纲完整解析系列由五篇文章组成。第一篇文章我们重点介绍整个考试的性质、考试目标、新大纲的变化以及相应的备考策略。在接下来的四篇文章中，我们将详细讲解教学大纲规定的四门课程的考试内容，并给出针对性的复习提示。

今天我们先来分析一下计算统考大纲中的数据结构部分及其相关知识点。数据结构占45分，与计算机组成原理比例相同。在历年计算机专业的研究生入学考试中，几乎没有学校不考数据结构的内容，而且在大多数考试中，数据结构的科目都占据着重要的地位，这足以体现了数据结构课程在计算机专业研究生选拔中的重要性。

2010年统一考试大纲中数据结构的考试目标定位为理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其区别，以及各种基本操作的实现；掌握基本的数据处理原理和方法后，基本上能够进行算法的基本时间复杂度和空间复杂度分析；能够选择合适的数据结构和方法解决问题，具有使用C或C++或JAVA语言设计程序和实现算法的能力。与2009年大纲的考试目标相比，本次考试目标最大的变化是“使用C或C++或JAVA语言设计程序和实现算法的能力”。其实，一方面，这可以认为是对去年考试中出现的一道与编程相关的题的修订。另一方面也可以看出，考研更强调将知识应用于实践的能力。当然，考生不必因此而专门复习C 或C++ 编程。毕竟复习时间有限，而且数据结构要求的重点是设计算法的能力而不是写代码的能力。因此，只要能用类似于伪代码的形式，将自己的想法表达清楚即可，没必要强迫自己写出没有任何语法错误的程序。

下面我们来分析一下知识点。

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

栈、队列、数组上可考的知识点比链表上要多。最基本的就是栈和队列FILO和FIFO的特性。例如，由于堆栈FILO的特点，堆栈进出顺序的问题经常出现在选择题中。其次，还有栈和队列的顺序和链式存储结构。这里常见的测试点是不同存储结构下栈顶指针、队列头指针和队列尾指针的操作，尤其是循环队列满和空这两个判断。方法。三是特殊矩阵的压缩存储。本次测试点复习的重点可以是二维矩阵和一维数组转换时下标的计算方法。例如，将与对角线平行的几行具有非零数据的矩阵存储在一维数组中，然后计算每个数据点对应的下标。本章可能的大主题是利用栈或队列作为基础数据结构的特性来支持实际解决问题算法的设计，比如用栈解决递归问题、用队列解决图遍历问题等。

树和二叉树。在本章中，我们从顺序数据结构转向分层数据结构。我们需要掌握树和二叉树的各种属性，树和二叉树的不同存储结构，森林、树和二叉树之间的转换，以及线程二叉树。二叉树（二叉排序树、平衡二叉树和哈夫曼树）的应用，要掌握的重点是森林、树和二叉树三种遍历方法，并且必须能够设计相应的算法。这部分一直是数据结构试题的重点和难点，复习时要特别注意。一些常见的多项选择测试点包括：计算满二叉树和完全二叉树的节点数，从树和二叉树的示意图中给出相应的遍历序列，根据二叉树的遍历顺序、线索的本质以及使用不同方法计算线索优化后二叉树中剩余空指针字段的数量、平衡二叉树的定义、性质、建立、四种调整算法及相关问题到回溯法。常见的综合应用题包括：二叉树遍历算法、基于遍历对二叉树进行一些统计和操作（如节点数统计、左右子树交换等）、判断某棵二叉树是否是二叉排序树、而以上都需要通过递归和非递归算法来解决。特别要注意的是非递归算法，即线索后遍历二叉树的算法，例如线索后查找节点的前驱或后继节点并给予哈夫曼编码的算法。 ETC。

图片。本章需要记忆的是图以及基于图的各种定义和存储方法。必须精通图的深度遍历和广度遍历算法，这是使用图解决应用问题时常用的算法的基础。您需要掌握多种基于图的算法，并能够在给定的图上执行特定的算法，通过手动计算来解决问题。常见的应用问题直接给出或者抽象出来，变成如下问题：最小生成树求解（PRIM算法和KRUSKAL算法，两种方法思想都很简单，但是注意不要混淆这两种方法）、拓扑排序问题（链表）这里会用到数组实现，请注意），关键路径问题（数据结构难度较大，必须理解透彻的概念，会做表找出关键路径），最短路径问题（有重要的应用背景） ，这也是很少有贪心方法能够给出最优解的典型问题之一）。

寻找。本章需要记住关键词、主关键词、次关键词的含义；静态搜索和动态搜索的含义和区别；平均搜索长度ASL的概念以及各种搜索算法中的计算方法和结果。特别是一些典型结构的ASL值、B树的概念和基本操作冲突解决方法的选择以及冲突处理过程的描述、B+树的概念（新增测试点），付费专注意B-树和B+树的概念比较，以及Hash表相关的概念。必须精通顺序表、链表、二叉树的查找方法，并特别注意顺序查找和二分查找的适用条件（例如链表二分查找不合适）以及算法的复杂度。

内部排序。内部排序既重要又困难。排序算法有很多种，仅教学大纲中就列出了其中的9种。不同的算法也有相应的概念定义需要记住。选择题中常见的问题包括：不同排序算法的复杂度。给定一个序列，要求给出经过一轮特定排序方法后的排序结果，或者给出初始数列和一轮排序结果并要求选择排序算法。给定时间、空间复杂度要求和序列特征，选择合适的排序算法等。如果排序测试点出现在综合应用题中，往往会结合数组进行测试。

另外需要提醒考生的是，大纲中考试目标中提到的算法复杂度分析在具体考点中并没有明确列出。因此，需要学习参考书中关于算法复杂度分析的相关内容，并关注相关章节中提到的一些典型算法的算法复杂度。

建议大家使用清华严为民版的工具书，有助于建立知识体系，而且更加透明。在复习数据结构的时候，要紧跟参考书，仔细读几遍书，深入理解大纲相关的知识点。

  相关文章:

   8月底，考研大纲即将公布。预注册将于9月进行，正式注册将于10月进行。考研初试离我们越来越近了。朋友们早出晚归，努力复习、收集各种材料。很多人的状态可以用“忙、累、慌、乱”来形容。是不是意味着复习越努力、收集的信息越多，考研成功的概率就越大呢？并非如此。考研，你要学

   1.学校声誉虽然MPA的学习内容与各学校的基础课程非常相似，但附加课程却明显不同，具有很强的特色。课程的设置和重点与各学校的专业特长和教学领域有很大关系。例如，对外经济贸易学校有以海关为主的课程，农业院校有以农业或扶贫为主的课程等。考生在选择时应根据自己的喜好考虑学校的声

   摘要本文主要从五个角度论证研究生政考试卷的重要性和必要性。首先，研究生政治考试试卷是研究生政治考试的重要组成部分。掌握真题真题可以帮助你更好的应对考试。其次，通过分析真题，可以了解考研政治的考点和命题思路，有助于提高备考效果。第三，通过分析真题，可

   云南大学研究生2023录取摘要云南大学是云南省重点大学之一，以优良的学风和丰富的研究资源而闻名。随着时间的流逝，云南大学2023年研究生招生即将拉开帷幕。本文将从五个角度论证并详细介绍云南大学2023年研究生招生的重要性以及招生政策的变化。1.录取政策的变化云南大学的研究生招生政策将随着时间的推移进行调整，以更好地适应当今社会的需求。2023年招生

   南京大学新闻传播硕士考研经验摘要本文旨在分享我作为南京大学新闻与传播专业研究生的经历。我将从多个角度来论证这一点，包括准备计划、复习方法和技巧、面试准备、学术研究和准备阶段的实践经验。本文总结了我在考研期间所学到的知识，希望对即将考