全国研究生入学计算机统一考试考点、题解与模拟试卷

章节摘录

第1部分数据结构考查目标和知识点解析【考查目标】1．理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2．在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3．能够选择合适的数据结构和方法进行问题求解。【知识点解析】1．线性表线性表是一种最简单的数据结构，但线性表在线性结构的学习乃至整个数据结构学科的学习中都具有非常重要的作用。本书系统地引入了链式存储的概念，链式存储概念是整个数据结构学科的重中之重，无论哪一章都涉及了这个概念，所以需要透彻理解。这部分要识记线性表相关的基本概念和线性表的结构特点，掌握线性表的顺序存储方式和链式存储方式的实现方法及相应的运算，掌握链表与顺序表的相似及不同之处，掌握几种常用的链表的特点和运算。在理解线性表的顺序存储及链式存储的情况下，了解其不同的优缺点的比较及各自适用的场合。另外，还要掌握线性表的基本应用。（1）线性表的定义和基本操作线性表是若干个数据元素的有限序列，线性表的特点是具有唯一的首结点和唯一的尾结点，除了首结点外的每个结点有唯一的前驱，除了尾结点外每个结点有唯一的后继。与线性表相关的基本操作包括：初始化线性表、销毁线性表、判表空、置表空、取表长、定位、取第i个元素、取前驱、取后继、插入元素、删除元素等。（2）线性表的实现①顺序存储结构线性表的顺序存储是用一组地址连续的存储单元依次存放线性表中的数据元素，用这种方法存储的线性表称为顺序表。②链式存储结构链式存储的线性表称为链表，链表是用一组任意的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。在实现时，构成结点的结构体有两个域，一个数据域存放数据，一个指针域存放后继结点的地址。循环链表是一种特殊的链表，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成环状结构。双向链表中有两个指针域，一个指针域指向后继，另一个指针域指向前驱。当双向链表中的最后一个结点的后继指向头结点，而头结点的前驱指向最后一个结点时，就构成了双向循环链表。⑧线性表的应用线性表应用于多项式的表示及加法和乘法运算。2．栈、队列和数组栈、队列和数组都属于线性结构的拓展，栈和队列是特殊的线性表，是操作受限的线性表，数组是数据元素为非原子类型的线性表。这部分要识记栈、队列的定义及相关数据结构的概念，理解栈和队列的特点与运算的实现，掌握栈和递归的关系，掌握循环队列的各种判断和运算，了解栈和队列的应用。对于数组这部分，主要掌握数组的存储结构，例如按行优先、按列优先等，掌握多维数组中某个元素的位置求解。了解特殊矩阵的定义，掌握特殊矩阵的压缩存储。（1）栈和队列的基本概念栈是插入、删除操作只能在表的一端进行的线性表。栈中允许插入、删除的一端称为栈顶，另一端称为栈底。栈的特点是后进先出（LastInFirstOut，LIFO）。队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列的特点是先进先出（FirstInFirstOut，FIFO）。（2）栈和队列的顺序存储结构顺序存储的栈称为顺序栈，在实现时也是借助数组。但是插入和删除元素必须在约定好的栈顶位置。顺序存储的队列称为顺序队列，在实现时同样借助数组。分别设立队头指针和队尾指针，以方便进行插入和删除，插入必须在队尾进行，删除必须在队头位置。为了解决假溢出，通常采用循环队列，循环队列中对于元素的插入和删除及其队空、队满的判定是重点。（3）栈和队列的链式存储结构栈的链式存储也叫链栈，我们把插入和删除操作均在链表表头进行的链表称为链栈。链栈的优点是不受连续存储空间大小的限制。队列的链式存储实现称为链队，它实际上就是一个同时带有头指针和尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。（4）栈和队列的应用由于栈结构的特殊性，栈的应用非常广泛，常见的应用有表达式求值、数制转换、括号匹配、迷宫问题及递归问题。队列的应用主要是排队问题。（5）特殊矩阵的压缩存储特殊矩阵的压缩存储包括数组和特殊矩阵的存储两部分知识。数组的顺序表示中有两种顺序存储方法，即行主序和列主序。数组元素的位置是其下标的线性函数，需要掌握行主序和列主序两种方法所决定的数组元素位置的计算公式。简单地说，特殊矩阵是值或零元素在矩阵中的分布有一定规律的矩阵。常见的特殊矩阵有对称矩阵、下（上）三角矩阵、对角矩阵。稀疏矩阵中非0元素很少且分布没有规律。为了节约空间，常常对稀疏矩阵和特殊矩阵进行压缩存储。稀疏矩阵常用的存储方法有三元组表示和十字链表表示。矩阵压缩存储的关键是矩阵元素位置的计算方法。3．树与二叉树树和二叉树是考试的重点和难点章节，二叉树和树是两种不同的概念。在这个部分，要掌握树的定义、二叉树的定义及主要特征（特殊的二叉树、二叉树的性质）。掌握二叉树的性质和不同存储方式及各自的优缺点和适用场合。熟练掌握二叉树的遍历方法。在特殊的二叉树中，完全二叉树的概念是必须要熟练掌握的。另外，要掌握线索二叉树的基本概念和构造，二叉排序树、平衡二叉树的基本概念和应用。要掌握树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识。最后介绍树的应用，要掌握哈夫曼树的构造和等价类问题。（1）树的概念树是0个或多个结点的有限集合，在一棵非空树中，有一个树根和若干棵根的子树。树的定义是递归的即在树的定义中又用到了树的概念。树中有许多基本术语，如结点、结点的度、树的度、叶子、分支结点、孩子、双亲、子孙、祖先、兄弟结点的层次、树的深度、森林等。树中也有一些基本性质需要掌握。（2）二叉树①二叉树的定义及其主要特征二叉树是结点的有限集合，这个集合或者为空，或者是由一个根结点及两棵不相交的分别称为这个根的左子树和右子树的二叉树组成。二叉树中每个结点至多有两棵子树，且有左、右之分，次序不能颠倒。二叉树是一种重要的树形结构，但二叉树不是特殊的树。树和二叉树是两种不同的数据结构。满二叉树、完全二树是两种特殊的二叉树。二树有许多性质需要读者掌握。②二叉树的顺序存储结构和链式存储结构顺序存储二叉树就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。对于一般二叉树，则应将其每个结点与完全二叉树上的结点对照，存储在一维数组的相应分量中。二叉树的链式存储结构是指用一个链表来存储一棵二叉树，二叉树中每个结点用链表的一个链结点存储。因链表的结点类型不同，存储二叉树的链表有很多种，常用的有二叉链表和三叉链表。③二叉树的遍历二叉树的遍历是指按照一定的次序访问树中的所有结点，并且每个结点仅被访问一次的过程。根据访问结点的顺序分为先序遍历、中序遍历和后序遍历。④线索二叉树的基本概念和构造n个结点的二叉链表中有n+1个空链域，用这些链域存放结点在遍历中的前驱和后继信息构成了线索链表。其中，指向结点前驱和后继的指针叫线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫线索化。⑤二叉排序树二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：?若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。?左、右子树也都是二叉排序树。⑥平衡二叉树平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。在平衡二叉树上插入或删除结点后，可能使树失去平衡，因此，需要对失去平衡的树进行平衡化调整。设a结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下4种情况：左单旋转、右单旋转、先左后右双向旋转、先右后左双向旋转。（3）树和森林①树的存储结构在计算机中，树的存储有多种方式，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。基本的树的存储方式包括：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法。②森林与二叉树的转换

书籍目录

应试策略第1部分  数据结构　考查目标和知识点解析　第1章  概论　　一、单项选择题　　二、综合应用题　第2章  线性表　　一、单项选择题　　二、综合应用题　第3章  栈、队列和数组　　一、单项选择题　　二、综合应用题　第4章  树与二叉树　　一、单项选择题　　二、综合应用题　第5章  图　　一、单项选择题　　二、综合应用题　第6章  查找　　一、单项选择题　　二、综合应用题　第7章  排序　　一、单项选择题　　二、综合应用题　习题　　一、单项选择题　　二、综合应用题　参考答案　　一、单项选择题　　二、综合应用题第2部分  计算机组成原理　考查目标和知识点解析　第8章  计算机系统概述　　一、单项选择题　　二、综合应用题　第9章  数据的表示和运算　　一、单项选择题　　二、综合应用题　第10章  存储器层次结构　　一、单项选择题　　二、综合应用题　第11章  指令系统　　一、单项选择题　　二、综合应用题　第12章  中央处理器（CPU）　　一、单项选择题　　二、综合应用题　第13章  总线　　一、单项选择题　　二、综合应用题　第14章  输入/输出（I/O）系统　　一、单项选择题　　二、综合应用题　习题　　一、单项选择题　　二、综合应用题　参考答案　　一、单项选择题　　二、综合应用题第3部分  操作系统　考查目标和知识点解析　第15章  操作系统概述　　一、单项选择题　　二、综合应用题　第16章  进程管理　　一、单项选择题　　二、综合应用题　第17章  内存管理　　一、单项选择题　　二、综合应用题　第18章  文件管理　　一、单项选择题　　二、综合应用题　第19章  输入/输出（I/O）管理　　一、单项选择题　　二、综合应用题　习题　　一、单项选择题　　二、综合应用题　参考答案　　一、单项选择题　　二、综合应用题第4部分  计算机网络　考查目标和知识点解析　第20章  计算机网络体系结构　　一、单项选择题　　二、综合应用题　第21章  物理层　　一、单项选择题　　二、综合应用题　第22章  数据链路层　　一、单项选择题　　二、综合应用题　第23章  网络层　　一、单项选择题　　二、综合应用题　第24章  传输层　　一、单项选择题　　二、综合应用题　第25章  应用层　　一、单项选择题　　二、综合应用题　习题　　一、单项选择题　　二、综合应用题　参考答案　　一、单项选择题　　二、综合应用题第5部分  模拟试卷及参考答案　全真模拟试卷（一）　　一、单项选择题（本大题共40小题，每小题2分，共80分）　　二、综合应用题（本大题共11小题，共70分）　全真模拟试卷（一）分析解答　　一、单项选择题　　二、综合应用题　全真模拟试卷（二）　　一、单项选择题（本大题共40小题，每小题2分，共80分）　　二、综合应用题（本大题共11小题，共70分）　全真模拟试卷（二）分析解答　　一、单项选择题　　二、综合应用题附录A  2009年计算机专业硕士入学考试大纲参考文献

编辑推荐

《全国研究生入学计算机统一考试考点、题解与模拟试卷(2009年新大纲)(第2版)》：数据结构，计算机组成原理，操作系统，计算机网络。

作者简介

《全国研究生入学计算机统一考试考点、题解与模拟试卷(2009年新大纲)(第2版)》是根据“全国研究生入学考试（计算机专业）考试大纲（2009年）”，精选各个著名高校历年考研真题和习题编写的。《全国研究生入学计算机统一考试考点、题解与模拟试卷(2009年新大纲)(第2版)》主要包括5大部分：第1部分是数据结构；第2部分是计算机组成原理；第3部分是操作系统；第4部分是计算机网络；第5部分是模拟试卷及参考答案；另外，还包括应试策略和附录。

《全国研究生入学计算机统一考试考点、题解与模拟试卷(2009年新大纲)(第2版)》紧扣考试大纲，广泛收集了近几年全国20余所重点高校考研试卷，对典型的真题进行了深入、细致的分析和解答。叙述通俗易懂，每门课程都附有习题及参考答案。书中还给出了模拟试卷，可用于考前训练。

《全国研究生入学计算机统一考试考点、题解与模拟试卷(2009年新大纲)(第2版)》适合报考计算机专业研究生的考生有针对性地进行专业课的复习，也适合希望深入学习计算机专业知识的高校学生作为学习相关课程的参考书，同时也适用于讲授该课程的教师及自修该课程的其他人员。

图书封面

---

 全国研究生入学计算机统一考试考点、题解与模拟试卷下载

---