华北计算技术研究所专业课试题答案.docx
《华北计算技术研究所专业课试题答案.docx》由会员分享，可在线阅读，更多相关《华北计算技术研究所专业课试题答案.docx（21页珍藏版）》请在冰点文库上搜索。
华北计算技术研究所专业课试题答案
更多学校考研真题：
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，请画出该树，并给出计算或推理过程。
参考答案：
E
BF
ADH
CGI
K
J
（2）已知一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，请画出该树，并给出计算或推理过程。
参考答案：
A
BI
CGHJ
DEFK
4．（15分）
某人自下往上走完一个N级的台阶，每步只能走一级或两级台阶：
（1）给出能够计算出上述台阶所有走法的递归算法。
（2）以C或C++实现上述算法。
参考答案：
step
（1）如果n=1
walk（n）={step
（1）||step
（1）}∪step
（2）如果n=2
{step
（1）||walk（n-1）}∪{step
（2）||walk（n-2）}如果n≥3
5．（20分）
下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。
请用Dijkstra算法计算v0到各点的最短路径及路径的长度（要求给出计算过程）。
参考答案：
v0到v1的最短路径是（v0,v3,v1）,最短路径的长度为4
v0到v2的最短路径是（v0,v2）或（v0,v3,v1,v2）,最短路径的长度为7
v0到v3的最短路径是（v0,v3）,最短路径的长度为2
v0到v4的最短路径是（v0,v3,v4）,最短路径的长度为4
v0到v5的最短路径是（v0,v3,v1,v2,v5）或（v0,v2，,v5）,最短路径的长度为8
6．（30分）
已知如下所示长度为12的表
（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）
（1）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。
（2）若对表中元素先进行排序构成有序表，求在等概率情况下对此有序表进行折半查找时查找成功的平均查找长度。
（3）请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率情况下查找成功的平均查找长度。
参考答案：
（1）
Jan
FebMar
AprJuneMay
AugJulySep
DecOct
Nov
在等概率情况下平均查找长度=（1*1+2*2+3*3+4*3+5*2+6*1）/12=7/2
（2）经排序后的表及在折半查询时找到表中元素所需比较的次数为：
AprAugDecFebJanJulyJuneMarMayNovOctSept
342341342434
在等概率情况下平均查找长度=（1*1+2*2+3*4+4*5）=37/12
（3）
Mar
JanOct
AugJuneMaySept
AprFebJulyNov
Dec
平衡二叉排序树平均查找长度（1*1+2*2+3*4+4*3+5*1）/12=19/6
7．（25分）如图所示的方块图表表示一个迷宫。
图中的每个白方块表示为通道，黑方块为墙。
请在①、②、③处填充必要的C语言代码，完成下面求从迷宫入口到出口路径的程序。
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
出口
8
9
#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;
else
returnfalse;
}
//插入元素E为新的栈顶元素
boolPush（SqStack&S,SElemTypee）
{
①
}
//若栈不空，则删除S的栈顶元素，用E返回其值，并返回OK，否则返回ERROR
boolPop（SqStack&S,SElemType&e）
{
②
}
//能否通过curpos位置的通道块
boolPass（int*maze,PosTypecurpos）
{
if（maze[curpos.x*MAZEWIDTH+curpos.y]==NOT_PASSED）
//当前的还没有走过
returntrue;
else
returnfalse;
}
//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;
}else
assert（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++;
}//ifpass
else{
//如果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.di<4）{
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的友元吗？
简述理由。
参考答案：
类B不是类A的友元，友元关系不具有交换性；
类C不是类A的友元，友元关系不具有传递性；
类D不是类B的友元，友元关系不能被继承。
（3）什么叫多态性？
C++支持多态的主要方式是什么？
参考答案：
多态性是指同样的消息被不同类型的对象接收时导致完全不同的行为。
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的正方形的面积。
参考答案：
#include
#definePI3.14159
classShape
{
public:
Shape（）{}
~Shape（）{}
virtualfloatGetArea（）{return-1;}
};
classCircle:
publicShape
{
public:
Circle（floatradius）:
itsRadius（radius）{}
~Circle（）{}
floatGetArea（）{return（float）PI*itsRadius*itsRadius;}
private:
floatitsRadius;
};
classRectangle:
publicShape
{
public:
Rectangle（）;
Rectangle（floatlen,floatwidth）:
itsLength（len）,itsWidth（width）{}
~Rectangle（）{}
floatGetArea（）{returnitsLength*itsWidth;}
private:
floatitsWidth;
floatitsLength;
};
Rectangle:
:
Rectangle（）
{
itsWidth=2;
itsLength=3;
}
classSquare:
publicRectangle
{
public:
Square（floatlen）;
~Square（）{}
};
Square:
:
Square（floatlen）:
Rectangle（len,len）
{
}
voidmain（）
{
Shape*sp;
sp=newRectangle（）;
cout<<"Theareaoftherectangleis"<GetArea（）<deletesp;
sp=newRectangle（4,5）;
cout<<"Theareaoftherectangleis"<GetArea（）<deletesp;
sp=newCircle（6）;
cout<<"Theareaofthecircleis"<GetArea（）<deletesp;
sp=newSquare（7）;
cout<<"Theareaofthesquareis"<GetArea（）<deletesp;
}
升级会员 