数据结构习题(有答案).doc

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

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(intj=1;j

3、<=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;j

5、i至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)定位到第i个结

6、点的前驱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{//定位成功，进行