考研汉语国际教育硕士354汉语基础名校真题解析.pdf

数据结构 目　　录 第一章　线性表 （１） 第二章　栈、队列和数组 （８） 第三章　树与二叉树 （１５） 第四章　图 （２５） 第五章　查找 （３３） 第六章　排序 （４０） 《数据结构》４０８及历年名校真题精选 第一章　线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操 作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结 构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本 应用。 线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实 际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等 一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。 ※考情分析 【大纲解读】 通过对历年计算机考研中数据结构部分考试大纲的分析不难看出，最近几年计算机 考研中针对数据结构第一部分线性表的考点、试题类型及侧重点几乎没有改变。依然保 持的是最初的要求： （一）线性表的定义及基本操作 （二）线性表的实现 １．顺序存储 ２．链式存储 ３．线性表的应用 其中，在２００９年综合题第４２题中考查了线性表链式存储结构的应用。 【考点归纳】 作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的 学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式 存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。 总体来说，线性表一章可供考查的重要考点有以下几个方面： １．线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等 概念。 — １— 考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名师精品课程　电话：４００６８８５３６５ ２．线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前 趋和只有一个后继。 ３．线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分 配和动态分配。静态链表与顺序表的相似及不同之处。 ４．线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双 向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双 向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中 还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。 在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的 方式是不一样的，请大家注意。 ５．线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场 合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的 各自好处。 ※真题及典型题精讲精练 例题精讲 【例１】（２００９ ４２综合应用题）已知一个带有头结点的单链表，结点结构为 图１－１　 单链表结点结构 假设该链表只给出了头指针ｌｉｓｔ。在不改变链表的前提下