数据结构（c语言版）程海英-习题答案

《数据结构（c语言版）程海英-习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章习题1.解释下列术语：数据、数据元素、数据对象、数据结构、存储结构、线性结构、算法、抽象数据类型。略。2.试举一个数据结构的例子，叙述其逻辑结构、存储结构及运算3方面的内容。当你拿起一本厚厚的汉语字典查找某一个汉字时，你首先必须知道你使用的字典的编码方法，然后才能按照偏傍部首、四角号码或者拼音等相应的编码方法较快地查到你所需要查找的汉字。3.选择题1）在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A．存储

2、结构B．存储实现C．逻辑结构D．运算实现3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等4）以下说法正确的是（）。A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构5）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈4.填空题1）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它

3、们之间的关系和运算等的学科。2）数据结构被形式定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。3）数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4）线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。5）一个算法的效率可分为时间效率和空间效率。5.试分析下面各算法的时间复杂度。1）x=90;y=100; while(y>0)if(x>100){x=x-10;y--;}elsex++;O（1）2）for(i=0;i

4、]=0;O（m*n）3）for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)s++;O（n2）4）i=1;while(i<=n)i=i*2;O（log2n）5）i=0,s1=0,s2=0;while(i++1y=0;while(x>=(y+1)*(y+1))y++;O()第2章习题1.线性表有两种存储结构，分别是顺序表和链表。试问：两种存储结构各有哪些主要优缺点?①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须

5、是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2.试分析线性表的特征并举例说明。线性表是有限元素（a0,a1,...,an-1）的有序序列，该线性表的第

6、一个元素是a0，第二个元素是a1，...an-1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。每个元素只有一个直接前驱，仅有一个直接后继元素。例如，有一组实验数据（41,21,34,53,62,71,75,81,76,45），它是一个线性表，它们之间有着一定的顺序。这个线性表有10个元素，即表长为10，元素34的直接前驱元素是21，而直接后继元素是53。3.选择题1）在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（）个元素。A．n-iB．n-i+1C．n-i-1D．i2）在一个长度为n的

7、顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（）个元素。A．n-iB．n-i+1C．n-i-1D．i3）在一个顺序表中任何位置插入一个元素的时间复杂性的量级为（）。A．O（n）B．O（n/2）C．O（1）D．O（n2）4）在一个顺序表的表尾插入一个元素的时间复杂性的量级为（）。A．O（n）B．O（1）C．O（n*n）D．O（㏒2n）5）线性表的链式存储比顺序存储最有利于进行（）操作。A．查找B．表尾插入或删除C．按值插入或删除D．表头插入或删除6）在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。