数据结构课后习题答案.doc

《数据结构课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1=n(n-1)/2，所以执行时间为O（n2）（6）O()第2章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL){if(L->next==NULL)returnNULL;pmax=L->next;//假定第一个结点中数据具有最大值p=L->next->next;while(p!=NULL){//如

2、果下一个结点存在if(p->data>pmax->data)pmax=p;p=p->next;}returnpmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L->next;L->next=NULL;while(p){q=p->next;//q指向*p的后继p->next=L->next;L->next=p;//*p插入在头结点之后p=q;}}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线

3、性表中所有值为item的数据元素。[题目分析]在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。voidDelete（ElemTypeA[]，intn）∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。{i=1；j=n；∥设置数组低、高端指针（下标）。while（i

4、=item）i++；∥若值不为item，左移指针。if（i

5、义　#defineStackSize100//假定预分配的栈空间最多为100个元素　typedefcharDataType;//假定栈元素的数据类型为字符　typedefstruct{　　DataTypedata[StackSize];　　inttop;　}SeqStack; 　intIsHuiwen(char*t)　　{//判断t字符向量是否为回文，若是，返回1，否则返回0　　　SeqStacks;　　　inti,len;　　　chartemp;　　　InitStack(&s);　　　len=strlen(t);//求向量长度　　　for(i=0;i

6、　　　Push(&s,t[i]);　　　while(!EmptyStack(&s))　　　　{//每弹出一个字符与相应字符比较　　　　　temp=Pop(&s);　　　　　if(temp!=S[i]) return0;//不等则返回0　　　　　elsei++;　　　　} 　　　return1;//比较完毕均相等则返回1　　}（7）假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列

7、类定义#includetemplateclassQueue{//循环队列的类定义public:Queue(int=10);~Queue(){delete[]Q;}voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty(){front=rear=tag=0;}//置空队列intIsE