文档介绍：课后答案数据结构第一章三、计算下列程序段中 X=X+1 的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; [ 提示]: i=1 时: 1= (1+1) × 1/2 = (1+12)/2 i=2 时: 1+2 = (1+2) × 2/2 = (2+22)/2 i=3 时: 1+2+3 = (1+3) × 3/2 = (3+32)/2 … i=n 时: 1+2+3+ ……+n= (1+n) × n/2 = (n+n2)/2 f(n) =[ (1+2+3+ ……+n) + (12 + 22+ 32+ ……+ n2)]/2 =[ (1+n) × n/2 + n(n+1)(2n+1)/6 ]/2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3 区分语句频度和算法复杂度: O(f(n)) = O(n3) 四、试编写算法求一元多项式 Pn(x)=a0+a1x+a2x2+a3x3+ … anxn 的值 Pn(x0) , 并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。注意:本题中的输入 ai(i=0,1, …,n), x和n ,输出为 Pn(x0). 通常算法的输入和输出可采用下列两种方式之一: (1 )通过参数表中的参数显式传递; (2 )通过全局变量隐式传递。试讨论这两种方法的优缺点, 并在本题算法中以你认为较好的一种方式实现输入和输出。[ 提示]: float PolyValue(float a[ ], float x, int n){ ……} 核心语句: p=1; (x 的零次幂) s=0; i从0到n 循环 s=s+a[i]*p; p=p*x; 或: p=x; (x 的一次幂) s=a[0]; i从1到n 循环 s=s+a[i]*p; p=p*x; 第二章描述以下三个概念的区别:头指针,头结点,首元素结点。填空: (1) 在顺序表中插入或删除一个元素, 需要平均移动__一半__ 元素,具体移动的元素个数与__插入或删除的位置__有关。(2) 在顺序表中, 逻辑上相邻的元素, 其物理位置______相邻。在单链表中, 逻辑上相邻的元素, 其物理位置______相邻。(3) 在带头结点的非空单链表中, 头结点的存储位置由_____ _指示, 首元素结点的存储位置由______指示, 除首元素结点外,其它任一元素结点的存储位置由__其直接前趋的 next 域__ 指示。已知 L 是无表头结点的单链表,且 P 结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。结点后插入 S 结点的语句序列是:_( 4 )、( 1 )_。结点前插入 S 结点的语句序列是:( 7 )、( 11 )、( 8 )、(4 )、( 1 )。 c. 在表首插入 S 结点的语句序列是:( 5 )、( 12 )。 d. 在表尾插入 S 结点的语句序列是:( 11)、(9)、(1)、(6)。供选择的语句有: (1) P->next=S; (2) P->next= P->next->next; (3) P->next= S->next; (4) S->next= P->next; (5) S->next= L; (6) S->next= NULL; (7) Q= P; (8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; ( 10) P= Q; ( 11) P= L; ( 12) L= S; ( 13) L= P; 已知线性表 L 递增有序。试写一算法,将X 插入到 L 的适当位置上,以保持线性表 L 的有序性。[ 提示]: void insert(SeqList *L; ElemType x) < 方法 1>(1 )找出应插入位置 i ,( 2 )移位,( 3) ……< 方法 2>参 P. 229 写一算法,从顺序表中删除自第 i 个元素开始的 k 个元素。[ 提示] :注意检查 i和k 的合法性。(集体搬迁, “新房”、“旧房”) < 方法 1> 以待移动元素下标 m(“旧房号”)为中心, 计算应移入位置( “新房号”): for ( m=i- 1+k; m<= L- >last; m++) L- >elem[ m-k]=L- >elem[ m ]; < 方法 2> 同时以待移动元素下标 m 和应移入位置 j 为中心: < 方法 2> 以应移入位置 j 为中心,计算待移动元素下标: 已知线性表中的元素( 整数) 以值递增有序排