数据结构习题(有答案)

《数据结构习题(有答案)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章绪1.1冇下列几种二元组表示的数据结构，试a出它们分别对应的图形表示，⑴集合并指出它们分别属于何种结构。(1)A=(D,R),其中，D={a,,如，a3，a4),R={}⑵线性表(2)B=(D,R),其中，D={a,b，c,d,e},R={(a，b)，(b,c)，(c,d)，(d，e)}(3)C=(D,R),其屮，D={a,b，c，d，e，f，g}，R={(d，b)，(d，g)，)(b,a),(b，c)，(g,e),(e,f)}(4)K=(D，K)，•其中，D={1，2，3，4，5,6}，K={<1,2〉，〈2,rJ©(3J3>,〈2,4〉

2、，〈3，4>，〈3,5〉，〈3，6>,<4,5>,<4,6>}(3)树①⑷阁1.2设n为正整数，求下列各程序段中的下划线语句的执行次数。(l)i=l;k=O(2)for(inti=l;i<=n;i++)解:while(i<=n-l)for(intj=l;j<=n;j++)(l)n-l{{c[i]U]=O;nnnk+=10*i;for(intk=l;k<=n;k++)i++；}cfilfi

3、=cfi

4、fi

5、+afilfkl*bfkllil}/=1;=iA=i(3)x=0;y=0;for(inti=l;i<=n;i++)(3)nijniyyy)=yy

6、j=/=!LZ/=!L/=11n(z?+l)(2n+l)(1n(n+1)i=ijt=i/=iy=iZ02Lfor(intj=1;j<=i;j++)n(n+l)(n+2)for(intk=l;k<=j;k++)6x=x+y;i.3指出下列个算法的功能，并求艽时间a杂度。(1)intsuml(intn){intp=l，s=O;for(inti=l;i<=n;i++){p*=i;s+=p;}returns;}(2)intsum2(intn){int$=0;for(inti=l;i<=n;i++){intp=l;for(intj=l;j<=i;j++)p

7、*=j；s+=p;}returns;}解：n(1)[i!，T(n):O⑻i=ln(2)fi!，T(n)=O(n2)i=l1.4算法设计有3枚硬币，W屮柯1枚是假的，伪币与真币重撒略存不同。如何借用一架天平，找出伪iT?以流程图表示算法。f一开始一A=B?>►C是伪币、_》是

8、,A=C?——►B足伪币—►［丫否飞A足伪币::结Mi上机练习题耍求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设a，b，c为3个整数，求其屮位于中间位的整数。第2章线性表1.设计算法：在顺序表中删除值为e的元素，删除成功，返回1;否则，返回0。intSqlis

9、t::DeleteElem(Te){for(i=l;i<=length;i++)//按位顺序杏找*i可从0开始if(elem[i-l]==e)//找到，进行删除操作{for(j=i;j::Locate(Te)的时间复杂度。解：设表长为n,等概率下，每个元素被定位的概率为：p=l/n定位成功第i个

10、元素，需比较i次Zin223.对于有久•结点的单链表，分別写出定位成功吋，实现下列定位语句序列。(1)定位到第i个结点ai;p=head;j=0;while(p&&jnext;j++;}(2)定位到第i个结点的前驱ay;p=head;j=0;while(p&&jnext;j++;}(3)定位到尾结点；p=head;while(p-〉next)p=p-〉next;(4)定位到尾结点的前驱。p=head;while(p->next->next)p=p->next;4.描述一下三个概念的区别：头指针，头结点，首元

11、结点。并给头指针：是一个指针变撒，甩面存储的是链表屮首结点的地址，并以此来标识一个链表。予阁示。头结点:附加在第首元结点：指链表央推针央格成一个元素结点之前的一个结点，尖指针指向尖结点。屮的第一个元素结点。甘(元僻点叫元)休成hj3^2"I~an八5.对于无爻结点单链表，给出删除第i个结点的算法描述。templateTLinkLi$t::Delete(inti)templateTLinkList::Delete(inti){//在单链表上删除第i个数据元素if(head==NULL)throw“表空!”

12、;//空表，不能删elseif(i==l){//删除第1个元素p=Head;x=p->data;//促存被删元素值Head=p-〉nex