严蔚敏数据结构各章习题及答案

数据结构习题及解答第1章概述【例1-1】分析以下程序段的时间复杂度。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;解：该程序段的时间复杂度为O(m*n)。【例1-2】分析以下程序段的时间复杂度。i=s=0;①while(sn){i++;②s+=i;③}解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O(1)。语句②和语句③构成while循环语句的循环体，它们的执行次数由循环控制条件中s与n的值确定。假定循环重复执行x次后结束，则语句②和语句③各重复执行了x次。其时间复杂度按线性累加规则为O(x)。此时s与n满足关系式：s≥n，而s=1+2+3+…+x。所以有：1+2+3+…+x≥n，可以推出：x=nn241212811x与n之间满足x=f(n），所以循环体的时间复杂度为O(n)，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O(n）。【例1-3】分析以下程序段的时间复杂度。i=1;①while(i=n)i=2*i;②解：其中语句①的执行次数是1，设语句②的执行次数为f(n)，则有：nnf)(2。得：T（n）=O(n2log)【例1-4】有如下递归函数fact(n)，分析其时间复杂度。fact(intn){if(n=1)return(1);①elsereturn(n*fact(n-1));②}解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+O(1)，其中O(1)为常量运行时间。由此可得fact（n）的时间复杂度为O(n)。习题1一、单项选择题1.数据结构是指（1.A）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2.C）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种（3.D）。A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（4.B）。for(i=1;i=n;i++)for(j=i;j=n;j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)5.算法分析的目的是（5.C、），算法分析的两个主要方面是（A）。（1）A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2）A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（6.C、），它具备输入，输出和（B）等五个特性。（1）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（7.B）。A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（8.D）年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（9.B）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（10.B）。A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。1.线性结构，非线性结构2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图3.线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。3.一对一，一对多或多对多4.一个算法的效率可分为__________________效率和__________________效率。4.时间，空间5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。5.前趋，一，后继，多6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。6.有多个7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。7.一对一，一对多，多对多8.下面程序段的时间复杂度是__________________。8.O(2n)for(i=0;in;i++)for(j=0;jn;j++)A[i][j]=0;9.下面程序段的时间复杂度是__________________。9.O(n)i=s=0;while(sn){i++;s+=i;}10.下面程序段的时间复杂度是__________________。10.O(2n)s=0;for(i=0;in;i++)for(j=0;jn;j++)s+=B[i][j];sum=s;11.下面程序段的时间复杂度是__________________。11.O(log3n)i=1;while(i=n)i=i*3;12.衡量算法正确性的标准通常是__________________________。12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。13.事后统计，事前估计三、求下列程序段的时间复杂度。1.x=0;for(i=1;in;i++)for(j=i+1;j=n;j++)x++;1.O(2n)2.x=0;for(i=1;in;i++)for(j=1;j=n-i;j++)x++;2.O(2n)3.inti,j,k;for(i=0;in;i++)for(j=0;j=n;j++){c[i][j]=0;for(k=0;kn;k++)c[i][j]=a[i][k]*b[k][j]}3.O(n3)4.i=n-1;while((i=0)&&A[i]!=k))j--;return(i);4.O(n)5.fact(n){if(n=1)return(1);elsereturn(n*fact(n-1));}5.O(n)第2章线性表【例2-1】试编写出将两个顺序存储的有序表A和B合成一个有序表C的算法。解：假设A、B和C的类型为下述SqList类型：#definemaxlen1000typedefintelemtypetypedefstruct{elemtypeelem[maxlen];intlen;}SqList;设A和B的数据元素均为整数且为升序排列，设A的长度为m，B的长度为n，则合并后C的长度为m+n。合并时进行A、B元素的比较，将较小的链入C中，算法描述如下：intmerge(SqList*A,SqList*B,SqList*C)//将两个有序表A和B合成一个有序表C{intm,n,i,j,k;m=(*A).len;n=(*B).len;if(m+nmaxlen-1){printf(overflow);exit(0);}i=0;j=0;//i和j分别作为扫描顺序表A和B的指针k=0;//k指示顺序表C中当前位置while((i=m)&&(j=n))if((*A).elem[i]＝(*B).elem[j]){(*C).elem[k]＝(*A)elem[i];i++;k++;}else{(*C).elem[k]＝(*B)elem[j];j++;k++;}while(i=m)//表B已结束，表A没有结束，链入表A的剩余部分{(*C).elem[k]＝(*A).elem[i];i++;k++;}while(j=m)//表A已结束，表B没有结束，链入表B的剩余部分{(*C).elem[k]＝(*B).elem[j];i++;k++;}return(1);}【例2-2】写一算法实现单链表的逆置。解：假设单链表的表头指针用head表示，其类型为下面定义的LinkList，并且单链表不带头结点。逆置后原来的最后一个结点成为第一个结点，于是从第一个结点开始逐个修改每个结点的指针域进行逆置，且刚被逆置的结点总是新链表的第一个结点，故令head指向它（如图2-1所示）。typedefstructNode{elemtypedata;structNode*next;}LinkList;具体算法描述如下：voidcontray(LinkList*head){//将head单链表中所有结点按相反次序链接LinkList*p,*q;p=head;//p指向未被逆序的第一个结点,初始时指向原表头结点head=NULL;while(p!=NULL){q=p;//q指向将被逆序链接的结点p=p-next;q-next=head;head=q;}}【例2-3】假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指图2-1单链表逆置示意图示示图head∧…head∧qphead…q(a)单链表初始状态示示图(b)第三个结点逆置示示图向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。解：可引入一个指针q，当q-next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下：voiddelete(LinkList*p){//在链表中删除p所指结点的前趋结点LinkList*q,*t;q=p;while(q-next-next!=p)//q-next不是p的前趋结点q=q-next;t=q-next;//t指向要删除结点q-next=p;//删除t结点free(t);｝【例2-4】试设计实现删除单链表中值相同的多余结点的算法。解：该例可以这样考虑，先取开始结点的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。设单链表（其类型为LinkList）的头指针head指向头结点，则可按下列步骤执行：首先，用一个指针p指向单链表中第一个表结点，然后用另一个指针q查找链表中其余结点元素，由于是单链表，故结束条件为p==NULL，同时让指针s指向q所指结点的前趋结点，当查找到结点具有q-data==p-data时删除q所指的结点，然后再修改q，直到q为空；然后使p指针后移（即p=p-next），重复进行，直到p为空时为止。算法描述如下：del(LinkList*head){//删除单链表中值相同的多余结点LinkList*p,*s,*q;p=head-next;while(p!=NULL&&p-next!=NULL){s=p;//s指向要删除结点的前趋q=p-next;while(q!=NULL){if(q-data==p-data)}//查找值相同的结点并删除{s-next=q-next;free(q);q=s-next;}else{s=q;q=q-next;}}p=p-next;}}习题2一、单项选择题1.线性表是________。1．AA．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动个元素。2．AA．n-iB．n-i+lC．n-i-1D．i