数据结构作业.doc

数据结构作业
数据结构****题
第一章绪论
在程序设计中,常用下列三种不同的出错处理方式:
1) 用exit语句终止执行并报告错误;
2) 以函数的返回值区别正确返回或错误返回;
3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。
在程序设计中,可采用下列三种方法实现输出和输入:
1) 通过scanf和printf语句;
2) 通过函数的参数显示传递;
3) 通过全局变量隐式传递。
试讨论这三种方法的优缺点。
设n为正整数。试确定下列各程序段中前置以记号@的语句的频度:
5) for (i = 1; i <= n; i++ ) {
for (j = 1; j <= i; j++) {
for (k = 1; k <= j; k++) {
@ x += delta;
}
}
}
答案:n*(n+1)*(n+2)
=1+(1+2)+(1+2+3)+...+(1+2+3+...+n)
=i*(i?1)/2 ?i?1n
=1/2*i*i?i?i?1n
=n*(n+1)*(2n+1)/12 +n*(n+1)/4
=n*(n+1)*(n+2)/6
7) x = n; //n是不小于1的常数
y = 0;
while (x >= (y + 1) * (y + 1)) {
@ y++;
} 答案:n 向下取整
8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;}
else {
x++;
}
}
答案:if执行次数为1100, if判断内部执行为100次
试编写算法,计算i!·2i(i = 0, 1, ?, n-1)的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT,则当n > arrsize或对某个k(0 ≤ k ≤ n-1)使k!·2k > MAXINT时,应按出错处理。注意选择你认为较好的出错处理方法。
试编写算法求一元多项式Pn(x)??axi
i?0ni 的值Pn(x0),并确定算法中每一语句的执行
次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai(i=0, 1, ?, n)、x0和n,输出为Pn(x0)。
第二章线性表
设顺序表va中的数据元素非递减有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
设A=(a1,?,am)和B=(b1,?,bn)均为顺序表,A’和B’分别为A和B中除去最大共同前缀后的子表(例如,A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者中最大的共同前缀为(x,y,y,z),在两表中除去最大共同前缀后的子表分别为A’=(x,z)和B’=(y,x,x,z))。若A’=B’=空表,则A=B;若A’=空表,而B’≠空表,或者两者均不为空,且A’的首元小于B’的首元,则A < B,否则A > B。试写一个比较A