算法与数据结构C语言习题参考答案-章.doc

. 精选范本 绪 论 1．将下列复杂度由小到大重新排序： A．2n B．n! C．n5 D．10 000 E．n*log2 (n) 【答】10 000 n*log2(n) n5 2n n! 2．将下列复杂度由小到大重新排序： A．n*log2(n) B．n + n2 + n3 C．24 D．n 【答】24 n0.5 n*log2 (n) n + n2 + n3 3．用大“O”表示法描述下列复杂度： A．5n5/2 + n2/5 B．6*log2(n) + 9n C．3n4+ n* log2(n) D．5n2 + n3/2 【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2) 4．按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/3。又n！应排在第几位？ 【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。 n！的增长率比它们中的每一个都要大，应排在最后一位。 5. 计算下列程序片断的时间代价： int i=1; while(i=n) { printf(“i=%d\n”,i); i=i+1; } 【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为： T(n) = 1 + n + 2n = 3n+ 1 = O(n) 6. 计算下列程序片断的时间代价： int i=1; while(i=n) { int j=1; while(j=n) { int k=1; while(k=n) { printf(“i=%d,j=%d,k=%d\n”,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. 线性表 1.试写一个插入算法int insertPost_seq(palist, p, x )，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。 【答】 数据结构 采用2.1.2 int insertPost_seq(PseqList palist, int p, DataType x ){ /* 在palist所指顺序表中下标为p的元素之后插入元素x */ int q; if ( palist-n = palist- MAXNUM ) { /* 溢出 */ printf(“Overflow!\n”); return 0; } if (p0 || ppalist-n-1 ) { /* 不存在下标为p的元素 */ printf(“Not exist! \n”); return 0; } 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 */ return 1; } 2试写一个删除算法deleteV_seq(palist, x )，在palist所指顺序表中，删除一个值为x的元素，返回删除成功与否的标志。 【答】 数据结构 采用2.1.2 int deleteV_seq(PseqList palist, p, DataType x ) { /* 在palist所指顺序表中删除值为x的元素 */ int p,q; for(p=0;pn;p++) /*查找值为x的元素的下标*/ if(x==palist-element[p]){ for(q=p; qpalist-n-1; q++) /* 被删除元素之后的元素均前移一个位置 */ palist-e