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

1哈尔滨工业大学哈尔滨工业大学2013 年硕士研究生入学考试试题年硕士研究生入学考试试题 考试科目：考试科目：计算机专业基础计算机专业基础报考专业：报考专业：计算机科学与技术计算机科学与技术考试科目代码：考试科目代码：854 考生注意：答案务必写在答题纸上，并标明题号。答在试题上无效。考生注意：答案务必写在答题纸上，并标明题号。答在试题上无效。题号一二三四五六七总分分数20 10 20 25 15 30 30 150 数据结构部分（共数据结构部分（共 75 分）分）一、单项选择题：（一、单项选择题：（1-10 小题，每小题小题，每小题 2 分，共分，共 20 分。在每小题给出的四个选项中，请选出一项最符合题目要求的。）分。在每小题给出的四个选项中，请选出一项最符合题目要求的。）1深（高）度为 6（根的层次为 1）的完全二叉树至少有（1）结点。A64 B32 C31 D63 2若具有 n 个结点，k 条边的非连通无向图是森林（nk），则该森林中必有（2）棵树。Ak Bn Cn-k Dn+k 3若无向图 G 有 n 各顶点，其邻接矩阵为 A1n,1n，且压缩存储在 B1k，则 k 的值至少为（3）。An(n+1)/2 Bn2/2 C(n-1)(n+1)/2 Dn(n-1)/2 4下列排序算法中，（4）算法可能会出现下面情况：在最后一趟（遍）开始之前，所有元素都不在其最终的位置上。A堆排序 B冒泡排序 C选择排序 D插入排序 5文件有 m 各初始归并段，采用 k 路归并时，所需要的归并趟（遍）数是（5）。A2log k B2log m Cklog m Dmlog k 6下述编码中那一组不是前缀码（6）。A（00，01，10，11）B（0，1，00，11）C（0，10，110，111）D（1，01，000，001）7设高度为 h 的二叉树只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数为（7）。A2h B2h-1 C2h+1 Dh+1 8在某棵树中，结点 M 和 N 是结点 P 的第 i 和 i+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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研2结点 M 与 N 的关系是（8）。AM、N 具有同一双亲 BM 是 N 的左孩子 CN 是 M 的左孩子 DN 是 M 的右孩子 9具有 n 各结点的二分（折半）查找判定树，查找失败的外部结点（失败结点）共有（9）个。An-1 Bn Cn+1 Dlog2n 10 在含有 n 各关键字的最小堆（堆顶元素最小）中，关键字最大的记录有可能存储在（10）。An/2 Bn/2-1 C1 Dn/2+2 二、填空题：（二、填空题：（11-15 小题，每空小题，每空 1 分，共分，共 10 分。）分。）11对于一个长度为 n 的顺序存储的线性表，在第一个元素前插入元素的时间复杂度为 11-1；如果插入任何位置的几率相同，那么插入操作的平均时间复杂度为 11-2。12稀疏矩阵常用的两种存储方法是 12-1 和 12-2。13后缀算术表达式 9 2 3+-8 2/-的值为 13-1。中缀算术表达式(3+4*X)-2*Y/3 对应的后缀算术表达式为 13-2。14具有 2n 个结点的完全二叉树，含有 14-1 个度为 1 的结点，14-2 个度为 2 的结点。15在一棵高度为 h 的 B 树中，叶子结点处于第 15-1 层，当向该 B 树中插入一个新关键字时，为查找插入位置需读取 15-2 个结点。三、解答题：（三、解答题：（16-17 小题，每小题小题，每小题 10 分，共分，共 20 分。）分。）16一颗二叉树 T 的前序和中序遍历序列分别为：C，A，B，D，E，F 和 C，B，D，A，F，E。请回答下列问题：画出二叉树 T；简要概括由任意二叉树的前序和中序遍历序列构造二叉树的方法；画出二叉树 T 的后续线索二叉树。17已知加权有向图的邻接矩阵如下图所示，如需在其中一个顶点建立娱乐中心，请回答下列问题：利用 Floyd 算法求出每对顶点的最短距离，并用矩阵表示；求每个顶点的偏心度；确定娱乐中心应选哪个顶点。第 17 题图 各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研3四、算法设计题（四、算法设计题（18-19 小题，共小题，共 25 分）分）按以下要求设计算法：（按以下要求设计算法：（1）描述算法设计的基本思想；（）描述算法设计的基本思想；（2）根据设计思想，采用）根据设计思想，采用 C 或或 C+或或 Java 语言描述算法；（语言描述算法；（3）分析算法时间复杂度和空间复杂度。）分析算法时间复杂度和空间复杂度。18（12 分）已知一个按升序排好的数组和一个数字，请设计一个尽可能高效的算法 Findsum，在数据组中查找两个数，使得它们的和正好等于已知的那个数字，例如数组 1、2、4、6、7、11 和数字 11。由于 4+7=11，因此输出 4 和 7。如果存在多对这样的数字，输出任意一对即可。19（13 分）在森林的孩子-兄弟表示法（二叉链表表示法）存储结构中，每个结点的结构为：firstchilddatarightsib请设计一个算法 LeavesCounter，求森林的叶子结点数。计算机组成原理部分（共计算机组成原理部分（共 75 分）分）五、填空题（五、填空题（15 分，每空分，每空 1 分）分）1在总线判优控制中，采用集中控制，_方式对电路故障很敏感，_方式相应速度最快。2设寄存器内容为 FFH，若其表示 127，则为_码；若其表示-127，则为_码；若其表示-1，则为_码；若其表示-0，则为_码。3低位交叉编址的存储器能够提高访存速度的原因是_，其地址的最高位部分用于_，低位部分用于_。4影响流水线性能的因素主要有_冲突，_相关和_相关。5 设相对寻址的转移命令占两个字节，第一个字节是操作码，第二个字节是相对位移量（用补码表示），若 CPU 每从存储器取出一个字节时，即自动完成(PC)+1PC，设当前 PC 的内容为 2000H，要求转移到 2008H 地址，则转移指令第二个字节的内容应为_。6在微程序控制器中，一条机器指令对应一个_，若某机有 35 条机器指令，通常可对应_。六、简答题（每小题六、简答题（每小题 6 分，共分，共 30 分）分）1设浮点数 X=0.1101012010，Y=-0.1010102100，若阶码取 3 位，尾数取 6 位，（均不包括符号位），按补码运算步骤计算 X+Y 和 X-Y。各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研42设某机主存容量为 4MB，Cache 容量为 4096B，字块长度为 8 字，字长 32 位，试使用直接映象，全相联映象和四路组相连映象（即 Cache 每组内共有 4 各字块）三种方式的 Cache组织，要求：分别画出上述三种方式中主存地址字段的组成及各段的位数。3试比较单重分组和双重分组跳跃进位链。4某 CPU 的主频为 8MHz，若已知每个机器周期平均包括 4 个时钟周期，该机的平均指令执行速度为 0.8MIPS，试求该机的平均指令周期及每个指令周期含有几个机器周期？若改用主频为 0.4s 的 CPU 芯片，则计算机的平均指令执行速度为多少 MIPS？若要得到 0.4MIPS的平均指令执行速度，则应采用主频为多少的 CPU 芯片？5中断处理过程中为什么要中断判优？有几种方法实现？若想改变原定的中断处理优先顺序可采用什么措施？七、综合题（七、综合题（30 分）分）1（8 分）某机存储字长、指令字长和机器字长均为 16 位，指令格式如下：其中，D 为形式地址，补码表示（包括一位符号位）：M 为寻址模式：M=0 立即寻址；M=1 直接寻址（此时 D 视为无符号数）；M=2 间接寻址（此时 D 视为无符号数）；M=3 变址寻址（变址寄存器为 Rx）M=4 相对寻址；（1）写出各种寻址模式计算有效地址的表达式；（2）当 M=1、2、4 时，能访问的最大主存区为多少机器字（主存容量为 64K 字）。2（10 分）假设某机指令周期由取指周期、间指周期、执行周期和中断周期构成，CPU 内有寄存器 PC、IR、MAR、MDR 等，且未采用内部总线方式实现。如果 CPI 在中断周期用栈堆保存程序断点，而且进栈时指针减 1，出栈时指针加 1，请分别写出组合逻辑控制和微程序控制在完成中断返回指令时，取指周期和执行周期所需要的全部微程序命令及节拍安排。3（12 分）设 CPU 共有 16 根地址线，8 根数据线，并用MREQ信号（低电平有效）作为访存控制信号，用R/W（高电平为读，低电平为写）作为读写控制信号，现有下列芯片：ROM（2K*8位，4K*8位，8K*8位，32K*8位，）RAM（1K*4位，2K*8位，8K*8位，16K*1位，4K*4位）各个学校计算机/软件专业考研真题 免费分享 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及74138译码器和其他门电路（门电路自定）。画出CPU与存储器的连接图，要求：（1）存储芯片地址空间分配为：最小4K地址空间为系统程序区，相邻的4K地址空间为系统程序工作区，与系统程序工作区相邻的是24K用户程序区；（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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研