华北计算技术研究所2004年硕士研究生考试专业课试题

华北计算技术研究所2004年硕士研究生考试专业课试题

 

要求：1、答案必须写在答题纸上，标明题号；

2、答卷要字迹清楚，语义确切；

3、所有计算要求给出计算过程。

 

1．（10分）

（1）以n、a_i(i=0,1, ．．．，n)、x₀作为输入，为了进行一元n次多项式P_n(x)=a₀xⁿ+a₁x^n-1+a₂x^n-2+…+a_n-1x+a_n在x₀点的值P_n(x₀)的计算，请给出你认为效率最好的算法。

（2）给出上述算法的基本操作、基本操作执行次数和时间复杂度。

 

2．（10分）

设有三对角矩阵（a_ij）nxn，将其三条对角线上的元素逐行地存于数组B[3n-2]中，使得B[k]=a_ij，求：

（1）用i，j表示k的下标变换公式；

（2）用k表示i，j的下标变换公式。

 

3．（10分）

（1）已知一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树，并给出计算或推理过程。

（2）已知一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，请画出该树，并给出计算或推理过程。

 

4．（15分）

某人自下往上走完一个N级的台阶，每步只能走一级或两级台阶：

（1）给出能够计算出上述台阶所有走法的递归算法。

（2）以C或C⁺⁺实现上述算法。
..............................