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

2004年专业基础课参考答案1．（10分）（1）以n、ai(i=0,1,．．．，n)、x0作为输入，为了进行一元n次多项式Pn(x)=a0xn+a1xn-1+a2xn-2+…+an-1x+an在x0点的值Pn(x0)的计算，请给出你认为效率最好的算法。参考答案：sum=a0;for(inti=1;i=n;i++){sum=sum*x0+ai;}（2）给出上述算法的基本操作、基本操作执行次数和时间复杂度。参考答案：基本操作：sum=sum*x0+ai基本操作执行次数：n时间复杂度：O(n)2．（10分）设有三对角矩阵（aij）nxn，将其三条对角线上的元素逐行地存于数组B[3n-2]中，使得B[k]=aij，求：（1）用i，j表示k的下标变换公式；（2）用k表示i，j的下标变换公式。参考答案：k=2*i+j–3(|i-j|≤1)i=[(k+1)/3]+1（0≤k≤3n-1）j=k+1–2*[k/3]3．（10分）（1）已知一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树，并给出计算或推理过程。参考答案：EBFADHCGIKJ（2）已知一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，请画出该树，并给出计算或推理过程。参考答案：ABICGHJDEFK4．（15分）某人自下往上走完一个N级的台阶，每步只能走一级或两级台阶：（1）给出能够计算出上述台阶所有走法的递归算法。（2）以C或C++实现上述算法。参考答案：step(1)如果n=1walk(n)={step(1)||step(1)}∪step(2)如果n=2{step(1)||walk(n-1)}∪{step(2)||walk(n-2)}如果n≥35．（20分）下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。请用Dijkstra算法计算v0到各点的最短路径及路径的长度（要求给出计算过程）。参考答案：v0到v1的最短路径是（v0,v3,v1）,最短路径的长度为4v0到v2的最短路径是（v0,v2）或（v0,v3,v1,v2）,最短路径的长度为7v0到v3的最短路径是（v0,v3）,最短路径的长度为2v0到v4的最短路径是（v0,v3,v4）,最短路径的长度为4v0到v5的最短路径是（v0,v3,v1,v2,v5）或（v0,v2，,v5）,最短路径的长度为8v0522610316272v1v3v4v2v56．（30分）已知如下所示长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。（3）请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。参考答案：（1）JanFebMarAprJuneMayAugJulySepDecOctNov在等概率情况下平均查找长度=（1*1+2*2+3*3+4*3+5*2+6*1）/12=7/2（2）经排序后的表及在折半查询时找到表中元素所需比较的次数为：AprAugDecFebJanJulyJuneMarMayNovOctSept342341342434在等概率情况下平均查找长度=（1*1+2*2+3*4+4*5）=37/12（3）MarJanOctAugJuneMaySeptAprFebJulyNovDec平衡二叉排序树平均查找长度(1*1+2*2+3*4+4*3+5*1)/12=19/67．（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---北面}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){②}//能否通过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;}//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;}参考答案①if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;}*S.top=e;S.top++;returnOK;②if(S.top==S.base)returnERROR;S.top--;e=*S.top;returnOK;③SqStackS;InitStack(S);PosTypecurpos=start;intcurStep=1;do{if(Pass(maze,curpos)){//如果curpos通道块可以通过(没有走过此通道块，也不是墙壁)//标记已经走过maze[curpos.x*MAZEWIDTH+curpos.y]=PASSED;SElemTypee;e.ord=curStep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(S,e);if(curpos.x==end.x&&curpos.y==end.y){//到达迷宫出口inti=0;while(!StackEmpty(S)){i++;SElemTypee;Pop(S,e);printf(%d,%d%d\n,i,e.seat.x,e.seat.y);}returntrue;}//搜索东面的通道块curpos=NextPos(maze,curpos,1);curStep++;}//ifpasselse{//如果curpos通道块不可以通过（已经走过此通道块，或者是墙壁）if(!StackEmpty(S)){SElemTypee;Pop(S,e);//从栈中推出不能通过的通道块while(e.di==4&&!StackEmpty(S)){//标记不通maze[e.seat.x*MAZEWIDTH+e.seat.y]=NOT_THROUGH;Pop(S,e);}//换下一个方向搜索if(e.di4){e.di++;Push(S,e);curStep=e.ord+1;curpos=NextPos(maze,e.seat,e.di);}}}}while(!StackEmpty(S));returnfalse;8．（13分）简答以下有关C++语言的问题：（1）比较类的三种继承方式public（公有继承）、protected（保护继承）和private（私有继承）之间的差别。参考答案：公有继承：基类的public（公有）和protected（保护）成员的访问属性在派生类中不变，而基类的private（私有）成员不可访问；私有继承：基类的public（公有）和protected（保护）成员都以private（私有）成员身份出现在派生类中，而基类的private（私有）成员不可访问；私有继承：基类的public（公有）和protected（保护）成员都以protected（保护）成员的身份出现在派生类中，而基类的private（私有）成员不可访问。（2）如果类A是类B的友元，类B是类C的友元，类D是类A的派生类，那么类B是类A的友元吗？类C是类A的友元吗？类D是类B的友元吗？简述理由。参考答