解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明：
(1)
?ii?1nn2?n?n?1??2n?1?/6
?1/?x?1?
?n?0? ?x?1,n?0?
(2)
?x??xii?0nn?1?
(3)
?2i?1ni?1?2n?1
?n?1? ?n?1?
(4)
??2i?1??ni?12
1.16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值
解：
int max3(int x,int y,int z) { }
1.17 已知k阶斐波那契序列的定义为
if(x>y) else
if(y>z) return y; else return z; if(x>z) return x; else return z;
f0?0，f1?0，…，fk?2?0，fk?1?1； fn?fn?1?fn?2???fn?k，n?k,k?1,?
试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
解：k>0为阶数，n为数列的第n项 int Fibonacci(int k,int n) {
if(k<1) exit(OVERFLOW); int *p,x;
p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j;
for(i=0;i } for(i=k+1;i if(i } 1.18 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为 项目名称 解： typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{ char event[3]; //项目 SexType sex; SchoolName school; int score; 性别 校名 成绩 得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。 } return p[k]; x=p[0]; for(j=0;j } Component; typedef struct{ int MaleSum; int FemaleSum; //男团总分 //女团总分 int TotalSum; //团体总分 } Sum; Sum SumScore(SchoolName sn,Component a[],int n) { } 1.19 试编写算法，计算i!*2的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个kiSum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i; for(i=0;i temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp; if(a[i].school==sn){ } if(a[i].sex==Male) temp.MaleSum+=a[i].score; if(a[i].sex==Female) temp.FemaleSum+=a[i].score; ?1?k?n?，使k!?2k?maxint时， 应按出错处理。注意选择你认为较好的出错处理方法。 解： #include int main() { } 1.20 试编写算法求一元多项式的值Pnint i,k; int a[ArrSize]; cout<<\cin>>k; if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ } for(i=0;i<=k;i++){ } return 0; if(a[i]>MAXINT) exit(0); else cout< if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1]; ?x???aixi的值Pn?x0?，并确定算法中每一语句的执行次数 i?0n和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai和n，输出为Pn解： #include double polynomail(int a[],int i,double x,int n); int main() { double x; int n,i; ?i?0,1,?,n?，x0?x0?。 } double polynomail(int a[],int i,double x,int n) { } 本算法的时间复杂度为o(n)。 if(i>0) return a[n-i]+polynomail(a,i-1,x,n)*x; else return a[n]; int a[N]; cout<<\输入变量的值x:\cin>>x; cout<<\输入多项式的阶次n:\cin>>n; if(n>N-1) exit(0); cout<<\输入多项式的系数a[0]--a[n]:\for(i=0;i<=n;i++) cin>>a[i]; cout<<\return 0; 第2章 线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); for(i=1;i<=4;i++){ } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; P=L;