哈工大计算机2008年考研试题

《哈工大计算机2008年考研试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、王道论坛：余人玫瑰手有余香第4页共5页哈尔滨工业大学二○○八年硕士研究生入学考试试题考试科目：计算机专业基础　　报考专业：计算机科学与技术考试科目代码：【424】是否允许使用计算器：【否】考生注意：答案务必写在答题纸上，并标明题号。答在试题上无效。题号一二三四五六七八九总分分数209163015329910答题注意事项：数据结构的答案必须写在计算机原理答案的前面。Ⅰ.数据结构（含高级语言）部分（75分）一、填空（每题2分．共20分）1.已知一个线性表有n个元素，其中每个元素的数据占8个字节，假设一个指针的大小为4个字节，如果采用有30个元素

2、的数组存储，那么当数组中有效元素个数满足⑴条件时，数组的存储效率比不带头结点的单链表更高。2.给定14个字母．假设它们的权值都相等．采用huffman编码，则每个字母的平均代码长度是⑵。3.按C语言的运算符优先级，中缀表达式“A&&B

3、

4、!(E>F)”的等价后缀形式为⑶。4.设按顺时针方向移动的循环队列Q[N]的头尾指针分别为F、R，头指针F总是指在队列中的第一个元素的前一位置，尾指针R在最后一个元素的位置，则队列中的元素个数为⑷。5.从空二叉树开始．严格按照BST（二又查找树）的插入算法，逐个插入关键字{18，73，10，5.68，99，

5、27，41,32，25）构造出一颗BST，对该BST按照先根遍历得到的序列为⑸。6.将两个长度为m的有序序列归井为一个有序序列，最少需要做⑹次关键字比较，最多需要做⑺次关键字比较。7.散列查找中，⑻现象称为冲突，⑼现象称为聚集。8.设可用的内存单元可处理4个记录，采用4路归并的选择树法生成由小到大的初始归井段，对有12个记录在案的文件，产生的第一个初的归井段长度为⑽个。9.在两种求图的最小生成树的算法中，⑾算法适合于边稀疏的图的最小生成树。10.已知一个序列为{21，39，35，12，17，43}，则利用堆排序方法建立的初始堆为：⑿。二、判

6、断（每题1分．共9分）1.倒排文件只能按关键字的顺序存储。（①）2.堆的存储表示可能是链接式的，也可以是顺序的。（②）王道论坛（www.cskaoyan.com）友情分享！请勿用于商业用途！王道论坛：余人玫瑰手有余香3.在AOE网中，任何一个关键活动的延迟，都会使整个工程延迟。（③）4.有环路的有向图不能进行拓扑排序。（④）5.对无向图进行一次深度优先搜索可以访问到图中的所有顶点。（⑤）6.大根堆的最大元素应该在堆顶，即根结点。（⑥）7.归并排序的平均时间复杂度为O（n㏒n）,最坏为O（n2）。（⑦）8.栈总是在栈底删除元素。（⑧）9.分块

7、查找只适合静态查找，不适合动态查找。（⑨）三、问答题（每题8分．共16分）1.许多文献中认为常用的排序算法是快速排序算法，而不是归并排序，你是如何理解的？2.在包含n个关键字的线性表中进行顺序查找,若查找第i个关键字的概率为Pi且分布如下：P1=1/2,P2=1/4,…,Pn-1=1/2(n-1),Pn=1/2n；求：（1）查找成功的平均查找长度。（2）查找失败的情况下的平均查找长度。四、算法设计题(每题15分．共30分)1.设二叉树结点表示的数据元素类型为Elementtype,二叉树用左右链表示。一棵二叉树的最大枝长和最小枝长分别如下定

8、义：最大枝长就是二叉树的层数；最小枝长就是离根结点距离最近的叶结点到根路径上的边数。请设计一个算法，同时求出一棵二叉树的最大和最小枝长。2.设计一找无环路有向图第对顶点间“最长简单路径“（所谓最长简单路径是指该简单路径包含边最多）的算法，即以一个无环路有向图作为输入，对于每个顶点如果它们之间存在简单路径，则输出其中最长的，否则输出为空。Ⅱ.计算机组成原理部分（共75分）五、填空题（每空1分．共15分）1.总线控制主要解决⑴问题。集中式仲裁有⑵、⑶、⑷三种。2.若数据在存储器中采用以低字节地址的存放方式，则十六进制数12,34,56,78H按

9、字节地址由小到大依次为⑸。3.总线⑹技术是指不同的信号（如地址信号和数据信号）共用一组物理线路，分时使用，此时需要配置相应的电路。4.一个四级流水的处理器，共有关12条指令连续输入此流水线，则在12个时钟周期结束时执行完⑺条指令。5.CPU在⑻时刻采样中断请求信号（在开中断情况下）。而在⑼时刻采样DMA的总路线请求信号。6.32位字长的浮点数，其中阶码8位（含1位阶符），基值为2，尾数为24位（含1位数符）。当机器数采用原码表示，则其对应的最小正数是⑽，最小负数是⑾；当机器数采用补码表示，尾数为规格化形式，则其对应的最大正数是⑿，最大负数是

10、⒀。（均用十进制表示）7.定点原码除法和定点补码除法均可采用⒁法，但补码除法中王道论坛（www.cskaoyan.com）友情分享！请勿用于商业用途！王道论坛：余人玫瑰手有余香⒂