精品文档2016年哈工大计算机科学与技术专业 854考研真题I •数据结构部分 单项选择题具有2015个结点的完全二叉树，叶子节点个数为（A.1006 B.1007 C.10081.2.3.4.5.6.7.8.9.D.1009算术表达式a*（b+c）-d化为后缀表达式为（2） °A.abcd+*- B.abc+*-d C.abc+*d-某队列允许在某两端进入入队操作，但仅允许在一端进行出队操作，元素e依次入队，则不可能得到的顺序是（D.ab+c*d-a、b、 c、d、3)°A.bacde B.dbace C.dbcae D.ecbad在有N个叶子结点的哈夫曼树中，其结点总数为（A.不确定 一个只有度为 是（5） °A.3 , 44) °B.2N-1 C.2N+1 D.2N0和2的二叉树，有5个叶子结点，该二叉树最小层数是（5），最大层数B.4, 5若邻接表中有奇数个边表结点，A. 图中有奇数个结点B. 图中有偶数个结点C. 图为无向图D. 图为有向图下面给出的四种排序中（7）A.插入 B.冒泡当初始序列已按关键字有序时，A.n-1 B.log2nC.5，6 则一定是D.6，76)°排序是不稳定性排序。
C.二路归并 D.堆用直接插入算法进行排序，需要比较次数为（C.2log2 n8)°设散列表中有m个存储单元，散列函数A. 小于等于m的最大奇数B. 小于等于m的最大素数C. 小于等于m的最大偶数D. 小于等于m的最大合数10.哈希查找中k个关键字具有同一哈希值， 入哈希表中，至少要进行（10）次探测A.k B.k+1 C.k（k+1）/2填空题在单链表中设置头结点的作用是 一知的结点*p后插入一个新结点的时间复杂度为入一个新结点的时间复杂度为11.12.13.14.15.16.D.n2H（key）=key%p，则 p 最好选择（9）若用线性探测法将这 k个关键字对应的记录存D.1+k(k+1)/2，对于一个具有n个结点的单链表，在已 ，在给定值为 x的结点后插完整的存储一个n*n对称矩阵所需的存储单元数为缩方式，存储一个对称矩阵所需的存储单元数为设一棵二叉树中的中序遍历序列为 DBCA，后序遍历序列为 DBAC，则这棵二叉树的前序遍历序列为，采用上三角形式的压设图有37条边，其最小的顶点数为解决Hash冲突的两种常用方法为简答题设有一优先级队列插入时可以任意优先级的元素，删除时只能删除最大优先级元素，写，最多的顶点数为出用以下存储结构实现时的时间复杂度。
插入时间复杂度删除时间复杂度无序数组有序数组无序单链表有序双链表最大堆17. 设有一组关键字 T=（12,2,16,30,8,28,4,10,20,6,18），设内存工作区可存放 4条记录，用置换选择排序的方法生成初试归并段：（1） 一共可以生成多少个初始归并段？（2） 对其进行归并排序，写出每一步结果，并给出最终输出结果四、 算法设计题按下列要求设计算法：（1） 描述算法设计的基本思想；（2） 根据设计思想，采用 C或C++或Java语言描述算法；（3） 分析算法时间复杂度和空间复杂度18. 有一长度为n的整数序列a[n],其元素按先严格递减后平桥递增的顺序排列，请设计一个时间上尽可能高效的算法 FindMin（）查找最小值元素，并分析时间复杂度和空间复杂度19. 二叉树采用二叉链表表示法，并增加一个你父结点指针 pare nt域，以及flag域（可以取0，1，2三个值，取0时表示访问根结点，取 1表示访问左孩子，取 2时表示访问右孩 子），在该存储结构上，设计一个算法实现非递归不用栈的后序遍历算法II •计算机组成原理部分五、 填空题1. 计算机通电后执行的第一条微指令地址（微程序入口）来自 ，控制实现取令操作，然后由 产生后继微地址。
2. 十六进制整数 FEH分别表示的是反码、补码、移码，对应的十进制值是 、_ 、 3. 某机共有156条指令，采用一地址格式，则指令字需取 位才能直接寻址64K个存储单元完成一条这种形式的加法指令，需访问 次存储器4. 设x为17/35，则吃岬为 , 1岬为 5. 已知接收到的海明码为 0100111 （按配偶原则配置），试问欲传送的信息是 六、 选择题1. 计算机与日常使用的袖珍计算器的本质区别在于（ 1 ）A. 运算速度的高低B. 存储器容量的大小C. 规模的大小D. 自动化程度的高低2. 开设计算机组成原理这门课的主要目的是为了研究（ 2）A. 计算机系统的层次结构和组成B. 计算机系统的软件和硬件C. 计算机的工作过程D. 计算机的设计和工作原理3. 总线的半同步通信方式（3）A. 既不采用时钟信号，也不采用握手信号B. 只采用时钟信号，不采用握手信号C. 不采用时钟信号，只采用握手信号D. 既采用时钟信号，又采用握手信号4. 在二种集中式总线控制中，（4）方式响应时间最快A. 链式查询B. 计数器定时查询C. 独立请求D. 一样快5. 以下属于单总线特点的是（5）。
A. 可以减少CPU和各部件的连线，易于增删设备B. 传送速度快，大多数计算机都采用这种连接方式C. 可以匹配访存速度不一的设备，使得计算机系统效率更高D. 是从多总线优化发展而来的七、 简答题1. 在微程序设计中，多路选择器的输入信号来源有哪些？并指出其各自的作用3.简述中断系统的基本组成，说明其各自的作用4.设x=-0.1110, y=0.1101，用原码一位乘计算八、 综合题1.设某机共有50个微操作控制信号，按 8, 12, 14, 16分成4组互斥的微命令组，并有 3 个互斥的可判定的外部条件，微指令长度为 32位1） 写出采用字段直接编码方式的微指令格式并说明理由2） 求控存容量（3） 这种方式比直接编码方式节省了多少存储空间？2. 设CPU共有16根地址线和8根数据线，并用作访存控制信号， ；作读写命令信号（高电平读，低电平写）设计一个容量为 8K*8位，地址范围为0000H~仆FFH，且 采用低位交叉编址的四体并行存储器要求：（1） 采用下图所列芯片（门电路自定），详细画出CPU和存储芯片的连接图2） 指出图中每个存储芯片的容量及地址范围（用十六进制表示） 。