数据结构考研真题答案复习重点

本书是详解考研基础专业课“数据结构”历年考研真题与典型题详解的一本复习资料，是参考数据结构权威教材和全国各大院校考研真题的结构和内容来编著的。本书共分8章。每章由两部分组成：第一部分为知识要点总结；第二部分是考研真题与典型题详解，按照各高校考研常考题型对各章的考研真题与典型题进行了整理，并对所有考研真题与典型题进行了详细的解答。

目录：

第1章　绪论

1.1　知识要点总结

1.2　考研真题与典型题详解

第2章　线性表

2.1　知识要点总结

2.2　考研真题与典型题详解

第3章　栈和队列

3.1　知识要点总结

3.2　考研真题与典型题详解

第4章　树与二叉树

4.1　知识要点总结

4.2　考研真题与典型题详解

第5章　图

5.1　知识要点总结

5.2　考研真题与典型题详解

第6章　查找

6.1　知识要点总结

6.2　考研真题与典型题详解

第7章　排序

7.1　知识要点总结

7.2　考研真题与典型题详解

第8章　文件

8.1　知识要点总结

8.2　考研真题与典型题详解

第1章绪论

1.1 知识要点总结

一、数据结构的基本概念

基础概念和术语

(1)数据(Data) :数据是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

(2)数据元素(Data Element) :数据元素是数据的基本单位,在程序中通常作为-个整体来进行考虑和处理。

(3)数据项(Data Item) : 数据项是数据的不可分割的最小单位,数据项是对客观事物的某一方面的数据描述。-一个数据元素可由若干个数据项(Data Item)组成。

(4)数据对象(Data Object) :数据对象是性质相同的数据元素的集合，是数据的一-个子集。如字符集合C={'A','B';'C' ..}.

(5)数据结构(Data Structure) :数据结构是指相互之间存在一定联系(关系)的数据元素的集合。元素之间的相互联系(关系) 称为逻辑结构。

2.数据结构的形式定义

数据结构的形式定义是一个二元组:Data Structure= (D, S)其中D是数据元素的有限集，S是D 上关系的有限集。

数据元素之间的关系可以是元素之间本身代表的某种自然关系,也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系,相应的结构称为逻辑结构。

3. 数据结构的组成

数据结构的三个组成部分:

(1)逻辑结构

数据元素之间的逻辑关系的描述。数据元素之间的逻辑结构有四种基本类型:

①集合:结构中的数据除了“同属于一个集合”外, 没有其它关系。

②线性结构:结构中的数据元素之间存在-对一的关系。

③树形结构:结构中的数据元素之间存在-对多的关系。

④图形结构或网状结构:结构中的数据元素之间存在多对多的关系。

(2)存储结构

数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。存储结构主要有:顺序存储、链式存储、索引存储和散列存储。

①顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。数据元素存放的地址是连续的。其优点是可以实现随机存取,存储空间小;缺点是只能使用相邻的一整块存储单元，容易产生碎片。

②链式存储结构:在每一个数据元素中增加一 个存放另一个元素地址的指针, 用该指针来表示数据元素之间的逻辑结构。对数据元素存放的地址是否连续没有要求。其优点是能充分利用所有存储单元;缺点是每个结点都需要额外的存储空间，且只能实现顺序存取。

③索引存储结构:在存储元素信息的同时.还建立附加的索引表。索引表中的每一项称为索引项,索引项的一般形式是: (关键字. 地址)，关键字唯一 标识-个元素,地址作为指向元素的指针。其优点是检索速度快;缺点是需要额外的存储空间来存放索引表。

④散列(或哈希)存储结构:根据元素的关键字通过哈希函数直接计算出该元素的存储地址。其优点是检索速度快,缺点是可能存在冲突,而解决冲突会增加时空开销。

(3)数据操作

对数据要进行的运算。

[例]下列有关数据存储结构的叙述中,正确的是(o ) 。

A.顺序存储方式只能用于存储线性结构

B.顺序存储方式的优点是占用存储空问小，插入、删除等操作效率高

C.链表的每个结点中都恰好含有一一个指针

D. Hash存储的基本思想是由关键词的值决定数据的存储地址