2017年空军工程大学566计算机专业基础综合之数据结构考研复试核心题库
● 摘要
一、应用题
1． 某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。
（1）若使用一级页表的分存储管理方式，逻辑地址结构为：
则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分存储管理方式，逻辑地址结构为：
设逻辑地址为LA ，请分别给出其对应的页目录号和表索引达式。
（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H ，其长度为8KB ，被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存0020 0000H 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。
【答案】
（1）因为页内偏移量是12位所以页大小为4KB 页表项数为页表索引可表示为：
表项，所以第8个页表项的物理地址=页表起始地
址
如下图所示。
该一级页表最大为 页表项的字节
数（2）页目录号可表示为：（3）代码页面1的逻辑地址为0000 8000H, 表明其位于第8个页处，对应页表中的第8个页
2． 如果只要找出一个具有n 个元素的集合的第
种最适合? 给出实现的思想。
【答案】在具有n 个元素的集合中找第个最小元素，你所学过的排序方法中哪个最小元素，应使用快速排序方法。其基本思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若
素。
3． 三维数组
的存储首地址。
【答案】数组占的存储字节
数
的存储地
址则在1至i-1间继续进行快速排序的划分；若则在i+1至n 间继续进个最小元行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素
4． 某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU 采用单总线结构，主要部分如下图所示。图中为通用寄存器；T 为暂存器；SR 为移位寄存器，可实现直送（mov ）、左移一位（left ）、右移一位（right ） 3种操作，控制信号为Srop , SR的输
ALU 可实现直送A A 加 B （add ）A 减 B （sub ）A 与 B （and ）出信号Srout 控制；（mova ）、、、、
A 或 B （or ）、非 A （not ）、A 加 1 （inc ） 7 种操作，控制信号为
请回答下列问题。
（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T?
（2）控制信号（4）端点和的位数至少各是多少？ （3）控制信号Srout 所控制部件的名称或作用是什么？ 中，哪些端点须连接到控制部件的输出端？
中相应的端点之间添加必要的连线。写出连（5）为完善单总线数据通路，需要在端点
线的起点和终点，以正确表示数据的流动方向。
（6）为什么二路选择器MUX 的一个输入端是2?
【答案】（1）图中程序员可见的寄存器有通用寄存器和程序计数器PC ; 当执行算术或逻辑操作时，由于ALU 本身是没有内部存储功能的组合电路，因此如要执行加法运算，被相加的两个数必须在ALU 的两个输入端同时有效，因此设置暂存器T 用于暂存数据总线发送的数据。
（2）ALUop 和SRop 的位数分别为3，2。
（3）Srout 所控制的部件是状态字寄存器，用来存放ALU 及CPU 的指令状态。
（4）须连接到控制部件的输出端端点有
（5）
（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU 的第二个操作数。
【解析】（1）程序员可见的寄存器包括：程序计数器、通用寄存器和状态寄存器。其他的IR 、MAR 和MDR 等 是CPU 的内部工作寄存器，对程序员不可见。
（2）ALU 中共有7种命令，用三位即可区别表示，SR 共有三种命令二位二进制即可表示。 （4）操作符命令，传输等都需要控制信号进行控制。
5． 请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天
数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）
表示进行作业的路径。
完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充
，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。
图1
【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0
6． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？
【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺