2、3n,3n,20n,2000,log2n,n2/3。又n！应排在第几位？【答】按照增长率从低到高依次为：2000,log3n,log2n,n2/3,20n,4n2,3n。n！的增长率比它们中的每一个都要大，应排在最后一位。5.计算下列程序片断的时间代价：inti=1;while(i<=n){printf(“i=%d”,i);i=i+1;}【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为：T(n)=1+n+2n=3n
3、+1=O(n)6.计算下列程序片断的时间代价：inti=1;while(i<=n){intj=1;while(j<=n){intk=1;while(k<=n){printf(“i=%d,j=%d,k=%d”,I,j,k);k=k+1;}j=j+1;}i=i+1;}【答】循环控制变量i从1增加到n，最外层循环体执行n次，循环控制变量j从1增加到n，中间层循环体执行n次，循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：T(n)=1+n+n｛1+n+n[1+n+2n+1]+1+1｝+1=3n3+3n2+4n+2=O(n3)2.线性表
4、1.试写一个插入算法intinsertPost_seq(palist,p,x)，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。【答】数据结构采用2.1.2节中顺序表定义。intinsertPost_seq(PseqListpalist,intp,DataTypex){/*在palist所指顺序表中下标为p的元素之后插入元素x*/intq;if(palist->n>=palist->MAXNUM){/*溢出*/printf(“Overflow!”);return0;}if(p<0
5、
6、p>palist->n-1
7、){/*不存在下标为p的元素*/printf(“Notexist!”);return0;}for(q=palist->n-1;q>=p+1;q--)/*插入位置及之后的元素均后移一个位置*/palist->element[q+1]=palist->element[q];palist->element[p+1]=x;/*插入元素x*/palist->n=palist->n+1;/*元素个数加1*/return1;}2试写一个删除算法deleteV_seq(palist,x)，在palist所指顺序表中，删除一个值为x的元素，返回删除成功与否的标志。【答】数据
8、结构采用2.1.2节中顺序表定义。intdeleteV_seq(PseqListpalist,p,DataTypex){/*在palist所指顺序表中删除值为x的元素*/intp,q;for(p=0;pelement[p]){for(q=p;qn-1;q++)/*被删除元素之后的元素均前移一个位置*/palist->element[q]=palist->element[q+1];palist->n=palist->n-1;/*元素个数减1*/return1;}return
9、0;}3.设有一线性表e=(e0,e1,e2,…,en-1)，其逆线性表定义为e¢=(en-1,…,e2,e1,e0)。请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的空间。【答】数据结构采用2.1.2节中顺序表的定义。思路考虑对数组element[]进行置逆，即把第一个元素和最后一个元素换位置，把第二个元素和倒数第二个元素换位置……。A注意这种调换的工作只需对数组的前一半元素进行，所以设置整数变量count用于存放数组长度的一半的值。大家可以考虑一下：为什么不能对整个数组进行如上的对元素“换位置”的工作？（提示：这样会将本来已经置逆的
10、线性表又置逆回来，即又变成了原来的表。
