全国硕士研究生入学考试计算机专业统考考前辅导教程

章节摘录

插图：第2章 栈、队列和数组本章大纲要求栈和队列的基本概念栈和队列的顺序存储结构栈和队列的链式存储结构栈和队列的应用特殊矩阵的压缩存储重点考点提示根据对最新考试大纲和各大高校历年试卷的分析可知，本章考核内容约占数据结构部分的10％。主要考核以下几个方面：·栈和队列两种存储结构的实现和比较·栈和队列的典型应用2.1 栈和队列的基本概念2.1.1　考点辅导考点1：栈（Stack）是插入、删除操作只能在固定一端进行的线性表。栈中允许插入、删除的一端称为栈项，不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈项元素，不含任何数据元素的栈称为空栈。栈的特点为后进先出（Last In First Out，LIFO）。考点2：队列（Queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表。与堆栈类似，它也是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（Rear），只允许进行删除的一端称为队头（Front）。队列的插入操作通常称为入队列，而队列的删除操作则称为出队列。当队列中无数据元素时，称为空队列。由队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（First In First Out，FIFO）的原则组织数据的。因此，队列也被称为“先进先出”表。提示队列还有一种特殊形式，即优先权队列。该种队列对每个元素赋予一定的优先级，每次出队列操作取出当前队列中优先级最高的元素。这与操作系统中进程的最短作业优先调度算法大体相同。

前言

教育部对2009年硕士研究生入学考试计算机科学与技术学科的初试科目进行了调整，其中计算机学科专业基础综合科目实行联合命题，由教育部考试中心和中国学位与研究生教育学会工科工作委员会组织实施，进行全国统一命题，由省级招生考试机构统一组织阅卷。新《考试大纲》对考试范围、方法和要求做出明确规定，是考试命题和考生准备考试的基本依据。《考试大纲》给出了计算机专业基础综合考试试题的分布情况：卷面满分值为150分，包括数据结构、计算机组成原理、操作系统和计算机网络四大部分，数据结构和计算机组成原理各占45分，操作系统占35分，计算机网络占25分。统考中只有两种题型：单项选择题和综合应用题。其中选择题占80分，综合应用题占70分。从样题看来，针对操作系统和计算机网络的综合应用题相对较易，重点、难点仍是数据结构和计算机组成原理。数据结构是考试中的重点内容。为了帮助考生全面系统地理解和掌握考试大纲中数据结构部分的各个考点，我们依据《2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲》，参考了全国著名高等院校近几年的研究生入学考试计算机专业课试题，同时结合编者的工作经验编写了这本考前辅导教程。本书定位于考生考前复习使用，主要从应试的角度出发，在编写的过程中以“考点讲解、试题分析”为主线，以“辅导与训练并重，习题与分析结合”为编写原则；在内容上不求完整性、系统性，而是将“针对性”视为重中之重，把与考试无关的内容大刀阔斧地略去，引导考生花较少的时间顺利通过考试。本书每章包括4个板块：考点辅导、典型例题分析、同步练习、同步练习答案。考点辅导：略去与统考大纲无关的数据结构知识点，突出常考知识与核心知识，对考点、重点、难点内容进行解释与讲述，让考生掌握问题的本质。典型例题分析：针对新大纲中只有单项选择题和综合应用题的特点，精选常考题型和全国著名60所高校近3年来的考题进行解析，分析解题思路，找出解题方法，让考生掌握解题方法与技巧，增强考生的解题能力。同步练习：对介绍的知识点给出一定数量的习题，加强考生对知识点的理解。同步练习答案：考生通过对参考答案的分析和领会，可进一步加深对所学内容的理解，旨在达到启发解题思路的目的。全书共分7章，章节安排与最新考试大纲同步，主要从考试大纲要求、考试要点、典型例题分析和同步练习训练等几方面对知识点加以系统地阐述和解释。第1章主要讨论线性表的定义和基本操作及其顺序、链式存储结构实现，并在此基础上给出线性表的应用。第2章主要讨论栈和队列的基本概念、存储结构和应用，以及特殊矩阵的压缩存储。第3章主要讨论树的概念，二叉树的定义、存储结构和遍历方法，线索二叉树、二叉排序树和平衡二叉树的构造，树与森林的存储结构、遍历方法，以及树的应用等。第4章主要讨论图的概念、存储结构、遍历方法以及图的基本应用和复杂度分析。第5章主要讨论查找的基本概念、顺序查找法、折半查找法、B-树、散列表，以及查找算法的分析和应用。第6章主要讨论排序的基本概念，插入排序、气泡排序、简单选择排序、希尔排序、快速排序、堆排序、二路归并排序和基数排序等各种排序算法，以及各种排序算法的比较和应用。第7章根据大纲的要求编写了三套模拟试卷，并给出了参考答案。本书由段卫华、刘志鹏编著。另外感谢骆健、郭剑、邱丽姣、阚德涛、王珊珊、陈芳、郭沛仪、李勇智、张凌云、谢波等同志的关心和帮助。由于作者水平有限，书中难免有不当之处，恳请广大读者批评指正。最后预祝广大考生在研究生入学考试中取得理想的成绩。

书籍目录

第1章  线性表　1.1  线性表的定义和基本操作　　1.1.1  考点辅导　　1.1.2  典型例题分析　　1.1.3  同步练习　　1.1.4  同步练习答案　1.2  线性表的实现　　1.2.1  考点辅导　　1.2.2  典型例题分析　　1.2.3  同步练习　　1.2.4  同步练习答案第2章  栈、队列和数组　2.1  栈和队列的基本概念　　2.1.1  考点辅导　　2.1.2  典型例题分析　　2.1.3  同步练习　　2.1.4  同步练习答案　2.2  栈和队列的顺序存储结构　　2.2.1  考点辅导　　2.2.2  典型例题分析　　2.2.3  同步练习　　2.2.4  同步练习答案　2.3  栈和队列的链式存储结构　　2.3.1  考点辅导　　2.3.2  典型例题分析　　2.3.3  同步练习　　2.3.4  同步练习答案　2.4  栈和队列的应用　　2.4.1  考点辅导　　2.4.2  典型例题分析　　2.4.3  同步练习　　2.4.4  同步练习答案　2.5  特殊矩阵的压缩存储　　2.5.1  考点辅导　　2.5.2  典型例题分析　　2.5.3  同步练习　　2.5.4  同步练习答案第3章  树与二叉树　3.1  线性表的定义和基本操作　　3.1.1  考点辅导　　3.1.2  典型例题分析　　3.1.3  同步练习　　3.1.4  同步练习答案　3.2  二叉树　　3.2.1  考点辅导　　3.2.2  典型例题分析　　3.2.3  同步练习　　3.2.4  同步练习答案　3.3  树、森林　　3.3.1  考点辅导　　3.3.2  典型例题分析　　3.3.3  同步练习　　3.3.4  同步练习答案　3.4  树的应用　　3.4.1  考点辅导　　3.4.2  典型例题分析　　3.4.3  同步练习　　3.4.4  同步练习答案第4章  图　4.1  图的概念　　4.1.1  考点辅导　　4.1.2  典型例题分析　　4.1.3  同步练习　　4.1.4  同步练习答案　4.2  图的存储及基本操作　　4.2.1  考点辅导　　4.2.2  典型例题分析　　4.2.3  同步练习　　4.2.4  同步练习答案　4.3  图的遍历　　4.3.1  考点辅导　　4.3.2  典型例题分析　　4.3.3  同步练习　　4.3.4  同步练习答案　4.4  图的基本应用及其复杂度分析　　4.4.1  考点辅导　　4.4.2  典型例题分析　　4.4.3  同步练习　　4.4.4  同步练习答案第5章  查找　5.1  查找的基本概念　　5.1.1  考点辅导　　5.1.2  典型例题分析　　5.1.3  同步练习　　5.1.4  同步练习答案　5.2  顺序查找法　　5.2.1  考点辅导　　5.2.2  典型例题分析　　5.2.3  同步练习　　5.2.4  同步练习答案　5.3  折半查找法　　5.3.1  考点辅导　　5.3.2  典型例题分析　　5.3.3  同步练习　　5.3.4  同步练习答案　5.4  B-树　　5.4.1  考点辅导　　5.4.2  典型例题分析　　5.4.3  同步练习　　5.4.4  同步练习答案　5.5  散列(Hash)表及其查找　　5.5.1  考点辅导　　5.5.2  典型例题分析　　5.5.3  同步练习　　5.5.4  同步练习答案第6章  内部排序　6.1  排序的基本概念　　6.1.1  考点辅导　　6.1.2  典型例题分析　　6.1.3  同步练习　　6.1.4  同步练习答案　6.2  插入排序　　6.2.1  考点辅导　　6.2.2  典型例题分析　　6.2.3  同步练习　　6.2.4  同步练习答案　6.3  起泡排序　　6.3.1  考点辅导　　6.3.2  典型例题分析　　6.3.3  同步练习　　6.3.4  同步练习答案　6.4  简单选择排序　　6.4.1  考点辅导　　6.4.2  典型例题分析　　6.4.3  同步练习　　6.4.4  同步练习答案　6.5  希尔排序　　6.5.1  考点辅导　　6.5.2  典型例题分析　　　　6.5.3  同步练习　　6.5.4  同步练习答案　6.6  快速排序　　6.6.1  考点辅导　　6.6.2  典型例题分析　　6.6.3  同步练习　　6.6.4  同步练习答案　6.7  堆排序　　6.7.1  考点辅导　　6.7.2  典型例题分析　　6.7.3  同步练习　　6.7.4  同步练习答案　6.8  二路合并排序　　6.8.1  考点辅导　　6.8.2  典型例题分析　　6.8.3  同步练习　　　　6.8.4  同步练习答案　6.9  基数排序　　6.9.1  考点辅导　　6.9.2  典型例题分析　　6.9.3  同步练习　　6.9.4  同步练习答案　6.10  各种内部排序算法的比较与应用　　6.10.1  考点辅导　　6.10.2  典型例题分析　　6.10.3  同步练习　　6.10.4  同步练习答案第7章  模拟试题　7.1  模拟试题一　7.2  模拟试题二　7.3  模拟试题三　7.4  模拟试题一参考答案　7.5  模拟试题二参考答案　7.6  模拟试题三参考答案

编辑推荐

《全国硕士研究生入学考试计算机专业统考考前辅导教程:数据结构》由清华大学出版社出版。考点辅导略去与统考大纲无关的数据结构知识点，突出常考知识与核心知识，对考点、重点、难点内容进行解释与讲述，让考生掌握问题的本质典型例题分析针对新大纲中只有单项选择题和综合应用题的特点，精选常考题型与往年考试真题进行解析，增强考生的解题能力同步练习对介绍的知识点给出一定数量的习题，便于考生复习与检查同步练习答案考生通过对参考答案的分析和领会，可进一步加深对所学内容的理解，旨在达到启发解题思路的目的

作者简介

《全国硕士研究生入学考试计算机专业统考考前辅导教程:数据结构》根据《2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲》中的要求，参考全国著名高等院校近几年研究生入学考试计算机专业课试题编写而成。全书共7章，主要讨论了线性表、栈、队列、树和二叉树以及图等基本类型的数据结构及其应用，分析了查找和排序的各种实现方法。最后一章根据大纲要求编写了三套模拟试卷，并给出了参考答案。

《全国硕士研究生入学考试计算机专业统考考前辅导教程:数据结构》章节安排与最新考试大纲同步，主要从考试大纲要求、考试要点、典型例题分析和同步练习训练等几方面对知识点加以系统阐释，可以帮助考生系统地理解和掌握考试大纲中的各个考点，通过实战练习提高考生的应试能力。

《全国硕士研究生入学考试计算机专业统考考前辅导教程:数据结构》内容丰富、资料翔实、例题典型、讲解精当，特别适合参加全国研究生入学考试计算机统考的考生在考前复习使用，也可供大专院校计算机专业师生以及相应层次的计算机技术人员学习和参考。

图书封面

---

 全国硕士研究生入学考试计算机专业统考考前辅导教程下载

---