2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题
更新时间:2023-04-28 16:37:00 阅读量: 实用文档 文档下载
专注考研专业课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 之间的映射关系如下图所示:
正在阅读:
2018年东北大学秦皇岛分校842计算机专业基础之数据结构考研冲刺五套模拟题04-28
精编办公室个人半年总结08-23
韩国头像男生帅气02-14
2019全国卷1江苏浙江高考英语听力文本05-03
车间噪声防治措施.doc04-08
微机原理与接口技术实验报告01-21
建筑工程施工细部做法图例(附图丰富、图文对照)_secret06-15
歌颂改革开放40周年演讲稿02-25
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 东北大学
- 秦皇岛
- 数据结构
- 模拟题
- 分校
- 冲刺
- 考研
- 计算机
- 基础
- 专业
- 2018
- 842
- 企业薪酬管理体系培训重点是什么 企业薪酬管理体系培训总结
- 直线与平面平行的判定教案..
- 部编版一年级上册语文识字6《画》课文原文及教案
- 部编版小学语文《飞向蓝天的恐龙》公开课优质课教案设计
- 江苏省盐城中学2021届高三上学期12月第三次阶段性质量检测英语试题
- 【整编】河道整治综合工程、截污干管工程和沿河道路工程施工组织设计
- 涟源亿丰项目销售说辞11.27(1)(1)(1)
- 汽车设计工程师简历模板
- 北京大学自主招生个人陈述自荐信.
- 康复治疗三基考试 题
- 小学一年级上学期班主任工作方案
- 瘦西湖引水泵站改造工程施工组织设计
- IC datasheet pdf-TLK3114SC,pdf(10-Gbps XAUI Transceiver)
- 高新技术产业园项目可行性研究报告(DOC 43页)
- 2016年黑龙江省社会科学院世界史809马克思主义哲学考研内部复习题及答案
- 二季度可布局五类股票
- 山东省冠县武训高级中学高考地理一轮复习活页训练9 洋流及其他地理意义
- 关于密封防水胶点胶加工所用防水胶的特点
- 北京蓝鼎智联科技有限公司_中标190925
- 恒大恒大恒大万科防止图纸错漏碰缺的施工图成果标准建筑部分