文档介绍：课后答案数据结构第一章三、计算下列程序段中 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; (1) 找到第一个应删结点的前驱 pre pre=L; p=L - >next; while (p!=NULL &&p- >data <= mink) { pre=p; p=p - >next; } (2) 找到最后一个应删结点的后继 s ,边找边释放应删结点 s=p; while (s!=NULL &&s- >data < mink) 课后答案网 {t =s; s=s - >next; free(t); } (3) pre - >next = s; 试分别以不同的存储结构实现线性表的就地逆置算法, 即在原表的存储空间将线性表( a1, a2..., an )逆置为( an, an-1,..., a1)。(1) 以一维数组作存储结构,设线性表存于 a(1:arrsize) 的前 elenum 个分量中。(2) 以单链表作存储结构。[ 方法 1]: 在原头结点后重新头插一遍[ 方法 2]: 可设三个同步移动的指针 p, q,r ,将 q 的后继 r 改为 p 假设两个按元素值递增有序排列的线性表 A和B, 均以单链表作为存储结构, 请编写算法,将A 表和 B 表归并成一个按元素值递减有序的排列的线性表 C, 并要求利用原表(即A 表和 B 表的) 结点空间存放表 C. [ 提示] :参例 2-1 < 方法 1> void merge(LinkList A; LinkList B; LinkList *C