数据结构作业.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) =??? niii 12/)1(* =1/2*??? niiii 1* =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!·2 i(i= 0, 1,…, n-1 ) 的值并分别存入数组 a[arrsize] 的各个分量中。假设计算机中允许的整数最大值为 MAXINT ,则当 n> arrsize 或对某个 k(0≤k≤ n-1 )使 k!·2 k> MAXINT 时,应按出错处理。注意选择你认为较好的出错处理方法。 试编写算法求一元多项式??? ni iixax 0 n)(P 的值 P n (x 0), 并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为 a i ( i=0, 1,…,n)、x 0和n ,输出为 P n (x 0)。第二章线性表 设顺序表 va 中的数据元素非递减有序。试写一算法,将x 插入到顺序表的适当位置上, 以保持该表的有序性。 设A =( a 1,…,a m )和 B =( b 1,…,b n )均为顺序表, 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、B 大小的算法(请注意:在算法中,不要破坏原表 A和B ,并且也不一定先求得 A’和B’才进行比较)。 已知线性表中的元素以值非递减有序排列, 并以单链表作存储结构。试写一高效算法, 删除表中所有值大于 mink 且小于 maxk 的元素( 若表中存在这样的元素) 同时释放被删节点空间, 并分析你的算法的时间复杂度( 注意: mink 和 maxk 是给定的两个参变量, 它们的值可以和表中的元素相同,也可以不同)。 试写一算法,对单链表实现就地(原地)逆置。 设有一双向循环链表, 每个结点中除有 prior , data 和 next 三个域外, 还增设了一个访问频度域 freq 。在链表被起用之前, 频度域 freq 的置均初始化为零, 而每当对链表进行一次 LOCATE (L,x )的操作后,被访问的结点(即元素值等于 x 的结点)中的频度域 fre q 的值便增 1, 同时调整链表中结点之间的次序,使其按访问频度非递增的次序顺序排列,以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE 操作的算法。 试以循环链表作稀疏多项式的存储结构,编写求其导函数的算法,要求利用原多项式中的结点空间存放其导函数(多项式) ,同时释放所有无用(被删)的结点。第三章栈和队列 试写一算法, 识别依次读入的一个以@ 为结束符的字符序列是否为形如‘序列 1& 序列 2’模式的字符序列。其中序列 1 和序列 2 中都不包含字符‘& ’, 且序列 2 是序列 1 的逆序