2017年海南大学1087数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 解答问题。设有数据逻辑结构为：
（1）画出这个逻辑结构的图示。
（2）相对于关系R ，指出所有的开始结点和终端结点。
（3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。
（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。
【答案】
⑴如图1所示：
图1
（2）开始结点（入度为0）:
（3）拓扑序列：
规则：开始结点为
或之后，若遇多个入度为0的顶点，按顶点编号顺序选择。
（4）正向邻接表如图2所示，逆向邻接表如图3所示：
终端结点（出度为0）:
图2 正向邻接表
图3 逆邻接表
2． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？
【答案】（1）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
（若）
，
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若
（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
3． 某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，故总线带宽为
空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：）。
（2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮存块。
（3）—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址;
每隔，第一个体读数据花费40ns ，之后数据启动一个体工作（各进行1次存取）
存取与数据传输重叠；用8个总线时钟周期传输数据。读突发传送总线事务时间
：
s
BP 的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。（4）
即执行时间=指令条数
间
：时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时指令执行过程中
的CPU 执行时间
：
4． 假定在一个8位字长的计算机中运行下列C 程序段：
若编译器编译时将8个8位寄存器R1〜R8分别分配给变量
回答下列问题。（提示：带符号整数用补码表示）
（1）执行上述程序段后，寄存器Rl 、R5和R6的内容分别是什么？（用十六进制表示） （2）执行上述程序段后，变量m 和kl 的值分别是多少？（用十进制表示）
（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。
（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？
【答案】（1）无符号整数运算，（Rl ） =x=134=10000110B=86H、（R5）=x-y=246=10010000B=90H、（R6）=x+y=01111100B=7CH。
（2） m 的机器数与x 的机器数相同为86H=1000 0110B，解释为带符号整数（用补码表示）时，其值为-111 1010B= -112; 同理kl=（m-n ）=（x-y ）=90H=1001 0000B，解释为带符号整数（用补码表示）时，其值为-111 1010B=-112；
（3）四种运算可以利用同一个加法器及辅助电路实现，n 位加法器实现的是模2n 无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现，而实现；对于带符号整数用补码表示，补码加减运算公式为
：
，所以四种运算都可在n 位加法器
中实现。
Cache 缺失时的额外开
销 请
相关内容
相关标签