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

《华北计算技术研究所2005年专业课试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华北计算技术研究所2005年专业课试题要求：1.答案必须写在答题纸上，并标明题号。2.答案要字迹清楚，语义确切。3.所有计算要求给出计算过程。一、填空题（20分）1.是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。它具有5个重要特征：、、、、。2.一棵非空的二叉树，其第i层上最多有个结点。满二叉树是一棵深度为k且恰好有个结点的二叉树。3.图的存储结构包括、、和等几种。图的遍历路径包括和。4.常用的构造哈希函数的方法有、、、、、和。二、选择题（20分）请在你认为正确的答案

2、所对应的字母上画“√”。1.在C语言中，要存储一个8个字符的字符串，至少需要声明大小为多少的一维字符数组？（A）7（B）8（C）9（D）102.两个矩阵A：m×n，B：n×p相乘，其时间复杂度为：（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;}4则在stack[]的中括号内横线上的正确内容

3、应为：（A）++*top（B）*top++（C）*top--（D）*top1.有如下函数：voidfun(structnodeh1,structnodeh2){structnode*t;t=h1;while(t->next!=’’)t=t->next;t->next=h2;}其中形参h1和h2分别指向2个不同链表的第一个结点，此函数的功能是：（A）将链表h2接到链表h1后（B）将链表h1接到链表h2后（C）找到链表h1的最后一个结点由指针返回（D）将链表h1拆分成两个链表2.一个栈的入栈序列是abcde

4、，则栈的不可能输出序列是：（A）edcba（B）decba（C）dceab（D）abcde一、回答问题，并给出理由。（10分）1.设在一个有关串的程序编码当中，有如下定义与赋值：constcharA[]={‘a’,’b’,’c’,’’};charB[]={‘a’,’b’,’c’,’d’,’’};……for(i=0;i<4;i++){A[i]=’a’;B[i]=’b’;}…...在该程序编码中是否有错？为什么？2.若A为一下三角矩阵数组，则采用以行为主和以列为主的数据存放方式哪一种更合适？为什么？二、

5、根据要求编写算法。（20分）1.4线性表A和B均是按元素值递增有序排列，均以单链表作存储结构。请编写一算法将表A和表B归并成一个按元素值递减有序排列的线性表C（允许表中含有值相同的元素），并要求利用原表空间。1.编写一个算法，对于输入的十进制非负整数，将它的八进制表示打印出来。一、回答以下问题，并给出计算或推理过程。（20分）1.已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa。给出其先序序列，并画出该二叉树。2.画出对长度为10的有序表进行折半查找的一棵判定树，并求其等概率时

6、查找成功的平均查找长度。二、已知如图所示的有向图，请给出该图的：（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。（10分）①⑥②⑤④③三、下图是一个有向图，其中每条弧段上的数字表示该弧段的权值。1.请用Dijkstra算法计算v0到各点的最短路径（要求给出计算过程）。2.给出用C语言描述的Dijkstra算法。（20分）4v010010106050305V5V1V2V4V320一、请回答以下有关C++语言的问题。（16分）1.请比较一下值调用与引用调用的相同点和不同

7、点。2.什么叫作抽象类？抽象类有何作用？抽象类的派生类是否一定要给出纯虚函数的实现？3.什么叫作指针？指针中存储的地址和这个地址中的值有何区别？4.什么叫拷贝构造函数？拷贝构造函数何时被调用？二、建立基类Building，用来存储一座楼房的层数、房间数以及它的总平方英尺数。建立派生类Housing，继承Building，并存储下面的内容：卧室和浴室的数量。另外，建立派生类OfficeBuilding，继承Building，并存储灭火器和电话的数目。然后，用C++语言编制应用程序，建立住宅楼对象和办公楼对象，

8、并输出它们的有关数据。（14分）4