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

数据结构与算法概论复习习题[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 的值大于的值