2009年全国硕士研究生入学统一考试

一、数据结构选择题部分

1 队列

2 队列

3 树遍历

4 平衡二叉树

5 完全二叉树 错题，重点题

6 森林转化为二叉树 – 左孩子右兄弟 错题

7 无向连通图

8 B树定义

9 小根堆排序、再看

10 排序算法，再看

插入排序局部有序

冒牌和选择排序一轮排序后必定有一个在固定位置上。

二、计算机组成原理选择题部分

11 指令和数据的区分方式

12 补码、十六进制计算、错题

13 重点看，浮点数的计算

尾数右规，阶码+1

小阶向大阶看齐

14 Cache组相联计算，再看

15 存储器芯片(主存容量)的扩展，再看

现代计算机中，MAR和MDR通常集成在CPU的内部，而存储芯片内的仅是一个普通的寄存器。主存储器与CPU的连接示意图如下

●主存储器通过数据总线、地址总线和控制总线与CPU连接
●数据总线的位数与工作频率的乘积正比于数据传输率
●地址总线的位数决定了可寻址的最大内存空间
●控制总线（读或写）指出总线周期的类型和本次输入输出操作完成的时刻

位扩展

字扩展
1、线选法（不好用）

2、译码片选法

译码片选法
会在线选法的基础上做一定改进，只需要加入一个非门

译码器编号：1-2译码器是输入1个对应2个，2-4译码器是输入两个对应4个，以此类推

16 相对寻址