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

1. 设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂性为 （1）。 2. 线索二元树的左线索指向 （2） ，右线索指向 （3） 。

3. 若分别以实数4,5,6,7,8作为叶结点的权值来构造哈夫曼（Huffman）树，则该哈夫曼树

的带权路径长度是 （4） 。

4. N个顶点的连通图用邻接矩阵表示时，该矩阵至少有 （5） 个非零元素。

5. 设只包含根结点的二元树的高度为0，则高度为K的二元树的最多结点数为 （6），最

少结点数 （7） 。

6. 任意一个有n个结点的二元树，已知它的m个叶结点，则度数为2的结点有 （8）。 7. 对n个记录的表进行选择排序，在最坏情况下所需要进行的关键字的比较次数为

（9）。

8. 在 （10） 情况下，等长编码是最优前缀码。 二、选择题

1. 若结点的存储地址是其关键字的某个函数，则称这种存储结构为（1）。

A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构

2. 对于一个索引顺序文件，索引表中的每个索引项对应主文件中的（2）。

A. 一个记录 B. 多条记录 C. 所有记录 D. 以上都不对

3. 将两个各有n个元素的已排序表归并成一个排好序的表，其最少的比较次数是（3）。

A. n B. 2n-1 C. 2n D. n-1

4. 假定有K个关键字且散列地址相同，若用线性探测法（步长1）把K个关键字存储散列

表中，至少要进行（4）次探测。 A. K-1 B. K C. K+1

D. K(K+1)/2

5. 在关键字随机分布的情况下，用二元查找树的方法进行查找，其平均查找长度与（5）

量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 散列查找

6. 对于一个有向图，若某顶点的入度为K1，出度为K2，则在该图的逆邻接表中，关于该

顶点链表的结点个数为（6）。

A. K1 B. K2 C. K1-K2 D. K1+K2

7. 下列说法正确的是（7）。

A. 最小生成树也是哈夫曼（Haffman）树 B. 最小生成树唯一

C. 对于n个顶点的连通无向图，Prim算法的时间复杂性为O(n2) D. Kruskal算法比Prim算法更适合边稠密的图

8. 一个有n个顶点的连通无向图，它所包含连通分量个数为（8）。

A. 0 B. 1 C. n D. n+1 三、判断题

1. 顺序存储的线性表可以随机存取。（1）

2. 单源最短路径的Dijkstra算法中要求边上的权值不能为负的原因是实际应用无意义。（2） 3. 若无向图G的顶点度数的最小值大于或等于2，则G必然存在环路。（3） 4. 在二元树中，具有一个儿子的父结点，在中根遍历序列中没有后继结点。（4） 5. 广义表中原子的个数即为广义表的长度。（5） 6. 有环路的有向图不存在拓扑序列。（6）

7. 快速排序的速度在所有以比较为基础的排序方法中是最快的，且所需附加空间最小。（7） 8. 对于n个记录的集合进行归并排序，在最坏情况下所需要的时间是O(n2)。（8） 9. 外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并。（9） 10. 一个连通的无几图是双连通的，当且仅当它没有关节点。（10） 四、简答题

1. 举例说明4*3的稀疏矩阵的两种存储方法。

2. 一组关键字(46,79,56,38,40,84)所对应的完全二元树是否为堆，如果是堆，请给出堆排序

的前两步的图示：如不是，则给出建立初始堆（大顶堆）及堆排序的前两步的图示。 五、算法设计题

队列和栈的基本操作可以直接使用。

1. 设二元树的存储结构为左右链形式，设计按层次遍历该二元树的算法并输出结点序列。 2. 对于给定的一个排好序的整数序列。设计一个算法构造。

一棵二元树，使得在该二元树中，以任意结点为根的子树的高度之差的绝对值不大于1。 3. 可以使用“破圈法”求解带权连通无向图的一棵最小生成树。所谓“破圈法”就是任取

一个圈并去掉圈上权最大的边，反复执行这一步骤，直到没有圈为止。请设计该算法求解给定带权连通无向图的最小生成树。（注：图即为环路）。 II．计算机组成原理部分 六、填空

1. 某机有五级中断，优先级从高到低为12345。若将优先级顺序修改，改后1级

中断的屏蔽字为11111，2级中断的屏蔽字为01010，3级中断的屏蔽字为01111，4级中断的屏蔽字为00001，5级中断的屏蔽字为01011，则修改后的处理优先级顺序从高到低为 （1） 。

2. 已知74181是4位的ALU芯片，其4位进位是同时产生的，74182是先行进位芯片，现

用8片74181和2片74182可组成 （2） 。 3. 在集中式总线仲裁中， （3-1） 方式响应时间最快， （3-2） 方式对电路故障

最敏感。

4. 有一主存-cache层次的存储器，其主存容量1MB，Cache容量16KB，每字块有8个字，

每字32位，采用直接地址映像方式，若主存地址为35301H，且CPU访问Cache命中，则在Cache的第 （4） （十进制表示）字块中（Cache起始字块为第0字块）。 5. 对于某些指令（如乘法指令），控制器通常采用 （5-1） 控制方式来控制指令的执

行，但这种控制中的节拍宽度与 （5-2） 控制的节拍宽度是相等的，而且这两种控制是 （5-3） 。

6. 一个DMA接口可采用周期窃取方式把字符传送到寄存器，它支持的最大批量为200个

字节，若存取周期为0.2μs，每处理一次中断需4μs，现有的字符设备的传输率为9600位/秒。假如字符之间的传输是无间隙的，试问DMA方式每秒因数据传输占用处理器 （6） 时间。（忽略预处理所需的时间）。

7. 设相对寻址的转移指令占2个字节，第一字节为操作码，第二字节为位移量（用补码表

示），每当CPU从存储器取出一个字节时，即自动完成(pc)+1pc。设当前指令地址为3008H，要求转移到300FH，则该转移指令第二字节的内容应为 （7-1） 。若当前指令地址为300FH，要求转移到3004H，则该转移指令第二字节的内容为 （7-2） 。 8. 二进制数在计算机中常用的表示方法有原码、补码、反码和移码等多种。表示定点整数，

若要求数值0在计算机中唯一表示为全“0”，应采用 （8-1） ；表示浮点数时，若要机器零（即尾数为零，且阶码最小的数）在计算机中表示为全“0”，则阶码应采用（8-2）。某计算机中，浮点数的阶码占8位，（含1位阶符），尾数占40位（含1位数符），都采用补码，则该机器中所能表达的最大浮点数是 （8-3） 。

9. 在浮点檛，设尾数采用双符号位，当补码运算结果的尾数部分不是 （9-1）的形式应进行规格化处理，当尾数符号位为 （9-2）时，需要右规。

10. 除了采用高速芯片外，从计算机的各子系统的角度分析，可采用 （10-1）、（10-2）、

（10-3）、（10-4）、（10-5）、（10-6）等措施提高整机速度。 七、简答与计算

1. 为了减轻总线负载，总线上的部件应具备什么特点？什么是总线通信控制？总线通信控

制有几种方式？

2. 设计中断系统需考虑哪些主要问题？分别可用哪些技术解决？

3. 已知二进制数x=-0.1111，y=0.1101，用补码一位乘Booth算法计算x*y。

八、假设某机有8个16位的通用寄存器，主存容量为256K字，共能完成54种操作，且有

4种寻址方式，试回答：

1. 设计一个三地址格式的寄存器-存储器型指令，可完成(Ri) OP (M)  Rj。

2. 若采用直接寻址方式访问主存中的任一地址，上述三地址格式指令中的地址码域应分配

多少位？指令字长应为几位？

3. 若采用基址寻址方式，上述指令格式应如何修改？

4. 若指令字长等于存储字长，假设主存容量扩充到4G字，在不改变硬件结构的前提下，

可采用什么建起方式使指令能访问主存空间中的任一位置？

作访存控制信号， 九、设CPU有18根地址线和8根数据线，并用 作读写命令，

存储器采用四体低位交叉结构，画出CPU和存储芯片的连接图。要求：

1. 合理选用下列芯片，门电路自定。 2. 写出每片存储芯片的二进制地址范围。 3. 详细画出存储芯片的片选逻辑。

4. 该存储器在一个存取周期内可向CPU提供多少位信息？ 十、已知带返转指令的含义如下图所示：

1. 写出机器在完成带返转指令时，组合逻辑控制取指阶段和执行阶段所需的全部微操作从

及节拍安排。

2. 若采用微程序控制，还需增加哪些微操作？

3. 假设该机指令系统采用6位定长操作码格式，共对应多少个微程序？ 4. 微指令的操作控制方式有几种？各有何特点？ 5. 微指令的下地址字段位数如何确定？