数据结构习题解答.pdf

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

1、习题一1、简要回答术语：数据，数据元素，数据结构，数据类型。数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是？

2、元素之间的相互联系（关系）称为逻辑结构。四种基本类型是集合、线性结构、树型结构、图状结构或网状结构。数据结构在计算机中的表示（又称为映像）称为数据的物理结构，又称为存储结构。区别和联系：数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素之间的逻辑关系，而不管其在计算机中的存储方式，数据的逻辑结构分为线性结构和非线性结构。需要注意以下几点：逻辑结构与数据元素本身的形式、内容无关；与数据元素的相对位置无关；与所含数据元素的个数无关；与数据的存储无关，他独立于计算机。数据的存储结构是数据逻辑结构在计算机存储器里的，即数据的

3、存储结构是数据及其逻辑结构在计算机中的表现，存储结构除了存储数据元素之外还必须能隐式或显式的表示数据元素之间的逻辑关系，这样，在逻辑上相邻的数据元素在存储结构中就未必相邻。数据的存储结构分为顺序存储结构和链式存储结构。数据的逻辑结构和物理结构是密不可分的两个方面，一个逻辑结构可表示成多种存储结构，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。3、数据结构的主要运算包括哪些？⑴建立(Create)一个数据结构；⑵消除(Destroy)一个数据结构；⑶从一个数据结构中删除(Delete)一个数据元素

4、；⑷把一个数据元素插入(Insert)到一个数据结构中；⑸对一个数据结构进行访问(Access)；⑹对一个数据结构(中的数据元素)进行修改(Modify)；⑺对一个数据结构进行排序(Sort)；⑻对一个数据结构进行查找(Search)。4、算法分析的目的是什么？算法分析的主要方面是什么？目的：分析算法的效率以求改进或对不同的算法进行比较算法分析的主要方面是：空间复杂性和时间复杂性。5、分析一下程序段的时间复杂度，请说明分析的理由或原因。（1）Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m+

5、+){p*=m;sum+=p;}Return(sum);}（2）Sum2(intn){intsum=0,m,t;For(m=1;m<=n;m++){p=1;For(t=1;t<=m;t++)p*=t;Sum+=p;}Return(sum);}(3)Fact(intn){if(n<=1)return1;Elsereturn(n*fact(n-1));}⑴基本操作的语句频度为：2n，其时间复杂度为：O(n)。⑵基本操作的语句频度为：1+2+3+„+n=n(n-1)/2，其时间复杂度为：O(n2)。⑶基本操作的语句频度为：n，其

6、时间复杂度为：O(n)。习题二1、简述下列术语：线性表，顺序表，链表线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。2、何时选用顺序表，何时选用链表作为线性表的存储结构为宜？各自的主要有缺点是什么？在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：（1）基于空间的考虑。当要求存储的线性表长

7、度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。（2）基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大

8、小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定元素进栈顺序)，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不