数据结构作业要领.docVIP

数据结构习题 第一章 绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设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) = =1/2* =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++; } 答案： 向下取整 8) x = 91; y = 100; while (y 0) { @ if (x 100) { x -= 10; y--;} else { x++; } } 答案：if执行次数为1100， if判断内部执行为100次 1.19 试编写算法，计算i!·2i（i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT，则当n arrsize或对某个k（0 ≤ k ≤ n-1）使k!·2k MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式 的值Pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai（i=0, 1, …, n）、x0和n，输出为Pn(x0)。第二章 线性表 2.11 设顺序表va中的数据元素非递减有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 2.12 设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、B大小的算法（请注意：在算法中，不要破坏原表A和B，并且也不一定先求得A’和B’才进行比较）。 2.19 已知线性表中的元素以值非递减有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删节点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 2.22 试写一算法，对单链表实现就地（原地）逆置。 2.38 设有一双向循环链表，每个结点中除有prior，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的置均初始化为零，而每当对链表进行一次LOCATE（L，x）的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。 2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）的结点。第三章 栈和队列 3.17 试写一算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1序列2’模式的字符序列。其中序列1和序列2中都不包含字符‘’，且序列2是序列1的逆序列。例如‘a+bb+a’是属于该模式的字符序列，而‘1+33-1’则不是。 3.21 假设表达式由单字母变量和双目四则运算符构成。试写一算法，将