上海理工大学2013硕士考试：数据结构与计算机组成原理真题解析

"2013年上海理工大学硕士研究生入学考试真题841，包含数据结构及计算机组成原理的相关内容。" 此份考试真题主要涵盖了计算机科学中的两个核心领域：数据结构和计算机组成原理。以下是这两个领域的关键知识点： **计算机组成原理部分** 1. **计算机系统结构、计算机组成与计算机实现的关系**： 计算机系统结构是指从程序员的角度看计算机的抽象模型，包括指令集、存储系统、输入/输出系统等。计算机组成涉及硬件部件的逻辑设计，如CPU、内存、I/O设备等。计算机实现则是将这些设计转化为实际电路，通常包括逻辑门、集成电路等。三者之间层层递进，系统结构定义了基本功能，组成实现这些功能的逻辑，而实现则是在物理层面上的具体化。 2. **缓存一致性问题及其解决方案**： 在多处理器系统中，当CPU写入缓存时，可能会导致缓存和主存中数据不一致。解决这个问题的方法包括：总线锁定、MESI协议（Modified, Exclusive, Shared, Invalid）等，通过这些机制确保在多个处理器访问同一数据时保持一致性。 3. **程序与微程序、机器指令和微指令的区别**： - 程序是由高级语言编写的，最终被编译或解释为机器指令执行。 - 机器指令是计算机硬件直接理解和执行的低级代码。 - 微指令是构成微程序的基本单元，微程序控制计算机时，一组微指令组成一个控制字段，控制计算机执行特定操作。 4. **微程序控制计算机的执行过程**： 在微程序控制的计算机中，当执行一条机器指令时，控制单元首先读取相应的微指令，微指令解释后产生控制信号，驱动硬件执行相应的操作。 5. **主存储器的组织**： 题目中提到的16M x 8位的主存储器，表示有16兆（即16 * 2^20）个存储单元，每个单元存储8位数据。计算所需的地址线和数据线数量，地址线需22位（2^22 = 4M > 16M），数据线需8位。 6. **DMA（直接内存访问）与程序中断方式**： DMA允许外部设备直接访问内存，无需CPU干预，提高了数据传输效率。中断方式则是CPU暂停当前任务，处理外部事件后再返回原任务。DMA在批量数据传输时更快，因为减少了CPU的介入次数。 7. **补码运算**： 补码运算是计算机中表示和处理负数的方式。题目中要求计算二进制数的补码形式以及进行加减运算，涉及符号位处理和溢出判断。 **数据结构部分** 1. **链表和链域**： 链表中的每个节点包含数据和指向下一个节点的指针（链域）。除首节点外，其他节点的位置由其链域值（即指针）决定。 2. **循环队列的队满条件**： 队满时，最后一个元素的下一个位置会指向队列的起始位置，因此队满时队列中的元素个数为n（对于n个单元的队列）。 3. **栈的操作**： 向顺序栈中压入元素时，栈顶指针TOP通常会向上移动一位，指向新的栈顶元素。 4. **对称矩阵的存储**： 对称矩阵的压缩存储只需存储下三角或上三角，因为其余部分是对称的。如果是行主序存储，容量为n(n+1)/2；如果是列主序，容量为n(n-1)/2。 5. **树的遍历**： 给出的中序遍历和后序遍历序列，可以推断出该二叉树的结构，例如，中序遍历序列定义了左子树、根节点、右子树的顺序，后序遍历序列定义了左子树、右子树、根节点的顺序。 这份考试真题全面测试了学生对计算机系统基础理论和数据结构的理解，涵盖了许多重要的概念和技术，对准备这类考试的学生来说具有很高的参考价值。