数据结构与算法课后习题解答.doc

《数据结构与算法课后习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第一章绪论（参考答案）1.3(1)O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/2)(5)(5)执行程序段的过程中，x,y值变化如下：循环次数xy0（初始）91100192100293100………………9100100101011001191991292100………………2010199219198………………3010198319197到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.52100,(2/3)n,log2n,n1/2,n3/2,(3/2)n,nlog2n,2n,n!,nn第二章线性

2、表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#defineMAXSIZE1024typedefintElemType;//实际上，ElemType可以是任意类型typedefstruct{ElemTypedata[MAXSIZE];intlast;//last表示终端结点在向量中的位置}sequenlist;（2）链式存储结构（单链表）typedefstructnode{ElemTypedata;structnode*next；}linklist;（3）链式存储结构（双链表）typedefstructn

3、ode{ElemTypedata;structnode*prior,*next；}dlinklist;（4）静态链表typedefstruct{ElemTypedata;intnext;}node;nodesa[MAXSIZE];2.1头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当

4、然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2·3voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。{inti=0,j;while(i=i;j--)A[j+1]=A

5、[j];//向后移动元素A[i]=x;//插入元素}//算法结束2·4voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。{intnum=0;//计数，最终应等于nintstart=0;//记录开始位置（下标）while(num

6、=start){A[empty]=A[next];//右移num++;//右移元素数加1empty=next;next=(next-K+n)%n;//计算新右移元素的下标}A[empty]=temp;//把一轮右移中最后一个元素放到合适位置num++;start++;//起点增1，若num

7、右移k位，且只用一个辅助空间。{ElemTypetemp;for(i=0;i<(n-k)/2;i++)//左面n-k个元素逆置{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i]=temp;}for(i=1;i<=k;i++)//右面k个元素逆置{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i]=temp;}for(i=0;i

8、nklist*L,ElemTypex)//带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。{linklist*p=L->next,*pre=L，*s;//p为工作指针，指向当前元素，pre为前驱指针，指向当前