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

华北计算技术研究所2005年专业课试题参考答案一、填空题（20分）1.算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它具有5个重要特征：有穷性、确定性、可行性、输入、输出。2.一棵非空的二叉树，其第i层上最多有2i-1个结点。满二叉树是一棵深度为k且恰好有2k-1个结点的二叉树。3.图的存储结构包括数组（邻接矩阵）、邻接表、十字链表和邻接多重表等几种。图的遍历路径包括深度优先遍历和广度优先遍历。4.常用的构造哈希函数的方法有直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。二、选择题（20分）请在你认为正确的答案所对应的字母上画“√”。1.在C语言中，要存储一个8个字符的字符串，至少需要声明大小为多少的一维字符数组？C（A）7（B）8（C）9（D）102.两个矩阵A：m×n，B：n×p相乘，其时间复杂度为：B（A）O（n）（B）O（mnp）（C）O（n2）（D）O（n3）3.下列程序为将一条数据插入栈上：voidadd(inttop,elementitem){if(top=MAX_STACK_SIZE-1)returnstack_full();stack[]=item;}则在stack[]的中括号内横线上的正确内容应为：A（A）++*top（B）*top++（C）*top--（D）*top4.有如下函数：voidfun(structnodeh1,structnodeh2){structnode*t;t=h1;while(t-next!=’\0’)t=t-next;t-next=h2;}其中形参h1和h2分别指向2个不同链表的第一个结点，此函数的功能是：A（A）将链表h2接到链表h1后（B）将链表h1接到链表h2后（C）找到链表h1的最后一个结点由指针返回（D）将链表h1拆分成两个链表5.一个栈的入栈序列是abcde，则栈的不可能输出序列是：C（A）edcba（B）decba（C）dceab（D）abcde三、回答问题，并给出理由。（10分）1.设在一个有关串的程序编码当中，有如下定义与赋值：constcharA[]={‘a’,’b’,’c’,’\0’};charB[]={‘a’,’b’,’c’,’d’,’\0’};……for(i=0;i4;i++){A[i]=’a’;B[i]=’b’;}…...在该程序编码中是否有错？为什么？参考答案：有错。错在：A[i]=’a’；A定义的是串常量。一旦定义并赋值后，不能再赋值。2.若A为一下三角矩阵数组，则采用以行为主和以列为主的数据存放方式哪一种更合适？为什么？参考答案：以行为主更合适。因为：以行为主，A(i,j)存储于B(k)，则k=[i(i-1)/2]+j。以列为主，A(i,j)存储于B(k)，则k=[n(j-1)]-j(j-1)/2]+i。可见以行为主的方式存储较简单。四、根据要求编写算法。（20分）1.线性表A和B均是按元素值递增有序排列，均以单链表作存储结构。请编写一算法将表A和表B归并成一个按元素值递减有序排列的线性表C（允许表中含有值相同的元素），并要求利用原表空间。参考答案：voidgetUnionList(SqList&A,SqList&B,SqList&C){nodepa,pb,pc,q;pa=A-next;pb=B-next;C=A;A-next=null;While(pa!=null&pb!=null){if(pa-data=pb-data){q=pa;pa=pa-next;q-next=C-next;C-next=q;}else{q=pb;pb=pb-next;q-next=C-next;C-next=q;}}if(pa!=null){while(pa!=null){q=pa;pa=pa-next;q-next=C-next;C-next=q;}}if(pb!=null){while(pb!=null){q=pb;pb=pb-next;q-next=C-next;C-next=q;}}2.编写一个算法，对于输入的十进制非负整数，将它的八进制表示打印出来。参考答案：voidprint_oct(intdec_number){PSeqStackpastack;inttemp=dec_number;if(temp0){printf(“Error!\n”);return;}pastack=createEmptyStack_seq();if(pastack==NULL)return;while(temp0){push_seq(pastack,temp%8);temp/=8;}while(!isEmptyStack_seq(pastack)){printf(“%d”,top_seq(pastack));pop_seq(pastack);}free(pastack);}五、回答以下问题，并给出计算或推理过程。（20分）1.已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa。给出其先序序列，并画出该二叉树。参考答案：先序序列为abcdefghij。2.画出对长度为10的有序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。参考答案：等概率时查找成功的平均查找长度为：1/10（1*1+2*2+3*4+4*3）=29/10=2.9六、已知如图所示的有向图，请给出该图的：（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。（10分）52134867109abcdefghij参考答案：（1）各个顶点的入/出度：顶点123456入度321122出度022313（2）邻接矩阵（3）邻接表（4）逆邻接表①⑥②⑤④③^1234564661^51^2^523^1^000000100100010001001011100000110010（5）有3个强连通分量七、下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。1.请用Dijkstra算法计算v0到各点的最短路径（要求给出计算过程）。2.给出用C语言描述的Dijkstra算法。（20分）参考答案：最短路径：始点终点最短路径路径长度v0v1无51234612345664^2^643^4^3^2^65v010010106050305V5V1V2V4V320v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60用C语言描述的Dijkstra算法：voidShorttestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;vG.vexnum;++v){final[v]=FALSE;D[v]=G.arcs[v0][v];for(w=0;wG.vexnum;++w)P[v][w]=FALSE;if(D[v]INFINITY){p[v][v0]=TRUE;P[v][v]=TRUE;}D[v0]=0;final[v0]=TRUE;for(i=1;iG.vexnum;++i){min=INFINITY;for(w=0;wG.vexnum;++w)if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=TRUE;for(w=0;wG.vexnum;++w)if(!final[w]&&(min+G.arcs[v][w]D[w])){D[w]=min+G.arcs[v][w];P[w]=P[v];P[w][w]=TRUE;}}}八、请回答以下有关C++语言的问题。（16分）1.请比较一下值调用与引用调用的相同点和不同点。参考答案：值调用是指当发生函数调用时，给形参分配内存空间，并用实参来初始化形参（直接将实参的值传递给形参）。这一过程是参数值的单向传递过程，一旦形参获得了值，便与实参脱离了关系，此后无论形参发生了怎样的改变，都不会影响到实参。引用调用将引用作为形参，在执行主调函数中的调用语句时，系统自动用实参来初始化形参。这样形参就成为实参的一个别名，对形参的任何操作也就直接作用于实参。2.什么叫作抽象类？抽象类有何作用？抽象类的派生类是否一定要给出纯虚函数的实现？参考答案：带有纯虚函数的类是抽象类。抽象类的主要作用是通过它为一个类族建立一个公共的接口，使它们能够更有效地发挥多态特性。抽象类的派生类不一定要给出纯虚函数的实现。3.什么叫作指针？指针中存储的地址和这个地址中的值有何区别？参考答案：指针是一种数据类型，具有指针类型的变量称为指针变量。指针变量存放的是另外一个对象的地址，这个地址的值就是另一个对象的内容。4.什么叫拷贝构造函数？拷贝构造函数何时被调用？参考答案：拷贝构造函数是一种特殊的构造函数，其形参是本类的对象的引用，其作用是使用一个已经存在的对象，去初始化一个新的同类的对象。拷贝构造函数在以下三种情况下会被调用：当用类的一个对象去初始化该类的另一个对象时；如果函数的形参是类对象，调用函数进行形参和实参结合时；如果函数的返回值是类对象，函数调用完成返回时。九、建立基类Building，用来存储一座楼房的层数、房间数以及它的总平方英尺数。建立派生类Housing，继承Building，并存储下面的内容：卧室和浴室的数量。另外，建立派生类OfficeBuilding，继承Building，并存储灭火器和电话的数目。然后，用C++语言编制应用程序，建立住宅楼对象和办公楼对象，并输出它们的有关数据。（14分）参考答案：#includeiostream.hclassBuilding{public:Buildiing(intf,intr,doubleft){floors=f;rooms=r;footage=ft;}voidShow(){cout“floors:”floorsendl;cout”rooms:”roomsendl;cout”totalarea:”footageendl;}protected:intfloors;introoms;intfootage;};classHousing:publicBuilding{public:Housing(intf,intr,doubleft,intbd,intbth):Building(f,r,ft){bedrooms=bd;bathrooms=bth;}voidShow(){cout”\nHOUSING:\n”;Building::Show();cout”Bedrooms:”bedroomsendl;cout”Bathrooms:”bathroomsendl;}private:intbedrooms;intbathrooms;};classOfficeBuilding:publicBuilding{OfficeBuilding(intf,intr,doubleft,intph,intex){phones=ph;extinguishers=ex;}voidShow(){cout”\nOFFICEBUILDING:\n”;Building::Show();cout”Phones:”phonesendl;cout”Extinguishers:”extinguishersendl;}private:intphones;intextinguishers;};voidmain(){Housinghob(5,7,140,2,2);OfficeBiuldingoob(8,12,500,12,2);hob.Show();oob.Show();}