耿国华数据结构C语言的描述课后大部分习题答案.doc

第一章 三、计算下列程序段中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+1 )/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+n )/2 f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n /6+n /2+n/3 区分语句频度和算法复杂度： O(f(n)) = O(n ) 四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +…a x 的值P (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能 使用求幂函数。注意：本题中的输入a (i=0,1,…,n), x和n，输出为P (x ).通常算法的输入和输出可采用下列两种方式之一： （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; 第二章 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1） 在顺序表中插入或删除一个元素，需要平均移动 一半 元素，具体移动的元素个数与 插入或删除的位置 有关。 （2 ） 在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上相邻的元素，其物理位置 相邻。 （3） 在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 其直接前趋的next 域 指示。 2.3 已知L 是无表头结点的单链表，且P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是： （4 ）、（1） 。 b. 在P结点前插入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; 2.4 已知线性表L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表L的有序性。 [提示]：void insert(SeqList *L; ElemType x) 方法 1 （1）找出应插入位置i，（2 ）移位，（3）…… 方法2 参P. 229 2.5 写一算法，从顺序表中删除自第i 个元素开始的k 个元素。 [提示]：注意检查i 和k 的合法性。（集体搬迁，“新房”、“旧房”） 方法 1 以待移动元