哈工大计算机科学与技术专业考研真题

1、2016年哈工大计算机科学与技术专业854考研真题I数据结构一、 选择题1. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。Int x = n * n;While (x >= 1) X = x / 2;A. O(log2n)B. O(n)C. O(nlog2n)D. O(n1/2)2. 需要分配一个较大的存储空间并且插入和删除操作不需要移动，元素满足以上特点的线性表存储结构是（）。A. 单向链表B. 静态链表C. 线性链表D. 顺序表3. 已知字符串S为”ababcabcacbab”，模式串T为”abcac”。若采用KMP算法进行模式匹配，则需要（）遍（趟匹配），就能确定

2、T是S的子串。A. 3B. 4C. 5D. 64. 已知某棵二叉树的前序序列是1,2,3,4，则不可能为该二叉树的中序序列的是（）。A. 1,2,3,4B. 2,3,4,1C. 1,4,3,2D. 3,1,4,25. 将森林F转换为对应的二叉树T，F中任何一个没有右兄弟的结点，在T中（）。A. 没有左子树B. 没有右子树C. 没有左子树和右子树D. 以上都不对6. 一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）个零元素。A. eB. 2eC. n2-2eD. n2-e7. 在一棵高度为2和7阶B树中，所含关键字的个数最少是（）。A. 5B. 7C. 8D. 148. 设待排序

3、的元素个数为n，则基于比较的排序最坏情况下的时间复杂度的下界为（）。A. log2nB. nC. nlog2nD. n29. 下面关于B树和B+树的叙述中，不正确的是（）。A. B树和B+树都能有效地支持随机检索B. B树和B+树都能有效地支持顺序检索C. B树和B+树都是平衡的多路树D. B树和B+树都可以用于文件的索引结构10. 若待排序关键字序列在排序前已按其关键字递增顺序排列，则采用（）方法比较次数最少。A. 插入排序B. 快速排序C. 堆排序D. 选择排序二、 填空题11. 在一棵n个结点的二叉树中，所有结点的空子树个数为11。12. 若二叉树的一个叶结点是其某子树的中序遍历序列中的

4、第一个结点，则它必是该子树的后序遍历序列中的第12个结点。13. 在有n个选手参加的单循环赛中，总共将进行13场比赛。14. 在有4033个叶子结点的完全二叉树中，叶子结点的个数为14个。15. 一个有向图G1的反向图是将G1的所有有向边取反而得到的有向图G2，若G1和G2的邻接矩阵分别为A，B，则A与B的关系为15。16. N个顶点e条边的无环路有向图，若采用邻接表作为存储结构，则拓扑排序算法的时间复杂度为16。17. 在10阶B树中根结点所包含的关键字最多有17个，最少有18个。18. 在具有12个结点的平衡二叉树（AVL树）中，查找AVL树中的一个关键字最多需要（18）次比较。19. 对

5、初态有序的表，最少时间的排序算法是（19）。三、 简答题20. 在n个数据中找出前K个最大元素，可以采用堆排序或败者树来实现。分别说明上述两种实现方法的基础步骤，并分析每种方法的时间复杂度和空间复杂度。21. 假设举办一个1000人参加的学术会议，作为会议报道组的负责人，你会收到会务组为每名参会者开具的包含其英文名字的注册费发票，同时还会收到为每位参会者提供的印有其英文名字的参会胸牌和其他会议资料。请回答以下问题：（1） 如何有效地把每个参会者注册费发票和参会胸牌等其他会议资料放在一起形成一份参会资料？（2） 如何在会议报道日更有效地把每份资料发放给参会者？要求：说明你所使用的主要技术和相关步

6、骤。四、 算法设计题按以下要求设计算法：（1） 描述算法设计的基本思想；（2） 根据设计思想，采用C或C+或Java语言描述算法；（3） 分析算法时间复杂度和空间复杂度。22. 给定一个n个整数的无序数组A，设计一个时间和空间尽可能高效的算法，找出其中第k个小的整数： int findTheKmin (int A, int n, int k)。23. 给定一棵n个结点的二叉排序树（即BST），每个结点均存放一个整数，其结点格式为lechilddatarechild。令half=(BST中的最大值+BST中的最小值)/2。设计一个算法intfindNearMid(BinTree * root)，

7、完成:（1） 找出BST中最大和最小以及计算 half的值；（2） 返回大于half且与half相差最小的结点值。II计算机组成原理部分五、 填空1. 在整数定点机中，采用1位符号位，若寄存器内容为10000000，当它分别表示为原码、补码，及无符号数时，其对应的真值分别为1-1、1-2、1-3和1-4。（均用十进制表示）2. 变址寻址和基址寻址的区别是：在基址寻址中，基址寄存器提供2-1，指令提供2-2；而变址寻址中，变址寄存器提供2-3，指令提供2-4。3. 利用3-1指令进行输入输出操作的I/O编址方式为统一编址。4. 设n=16（不包括符号位），机器完成一次加和移位各需100ns，则原

8、码一位乘最多需4-1ns，补码Booth算法最多需4-2ns。5. CPU从主存取出一条指令并执行该指令的时间叫5-1，它通常包含若干个5-2。而后者又包含若干个5-3、5-4组成多级时序系统。六、 选择题1. 冯·若依曼计算机中指令和数据均以二进制形式存放在存储器，CPU区分它们的依据是（）。A. 指令操作码的译码结果B. 指令和数据的寻址方式C. 指令周期的不同阶段D. 指令和数据所在的存储单元2. DMA方式传送数据时是在（）控制的。A. CPUB. 程序C. CPU+程序D. 硬件电路3. 总线通信中的同步控制是（）。A. 只适合于CPU控制的方式B. 由统一时序控制的方式C

9、. 只适合于外围设备控制的方式D. 只适合于主存4. 下列叙述中（）是错误的。A. 采用微程序控制器的处理器称为微处理器B. 在微程序编码中，编码效率最低的是直接编码方式C. 在各种微地址形成方式中，增量计数法需要的顺序控制字段较短D. CMAR是控制器中存储地址寄存器5. 设相对寻址的转移指令占两个字节，第一字节是操作码，第二字节是相对位移量（用补码表示），若CPU每当从存储器取出一个字节时，即自动完成(PC)+1àPC。设当前PC的内容为2009H，要求转移到2000H地址，则该转移指令第二字节的内容应为（）A. F5HB. F7HC. 09HD. 0AH七、 简答与计算1. 设

10、一个32位微处理器配有16位的外部数据总线，时钟频率为50MHz，若总线传输最短周期为4个时钟周期，试问处理器的最大数据传输率是多少？若想提高1倍数据传输率，可采用什么措施？2. 主机与I/O传送数据时，有几种控制方式，简述它们各自的特点，并指出哪种方式的CPU效率最高。3. 设主存容量为1MB，Cache容量为16KB，每字块有16个字，每字32位。（1） 若Cache采用直接相联映像，求出主存地址字段中各段的位数。（2） 若Cache采用四路组相联映像，求出主存地址字段中各段的位数。4. 设阶码取3位，尾数取6位（均不包括符号位），按浮点补码运算规则计算：25×916+24

11、15;-1116八、 综合题1. 设CPU共有16根地址线，8根数据线，并用MREQ作访存控制信号（低电平有效），用WR作读写控制信号（高电平为读，低电平为写）。现有下列芯片：ROM(2K*8位，8K*8位，32K*8位)RAM(1K*4位，2K*8位，8K*8位，16K*1位，4K*4位)及74138译码器和其他门电路（门电路自定）。画出CPU与存储器的连接图，要求：（1） 存储器芯片的地址空间分配为：最大4K地址空间空系统程序区，相邻的4K地址空间为系统程序工作区，最小16K地址空间为用户程序区；（2） 指出选用的存储芯片类型及数量；（3） 详细画出片选逻辑。2. 设CPU中各部件及其互相连接关系如图所示，图中W是写控制标志，R是读控制标志，R1和R2是暂存器。（1） 假设要求在取指周期由