数据结构与算法第章习题.pptVIP

数据结构 ——第1、2章习题解答 第1章 绪论 4.（2）执行下面程序段的时间复杂度为 . for(int i=0; im; i++) for(int j=0; jn; j++) a[i][j] = i*j; （3）执行下面程序段时，语句S的执行次数为 。 for(int i=0; i=n; i++) for(int j=0; j=i; j++) S; 5.计算下面程序段中x=x+1的语句频度。 for( i=1; i=n; i++) for(j=1; j=i; j++) for(k=1; k=j; k++) x=x+1; 6. 编写算法，求一元多项式 Pn(x)=a0+a1x+a2x2+a3x3+…+anxn 的值Pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用冪函数。 int f(int a[ ],int x,int n) { int s,i; s=a[n]; for(i=n-1;i=0;i--) s=s*x+a[i]; return(s); } 时间复杂度为O(n); 语句执行次数为： 1 n 1 第2章 线性表 第2章 线性表 2.(2) 已知L是无表头结点的单链表，且p结点既不是首元素结点，也不是尾元素结点，按要求从下列语句中选择合适的语句序列。 A. P-next=S; B. P-next=P-next-next; C. P-next=S-next; E. S-next=P-next; F. S-next=L; G. S-next=NULL; H. Q=P; I. while( P-next!=Q ) P=P-next; J. while( P-next!=NULL ) P=P-next K. P=Q; L. P=L; M. L=S; N. L=P; A. 在P结点后插入S结点的语句序列是 E A A. P-next=S; B. P-next=P-next-next; C. P-next=S-next; E. S-next=P-next; F. S-next=L; G. S-next=NULL; H. Q=P; I. while( P-next!=Q ) P=P-next; J. while( P-next!=NULL ) P=P-next K. P=Q; L. P=L; M. L=S; N. L=P; B. 在P结点前插入S结点的语句序列是 H L I E A A. P-next=S; B. P-next=P-next-next; C. P-next=S-next; E. S-next=P-next; F. S-next=L; G. S-next=NULL; H. Q=P; I. while( P-next!=Q ) P=P-next; J. while( P-next!=NULL ) P=P-next K. P=Q; L. P=L; M. L=S; N. L=P; C. 在表首插入S结点的语句序列是 F M A. P-next=S; B. P-next=P-next-next; C. P-next=S-next; E. S-next=P-next; F. S-next=L; G. S-next=NULL; H. Q=P; I. while( P-next!=Q ) P=P-next; J. while( P-next!=NULL ) P=P-next K. P=Q; L. P=L; M. L=S; N. L=P; D. 在表尾插入S结点的语句序列是 J A G J G A G J A J E A 4.已知顺序表L递增有序，编写一个算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 void sqinsert