2017年长春师范大学数据结构(同等学力及跨学科加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如图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
2． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：
源操作数目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：
（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？
（2）转移指令的目标地址范围是多少？
（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句
改变后的内容是什么？
【答案】（1）指令操作码占4位，则指令系统最多可有
量为128KB ，计算机字长为16位，故主存有
需16位。
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。
（3）汇编语句
寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
3． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）判定树如图所示：
+对应的机器码为该指令执行后，条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?
图 判定树
（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。
（3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。
（4）
4． 某32位计算机，CPU 主频为800MHz ，Cache 命中时的CPI 为4, Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns ; 存储器总线宽度为32位，总线时钟频率为200MHz , 支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备 数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。
（1）CPU 和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？
（2）Cache 缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？
（3）存储器总线完成一次读突发传送总线事务所需的时间是多少？
（4）若程序BP 执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache 缺失率为5%, 不考虑替换等开销，则BP 的CPU 执行时间是多少？
【答案】
（1）因为CPU 主频为800MHz ，故CPU 的时钟周期为：
总线时钟频率为200MHz ，故总线的时钟周期为：
总线宽度为32bit=4B，故总线带宽为
存块。
（3）—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址;
每隔，第一个体读数据花费40ns ，之后数据启动一个体工作（各进行1次存取）
存取与数据传输重叠；用8个总线时钟周期传输数据。读突发传送总线事务时间
：
s
BP 的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。（4）
即执行时间=指令条数
间
：时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时指令执行过程中
的CPU 执行时间
：
5． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
（2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮Cache 缺失时的额外开
销
相关内容
相关标签