数据结构与算法设计课后习题及答案详解.pdfVIP

数据结构与算法设计课后习题及答案详解--第1页

第一章

1.数据结构研究的主要内容包括逻辑结构、存储结构和算法。

2.数据元素是数据的基本单位，数据项是数据的最小标示单位。

3.根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、树形、线性、图状。

4.常见的数据存储结构有四种类型：顺序、链式、索引、散列。

5.可以从正确性、可读性、健壮性、高效性四方面评价算法的质量。

6.在一般情况下，一个算法的时间复杂度是问题规模的函数。

7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log2n）、平方阶O（n²）和指

数阶O（2ⁿ）。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。

8.时间复杂度排序由大到小（n+2）！2ⁿ＋²（n+2）4次方nlog2n100000.

问答题：

1.什么叫数据元素？

数据元素是数据的基本单位，是数据这个集合的个体，也称为元素、结点、顶点、记录。

2.什么叫数据逻辑结构？什么叫数据存储结构？

数据结构与算法设计课后习题及答案详解--第1页

数据结构与算法设计课后习题及答案详解--第2页

数据逻辑结构：指数据元素之间存在的固有的逻辑结构。

数据存储结构：数据元素及其关系在计算机内的表示。

3.什么叫抽象数据类型？

抽象数据类型是指数据元素集合以及定义在该集合上的一组操作。

4.数据元素之间的关系在计算机中有几种表示方法？

顺序、链式、索引、散列。

5.数据的逻辑结构与数据的存储结构之间存在着怎样的关系？

相辅相成，不可分割。

6.什么叫算法？算法的性质有哪些？

算法：求解问题的一系列步骤的集合。

可行性、有容性、确定性、有输入、有输出。

7.评价一个算法的好坏应该从哪几方面入手？

正确性、可读性、健壮性、高效性。

第二章

数据结构与算法设计课后习题及答案详解--第2页

数据结构与算法设计课后习题及答案详解--第3页

1.线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。

2.线性表常用的两种存储结构分别是顺序存储结构和链式存储结构。

3.在长度为n的顺序表中，插入一个新元素平均需要移动表中的n/2个元素，删除一个元素平

均需要移动（n-1）/2个元素。

4.在长度为n的顺序表的表头插入一个新元素的时间复杂度为O（n），在表尾插入一个新元素的

时间复杂度为O（1）。

5.已知顺序表中每个元素占用3个存储单位，第13个元素的存储结构为336，则顺序表的首地

址为300.

6.线性表的顺序存储结构通过物理相邻位置来反映数据元素之间的逻辑关系。

7.线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系。

8.在长度为n的顺序表中，若删除i位置处的元素，则i的可能取值范围为1≤i≤n

9.已知一指针p指向非空不带头单链表的某一个结点，若p满足条件“p-next！=NULL”，则p

指向单链表的不是最后一个结点。

10.双向链表的每个结点均包含2个指针域，一个是指向前驱，一个是指向后继。

数据结构与算法设计课后习题及答案详解--第3页

数据结构与算法设计课后习题及答案详解--第4页

11.若p指针指向不带头双向循环链表的某个结点，则判断该链表只有一个结点的条件是

p-prior==p-next。

12.若对线性表进行的主要操作是查询操作，则该线性表应该采用顺序存储结构；若需要频繁进

行插入和删除操作，则该线性表应该采用链式存储结构。

13.线性表所含结点的个数称为线性表的表长。表长为0的线性表称为空表。

14.线性表的链式存储结构主要有单链表、循环链表、双链表。

15.在静态链表中，结点之间的逻辑关系通过游标来表示。

第三章

1.能够实现递归函数调用的一种数据结构是堆栈。

2.允许在一端插入，在另一端删除的线性表称为队列。插入的一端为队尾，删除的一端为队头。

3.在一个循环队列Q中，判断队空的条件为Q.front==Q.rear，判断队满的条件为

（Q.rear+1）%QUEUESIZ