哈尔滨工业大学-854-1991-2008-真题.pdf

《哈尔滨工业大学-854-1991-2008-真题.pdf》由会员分享，可在线阅读，更多相关《哈尔滨工业大学-854-1991-2008-真题.pdf（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、哈尔滨工业大学 哈尔滨工业大学 一九九一年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 汇编语言部分 汇编语言部分 略 数据结构部分 数据结构部分 4、解释下列名词（34=12 分）（1）完全二元树 （2）先深搜索 （3）最小生成树 （4）二元查找树注：本试题中要求设计的算法可用任一种程序设计语言或流程图来描述 5、已知一个算术表达式如下：y=c+d(cos(2x+b)+b)（1）试用一株树将表示出来。（3 分）（2）将（1）中形成的树变换成相应的二元树。（3 分）（3）试给出的前缀表示和后缀表示。（3 分）6、略（此题为一 PASCAL 程序填空题。一是目前哈工大早

2、已经没有这种题型，二是哈工大目前已不再出 PASCAL 相关的题）第 1 页 共 2 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 7、图 1，给出的流程图试图完成下述功能：对于两个长度分别为 m 和 n（nm0）的字符序列：P=P0 P1Pm-1 S=S0 S1Sm-1 当 P 是 S 的子序列时，输出 P 在 S 中首次出现的位置，否则输出“失败”信息。查找方法是将 P 与 S 左端对

3、齐，自左至右逐个比较 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）其中：（ai，bi，wi）表示ai、biV，（ai，bi）E，wi为边（ai，bi）的权，（0，0，0）表示序列的结束。试给出一个算法，将所给的有向图用邻接表表示出来，并求出每个结点的入度，邻接表的形式如图 2 所示。其中：indegree 为顶点的入度；ptr 为指针，指向其直接后继顶点队列的头；nam

4、e 为顶点名，weight 为权；next 为指向下一个结点的指针。（15 分）9、试设计一个算法，将一株用左右链表示的任意二元树（图 3 给出一个示意性例子），加一些虚结点当成满二元树（如图 4，把图 3 的示例变成了满二元树），存放在数组中，使之满足：下标为 i 的结点，它的两个儿子的下标为 2i 和 2i+1，虚结点的数据域用表示。（18 分）第 2 页 共 2 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信

5、公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九二年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 汇编语言部分 汇编语言部分 略 数据结构部分 数据结构部分 三、回答下列问题（15 分）1.在一株二元分类树中，要使遍历结果是一个按关键字递减的顺序排列的，应如何遍历？（4分）2.设栈存在在数组 A0 m-1中，栈底位置是 m-1。栈空的条件是什么？栈满的条件是什么？（4 分）3.设有 n 个结点的完全二元树，顺序存放在 A1 n中，对任一结点 Ai：（4 分）（1）若 Ai有父亲结点，问父亲结点是哪个？（2）若 Ai有左儿子，问左儿子是哪个？（3）若 Ai

6、有右儿子，问右儿子是哪个？（4）i 值最大的非叶结点是哪一个？4.单向链表中引入头结点的作用是什么？（3 分）四、对图 1，要求用 prim 算法和 kruskal 算法分别构造一棵最小生成树，画出你的构造过程。（10 分）五、已经某有向图的邻接表表示如图 2。（10 分）（1）给出由 1 开始按深度优先遍历法访问顶点的顺序。（2）给出由 1 开始按广度优先遍历法访问顶点的顺序。（3）画出由 1 开始按深度优先遍历法访问顶点得到的生成树。（4）画出由 1 开始按广度优先遍历法访问顶点得到的生成树。第 1 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i

7、t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研六、写一个算法将一个单向链表拆成两个环形链表，并将每个个环形 链表的长度存入其表头结点的数据域中，拆的规则是第一个环形 链表包含原单向链表的第 1，3，5，结点；而第二个环形链表 包含原单向链表的第 2，4，6，结点。（10 分）七、给出一个二分查找算法如下：设记录 R1，R2，RN的关键字为 K1，K2，KN。要查找给定关键字 K 的记录。Step1初始化 L1，UN Step2求中点 如果 U L，则查找不成功，否则

8、i(L+U)/2；Step3比 较 如果 K Ki，转 Step4；如果 K Ki，转 Step5；如果 K Ki，则查找成功；Step4调整 U Ui 返回 Step2；Step5调整 L Li 返回 Step2；问上述算法能否正常执行，如果不能，试改进之。（10 分）八、对数列ri（i=1，2，9）：i 1 2 3 4 5 6 7 8 9 ri 85 89 64 93 06 15 98 37 105 执行图 3 所给的算法，试回答：（1）执行该算法后，数列ri的值（i=1，2，9）。（2）执行该算法后 i，j 的值。（10 分）第 2 页 共 3 页 各个学校计算机/软件专业考研真题 免费

9、分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研注：框图中 ij 表示 i 与 j 的比较。九、试设计一个算法，将图的邻接表表示的一株树转换成图的左右链 表示的二元树。（二元树的左右链表示见图 4 的示例。）（15 分）第 3 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信

10、公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九三年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 高级语言程序设计 高级语言程序设计 略 数据结构部分 数据结构部分 三、回答下列问题（34=12 分）1.在任意一棵二元查找树中，若删除一个结点，接着又将该结点插入到这棵二元查找树中，问所得的二元查找树和删除前的二元查找树是否一定相同？为什么？请举例说明2.设 T 是一非空二元树，每个结点有 0 个或两个儿子，如果我们把 T 看成是普通的树，可把该树转换成对应的一棵二元树 T，则对 T 的后根遍历的结果与对 T的后根遍历的结果一

11、样，对吗？为什么？3.n 个顶点的连通无向图，其边的条数至少是多少条？四、设 T 是一棵树，其中的结点命名为 1，2，n。我们用数组 A 表示树 T，即数组的下标对应于结点名，数组元素 Ai定义为：Ai j 若结点 i 的父亲是 j Ai 0 若结点 i 是根试设计算法将用数据 A 表示的树转换成用邻接表表示的树。（12 分）五、什么是顺序文件？什么是索引文件？并从存贮结构和使用角度比较这两种文件的优缺点。（8 分）六、设要分类的数据元素依次为：9，2，4，6，8，7，3，1，5，1。要进行堆分类，首先得为其建立一个初始堆，试画出在建立初始堆的过程中，二元树的变化情况。（10 分）七、通常的基

12、数分类法是对等长串进行的，对于不等长串 A1，A2，An（其中，每个 Ai 都是一个串，其分量是在0，m-1范围内的整数，并且串的长度可以不等）。试问能进行基数分类吗？若能，请写出算法的主要步骤。（10 分）八、设 F 是带表头的链接式线性表，如下图：第 1 页 共 2 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研试设计一个算法，将元素 a 插入到 F 中（若 a 已在 F 中，不必插入）

13、。（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，每条线性表中的元素都互不相同，试将它们合并成一条

14、链接式线性表 C，要求：A 和 B 中若有相同的元素，则在 C 中只允许出现一次。（18 分）第 2 页 共 2 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九四年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 说明1、对四年以上工龄的考生，第四、五、六、八题各 15 分，第七题 20 分；第九题不变。2、第四、五题可直接答在命题

15、纸上。程序设计部分 程序设计部分 略 数据结构部分 数据结构部分 四、判断题（10 分）1.存在这样的二元树，对它采用任何次序的遍历结果都相同。（）2.快速分类法在任何情况下都比简单分类法快。（）3.若连通图上各边的权值均不相同，则该图的最小生成树是唯一的。（）4.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）5.完全二元树中，若一个结点没有左儿子，则必是树叶。（）五、填空（10 分）1.一个线性表在计算机内主要有下述几种存放方法：。2.对图中各结点进行搜索的顺序主要有：。3.对二元树中各结点进行访问的顺序主要有：。4.文件的记录按照关键字的顺序存放，并带有索引的文件叫

16、做 ；带有索引，但不要求记录按关键字的顺序存放的文件叫做 ；索引顺序文件通常都没有溢出区，即文件存贮区分为 区，区和 区。六、已知一链接线性表如图 1 所示，当线性表空时，R，今要把它当成栈来使用，试问把何处看成栈顶较为方便？写出将一个结点 P 链入栈顶以及从栈顶删除一个结点的算法？（12分）七、已知奇偶转换排序如下所述：第一趟对所有奇数的 i，将 ai和 ai+1进行比较；第二第 1 页 共 2 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信

17、公众号 计算机与软件考研 微信公众号 计算机与软件考研趟对所有的偶数 i，将 ai和 ai+1进行比较；每次 比较时，若 aiai+1则将两者交换，以后重复上 述二趟过程交替进行，直至整个数组排好序。（15 分）（1）试问：排序结束的条件是什么？（2）写出一个实现上述排序过程的算法。八、画出包含四个元素 1，2，3，4 的所有可能的二元查找树。（15 分）注意：第九题四年以上工龄的考生不必做 九、对于一株用邻接表表示的树，设计一个算法将其转换成相应的二元树。该二元树用左右链表示，即每个结点的格式如图 2 所示。(18 分)Leftson data Rightson（图 2）第 2 页 共 2

18、页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九五年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 说明：对“单独考试”的考生，第八题不必做，第三题 24 分，第四题 12 分，第七题 20 分 程序设计部分 程序设计部分 略 数据结构部分 数据结构部分 三、判断题（28=16 分）1.折半查找首先要求数据是由小到大排好序的。（）2

19、.一个带权的连通无向图的最小生成树是唯一的。（）3.一旦在无环路的无向图中指定了一个根结点，并且将每条边都看成是背离根的，它就变成一棵树。（）4.若 T 是一棵树，则 T 中至少有一个叶结点。（）5.若 T 是一株二元树，则 T 中至少有一个叶结点。（）6.任给一个线性表都可以看成是一株树。（）7.任给一个线性表都可以看成是一个广义表。（）8.如果对有向图进行先深搜索得到的先深遍历森林中，若没有向后弧，则该有向图中一定没有环路。（）四、问答题（52=10 分）1.什么是散列法（杂凑法）？试说明内散列表与外散列表的区别？2.什么是随机文件？实现这种文件结构通常有哪几种方法？五、在下列分类方法中，

20、哪些是稳定分类？哪些是不稳定分类？若是不稳定分类，试举出一个例子说明这种分类方法的不稳定性。（10 分）（1）气泡分类 （2）插入分类 （3）选择分类 （4）快速分类 （5）堆分类 六、已知一个串连成线性表 F 如图 1 所示，试给出一个算法 （图 1）将 F 变成一个根元素递增的顺序排列的单链式线性表。（14 分）七、已知一个非空有向图 G（V，E）中有 n 个结点，并且 V1，2，n，是用邻接表表示的。试写出一个算法，判断该有向图中是否有环路。（14 分）八、设 T 是一株树，其中的结点命名为 1，2，n。对 T 中任意一结点 i，其子结点的名字是从左到右递增的大于 i 的整数，用数组 A

21、 表示树 T，即数组的下标对应于结点名，数组元素 Ai定义为：Ai j 若结点 i 的父亲是 j Ai 0 若结点 i 是根试写出一个算法，按先根顺序列出该树中每个结点的名字。（16 分）第 1 页 共 1 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九六年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 程序设计部分 程序设计部分

22、 略 数据结构部分（图 1）数据结构部分（图 1）三、名词解释（20 分）1.广义表2.连通分量3.最小生成树4.散列表5.随机文件四、问答题（9 分）1.若某树有n1个一元结点，n2个二元结点，nm个 m 元结点，试问它有多少个终结结点？2.在任意一棵二元查找树中，若删除一个结点，接着又将该结点插入到这棵二元查找树中，问所得的二元查找树和删除前的二元查找树是否一定相同？为什么3.高度为 k（k0）的完全二元树（从根结点到叶结点的最大路长加 1 称为二元树的高度）中结点个数最多为多少？最少为多少？五、已知有向图 G 的邻接表表示如图 1 所示。（9 分）1.试画出有向图 G。2.画出 G 的先

23、深生成森林。3.画出 G 的先广生成森林。六、有一种建堆的方法叫逐个插入式建堆方法，该方法是在堆分类中，被分类的数组 An中的数据是一次一次取来的，每取来一个新元素，都要把它插入现存的堆中并形成新的堆，如果实现了堆的插入算法，我们 k 次应用该算法，即先把一个元素插入空的堆，然后依次继续插入其他元素，直至 k 个元素插完，即可建成堆 Ak。算法要点：设 A1 Ak-1是一个堆。我们将一个新元素插入到堆的“底部”Ak，然后令 Ak和它的祖先（父亲，祖父，曾祖父等）比较；当它的祖先的值比它大时，就向堆的下部移动，如此重复，知道找到一个适当位置，使新元素可放在其中而不致违背堆的性质，第 1 页 共

24、3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研如图 2 例子所示。下述算法即体现了这种插入过程，试填空完善此算法。（12 分）七、已知两个线性表 L1和 L2是单向链接式线性表，如图 3 所示，并且 L1 和 L2中的元素是整型的。试编写一个算法，将 L1和 L2合并成一个带头结点的链接式线性表 L，使得 L1和 L2中的结点相互间隔并顺序地出现在 L 中，若 L1（L2）比 L2（L1

25、）长，则当 L2（L1）中结点都出现在 L 中后，再将 L1（L2）中的剩下的结点依次并入 L 中，并将 L 中的元素的个数置入表头结点的数据域中如图 3 所示。（12 分）第 2 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研八、设有一个森林，已转换成二元树的形式存放在内存中，按图 4 所给的例子的形式存放（设森林中结点名为 1，2，n，并且每个结点名互不相同）。1.试给出一个

26、算法，求森林中树的个数。（6 分）2.试给出一个算法，求每个结点在森林中的层号，写入 LEVEL 中。（12 分）（注：第八题中第 2 小题四年以上工龄单独考生不做，对于四年以上工龄单独考生的各题分数分布如下：第一 二 三 四 五题分数不变，第六题 16 分，第七题 16 分，第八题 10 分。）（图 4）（图 4）第 3 页共 3 页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学

27、 哈尔滨工业大学 一九九七年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 高级语言程序设计部分 高级语言程序设计部分 略 数据结构部分 数据结构部分 三、试论述下列概念的区别。（16 分）1.数据结构与程序设计语言中数据类型。（5 分）2.线性表与广义表。（5 分）3.顺序式文件、随机式文件和链接式文件。（6 分）四、阅读下列说明和流程图 2，回答问题 1 和问题 2。说明：流程图 2 用来实现中根顺序遍历二元树的算法，二元树存放在数组 tree 中，每个数组元素存放在树中的一个结点，每个结点的形式如下所示：值左 链右 链分别用 tree i.v，tree i.l 和

28、tree i.r 来表示 第 1 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研第 i 个结点的“值”，“左链”，“右链”。其中左，右链的值为所 指结点在数组中的下标，若链的值为零表示它指向空树。图中变 量 root 用以指向二元树的根节点。（16 分）问题 1.填充流程图 2 中的，使其按中根顺序遍历二元树。问题 2.将流程图 2 中的（A）框移至哪个位置（用图 2 中所示的回

29、答），使该流程图的算法从中根顺序遍历变成先根顺序遍历。五、某校学生学号由 8 位十进制数字组成 C1C2C3C4C5C6C7C8。C1C2 为入学时年份的最后两位；C3C4 为系别，0024 分别代表该校的 25 个系，C5 为 0 或 1，0 表示本科生，1 表示研究生，C6C7C8 为某班某系某类学生的顺序编号，对于本科生，它不超过 199，对于研究生，它不超过 049，共有 4 个年级在校，四年级学生 95 年入学。（12 分）六、设有数组 a1，a2，an。下面给出的算法（见图 3）是对该数组进行排序的算法。试说明：（1）该算法实现排序的基本步骤？（7 分）（2）框图中的a0起什么作用

30、？（3 分）七、设有一个双链表，每个结点中除有pre，data和next三个域之外（pre，next分别为指向前导结点和后继结点的指针，data 是该结点的数据域），还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次 LOCATE(L,X),操作时（LOCATE(L,X)是在头指针为 L 表中查找数据域的值为 X 的结点，并返回该结点的地址，令元素值等于 X 的结点中 Freq 域的值增 1，并使此链表中的结点保持按访问频度不增的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的 LOCATE 操作的算法。（13分）八、设有一无向图 G（V，E

31、），V1，2，n，在内存中用如 第 2 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研图 4 的例子所示的邻接多重表表示，试编写一算法建立图 G 的邻 接表表示。（13 分）第 3 页共 3 页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关

32、注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九八年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 高级语言程序设计部分 高级语言程序设计部分 略 数据结构部分 数据结构部分 三、判断题。（29=18 分）1.当 K1 时，高度（从根结点到叶结点的最大路长加 1 称为二元树的高度）为 K 的二元树至多有 2 K-1个结点。（）2.用树的先根遍历和中根遍历可以导出树的后根遍历。（）3.哈夫曼树是加权路长最短的二元树，路径上的权值较大的结点离根较近。（）4.将一株树转换成二元树后，根结点没有右子树。（）5.在任意一株二元查找

33、树中，若删除一个结点接着又将该结点插入到这株二元查找树中，所得到的二元查找树和删除前的二元查找树有可能相同。（）6.有 N 个顶点的连通无向图，其边的条数至少是 N-1 条。（）7.折半查找首先要求数据一定要按不减的顺序排好序的。（）8.在一个对有向图进行先深搜索得到的先深生成森林中，若没有向后弧，则该有向图中一定没有环路。（）9.一个带权的连通的无向图的最小生成树是唯一的。（）四、阅读下列对线性表进程操作 的 3 个子程序的流程图，从供选择的答案中选出应该填入 ae 处的字句写在答案的对应栏内。说明：在内存中一个如右图所示的表格结构，表格的每个元素由值（V）和游标（P）两部分组成。在表格中以

34、链接方式存放着一个线性表 L，它的第一个元素的位置存放在 LP 中。表格中的全部空闲元素也链接成一个线性表 E，它的第一个元素的位置存放在 CP 中。两个线性表的最后一个元素的游标都是 0。子程序（1）enter（u，m）：在线性表 L 中位于 m（m0）处（下标为 m）的元素之后插入一个以 u 为值的结点。子程序（2）find（u，m）：从 线 性表 L 中找出第一个其值为 u 的元素，把其位置（下标）放入 m 中。没有以 u 为值的元素时，把 m 置为 0。子程序（3）delete（m）：从至少有两个元素的线性表 L 中删除紧接在位置 m 之后的一个元素。把删除的元素放进线性表 E 中。第

35、 1 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 五、一个满 K 元树有如下性质：层号最大的结点都是叶子结点，其余各层上每个结点都有 K株非空子树，如果按层次顺序从 1 开始对全部结点编号。问：（13 分）（1）各层的节点数目是多少？（2）编号为 N 的结点的父结点（若存在）的编号是多少？（3）编号为 N 的结点的第三个儿子结点（若存在）的编号是多少？（4）编号为 N 的结点

36、有右兄弟的条件是什么？其右兄弟的编号是多少？六、长度为 10 的数组，其数组元素已排好序，画出对其进行折半查找的二元判定树。（16 分）七、填空，将适当的表达式或语句填入如下框图的处。该框图所表示的算法的说明如下：本算法用于基于快速分类思想的算法寻找给定数组的第 k 小元素。算法执行后，第 k小元素在 Ak中。设给定的数组 Ai（i=1，2，n）中各元素互不相等。它的第 k（1kn）小元素是指这样的元素：它大于 n 个元素中的 k-1 个元素，而小于其余 n-k。例如,假设 n=8，数组 A 的 8 个元素是：44，94，12，50，55，6，18，67 它的第 5 小元素（即 k=5）是 5

37、0.为了找出第 5 小元素，程序的大致执行过程如下：将 A5的值 55 记为 X，从左向右扫描，直到遇见第一个不大于 X 的元素（即 18），然后交换这两个元素，数组 A 称为：44，18，12，50，55，6，94，67 继续这一“扫描与交换”的过程，直到两个方向的扫描在数组中间的某处汇合。此时数组被分成两段，汇合点左边的元素均小于 X（即 55），而右边的元素均大于 X，然后适当取其中一段，重复尚需步骤，直至找到第 K 小元素为止。（18 分）八、已知一个有向图 G（V，E），其 中 V1，2，n，在内存中用邻接矩阵 Cnn表示。另外有一个二维数组 Dnn是整型数组。试编写一个算法，先深搜

38、索有向图 G，给 D 赋值，使得：（15 分）Di，j=0 当 E 中没有弧（i，j）时 Di，j=1 当在先深生成森林中（i，j）是树弧时 第 2 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 Di，j=2 当在先深生成森林中（i，j）是向前弧时 Di，j=3 当在先深生成森林中（i，j）是向后弧时 Di，j=4 当在先深生成森林中（i，j）是交叉弧时（其中：1in，1jn）

39、第 3 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九九年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 一、名词解释 1.广义表2.最小生成树3.散列表4.堆5.随机文件二、试分别画出具有3个结点的树和3个结点的二元树的所有不同形态（同构的算一个）。（6分）三、本题给出一个子程序的框图，如图 2，试填空完善此算法框图

40、。该子程序用来寻找第一个均出现在三个整数单向链表 f1，f2，f3 中的相同整数。假定在调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图 1 的例子所示。（15 分）注：在图 2 的框图中：found 和 exit 均为布尔型的变量，可取 第 1 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研值为 true 和 false。val 是整型变量，用来存放第

41、一个均 出现在 f1，f2，f3 中的相同整数。若 f1，f2 和 f3 中无相 同的整数，found 的值为 false，否则 found 的值为 true。f1.link 表示访问 f1 所指结点的 link 域。四、假设一株二元树，其按后根顺序的结点排列为：H，I，D，J，E，B，F，G，C，A 而按中根顺序的结点排列为：H，D，I，B，E，J，A，C，F，G。（1）试画出这株二元树。（7 分）（2）画出它的线索二元树。（7 分）五、已知集合 S=7，3，4，6，19，14，16，9，22，11，试按照自左而右的顺序依次取出 S中的每个元素，逐步建立一株对应于 S 的二元查找树。试画出所

42、得到的二元查找树（不要求给 算 法）。（8 分）六、本题给出的是将数组 a 的元素 a1,a3,an 从大到小排序的子程序的框图，如图 3（第 3 页），填空完善此算法框图。该子程序采用改进的选择排序方法，该方法基于以下思想：在选择第一大元过程中：a1 与 aj(j=n,n-1,2)逐个比较，若发现 aj1a1,则 aj1 与 a1 交换，交换后新的 aj1 有性质 aj1=at(j1tai(j2=at(j2t=0)个，依次为 aj1,aj2,ajk，则它们都满足这一性质。它们的下标满足 n=j1j2jk1。有了这些下标，在确定第二大元时，可只考虑 a2 与 aj(j=jk,jk-1,3)逐一

43、比较。倘若 jk=2,则可不经比较就知道 a2 就是第二大元。在选择第二大元的过程中，将与 a2 交换过的元素下标也记录下来，可供选择其他大元使用。但在选择第二大元时，应保证与 a2 交换的那些位置上的新值也都满足上述性质。依次类推，顺序选择第一，第二，,第 n-1 大元，实现对 a 的排序。（14 分）注：a 是整数数组，存放要排序的数组集合，n 是 a 的长度，p,i,j,k,m,t 是临时变量，p为整型数组，i,j,k,m,t 为整型变量。第 2 页共 3 页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k

44、 a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研七、假定用两个一维数组 LN和 RN作为有 N 个结点 1，2,，N 的二元树的存储结构。Li和 Ri分别指示结点 i 的左儿子和右儿子；Li=0（Ri=0）表示 i 的左（右）儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tn，使 Ti存放结点 i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。（14 分）八、一个只含有加，减，乘，除四则运算的算术表达式已在机器内用无环路有向图的邻接表方式存储。若每个操作数原子都由单个字母表示，试写一个算法输出其

45、逆波兰表达式。图 4给出了一个例子表达式及其存储形式。（14 分）第 3 页 共 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 一九九九年硕士研究生入学考试试题 考试科目：计算机原理 报考专业：计算机科学与技术 一、问答题（22 分）1微机中为减少 CPU 芯片引脚数，减少指令执行时间并缩短指令编码长度，都采用了什么方法？（4 分）2有信息长 7 位 10

46、11011，其海明码（采用奇校验）应该是什么样的？若在海明码的第 3 位上出错，怎么纠错？（10 分）3 若 8086 工作在最小模式下，CPU 的引脚中，当完成将 AX 中的内容送到物理地址为 2000OH 的存储单元的操作时，或者当完成的操作时将物理地址20001H 单元内容传到寄存器 CL 时，分别有哪些引脚信号处于低电平？（5 分）4衡量计算机的性能指标主要有哪些（答主要三项指标），并说明为什么？(3 分）二、设某微型机的寻址范围为 64K，其存储器选择信号为，接有 8 片 8K 的存储器，试回答下列问题：（16 分）1画出选片译码逻辑图；2写每片 RAM 的寻址范围；3如果运行时发现

47、不论往哪片存储器存放 8K 数据，以 AO00H 起始地址的存储芯片都有与之 相同的数据分析故障原因；4若出现译码中的地址线 A13 与 CPU 断线，并搭接到高电平上的故璋，问后果如何？三、设有虚拟 CPU X，在一个总线周期内执行一条加法指令 ADD M,R，其中 M 为某个内存单元，R 为某个寄存器。X 的总线周期由 4 个时钟周期组成，每个时钟周期从下降沿开始。X 可以发出读信号，写 信 号，地址锁存信号 ALE，地址信号 A0 Am，发出或接收数据信号 D0 Dn。当执行上述加法指令时，试设计总线上各信号 A0 Am，D0 Dn，ALE，的合理时序，并说明理由。假设指令已经取在 CP

48、U 内。（10 分）四、在中断优先权判优的排队电路中有一种用 比较器实现的方案其逻辑示意图如右：当输入的 3 位（8 级）中断优先权编码大于当前优先级编码时输出为高电平，否则为低电平。优先级从高到低的次序为 111 到 000。试用与，或，非，异或门设计比较器内部的逻辑电路。（10 分）五、8086、8088 的中断向量表的结构是怎样的？在中断过程中如何使用它？（5 分）六、PC 机中有一扬声器，可以发出约 1KHz 的音频信号。若采用 8253 来实现，时钟频率为4.77MHz，请回应如何设计 8253 计数寄存器的初值？应工作在哪种模式？（5 分）七、异步串行通讯的数据格式是怎样的？请画出

49、并说明。为什么这种格式可以保证数据传送的可靠性？(m 分）第 1 页 共 1 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研哈尔滨工业大学 哈尔滨工业大学 二年硕士研究生入学考试试题 考试科目：数据结构 报考专业：计算机科学与技术 一、名词解释：（12 分）1 抽象数据类型；2 算法的时间复杂性；3 散列法(hashing)；4 索引文件。二、填空：(12 分)1 在单链表中设置头结点的作用

50、是_。2 n 个顶点的连通无向图，其边的条数至少为_。3 线索二元树的左线索指向其_，右线索指向其_。4 树在计算机内的表示方式有_，_，_。5 排序（sorting）有哪几种方法_，_，_，_，_。三、判断下列叙述是否正确，若你认为正确，请画“”，否则画“”。1 存在这样的二元树，对它采用任何次序的遍历，结果相同。（）2 二元树就是结点度为 2 的树。（）3 若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）4 无向图的邻接矩阵一定是对称矩阵，但有向图的邻接矩阵一定是非对称矩阵。（）5 完全二元树中，若一个结点没有左儿子，则必是树叶。（）四、堆与二元查找树的区别？（6 分）五、快速