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

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

1、王道论坛：余人玫瑰手有余香哈尔滨工业大学二○○六年硕士研究生入学考试试题考试科目：计算机专业基础　　考试科目代码：[424]报考专业：计算机科学与技术考生注意：答案务必写在答题纸上，并标明题号。答在试题上无效。题号一二三四五六七八九总分分数9910202715301416150分答题注意事项：数据结构的答案必须写在计算机原理答案的前面。Ⅰ.数据结构（含高级语言）部分（75分）一、填空题（每空1分，共9分）1．由二元树的前序和后序序列①唯一确定这棵二元树。2．在一个堆的顺序存储中，若一个结点的下标为i(0＜i≤n-1)，则

2、它的左儿子的下标为②，右儿子的下标为③。3．以折半查找方法从长度为10的有序表中查找一个元素时，查找成功的平均长度为④。4．高度为K的完全二元树中，结点数n和K之间的关系是⑤。5．同一棵二元查找树中插入一个元素时，若元素的值小于根结点的元素值，则应把它插入到根结点的⑥上。6．举出两种磁带文件的分类方法：⑦和⑧。7．按二元树的定义，具有三个结点的二元树共有⑨种形态。二、单项选择（每题1分，共9分）1．已知一个序列为{21，39，35，12，17，43}，则利用堆分类方法建立的初试堆为（①）。A．39，21，35，12，17

3、，43B．43，39，35，12，17，21C．43，39，35，21，17，12D．43，35，39，17，21，122．算法性能分析的两个主要方面是（②）。A．数据复杂性和程序复杂性B．可读性和健壮性C．时间复杂性和空间复杂性D．正确性和简单性3．已知一个栈的输入序列顺序为1，2，3，4，…，n，输出序列为P1，P2，P3，…，Pn。若Pn＝n，则Pi（1＜i＜n）为（③）。A．iB．n－iC．n－i－1D．不确定4．在（④）算法中，第一趟排序后，最大的或最小的数一定在其最终位置上。A．归并排序B．插入排序C．快速排

4、序D．冒泡排序5．从二元查找树中查找一个元素时，其平均时间复杂性为（⑤）。A．O(n)B．O(1)C．O(㏒n)D．O(n2)6．设结点X和结点Y的二元树T中的两个结点，若在前序序列中X在Y之前，而在后序序列中X在Y之后，则X与Y的关系是（⑥）。A．X是Y的左兄弟B．X是Y的右兄弟C．Y是X的祖先D．Y是X的后代王道论坛（www.cskaoyan.com）友情分享！请勿用于商业用途！王道论坛：余人玫瑰手有余香7．在一个长度为n的线性表中的第i个元素(0＜i≤n-1)之前插入一个新元素时，需向后移动（⑦）个元素。A．n-1

5、B．n-i+1C．n-i-1D．i8．对于一组权值都相等的16个字母，构造相应的哈夫曼树，这棵哈夫曼树是一棵（⑧）。A．完全二元树B．一般二元树C．满二元树D．以上都不正确9．若要尽可能快地完成对实型数组的排序，且要求排序是稳定的，则应选择（⑨）。A．快速排序B．堆排序C．归并排序D．基数排序三、判断题（每题1分，共10分）1．折半查找只适合用于有序表，包括有序的顺序表和有序的链接。（ ①）2．拓扑分类适合于无环路有向图且拓扑序列唯一。（②）3．在n个结点的无向图中，若边数大于n-1，则该图必是连通图。（③ ）4．散列法

6、存储的基本思想是由关键字的值确定关键字的存储地址。（④）5．用邻接矩阵存储一个图，所需的存储单元数目与图的边数有关。（⑤）6．在磁盘分类中，对于能容纳P个记录的缓冲区，不能产生出长度大于P的初始归并段。（⑥）7．倒排文件与多重链表文件相似，都是用来处理多关键字查找。（⑦）8．中序线索二元树的优点是便于在中序遍历时查找任意结点的前驱结点和后继结点。（⑧）9．外部排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并。（⑨）10．索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。（⑩）四、简答题（共20分）1．

7、（10分）已知一个边带权无向图的顶点集V和边集E分别为：V＝{0，1，2，3，4，5，6，7}；E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20，（6，7）30}。边集E中的一条边表示成（x，y）z的形式，其中x，y代表边的两个顶点，z代表该边的权值。要求（1）简述Kruskal算法求最小生成树的基本思想；（2）按该算法写出构造最小生成树的每一步。2．（6分）简述用循环数组实现队列时队列满与队列空的区别方法，并给出判断

8、队列满和队列空的条件。3．（4分）试举例说明，如果允许带权有向图中某些边的权为负实数，则Dijkstra算法不能正确地求出从源点到每个顶点的最短路径。五、算法设计题（共27分）1．（13分）已知A、B、C是三个线性表且其元素按递增顺序排列，每个表中元素均无重复。在表A删去既在表B中出现又在表C中出现的元素。试设计实现