数据结构与算法概论复习习题[2]

在程序设计中常用下列三种不同的出错处理方式

() 用exit语句终止执行并报告错误

() 以函数的返回值区别正确返回或错误返回

() 设置一个整型变量的函数参数以区别正确返回或某种错误返回

试讨论这三种方法各自的优缺点

解()exit常用于异常错误处理它可以强行中断程序的执行返回操作系统

()以函数的返回值判断正确与否常用于子程序的测试便于实现程序的局部控制

()用整型函数进行错误处理的优点是可以给出错误类型便于迅速确定错误

在程序设计中可采用下列三种方法实现输出和输入

() 通过scanf和printf语句

() 通过函数的参数显式传递

() 通过全局变量隐式传递

试讨论这三种方法的优缺点

解()用scanf和printf直接进行输入输出的好处是形象直观但缺点是需要对其进行格式控制较为烦琐如果出现错误则会引起整个系统的崩溃

()通过函数的参数传递进行输入输出便于实现信息的隐蔽减少出错的可能

()通过全局变量的隐式传递进行输入输出最为方便只需修改变量的值即可但过多的全局变量使程序的维护较为困难

设n为正整数试确定下列各程序段中前置以记号@的语句的频度

() i=; k=;

while(i<=n){

@ k += *i;

i++;

}

() i=; k=;

do {

@ k += *i;

i++;

} while(i<=n);

() i=; k=;

while (i<=n) {

i++;

@ k += *i;

}

() k=;

for(i=; i<=n; i++) {

for(j=i; j<=n; j++)

@ k++;

}

() for(i=; i<=n; i++) {

for(j=; j<=i; j++) {

for(k=; k<=j; k++)

@ x += delta;

}

() i=; j=;

while(i+j<=n) {

@ if(i>j) j++;

else i++;

}

() x=n; y=; // n是不小于的常数

while(x>=(y+)*(y+)) {

@ y++;

}

() x=; y=;

while(y>) {

@ if(x>) { x = ; y; }

else x++;

}

假设n为的乘幂并且n>试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）

int Time(int n) {

count = ;x=;

while(x<n/) {

x *= ;count++;

}

return count;

}

已知有实现同一功能的两个算法其时间复杂度分别为O(n)和O(n)假设现实计算机可连续运算的时间为秒（多天）又每秒可执行基本操作（根据这些操作来估算算法时间复杂度)次试问在此条件下这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由

则对于同样的循环次数n在这个规模下第二种算法所花费的代价要大得多故在这个规模下第一种算法更适宜

设有以下三个函数

请判断以下断言正确与否

() f(n)是O(g(n))

() h(n)是O(f(n))

() g(n)是O(h(n))

() h(n)是O(n)

() h(n)是O(nlogn)

解()对 ()错 ()错 ()对 ()错

试设定若干n值比较两函数n和的增长趋势并确定n在什么范围内函数n的值大于的值

[] [] []