第1章绪1.1有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。R={}a}，，(1)A=(D，R)，其中，D={aa，a，4132，，d)R={(a，b)，(b，c)，(c(2)B=(D，R)，其中，D={a，b，c，d，e}，e)}(d，，，g)，b)，(d，R)，其中，D={a，b，c，d，e，f，g}R={(d，(3)C=(Df)}e)，(e，c)(b，a)，(b，，(g，，<2，，23，4，5，6}，R={<1，2>，(4)K=(D，R)，其中，D={16>}，，<4，5>，<46>4>3>，<2，4>，<3，，<3，5>，<3，(1)集合abcde(2)线性表12d51.2n为正整数，求下列各程序段中的下划线语句的执行次数。设(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-1nnn???3n1?(2)1??1j?y=0;(3)x=0;for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)for(intk=1;k<=j;k++)x=x+y;jnnninin1)?n(n2)(n?1)11ii(?1)n11n(?1?11?1?i?k1j1?i?1j?i1?i?1in(n?1)(n?2)?61.3指出下列个算法的功能，并求其时间复杂度。(1)intsum1(intn){intp=1,s=0;for(inti=1;i<=n;i++){p*=i;s+=p;}returns;}(2)intsum2(intn)解：{ints=0;n?i!,(1)T(n)=O(n)for(inti=1;i<=n;i++)i?1{intp=1;for(intj=1;j<=i;j++)p*=j;n?2i!)T(n)=O(n,(2)s+=p;i?1}returns;}算法设计1.4枚是假的，伪币与真币重量略有不同。如何借用一架13枚硬币，其中有有开始天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。个整数，求其中位于中间值的整数。3为a,b,c设1.第2章线性表；返回1在顺序表中删除值为e的元素，删除成功，1.设计算法：否则，返回0。intSqlist<T>::DeleteElem(Te){for(i=1;i<=len(elem[i-1]==e)//找到，进行删除操作{for(j=i;j<length;j++)//ai至an依次前移Elem[j-1]=elem[j];length--;//表长减一return1;//删除成功，返回1}return0;//未找到，删除不成功，返回0}2.分析顺序表中元素定位算法intSqList<T>::Locate(Te)的时间复杂度。解：设表长为n，等概率下，每个元素被定位的nn1n(n?1)11n?1???i??n()??i?fn2n2n1i1?i?对于有头结点的单链表，分别写出定位成功时，实现下列定位3.语句序列。；a(1)定位到第i个结点ip=head;j=0;while(p&&j<i){p=p->next;j++;}i(2)定位到第个结点的前驱；ai-1p=head;j=0;while(p&&j<i-1){p=p->next;j++定位到尾结点；(3)p=head;while(p->next)p=p->next;(4)定位到尾结点的前驱。p=head;p=p->next;while(p->next->next)4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表点：附加在第一个元素结点之前的一个结点，头个元素结点。头指针结点)元尾(头结点结点首)元(…...i个结点的算法描述。5.对于无头结点单链表，给出删除第template<calssT>TLinkList<T>::Delete(inti)template<calssT>TLinkList<T>::Delete(inti)(head==NULL)throw“表空!”;//空表，不能elseif(i==1){//删除第1个元素p=Head;x=p->data;//保存被删元素值Head=p->next;deletep;}else{//元素定位到第ai-1p=Head;j=1while{p->next&&j<i-1}{p=p->next;j++;}if(!p->next||j>i-1);//定位失败throw“删除位置不合理”;else{//定位成功，进行结点删除q=p->next;x=p>data;p->next=q->next;deleteq;}retrunx;//返回被删除元素值}//#6.用教材定义的顺序表的基本操作实现下列操作：template<calssT>intDeleteElem(SqListL,Te)#include“SqList.h“template<calssT>intDeL.LocateElem(e);//if(!i)//未找到return0;else//找到delete(i);//删除被找到的元素}7.已知L是有表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。结点；结点后插入(1)在PSS(2)在P结点前插入结点；(3)在表首插入S结点；.S(4)在表尾插入结点【解】(1)s->next=p->next;p->next=s;(2)q=L;while(qq->next=s;(3)s->next=L->next;L->next=s;(3)q=L;while(q->next!=NULL)q=q->next;s->next=q->next;q->next=s;上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。的元素。...