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

华北计算技术研究所2004年专业课试题 要求：1、答案必须写在答题纸上，标明题号； 2、答卷要字迹清楚，语义确切； 3、所有计算要求给出计算过程。 1．（10分） （1）以n、ai(i=0,1, ．．．，n)、x0作为输入，为了进行一元n次多项式Pn(x)=a0xn+a1xn-1+a2xn-2+…+an-1x+an在x0点的值Pn(x0)的计算，请给出你认为效率最好的算法。 （2）给出上述算法的基本操作、基本操作执行次数和时间复杂度。 2．（10分） 设有三对角矩阵（aij）nxn，将其三条对角线上的元素逐行地存于数组B[3n-2]中，使得B[k]=aij，求： （1）用i，j表示k的下标变换公式； （2）用k表示i，j的下标变换公式。 3．（10分） （1）已知一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树，并给出计算或推理过程。 （2）已知一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，请画出该树，并给出计算或推理过程。 4．（15分） 某人自下往上走完一个N级的台阶，每步只能走一级或两级台阶： （1）给出能够计算出上述台阶所有走法的递归算法。 （2）以C或C++实现上述算法。 5．（20分） 下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。请用Dijkstra算法计算v0到各点的最短路径及路径的长度（要求给出计算过程）。 6．（30分） 已知如下所示长度为12的表 （Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec） （1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。 （2）若对表中元素先进行排序构成有序表，求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。 （3）请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。  7．（25分）如图所示的方块图表表示一个迷宫。图中的每个白方块表示为通道，黑方块为墙。请在①、②、③处填充必要的C语言代码，完成下面求从迷宫入口到出口路径的程序。 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 #define STACK_INCREMENT 10 //栈每次增加的大小 #define OK true #define ERROR false #define MAZEWIDTH 10 //迷宫的X方向大小 #define MAZEHEIGHT 10 //迷宫的Y方向大小 //坐标位置状态,0----没有走过，1----走过了，2----不通,3----是墙壁 enum status { NOT_PASSED, //没有走过该通道块 PASSED, //该通道块已经走过了 NOT_THROUGH, //不通 IS_WALL //是墙壁 }; typedef struct postype { int x; //横坐标 int y; //纵坐标 }PosType; typedef struct selemtype { int ord; //通道块在路经中的序号 PosType seat; //通道块在迷宫中的坐标位置 int di; //从此通道块走向下一个通道块的方向 //1----东面，2---南面，3---西面，4---北面 }SElemType; //栈的元素类型 typedef struct { SElemType *base; //栈底 SElemType *top; //栈顶 int stacksize; //栈大小 }SqStack; //栈结构 //构造一个空栈 bool InitStack(SqStack S) { S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) return ERROR; S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } //判断栈是否为空 bool Sta