数据结构考研试题

《数据结构考研试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构考研试题1.知识点解析1、线性表线性表是一种最简单的数据结构，但是本章在整个数据结构学科的学习中占着非常重要的地位，在这一章中，首次引入了链式存储的概念，链式存储是整个数据结构的重中之重，后面的章节都将涉及到这个概念，所以一定能搞透彻。本章主要考查线性表的定义和基本操作、线性表的实现。（1）首先本章需要记住一些线性表的相关概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等，其中一定要注意首元结点、头结点和头指针三者的区别和联系，这在数据结构的考研题中经常出现。另外线性表的结构特点也要记住，有可能会出现在选择

2、题中；（2）然后就是要掌握线性表的两种存储方式的实现方法，要清楚静态链表与顺序表的相似及不同之处，并掌握几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表；（3）理解线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合；（4）理解单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处；（5）掌握对于线性表的各种实现方式能够实现指定的操作，尤其是各种线性链表的插入、删除（删除自己，还是删除后继结点）、判表空等。2、栈、队列和数组栈和队列是两种特殊的线性表，属于线性结

3、构的拓展，其中栈和队列是两种操作受限的线性表，数组是数据元素为非原子类型的线性表。本章是考试中的重点，各位考生在复习这章的时候一定要注意栈和队列的应用，数组这一节要特别注意特殊矩阵压缩方面的题目，还有就是数组寻址的计算题目。本章的重点在栈和队列部分，如果本章出大题的话应该是关于栈和队列的，数组部分的重要性相对而言要低一些，对于栈和队列：（1）首先要弄清楚栈和队列各自的特点以及它们的区别，记住一些有关栈和队列的相关概念，包括：顺序栈，链栈，共享栈，循环队列，链队等；（2）对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)

4、要有较深的理解；（3）在此基本上要掌握栈和队列插入、删除等基本操作的特点和算法描述，包括栈的出栈、入栈，单链队列的入队和出队，还有循环队列中判断空、队满条件的条件，判循环队列是空还是满的两种处理方法及其入队和出队的算法描述；（4）掌握递归算法，在弄清楚递归算法和栈的关系的基础上，要能把递归算法转换为用栈实现的非递归算法；（5）对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。数组部分为一维数组和多维数组，其中一维数组属于线性表范畴，但多维数组不属于线性表，这一部分重点要掌握多维数组中某数组元素的寻址

5、求解（不管是按行存储和按列存储）：一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置，其次要理解稀疏矩阵的三种不同实现方式：三元组，带辅助行向量的二元组，十字链表存储和稀疏矩阵各种实现方式的转置和相乘运算的操作及复杂性分析。3、树与二叉树树和二叉树历来都是考试的重点章节，同时也是难点，在数据结构考试中本章所占的分值比例很大，本章学习的好坏直接关系到数据结构考试中的得分高低，所以考生在复习本章的时候一定要力求吃透，不能只是浮在表面上，同时要注意算法设计题目。

6、复习本章的时候（1）首先必须要弄清楚二叉树和树是两种不同的概念，比如可以考判断二叉树是否为度为2的有序树这样的题目，同时弄清楚这一点也是学好本章的基础。（2）然后掌握二叉树的五个性质，都有可能在选择题中出现。（3）本章的一个重点中重点就是二叉树的三种遍历算法：先序、中序以及后序，要求熟练的掌握这三种遍历的递归算法和非递归算法，理解其执行的实际步骤，同时还要掌握在三种遍历算法的基础上改造完成的其它二叉树算法，比如求叶子节点个数，求二叉树结点总数，复制二叉树、交换二叉树左右子树等等诸如此类的综合应用题，这方面的题目考试一定要自己

7、实实在在地自己解决一两个，找到解这种题目方法和思想。本章还有特殊的二叉树，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造，以及三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题），会计算针对某个二叉树在采用不同的线索化方法后剩余空链域的个数二叉排序树，平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。本章还有一个很重要的点就是哈夫曼树，也叫最优二叉树。什么样的编码是哈夫曼编码。一般很少考哈夫曼

8、编码的算法，能够利用算法构造哈夫曼树并求出最小带权路径长度即可。还有一个树的应用：等价类问题，通常会作为综合应用类试题出现，最后对是树和森林，多棵独立的树就组成了森林，考生对树的三种存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了解，在选择题中可能会出现。4