欢迎来到天天文库
浏览记录
ID:34932059
大小:700.50 KB
页数:21页
时间:2019-03-14
《数据结构习题集(有答案解析)》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、第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
2、>,<3,5>,<3,6>,<4,5>,<4,6>}(1)集合(2)线性表(3)树(4)图1.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)(3)x=0;y=0;for(inti=1;i<=n;i++)for(int
3、j=1;j<=i;j++)for(intk=1;k<=j;k++)x=x+y;(3)1.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),T(n)=O(n)(2),T(n)=O(n2)1.4算法设计有3枚硬币
4、,其中有1枚是假的,伪币与真币重量略有不同。如何借用一架天平,找出伪币?以流程图表示算法。上机练习题要求:给出问题分析、算法描述、源程序及运行截图,在线提交。1.设a,b,c为3个整数,求其中位于中间值的整数。第2章线性表1.设计算法:在顺序表中删除值为e的元素,删除成功,返回1;否则,返回0。intSqlist::DeleteElem(Te){for(i=1;i<=length;i++)//按值顺序查找*i可从0开始if(elem[i-1]==e)//找到,进行删除操作{for(j=i;j5、至an依次前移Elem[j-1]=elem[j];length--;//表长减一return1;//删除成功,返回1}return0;//未找到,删除不成功,返回0}2.分析顺序表中元素定位算法intSqList::Locate(Te)的时间复杂度。解:设表长为n,等概率下,每个元素被定位的概率为:p=1/n定位成功第i个元素,需比较i次3.对于有头结点的单链表,分别写出定位成功时,实现下列定位语句序列。(1)定位到第i个结点ai;p=head;j=0;while(p&&jnext;j++;}(2)定位到6、第i个结点的前驱ai-1;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.描述一下三个概念的区别:头指针,头结点,首元结点。并给予图示。头指针:是一个指针变量,里面存储的是链表中首结点的地址,并以此来标识一个链表。头结点:附加在第一个元素结点之前的一个结点,头指针指向头结点。首元结点:指链表中的第一个元素结点。7、5.对于无头结点单链表,给出删除第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;//定位查找起始8、位置while{p->next&&jnext;j++;}if(!p->next9、10、j>i-1);//定位失败throw“删除位置不合理”;else{//定位成功,进行结点删除q=p->next;x=p>data;p->next=q->nex
5、至an依次前移Elem[j-1]=elem[j];length--;//表长减一return1;//删除成功,返回1}return0;//未找到,删除不成功,返回0}2.分析顺序表中元素定位算法intSqList::Locate(Te)的时间复杂度。解:设表长为n,等概率下,每个元素被定位的概率为:p=1/n定位成功第i个元素,需比较i次3.对于有头结点的单链表,分别写出定位成功时,实现下列定位语句序列。(1)定位到第i个结点ai;p=head;j=0;while(p&&jnext;j++;}(2)定位到
6、第i个结点的前驱ai-1;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.描述一下三个概念的区别:头指针,头结点,首元结点。并给予图示。头指针:是一个指针变量,里面存储的是链表中首结点的地址,并以此来标识一个链表。头结点:附加在第一个元素结点之前的一个结点,头指针指向头结点。首元结点:指链表中的第一个元素结点。
7、5.对于无头结点单链表,给出删除第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;//定位查找起始
8、位置while{p->next&&jnext;j++;}if(!p->next
9、
10、j>i-1);//定位失败throw“删除位置不合理”;else{//定位成功,进行结点删除q=p->next;x=p>data;p->next=q->nex
此文档下载收益归作者所有