-2016年哈工大计算机科学与技术专业854考研真题.doc

2016年哈工大计算机科学与技术专业854考研真题
I．数据结构部分
一、 单项选择题
1. 具有2015个结点的完全二叉树，叶子节点个数为（1）。
A.1006 B.1007 C.1008 D.1009
2. 算术表达式a*(b+c)-d化为后缀表达式为（2）。
A.abcd+*- B.abc+*-d C.abc+*d- D.ab+c*d-
3. 某队列允许在某两端进入入队操作，但仅允许在一端进行出队操作，元素a、b、c、d、e依次入队，则不可能得到的顺序是（3）。
A.bacde B.dbace C.dbcae D.ecbad
4. 在有N个叶子结点的哈夫曼树中，其结点总数为（4）。
A.不确定 B.2N-1 C.2N+1 D.2N
5. 一个只有度为0和2的二叉树，有5个叶子结点，该二叉树最小层数是（5），最大层数是（5）。
A.3，4 B.4，5 C.5，6 D.6，7
6. 若邻接表中有奇数个边表结点，则一定是（6）。
A.图中有奇数个结点
B.图中有偶数个结点
C.图为无向图
D.图为有向图
7. 下面给出的四种排序中（7）排序是不稳定性排序。
A.插入 B.冒泡 C.二路归并 D.堆
8. 当初始序列已按关键字有序时，用直接插入算法进行排序，需要比较次数为（8）。
A.n-1 B.log2n C.2log2n D.n2
9. 设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（9）。
A.小于等于m的最大奇数
B.小于等于m的最大素数
C.小于等于m的最大偶数
D.小于等于m的最大合数
10. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（10）次探测。
A.k B.k+1 C.k(k+1)/2 D.1+k(k+1)/2
二、 填空题
11. 在单链表中设置头结点的作用是 ，对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 ，在给定值为x的结点后插入一个新结点的时间复杂度为 。
12. 完整的存储一个n*n对称矩阵所需的存储单元数为 ，采用上三角形式的压缩方式，存储一个对称矩阵所需的存储单元数为 。
13. 设一棵二叉树中的中序遍历序列为DBCA，后序遍历序列为DBAC，则这棵二叉树的前序遍历序列为 。
14. 设图有37条边，其最小的顶点数为 ，最多的顶点数为 。
15. 解决Hash冲突的两种常用方法为 、 。
三、 简答题
16. 设有一优先级队列插入时可以任意优先级的元素，删除时只能删除最大优先级元素，写出用以下存储结构实现时的时间复杂度。

插入时间复杂度
删除时间复杂度
无序数组

有序数组

无序单链表

有序双链表

最大堆

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. 二叉树采用二叉链表表示法，并增加一个你父结点指针parent域，以及flag域（可以取0，1，2三个值，取0时表示访问根结点，取1表示访问左孩子，取2时表示访问右孩子），在该存储结构上，设计一个算法实现非递归不用栈的后序遍历算法。
II．计算机组成原理部分
五、 填空题
1. 计算机通电后执行的第一条微指令地址（微程序入口）来自 ，控制实现取令操作，然后由 产生后继微地址。
2. 十六进制整数FEH分别表示的是反码、补码、移码，对应的十进制值是 、 、 。
3. 某机共有156条指令，采用一地址格式，则指令字需取 位才能直接寻址64K个存储单元。完成一条这种形式的加法指令，需访问 次存储器。
4. 设x为17/35，则为 ，为 。
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. 在微程序设计中，多路选择器的输入信号来源有哪些？并指出其各自的作用。
2. 证明：。
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~1FFFH，且采用低位交叉编址的四体并行存储器。要求：
（1） 采用下图所列芯片（门电路自定），详细画出CPU和存储芯片的连接图。
（2） 指出图中每个存储芯片的容量及地址范围（用十六进制表示）。

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）