数据结构总复习+习题+解答.pdf

《数据结构总复习+习题+解答.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习资料数据结构总复习+习题解答第一章绪论1.1理解基本概念1、数据是信息的载体，是描述客观事物的数、字符以及能输入到计算机中，被计算机识别和处理的符号的集合。2、数据元素是数据的基本单位，可由若干数据项组成。3、数据对象是性质相同的数据元素的集合。4、数据结构指某一数据元素集合中所有数据成员之间的关系，定义为：数据结构={D，R}5、数据结构三要素：逻辑结构，物理结构，作用于数据结构的运算。6、逻辑结构：数据元素间的逻辑关系，分为线性结构和非线性结构（集合、树和图结构）。7、物理结构：数据元素及其关系在计算机上的映像，通常按顺序存储或链式存储。8、抽象数据类

2、型定义了一个数据对象，数据对象中各元素之间的关系以及一组处理数据的操作。特征：数据抽象和信息隐藏。9、数据类型和数据结构的异同：同：它们都具有抽象性，并不特指适用于何处，可根据问题需要用他们来表示数据元素间的关系。异：数据结构本身是一种数据的组织和使用形式，通过把数据定义成数据类型才能在计算机上使用。1.2算法特性与性能分析1、算法的定义：解决特定问题的一系列操作。2、算法的5大特性（要素）：输入、输出、确定性、可行性和有限性。3、算法时间复杂度分析：寻找关键操作（基本操作，通常为循环的最内层程序段），计算关键操作的执行次数，一般结果为问题规模n的多项式。时间复杂度为

3、该多项式的最高次幂。T(n)=O(1)的含义：常量时间复杂度，表示算法执行时间与问题规模无关。4、算法空间复杂度分析：算法执行时所需要的辅助空间。S(n)=O(1)的含义：常量空间复杂度，表示算法执行时需要的辅助空间与问题规模无关，也称为算法原地工作。题1.1如何理解抽象数据类型。答：定义了一个数据对象，数据对象中各元素之间的关系以及一组处理数据的操作。题1.2数据元素间的逻辑结构关系有哪些。答：四种。分别是集合结构、线性结构、树状结构、图状结构。题1.3通常从时间复杂度和空间复杂度来评价算法的优劣。题1.4下面算法的时间复杂度为（C）inti,j;for(i=0;i

4、=0)个数据元素的有限序列。其特点为：存在唯一首元素、尾元素，除首元素和尾元素外，其余每个元素只有一个前驱和后继。2.2线性表的存储表示1、线性表的顺序存储2、线性表的链式存储3、其他形式的链表：循环单链表、带尾指针的循环链表、双向链表、双向循环链表、静态链表、4、根

5、据实际问题，灵活选择存储方式。5、各种链表判空条件6、顺序存储与链式存储的优缺点①顺序表是静态分配，无需为了表示元素间的关系而增加额外的辅助空间，存储密度大；可按元素序号随机访问；但进行插入、删除时，需要移动大量元素；②链表是动态分配，需要增加指针域来表示元素间的逻辑关系，存储密度小；不能进行随机访问；插入、删除时不需要移动元素，只需要修改相关指针域即可。2.3线性表的基本运算1、在顺序表中执行插入、删除运算要点：①插入时，应先判断表是否已满以及插入位置的合法性。在第i个位置插入时，需要把从第i个位置到最后一个的元素(n-i+1)向后移动。②删除时，应先判断表是否空以

6、及删除位置的合法性。删除第i个位置元素时，需要把从i+1到最后一个的元素(n-i)向前移动。2、在单链表中执行插入、删除运算要点：①插入、删除时，需要找到被插入或删除结点的前驱结点。②指针更改顺序很重要，防止后继结点丢失。③删除的结点要记着释放空间。2.4综合应用根据给定需求，在顺序存储或链式存储上实现相应操作。重点是链表。题2.1一维数组和顺序表的异同。同：一维数组与顺序表都可按元素下标直接（或随机）存取元素；异：2/16数据结构复习资料①一维数组中各元素间可以有空元素，而顺序表中的元素必须按顺序存放；②一维数组的基本操作只有按下标存取，而顺序表可以有线性表的所有操

7、作，如插入、删除等；③一维数组的大小一经分配便不可变，而顺序表的长度是可变的。题2.2线性表的特点是：除第一个元素外其他每个元素有且只有一个直接前驱，除最后一个元素外其他每个元素都有且只有一个直接后继。那么，循环链表的每一个结点都有直接后继，双向链表的每一个结点都有直接前驱和直接后继，它们还是线性表吗？解：循环链表和双向链表示存储结构，线性表是逻辑结构。线性与非线性是从逻辑上划分的。因此，循环链表和双向链表是线性表，它们是线性表的不同存储形式。题2.2在一个单链表L中，P为中间某结点，在P前插入S结点，可否在O(1)时间复杂度内完成。解：intFro