数据结构习题有标准答案VIP免费

1/21第1章绪1.1有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1)A=(D，R)，其中，D={a1，a2，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，R)，其中，D={1，2，3，4，5，6}，R={<1，2>，<2，3>，<2，4>，<3，4>，<3，5>，<3，6>，<4，5>，<4，6>}(1)集合(2)线性表abcde(3)树fgabcde(4)图1453621.2设n为正整数，求下列各程序段中的下划线语句的执行次数。(1)i=1;k=0while(i<=n-1){k+=10*i;i++;}(2)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){c[i][j]=0;for(intk=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]}解：(1)n-1(2)ninjnkn11131(3)x=0;y=0;for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)for(intk=1;k<=j;k++)x=x+y;(3)62)1)(nn(n21)(216)12)(1(2121212)1(1112111111nnnnniiiijnininiijjkniijni2/211.3指出下列个算法的功能，并求其时间复杂度。(1)intsum1(intn){intp=1,s=0;for(inti=1;i<=n;i++){p*=i;s+=p;}returns;}(2)intsum2(intn){ints=0;for(inti=1;i<=n;i++){intp=1;for(intj=1;j<=i;j++)p*=j;s+=p;}returns;}解：(1)n1ii!,T(n)=O(n)(2)n1ii!,T(n)=O(n2)1.4算法设计有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设a,b,c为3个整数，求其中位于中间值的整数。开始A=B？A=C？A是伪币C是伪币B是伪币结束是是否否3/21第2章线性表1.设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。intSqlist::DeleteElem(Te){for(i=1;i<=length;i++)//按值顺序查找*i可从0开始if(elem[i-1]==e)//找到，进行删除操作{for(j=i;j::Locate(Te)的时间复杂度。解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n定位成功第i个元素，需比较i次212)1(111)(11nnnnininnfnini3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i个结点ai；p=head;j=0;while(p&&jnext;j++;}(2)定位到第i个结点的前驱ai-1；p=head;j=0;while(p&&jnext;j++;}4/21(3)定位到尾结点；p=head;while(p->next)p=p->next;(4)定位到尾结点的前驱。p=head;while(p->next->next)p=p->next;4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。首元结点：指链表中的第一个元素结点。头结点...a^a1a2⋯n首(元)结点尾(元)结点头指针5/215.对于无头结点单链表，给出删除第i个结点的算法描述。templateTLinkList::Delete(inti)templateTLinkList::Delete(inti){//在单链表上删除第i个数据元素if(head==NULL)throw“表空!”;//空表，不能删elseif(i==1){//删除第1个元素p=Head;x=p->data;//保存被删元素值Head=p->next;deletep;}else{//元素定位到第ai-1p=Head;j=1;//定位查找起始位置while{p->next&&jnext;j++;}if(!p->next||j>i-1);//定位失败throw“删除位置不合理”;else{//定位成功，进行结点删除q=p->next;x=p>data;p->next=q->next;deleteq;}retrunx;//返回被删除元素值}//#6.用教材定义的顺序表的基本操作实现下列操作：templateintDeleteElem(SqListL,Te)#include“SqList.h“templateintDeleteElem(SqListL,Te){//i=L.LocateElem(e);//按值查找6/21if(!i)//未找到return0;else//找到delete(i);//删除被找到的元素}7.已知L是有表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句...