练习题(第12章)-参考答案

第一、二章的练习题一、选择题1．数据结构可以用二元组来表示，它包括（A）集合K和K上的（C）集合R。A、数据元素B、存储结构C、元素之间的关系D、逻辑结构2．数据结构在计算机内存中的表示是指（A）。A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的（A）结构。A、逻辑B、存储C、逻辑和存储D、物理4．以下说法中正确的是（D）。A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构5．线性表的顺序存储结构是一种（A）的存储结构，线性表的链式存储结构是一种（B）的存储结构。A、随机存取B、顺序存取C、索引存取D、散列存取6．对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（B）。A、顺序存储方式B、链式存储方式C、散列存储方式D、索引存储方式7．已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（B）。A、p-next=s;s-next=p-next;B、s-next=p-next;p-next=s;C、p-next=s;s-next=p;D、s-next=p;p-next=s;8．单链表中各结点之间的地址（D）。该题做了修改！！！A、必须连续B、部分地址必须连续C、必须不连续D、连续与否都可以9．在一个长度为n的顺序表中向第i个元素（0i=n+1）之前插入一个新元素时，需向后移动（B）个元素。A、n-iB、n-i+1C、n-i-1D、i10．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A、单链表B、静态链表C、线性链表D、顺序存储结构11．在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关。A、删除单链表中的第一个元素B、删除单链表中的最后一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素12．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）。A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B、在第i个结点后插入一个新结点（1≤i≤n）C、删除第i个结点（1≤i≤n）D、将n个结点从小到大排序13．向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）个元素。A、8B、63.5C、63D、714．单链表的存储密度（C）A、大于1；B、等于1；C、小于1；D、不能确定15、链表不具备的特点（A）。A、可随机访问任结点B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与其长度成正比16、非空的单循环链表head的尾结点（由p所指向）满足（C）。A、p-NULLB、p==NULLC、p-next==headD、p==head17．若某表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，则采用（D）存储方式最节省时间。A、单链表B、给出表头结点的单循环链表C、双向链表D、带头结点的双循环链表18、在一个长度为n（n1）的单链表上，设有头和尾两个指针，执行（）操作与链表长度有关。A、删除单链表中第一个结点B、删除单链表是最后一个结点C、在单链表第一个结点前插入一个新结点D、在单链表最后一个结点后插入一个新结点19、设有两个长度为n的不带头结点的单链表，结点类型相同。其中，一个单链表h1是循环链表，而另一个单链表h2是非循环链表，则（B）。A、对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O(1)B、对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)C、循环链表要比非循环链表占用更多的内存空间D、h1和h2是不同类型的变量20、下面程序段的时间复杂度为（C）。voidprime(intn){inti=2;shile(n%i!=0&&isqrt(n))i++;if(i*1.0sqrt(n))coutn”是一个素数！”endl;dlsecoutn”是一个素数！”endl;}A、O(1)B、O(n)C、O(n)D、O(n2)二、填空题1．线性结构中元素之间存在（1：1）关系，树型结构中元素之间存在（1：n）关系，图型结构中元素之间存在（m:n）关系。2．一个算法的时间复杂度是该算法包含的（简单操作或原操作）的多少，一个算法的空间复杂度是指该算法在运行过程中临时占用的（存储空间）的大小。3．当一个算法的时间复杂度与问题的n大小无关时，则表示为（o(1)）；成正比时，表示为（o(n)），成平方时，则表示为（0(n2)）。4．顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样。插入一个元素大约移动表中的（n/2）个元素，删除一个元素时大约移动表中的（(n-1)/2）个元素。5．在线性表的顺序存储方式中，元素之间的逻辑关系是通过（物理位置）来体现的；在链式存储方式，元素之间的逻辑关系是通过（指针）体现的。6．对于一个长度为n的单链表，在已知的p结点后面插入一个新结点的时间复杂度为（o(1)），在p结点之前插入一个新结点的时间复杂度为（o(n)），在给定值为e的结点之后插入一个新结点的时间复杂度为（o(n)）。7．在双向链表中，每个结点包含两个指针域，一个指向（该结点的前驱）结点，另一个指向（该结点的后继）结点。8．对于循环链表来讲，逐个访问各个结点的结束判断条件是（最后一个结点的next=头指针）。9.在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(一个)个前驱结点；叶子结点没有(后继)结点，其余每个结点的后续结点数可以(0个或多个)。10.在图形结构中，每个结点的前驱结点数和后续结点数可以(0个或多个)。三、应用题1．阅读下面程序段，计算它的时间复杂度，要求写出计算过程。（1）for(j=1;j=n;j++)for(k=1;k=m;k++){++x;s+=x;}解：njmk111=njm1=n*m时间复杂度：o(n*m)（2）i=s=0;while(sn){i++;s+=i;}解：假设共循环x次，则循环次数123……xi123……xs+11+21+2+3……1+2+3+……+x循环结束条件：(1+2+3+……+x)nx(x+1)/2nx22nxn2时间复杂度：O(n)（3）i=1;while(i=n)i=i*3;解：计算过程与上一题类似，所以省略。时间复杂度：o(log3n)（4）fact(intn){if(n=1)return1;//语句1elsereturnfact(n-1)*n;//语句2}解：语句1的运行时间是o(1)，语句2的运行时间是fact(n-1)的运行时间T(n-1)+乘法运行o(1)。所以T(n)=T(n-1)+o(1)=T(n-2)+o(1)+o(1)=T(n-2)+2*o(1)......=T(1)+(n-1)*o(1)//T(1)表示n=1时的运行时间，等于o(1)=n*o(1)=o(n)时间复杂度：o(n)（5）for(j=1;j=n;j++)for(k=1;k=j;k++){++x;s+=x;}解：njjk111=njj1=1+2+3+……+n=n(n+1)/2时间复杂度：0(n2)2．给定的数据结构如图所示，回答以下问题:(1)用二元组表示法给出该数据结构的逻辑结构？(2)判断属于哪一种逻辑结构？123456（1）二元组表示A=（K，R），其中：K={1,2,3,4,5,6}R={r}r={1,2,2,3,3,4,4,5,5,6}逻辑结构：线性结构（一对一关系）（2）二元组表示A=（K，R），其中：K={a,b,c,d,e,f,g,h,i}R={r}r={a,b,a,c,c,d,c,e,d,f,d,g,e,g,e,h,g,i}逻辑结构：图型结构（多对多关系）提示：注意g结点的前驱和后继abcfdeghi3．对下列几种用二元组表示的数据结构，画出对应的逻辑结构图形表示，并指出属于哪一种结构。(1)A=（K，R），其中：K={a,b,c,d,e,f,g,h}R={r}r={a,b,b,c,c,d,d,f,f,e,e,h,h,g}aghefdcb逻辑结构：顺序结构(2)B=（K，R），其中：K={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}123456逻辑结构：图型结构(3)C=（K，R），其中：K={48,25,64,57,82,36,75}R={r1,r2}r1={25,36,36,48,48,57,57,64,64,75,75,82}r2={48,25,48,64,64,57,64,82,25,36,82,75}25827564574836其中，实线表示关系r1，虚线表示关系r2逻辑结构：关系r1表示线性结构，关系r2表示树型结构四、算法题1．编写有序表的插入算法，包括顺序表和单链表。顺序表：typedefstruct{DataTypedata[MAXSIZE];intlast;}SeqList;intInsert_SeqList_sort(SeqList&L,DataTypex){if(MAXSIZE=L.last+1)return-1;inti=0;while(i=L.last&&L.data[i]x)i++;for(intj=L.last;j=i;j--)L.data[j+1]=L.data[j];L.data[i]=x;L.last++;return1;}链表：typedefstructNode{DataTypedata;structNode*next;}LNode,*LinkList;voidInsert_LinkList(LinkListLDataTypex){LNode*s,*p=L;while(p-next&&p-next-datax)p=p-next;s=newLNode;s-data=x;s-next=p-next;p-next=s;}2．编写线性表的合并算法，包括顺序表和单链表。顺序表：P22算法2-6链表：P36算法2-193．编写删除线性表中所有值为x的元素的算法，包括顺序表和单链表。顺序表：voidDelete(SeqList&L,DataTypex){inti=0;while(i=L.last){if(L.data[i]==x){for(intk=i+1;k=L.last;k++)L.data[k-1]=L.data[k];L.last--;}elsei++;}}链表：voidDeleteAll_LinkList(LinkList&L,DataTypex){LNode*p=L,*q;while(p-next!=NULL){if(p-next-data==x){q=p-next;p-next=q-next;deleteq;}elsep=p-next;}}4．编写删除线性表中值相同的多余元素的算法，包括顺序表和单链表。顺序表：voidDelete3(SeqList&L){intj=0;while(j=L.last){inti=j+1;while(i=L.last){if(L.data[i]==L.data[j]){for(intk=i+1;k=L.last;k++)L.data[k-1]=L.data[k];L.last--;}elsei++;}j++;}}链表：P36算法2-185．编写单链表的逆置算法。逆置是指原链表中第一个结点变成最后一个结点，而最后一个结点变成第一个结点。链表：P35算法2-