文档介绍:数据结构考研试题
1. 知识点解析
1、线性表
线性表是一种最简单的数据结构,但是本章在整个数据结构学科的学习中占着非常重要的地位,在这一章中,首次引入了链式存储的概念,链式存储是整个数据结构的重中之重,后面的章节都将涉及到这个概念,所以一定能搞透彻。
本章主要考查线性表的定义和基本操作、线性表的实现。
(1)首先本章需要记住一些线性表的相关概念,如:前驱、后继、表长、空表、首元结点,头结点,头指针等,其中一定要注意首元结点、头结点和头指针三者的区别和联系,这在数据结构的考研题中经常出现。另外线性表的结构特点也要记住,有可能会出现在选择题中;
(2)然后就是要掌握线性表的两种存储方式的实现方法,要清楚静态链表与顺序表的相似及不同之处,并掌握几种常用链表的特点和运算:单链表、循环链表,双向链表,双向循环链表;
(3)理解线性表的顺序存储及链式存储情况下,其不同的优缺点比较,即其各自适用的场合;
(4)理解单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处;
(5)掌握对于线性表的各种实现方式能够实现指定的操作,尤其是各种线性链表的插入、删除(删除自己,还是删除后继结点)、判表空等。
2、栈、队列和数组
栈和队列是两种特殊的线性表,属于线性结构的拓展,其中栈和队列是两种操作受限的线性表,数组是数据元素为非原子类型的线性表。本章是考试中的重点,各位考生在复习这章的时候一定要注意栈和队列的应用,
数组这一节要特别注意特殊矩阵压缩方面的题目,还有就是数组寻址的计算题目。
本章的重点在栈和队列部分,如果本章出大题的话应该是关于栈和队列的,数组部分的重要性相对而言要低一些,对于栈和队列:
(1)首先要弄清楚栈和队列各自的特点以及它们的区别,记住一些有关栈和队列的相关概念,包括:顺序栈,链栈,共享栈,循环队列,链队等;
(2)对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解;
(3)在此基本上要掌握栈和队列插入、删除等基本操作的特点和算法描述,包括栈的出栈、入栈,单链队列的入队和出队,还有循环队列中判断空、队满条件的条件,判循环队列是空还是满的两种处理方法及其入队和出队的算法描述;
(4)掌握递归算法,在弄清楚递归算法和栈的关系的基础上,要能把递归算法转换为用栈实现的非递归算法;
(5)对于栈和队列的应用,例如,排队问题、子程序调用问题、表达式问题等,要搞清楚。
数组部分为一维数组和多维数组,其中一维数组属于线性表范畴,但多维数组不属于线性表,这一部分重点要掌握多维数组中某数组元素的寻址求解(不管是按行存储和按列存储):一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数,然后要求你求出该数组中的某个元素所在的位置,其次要理解稀疏矩阵的三种不同实现方式:三元组,带辅助行向量的二元组,十字链表存储和稀疏矩阵各种实现方式的转置和相乘运算的操作及复杂性分析。
3、树与二叉树
树和二叉树历来都是考试的重点章节,同时也是难点,在数据结构考试中本章所占的分值比例很大,本章学习的好坏直接关系到数据结构考试中的得分高低,所以考生在复习本章的时候一定要力求吃透,不能只是浮在表面上,同时要注意算法设计题目。
复习本章的时候(1)首先必须要弄清楚二叉树和树是两种不同的概