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

第一章1. 数据结构研究的主要内容包括逻辑结构、存储结构和算法。2. 数据元素是数据的基本单位，数据项是数据的最小标示单位。3. 根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、树形、线性、图状。4. 常见的数据存储结构有四种类型：顺序、链式、索引、散列。5. 可以从正确性、可读性、健壮性、高效性四方面评价算法的质量。6. 在一般情况下，一个算法的时间复杂度是问题规模的函数。7•常见时间复杂度有：常数阶 O(1)、线性阶 O(n)、对数阶 O(log2n)、平方阶 O(/)和指数阶O(2E。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。8•时间复杂度排序由大到小(n+2)!>2・十 2>(n+2)4 次方>nlog2n>100000.问答题：1. 什么叫数据元素？数据元素是数据的基本单位，是数据这个集合的个体，也称为元素、结点、顶点、记录。2. 什么叫数据逻辑结构？什么叫数据存储结构？数据逻辑结构：指数据元素之间存在的固有的逻辑结构。数据存储结构：数据元素及其关系在计算机内的表示。3. 什么叫抽象数据类型？抽象数据类型是指数据元素集合以及定义在该集合上的一组操作4. 数据元素之间的关系在计算机中有几种表示方法？顺序、链式、索引、散列。5. 数据的逻辑结构与数据的存储结构之间存在着怎样的关系？相辅相成，不可分割。6. 什么叫算法？算法的性质有哪些？算法：求解问题的一系列步骤的集合。可行性、有容性、确定性、有输入、有输出。7. 评价一个算法的好坏应该从哪几方面入手？正确性、可读性、健壮性、高效性。第二章1. 线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。2. 线性表常用的两种存储结构分别是顺序存储结构和链式存储结构。3•在长度为 n 的顺序表中，插入一个新元素平均需要移动表中的 n/2 个元素，删除一个元素平均需要移动(nT)/2 个兀素。4. 在长度为 n 的顺序表的表头插入一个新元素的时间复杂度为 O(n),在表尾插入一个新元素的时间复杂度为 O(1)。5. 已知顺序表中每个元素占用 3 个存储单位，第 13 个元素的存储结构为 336，则顺序表的首地址为 300.6. 线性表的顺序存储结构通过物理相邻位置来反映数据元素之间的逻辑关系。7. 线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系。8. 在长度为 n 的顺序表中，若删除 i 位置处的元素，则 i 的可能取值范围为 1WiWn9•已知一指针 p 指向非空不带头单链表的某一个结点，若 p ...