2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 33 页

目录

2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题（一） (2)

2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题（二） (10)

2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题（三） (16)

2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题（四） (23)

2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题（五） (28)

专注考研专业课13年，提供海量考研优质文档！

第 2 页，共 33 页 2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题

（一）

说明：根据本校该考试科目历年考研命题规律，结合考试侧重点和难度，精心整理编写。考研冲刺模考使用。共五套冲刺预模拟预测题，均有详细答案解析，考研冲刺必备资料。

——————————————————————————————————————————

一、综合题

1． 假定对有序表:(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题:

(1)画出描述折半查找过程的判定树；

(2)若查找元素54，需依次与哪些元素比较？

(3)若查找元素90，需依次与哪些元素比较？

(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。

【答案】(1)判定树如图所示:

图判定树

(2)若查找元素54，需依次和元素30、63、42、54比较，查找成功。

(3)若查找元素90，需依次和元素30、63、87、95比较，查找失败。 (4)

专注考研专业课13年，提供海量考研优质文档！

第 3 页，共 33 页 2． 某16位计算机主存按字节编码。存取单位为16位;采用16位定长指令格式;CPU 采用单总线结构,主要部分如下图所示。图中R0?R3为通用寄存器;T 为暂存器;SR 为移位寄存器,可实现直送(mov)、左移一位(left)、右移一位(right)3种操作,控制信号为Srop ,SR 的输出信号Srout 控制;ALU 可实现直送A(mova)、A 加B(add)、A 减B(sub)、A 与B(and)、A 或B(or)、非A(not)、A 加1(inc)7种操作,控制信号为ALUop 。

图

请回答下列问题。

(1)图中哪些寄存器是程序员可见的？为何要设置暂存器T?

(2)控制信号ALUop 和SRop 的位数至少各是多少？

(3)控制信号Srout 所控制部件的名称或作用是什么？

(4)端点①?⑨中,哪些端点须连接到控制部件的输出端？

(5)为完善单总线数据通路,需要在端点①?⑨中相应的端点之间添加必要的连线。写出连线的起点和终点,以正确表示数据的流动方向。

(6)为什么二路选择器MUX 的一个输入端是2？

【答案】(1)图中程序员可见的寄存器有通用寄存器R0?R3和程序计数器PC ;当执行算术或逻辑操作时,由于ALU 本身是没有内部存储功能的组合电路,因此如要执行加法运算,被相加的两个数必须在ALU 的两个输入端同时有效,因此设置暂存器T 用于暂存数据总线发送的数据。

(2)ALUop 和SRop 的位数分别为3,2。

(3)Srout 所控制的部件是状态字寄存器,用来存放ALU 及CPU 的指令状态。

(4)须连接到控制部件的输出端端点有①②③⑤⑧。

(5)⑥→⑨,⑦→④。

(6)数据宽度是16位,以字节编址,输入端是2是为了增加地址获取ALU 的第二个操作数。

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 33 页 【解析】(1)程序员可见的寄存器包括:程序计数器、通用寄存器和状态寄存器。其他的IR 、MAR 和MDR 等是CPU 的内部工作寄存器,对程序员不可见。

(2)ALU 中共有7种命令,用三位即可区别表示,SR 共有三种命令二位二进制即可表示。

(4)操作符命令,传输等都需要控制信号进行控制。

3． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

4． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B ，数据Cache 采用直接映射方式.现有两个功能相同的程序A 和B ，其伪代码如下所示:程序A :程序B :

假定int 类型数据用32位补码表示，程序编译时i ，j ，sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320(十进制数).请回答下列问题，要求说明理由或给出计算过程.

(1)若不考虑用于Cache 一致性维护和替换算法的控制位，则数据Cache 的总容量为多少？

(2)数组数据a[0][31]和a[l][1]各自所在的主存块对应的Cache 行号分别是多少(Cache 行号从0开始）？

(3)程序A 和B 的数据访问命中率各是多少?哪个程序的执行时间更短？

【答案】(1)每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位.由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264＝6位，Cache 块号为log 28＝3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28﹣6﹣3＝19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为8*(64＋20/8)B ＝532B

(2)数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示:

本文来源：https://www.bwwdw.com/article/3y6q.html