1、华北计算技术研究所2005年专业课试题及参考答案一、 填空题（20分）1. 算法 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它具有5个重要特征： 有穷性 、 确定性 、 可行性 、 输入 、 输出 。2. 一棵非空的二叉树，其第i层上最多有 2i-1 个结点。满二叉树是一棵深度为k且恰好有 2k-1 个结点的二叉树。3. 图的存储结构包括 数组（邻接矩阵） 、 邻接表 、 十字链表 和 邻接多重表 等几种。图的遍历路径包括 深度优先遍历 和 广度优先遍历 。4. 常用的构造哈希函数的方法有 直接定址法 、 数字分析法 、 平方取中法 、 折叠法 、
2、除留余数法 和 随机数法 。二、 选择题（20分）请在你认为正确的答案所对应的字母上画“”。1. 在C语言中，要存储一个8个字符的字符串，至少需要声明大小为多少的一维字符数组？ C （A） 7 （B）8 （C）9 （D）102. 两个矩阵A：mn，B：np相乘，其时间复杂度为： B （A） O（n） （B）O（mnp） （C）O（n2） （D）O（n3）3. 下列程序为将一条数据插入栈上：void add(int top,element item) if (top=MAX_STACK_SIZE-1)return stack_full();stack =item;则在stack 的中括号内横线上
3、的正确内容应为： A （A）+*top （B）*top+ （C）*top- （D）*top 4. 有如下函数：void fun(struct node h1,struct node h2)struct node *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）
4、decba（C）dceab（D）abcde 三、 回答问题，并给出理由。（10分）1. 设在一个有关串的程序编码当中，有如下定义与赋值：const char A=a,b,c,0;char B=a,b,c,d,0; for(i=0;inext; pb=B-next;C=A;A-next=null; While( pa!=null & pb!=null)if (pa-datadata)q=pa;pa=pa-next;q-next=C-next;C-next=q;elseq=pb ;pb=pb-next;q-next=C-next;C-next=q;if (pa!=null)while(pa!=nu
5、ll)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. 编写一个算法，对于输入的十进制非负整数，将它的八进制表示打印出来。参考答案：void print_oct(int dec_number)PSeqStack pastack;int temp=dec_number;if (temp0)push_seq(pastack,temp%8);temp/=8;while(!isEmptyStack_seq(pastack)print
6、f(“%d”,top_seq(pastack);pop_seq(pastack);free(pastack);五、 回答以下问题，并给出计算或推理过程。（20分）1. 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa。给出其先序序列，并画出该二叉树。参考答案：abcdefghij先序序列为abcdefghij。2. 画出对长度为10的有序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。参考答案：52134867109等概率时查找成功的平均查找长度为：1/10（1*1+2*2+3*4+4*3）=29/10=2.9六、 已知如图所示的有向图，请给出该
7、图的：（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表；（5） 强连通分量。（10分）参考答案：（1） 各个顶点的入/出度：顶点123456入度321122出度022313（2） 邻接矩阵000000100100010001001011100000110010（3） 邻接表12345646615125231（4） 逆邻接表12345664264343265（5） 有3个强连通分量512346七、 下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。1. 请用Dijkstra算法计算v0到各点的最短路径（要求给出计算过程）。2. 给出用C语言描述的Dijkstr
8、a算法。（20分）v010010106050305V5V1V2V4V320参考答案：最短路径：始点终点最短路径路径长度v0v1无v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)60用C语言描述的Dijkstra算法：void ShorttestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D)for(v=0; vG.vexnum; +v)finalv=FALSE; Dv=G.arcsv0v;for(w=0; wG.vexnum; +w)Pvw=FALSE;if(DvINF
9、INITY) pvv0=TRUE; Pvv=TRUE;Dv0=0; finalv0=TRUE;for(i=1; iG.vexnum; +i)min=INFINITY;for(w=0; wG.vexnum; +w)if(!finalw)if(Dwmin)v=w; min=Dw;finalv=TRUE;for(w=0; wG.vexnum; +w)if(!finalw&(min+G.arcsvwDw)Dw= min + G.arcsvw;Pw=Pv; Pww=TRUE;八、 请回答以下有关C+语言的问题。（16分）1. 请比较一下值调用与引用调用的相同点和不同点。参考答案：值调用是指当发生函数调用
10、时，给形参分配内存空间，并用实参来初始化形参（直接将实参的值传递给形参）。这一过程是参数值的单向传递过程，一旦形参获得了值，便与实参脱离了关系，此后无论形参发生了怎样的改变，都不会影响到实参。引用调用将引用作为形参，在执行主调函数中的调用语句时，系统自动用实参来初始化形参。这样形参就成为实参的一个别名，对形参的任何操作也就直接作用于实参。2. 什么叫作抽象类？抽象类有何作用？抽象类的派生类是否一定要给出纯虚函数的实现？参考答案：带有纯虚函数的类是抽象类。抽象类的主要作用是通过它为一个类族建立一个公共的接口，使它们能够更有效地发挥多态特性。抽象类的派生类不一定要给出纯虚函数的实现。3. 什么叫作
11、指针？指针中存储的地址和这个地址中的值有何区别？参考答案：指针是一种数据类型，具有指针类型的变量称为指针变量。指针变量存放的是另外一个对象的地址，这个地址的值就是另一个对象的内容。4. 什么叫拷贝构造函数？拷贝构造函数何时被调用？参考答案：拷贝构造函数是一种特殊的构造函数，其形参是本类的对象的引用，其作用是使用一个已经存在的对象，去初始化一个新的同类的对象。拷贝构造函数在以下三种情况下会被调用：当用类的一个对象去初始化该类的另一个对象时；如果函数的形参是类对象，调用函数进行形参和实参结合时；如果函数的返回值是类对象，函数调用完成返回时。九、 建立基类Building，用来存储一座楼房的层数、房
12、间数以及它的总平方英尺数。建立派生类Housing，继承Building，并存储下面的内容：卧室和浴室的数量。另外，建立派生类OfficeBuilding，继承Building，并存储灭火器和电话的数目。然后，用C+语言编制应用程序，建立住宅楼对象和办公楼对象，并输出它们的有关数据。（14分）参考答案：#include class Buildingpublic:Buildiing(int f, int r, double ft)floors=f;rooms=r;footage=ft;void Show()cout “ floors:”floorsendl;cout ” rooms:”rooms
13、endl;cout ” total area:”footage endl;protected:int floors;int rooms;int footage;class Housing:public Buildingpublic:Housing(int f, int r,double ft,int bd,int bth):Building(f,r,ft)bedrooms=bd;bathrooms=bth;void Show()cout ” n HOUSING:n”;Building:Show();cout ” Bedrooms:”bedroomsendl;cout ” Bathrooms:”
14、bathroomsendl;private:int bedrooms;int bathrooms;class OfficeBuilding:public BuildingOfficeBuilding(int f,int r,double ft,int ph,int ex)phones=ph;extinguishers=ex;void Show()cout ” n OFFICEBUILDING:n”;Building:Show();cout ” Phones:”phonesendl;cout ” Extinguishers:”extinguishersendl;private:int phones;int extinguishers;void main()Housing hob(5,7,140,2,2);OfficeBiulding oob(8,12,500,12,2);hob.Show();oob.Show();