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

第1页共7页华北计算技术研究所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到各点的最短路径及路径的长度（要求给出计算过程）。第2页共7页6．（30分）已知如下所示长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。v0522610316272v1v3v4v2v5第3页共7页7．（25分）如图所示的方块图表表示一个迷宫。图中的每个白方块表示为通道，黑方块为墙。请在①、②、③处填充必要的C语言代码，完成下面求从迷宫入口到出口路径的程序。01234567890123456789#defineSTACK_INCREMENT10//栈每次增加的大小#defineOKtrue#defineERRORfalse#defineMAZEWIDTH10//迷宫的X方向大小#defineMAZEHEIGHT10//迷宫的Y方向大小//坐标位置状态,0----没有走过，1----走过了，2----不通,3----是墙壁enumstatus{NOT_PASSED,//没有走过该通道块PASSED,//该通道块已经走过了NOT_THROUGH,//不通IS_WALL//是墙壁};typedefstructpostype{intx;//横坐标inty;//纵坐标}PosType;typedefstructselemtype{intord;//通道块在路经中的序号PosTypeseat;//通道块在迷宫中的坐标位置intdi;//从此通道块走向下一个通道块的方向//1----东面，2---南面，3---西面，4---北面出口出口入口第4页共7页}SElemType;//栈的元素类型typedefstruct{SElemType*base;//栈底SElemType*top;//栈顶intstacksize;//栈大小}SqStack;//栈结构//构造一个空栈boolInitStack(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(SqStack&S,SElemTypee){①}//若栈不空，则删除S的栈顶元素，用E返回其值，并返回OK，否则返回ERRORboolPop(SqStack&S,SElemType&e){第5页共7页②}//能否通过curpos位置的通道块boolPass(int*maze,PosTypecurpos){if(maze[curpos.x*MAZEWIDTH+curpos.y]==NOT_PASSED)//当前的还没有走过returntrue;elsereturnfalse;}//maze是个二维的迷宫矩阵//curpos是当前的通道块//di是下一个通道块的方向PosTypeNextPos(int*maze,PosTypecurpos,intdi){PosTyperet;if(di==1)//东面的通道块{ret.x=curpos.x+1;ret.y=curpos.y;}elseif(di==2)//南面的通道块{ret.x=curpos.x;ret.y=curpos.y+1;}elseif(di==3)//西面的通道块{ret.x=curpos.x-1;ret.y=curpos.y;}elseif(di==4)//北面的通道块{ret.x=curpos.x;ret.y=curpos.y-1;}elseassert(0);returnret;}第6页共7页//MazePath计算从迷宫入口到出口的路径，其中参数：//maze是个二维的迷宫矩阵，start是迷宫的出发点，end是迷宫的出口boolMazePath(int*maze,PosTypestart,PosTypeend){③}intmain(intargc,char*argv[]){//构造迷宫//0----没有走过,3----是墙壁intMaze[MAZEWIDTH][MAZEHEIGHT]={3,3,3,3,3,3,3,3,3,3,3,0,0,3,0,0,0,3,0,3,3,0,0,3,0,0,0,3,0,3,3,0,0,0,0,3,3,0,0,3,3,0,3,3,3,0,0,0,0,3,3,0,0,0,3,0,0,0,0,3,3,0,3,0,0,0,3,0,0,3,3,0,3,3,3,0,3,3,0,3,3,3,0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,3,3,3};//设置起始通道块和结束通道块PosTypestart,end;start.x=1;start.y=1;end.x=8;end.y=8;boolsuccess=MazePath((int*)Maze,start,end);getchar();return0;}第7页共7页8．（13分）简答以下有关C++语言的问题：（1）比较类的三种继承方式public（公有继承）、protected（保护继承）和private（私有继承）之间的差别。（2）如果类A是类B的友元，类B是类C的友元，类D是类A的派生类，那么类B是类A的友元吗？类C是类A的友元吗？类D是类B的友元吗？简述理由。（3）什么叫多态性？C++支持多态的主要方式是什么？9．（17分）编写一个C++程序，满足以下要求：（1）定义一个Shape基类，在此基础上派生出名为Rectangle的矩形类和名为Circle的圆形类，二者都有GetArea()函数计算对象的面积。由Rectangle类派生名为Square的正方形类。（2）Rectangle类有宽度和长度属性（其初值分别为2和3），Circle类有半径属性。（3）在程序输出中：（a）直接输出矩形的面积。（b）输出宽度、长度分别为4和5的矩形的面积。（c）输出半径为6的圆形的面积。（d）输出边长为7的正方形的面积。