历年年哈工大计算机考研试题(无水印)

硕士研究生入学考试初试专业课资料计算机专业基础计算机考研历年真题(1991年-2008年)友情分享！余人玫瑰手留余香！哈尔滨工业大学一九九一年硕士研究生入学考试试题考试科目：数据结构报考专业：计算机科学与技术汇编语言部分略数据结构部分4、解释下列名词（3×4=12分）（1）完全二元树（2）先深搜索（3）最小生成树（4）二元查找树注：本试题中要求设计的算法可用任一种程序设计语言或流程图来描述5、已知一个算术表达式如下：y=c+d(－cos(2x+b)+b)1（1）试用一株树将1表示出来。（3分）（2）将（1）中形成的树变换成相应的二元树。（3分）（3）试给出1的前缀表示和后缀表示。（3分）6、略（此题为一PASCAL程序填空题。一是目前哈工大早已经没有这种题型，二是哈工大目前已不再出PASCAL相关的题）第1页共2页7、图1，给出的流程图试图完成下述功能：对于两个长度分别为m和n（n≥m＞0）的字符序列：P=P0P1…Pm-1S=S0S1…Sm-1当P是S的子序列时，输出P在S中首次出现的位置，否则输出“失败”信息。查找方法是将P与S左端对齐，自左至右逐个比较P与S的对应字符。如不相同，P就向右移动一个字符的位置，试填充图1中的①～③，使之成为完整的流程图。（13分）8、设G=（V，E）是无环路有向图，V={1，2…n}，G由下述三元式给出：（a1，b1，w1），（a2，b2，w2）…（am，bm，wm），（0，0，0）2其中：（ai，bi，wi）表示ai、bi∈V，（ai，bi）∈E，wi为边（ai，bi）的权，（0，0，0）表示序列的结束。试给出一个算法，将2所给的有向图用邻接表表示出来，并求出每个结点的入度，邻接表的形式如图2所示。其中：indegree为顶点的入度；ptr为指针，指向其直接后继顶点队列的头；name为顶点名，weight为权；next为指向下一个结点的指针。（15分）9、试设计一个算法，将一株用左右链表示的任意二元树（图3给出一个示意性例子），加一些虚结点当成满二元树（如图4，把图3的示例变成了满二元树），存放在数组中，使之满足：下标为i的结点，它的两个儿子的下标为2i和2i+1，虚结点的数据域用○表示。（18分）第2页共2页哈尔滨工业大学一九九二年硕士研究生入学考试试题考试科目：数据结构报考专业：计算机科学与技术汇编语言部分略数据结构部分三、回答下列问题（15分）1.在一株二元分类树中，要使遍历结果是一个按关键字递减的顺序排列的，应如何遍历？（4分）2.设栈存在在数组A[0…m-1]中，栈底位置是m-1。栈空的条件是什么？栈满的条件是什么？（4分）3.设有n个结点的完全二元树，顺序存放在A[1…n]中，对任一结点A[i]：（4分）（1）若A[i]有父亲结点，问父亲结点是哪个？（2）若A[i]有左儿子，问左儿子是哪个？（3）若A[i]有右儿子，问右儿子是哪个？（4）i值最大的非叶结点是哪一个？4.单向链表中引入头结点的作用是什么？（3分）四、对图1，要求用prim算法和kruskal算法分别构造一棵最小生成树，画出你的构造过程。（10分）五、已经某有向图的邻接表表示如图2。（10分）（1）给出由1开始按深度优先遍历法访问顶点的顺序。（2）给出由1开始按广度优先遍历法访问顶点的顺序。（3）画出由1开始按深度优先遍历法访问顶点得到的生成树。（4）画出由1开始按广度优先遍历法访问顶点得到的生成树。第1页共3页六、写一个算法将一个单向链表拆成两个环形链表，并将每个个环形链表的长度存入其表头结点的数据域中，拆的规则是第一个环形链表包含原单向链表的第1，3，5，…结点；而第二个环形链表包含原单向链表的第2，4，6，…结点。（10分）七、给出一个二分查找算法如下：设记录R1，R2，…，RN的关键字为K1，K2，…，KN。要查找给定关键字K的记录。Step1[初始化]L︰＝1，U︰＝NStep2[求中点]如果U＜L，则查找不成功，否则i︰＝「(L+U)/2」；Step3[比较]如果K＜Ki，转Step4；如果K＞Ki，转Step5；如果K＝Ki，则查找成功；Step4[调整U]U︰＝i返回Step2；Step5[调整L]L︰＝i返回Step2；问上述算法能否正常执行，如果不能，试改进之。（10分）八、对数列r[i]（i=1，2，…，9）：i123456789r[i]8589649306159837105执行图3所给的算法，试回答：（1）执行该算法后，数列r[i]的值（i=1，2，…，9）。（2）执行该算法后i，j的值。（10分）第2页共3页注：框图中i︰j表示i与j的比较。九、试设计一个算法，将图的邻接表表示的一株树转换成图的左右链表示的二元树。（二元树的左右链表示见图4的示例。）（15分）第3页共3页哈尔滨工业大学一九九三年硕士研究生入学考试试题考试科目：数据结构报考专业：计算机科学与技术高级语言程序设计略数据结构部分三、回答下列问题（3×4=12分）1.在任意一棵二元查找树中，若删除一个结点，接着又将该结点插入到这棵二元查找树中，问所得的二元查找树和删除前的二元查找树是否一定相同？为什么？请举例说明2.设T是一非空二元树，每个结点有0个或两个儿子，如果我们把T看成是普通的树，可把该树转换成对应的一棵二元树T′，则对T的后根遍历的结果与对T′的后根遍历的结果一样，对吗？为什么？3.n个顶点的连通无向图，其边的条数至少是多少条？四、设T是一棵树，其中的结点命名为1，2，…，n。我们用数组A表示树T，即数组的下标对应于结点名，数组元素A[i]定义为：①A[i]＝j若结点i的父亲是j②A[i]＝0若结点i是根试设计算法将用数据A表示的树转换成用邻接表表示的树。（12分）五、什么是顺序文件？什么是索引文件？并从存贮结构和使用角度比较这两种文件的优缺点。（8分）六、设要分类的数据元素依次为：9，2，4，6，8，7，3，1，5，1。要进行堆分类，首先得为其建立一个初始堆，试画出在建立初始堆的过程中，二元树的变化情况。（10分）七、通常的基数分类法是对等长串进行的，对于不等长串A1，A2，…，An（其中，每个Ai都是一个串，其分量是在〈0，m-1〉范围内的整数，并且串的长度可以不等）。试问能进行基数分类吗？若能，请写出算法的主要步骤。（10分）八、设F是带表头的链接式线性表，如下图：第1页共2页试设计一个算法，将元素a插入到F中（若a已在F中，不必插入）。（10分）九、（第九题给非四年以上工龄的考生做，四年以上工龄的考生不必做）设非空有向图G=（V，E）有n个点，其编号为V={1，2，…，n}，且G已用邻接表表示，V中有两个特定点，点1叫出发点，点n叫目标点。试给出算法找出点1到点n的有向路之集合P，使之满足下述条件：（1）除点1和点n之外，P中任意两条路都没有公共点。（2）图也没有从点1到点n的有向路，可以加入P中而P仍满足条件（1）（18分）十、（第十题给四年以上工龄的考生做，非四年以上工龄的考生不必做）设已有两条链接式线性表A和B，每条线性表中的元素都互不相同，试将它们合并成一条链接式线性表C，要求：A和B中若有相同的元素，则在C中只允许出现一次。（18分）第2页共2页哈尔滨工业大学一九九四年硕士研究生入学考试试题考试科目：数据结构报考专业：计算机科学与技术说明︰1、对四年以上工龄的考生，第四、五、六、八题各15分，第七题20分；第九题不变。2、第四、五题可直接答在命题纸上。程序设计部分略数据结构部分四、判断题（10分）1.存在这样的二元树，对它采用任何次序的遍历结果都相同。（）2.快速分类法在任何情况下都比简单分类法快。（）3.若连通图上各边的权值均不相同，则该图的最小生成树是唯一的。（）4.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）5.完全二元树中，若一个结点没有左儿子，则必是树叶。（）五、填空（10分）1.一个线性表在计算机内主要有下述几种存放方法：。2.对图中各结点进行搜索的顺序主要有：。3.对二元树中各结点进行访问的顺序主要有：。4.文件的记录按照关键字的顺序存放，并带有索引的文件叫做；带有索引，但不要求记录按关键字的顺序存放的文件叫做；索引顺序文件通常都没有溢出区，即文件存贮区分为区，区和区。六、已知一链接线性表如图1所示，当线性表空时，R＝∧，今要把它当成栈来使用，试问把何处看成栈顶较为方便？写出将一个结点P链入栈顶以及从栈顶删除一个结点的算法？（12分）七、已知奇偶转换排序如下所述：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较；第二第1页共2页趟对所有的偶数i，将a[i]和a[i+1]进行比较；每次比较时，若a[i]＞a[i+1]则将两者交换，以后重复上述二趟过程交替进行，直至整个数组排好序。（15分）（1）试问：排序结束的条件是什么？（2）写出一个实现上述排序过程的算法。八、画出包含四个元素1，2，3，4的所有可能的二元查找树。（15分）注意：第九题四年以上工龄的考生不必做九、对于一株用邻接表表示的树，设计一个算法将其转换成相应的二元树。该二元树用左右链表示，即每个结点的格式如图2所示。(18分)LeftsondataRightson（图2）第2页共2页哈尔滨工业大学一九九五年硕士研究生入学考试试题考试科目：数据结构报考专业：计算机科学与技术说明：对“单独考试”的考生，第八题不必做，第三题24分，第四题12分，第七题20分程序设计部分略数据结构部分三、判断题（2×8=16分）1.折半查找首先要求数据是由小到大排好序的。（）2.一个带权的连通无向图的最小生成树是唯一的。（）3.一旦在无环路的无向图中指定了一个根结点，并且将每条边都看成是背离根的，它就变成一棵树。（）4.若T是一棵树，则T中至少有一个叶结点。（）5.若T是一株二元树，则T中至少有一个叶结点。（）6.任给一个线性表都可以看成是一株树。（）7.任给一个线性表都可以看成是一个广义表。（）8.如果对有向图进行先深搜索得到的先深遍历森林中，若没有向后弧，则该有向图中一定没有环路。（）四、问答题（5×2=10分）1.什么是散列法（杂凑法）？试说明内散列表与外散列表的区别？2.什么是随机文件？实现这种文件结构通常有哪几种方法？五、在下列分类方法中，哪些是稳定分类？哪些是不稳定分类？若是不稳定分类，试举出一个例子说明这种分类方法的不稳定性。（10分）（1）气泡分类（2）插入分类（3）选择分类（4）快速分类（5）堆分类六、已知一个串连成线性表F如图1所示，试给出一个算法（图1）将F变成一个根元素递增的顺序排列的单链式线性表。（14分）七、已知一个非空有向图G＝（V，E）中有n个结点，并且V＝{1，2，…，n}，是用邻接表表示的。试写出一个算法，判断该有向图中是否有环路。（14分）八、设T是一株树，其中的结点命名为1，2，…，n。对T中任意一结点i，其子结点的名字是从左到右递增的大于i的整数，用数组A表示树T，即数组的下标对应于结点名，数组元素A[i]定义为：①A[i]＝j若结点i的父亲是j②A[i]＝0若结点i是根试写出一个算法，按先根顺序列出该树中每个结点的名字。（16分）第1页共1页哈尔滨工业大学一九九六年硕士研究生入学考试试题考试科目：数据结构报考专业：计算机科学与技术程序设计部分略数据结构部分（图1）三、名词解释（20分）1.广义表2.连通分量3.最小生成树4.散列表5.随机文件四、问答题（9分）1.若某树有n1个一元结点，n2个二元结点，…，nm个m元结点，试问它有多少个终结结点？2.在任意一棵二元查找树中，若删除一个结点，接着又将该结点插入到这棵二元查找树中，问所得的二元查找树和删除前的二元查找树是否一定相同？为什么3.高度为k（k＞0）的完全二元树（从根结点到叶结点的最大路长加1称为二元树的高度）中结点个数最多为多少？最少为多少？五、已知有向图G的邻接表表示如图1所示。（9分）1.试画出有向图G。2.画出G的先深生成森林。3.画出G的先广生成森