2004年华北计算技术研究所专业课试题答案.doc

2004年专业基础课参考答案 1．（10分） 以n、ai(i=0,1, ．．．，n)、x0作为输入，为了进行一元n次多项式Pn(x)=a0xn+a1xn-1+a2xn-2+…+an-1x+an在x0点的值Pn(x0)的计算，请给出你认为效率最好的算法。 参考答案： sum = a0; for(int i=1;i=n;i++) { sum = sum * x0 + ai; } （2）给出上述算法的基本操作、基本操作执行次数和时间复杂度。 参考答案： 基本操作： sum = sum * x0 + ai 基本操作执行次数：n 时间复杂度：O(n) 2．（10分） 设有三对角矩阵（aij）nxn，将其三条对角线上的元素逐行地存于数组B[3n-2]中，使得B[k]=aij，求： （1）用i，j表示k的下标变换公式； （2）用k表示i，j的下标变换公式。 参考答案： k = 2* i + j – 3 (|i-j|≤1) i = [(k+1)/3] + 1 （0≤k≤3n-1） j = k+1 – 2 * [k/3] 3．（10分） 已知一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树，并给出计算或推理过程。 参考答案： E B F A D H C G I K J 已知一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，请画出该树，并给出计算或推理过程。 参考答案： A B I C G H J D E F K 4．（15分） 某人自下往上走完一个N级的台阶，每步只能走一级或两级台阶： 给出能够计算出上述台阶所有走法的递归算法。 以C或C++实现上述算法。 参考答案： step(1) 如果n = 1 walk(n) = {step (1) || step(1)} ∪ step(2) 如果n = 2 {step(1) || walk(n-1)} ∪ {step(2) || walk(n-2)} 如果n ≥ 3 5．（20分） 下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。请用Dijkstra算法计算v0到各点的最短路径及路径的长度（要求给出计算过程）。 参考答案： v0到 v1 的最短路径是（v0,v3,v1）,最短路径的长度为4 v0到 v2 的最短路径是（v0,v2）或（v0,v3,v1,v2）,最短路径的长度为7 v0到 v3 的最短路径是（v0,v3）,最短路径的长度为2 v0到 v4 的最短路径是（v0,v3,v4）,最短路径的长度为4 v0到 v5 的最短路径是（v0,v3,v1,v2,v5）或（v0,v2，,v5）,最短路径的长度为8 6．（30分） 已知如下所示长度为12的表 （Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec） （1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。 （2）若对表中元素先进行排序构成有序表，求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。 （3）请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。 参考答案： （1） Jan Feb Mar Apr June May Aug July Sep Dec Oct Nov 在等概率情况下平均查找长度=（1*1+2*2+3*3+4*3+5*2+6