華北計算技術研究所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⁺⁺實現上述算法。
..............................