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

《华北计算技术研究所2004年专业课试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华北计算技术研究所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，将其三条对角线上的元素逐行地存于

2、数组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）给出能够计算出上述台阶所有走法的递归算法。

3、（2）以C或C++实现上述算法。75．（20分）下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。请用Dijkstra算法计算v0到各点的最短路径及路径的长度（要求给出计算过程）。v0522610316272v1v3v4v2v56．（30分）已知如下所示长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找

4、长度。（2）若对表中元素先进行排序构成有序表，求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。77．（25分）如图所示的方块图表表示一个迷宫。图中的每个白方块表示为通道，黑方块为墙。请在①、②、③处填充必要的C语言代码，完成下面求从迷宫入口到出口路径的程序。出口入口012345678901234567出口89#defineSTACK_INCREMENT10//栈每次增加的大小#defineO

5、Ktrue#defineERRORfalse#defineMAZEWIDTH10//迷宫的X方向大小#defineMAZEHEIGHT10//迷宫的Y方向大小//坐标位置状态,0----没有走过，1----走过了，2----不通,3----是墙壁enumstatus{NOT_PASSED,//没有走过该通道块PASSED,//该通道块已经走过了NOT_THROUGH,//不通IS_WALL//是墙壁};typedefstructpostype{intx;//横坐标inty;//纵坐标}PosTyp

6、e;typedefstructselemtype{intord;//通道块在路经中的"序号"7PosTypeseat;//通道块在迷宫中的"坐标位置"intdi;//从此通道块走向下一个通道块的"方向"//1----东面，2---南面，3---西面，4---北面}SElemType;//栈的元素类型typedefstruct{SElemType*base;//栈底SElemType*top;//栈顶intstacksize;//栈大小}SqStack;//栈结构//构造一个空栈boolInitSt

7、ack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)returnERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//判断栈是否为空boolStackEmpty(SqStackS){if(S.base==S.top)returntrue;elsereturnfalse;}//插入元素E为新的栈顶元素boolPush

8、(SqStack&S,SElemTypee){①}7//若栈不空，则删除S的栈顶元素，用E返回其值，并返回OK，否则返回ERRORboolPop(SqStack&S,SElemType&e){②}//能否通过curpos位置的通道块boolPass(int*maze,PosTypecurpos){if(maze[curpos.x*MAZEWIDTH+curpos.y]==NOT_PASSED)//当前的还没有走过returntrue;elsereturnfalse;}//maze是