2017年大连海事大学Z01数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 如果输入序列为123456, 试问能否通过栈结构得到以下两个序列：435612和135426; 请说明为什么不能或如何才能得到。
【答案】输入序列为123456, 不能得出435612, 其理由是，输出序列最后两元素是12, 前面4个元素（4356）得到后，栈中元素剩12, 且2在栈顶，栈底元素1不可能在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1; 然后2和3入找，3出栈，部分输出序列变为13; 接着4和5入栈，5、4和2依次出栈，部分输出序列变为13542; 最后6入栈并出栈，得到最终结果135426。
2． 已知有5个顶点的图G 如下图所示
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。 （2）求什么？
【答案】（1）邻接矩阵为
矩阵
中位于0行3列元素值的含义是什么？
非零元素的含义是
（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：
0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。
（3）中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为
m 的路径的条数。
3． 在树和树中查找关键字时，有什么不同？
【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。
树的非终端结点是索引部分，其查找从根开始，从根往下查到关键
. 树还可以在最下层从最小关
字后，要继续查到最下层结点，得到查找成功与否的结论。另外，
键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。 4． 假定某计算机的CPU 主频为80MHz , CPI为4, 并且平均每条指令访存1.5次，主存与Cache 之间交换的块大小为168, Cache的命中率为
存储器总线宽度为32位。请回答下列问题。
（1）该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下，主存带宽至少达到多少才能满足CPU 的访存要求？
（2）假定在Cache 缺失的情况下访问主存时，存在期挪用方式，磁盘
接口的数据缓冲寄存器为32位，则磁盘
的缺页率，则CPU 平均每秒产
接口平均每秒发出的DMA
生多少次缺页异常? 若页面大小为4KB ，每次缺页都需要访问磁盘，访问磁盘时DMA 传送采用周请求次数至少是多少？
（3）CPU 和DMA 控制器同时要求使用存储器总线时，哪个优先级更高? 为什么？ （4）为了提高性能，主存采用4体交叉存储模式，工作时每每个体的存储周期为50ns ，则该主存能提供的最大带宽是多少？
【答案】
（1）平均每秒CPU 执行的指令数为：平均每秒Cache 缺失的次数为：为
：
足CPU 的访存要求。
（2）平均每秒钟“缺页”异常次数为：故平均每秒磁盘DMA 请求的次数至少为：请求得不到及时响应，
传输数据可能会丢失。
因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA 请求，CPU 和DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为若DMA （3）
（4）4体交叉存储模式能提供的最大带宽为：
故MIPS 数为20; =300000;
才能满
个存储周期启动一个体。若
当Cache 缺失时，CPU 访问主存，主存与Cache 之间以块为单位传送数据，此时，主存带宽
在不考虑DMA 传输的情况下，主存带宽至少达到
5． 某计算机主存按字节编址，逻辑地址和物理地址都是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个页
6． 解答问题。设有数据逻辑结构为：
（1）画出这个逻辑结构的图示。
（2）相对于关系R ，指出所有的开始结点和终端结点。 （3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。 （4）分别画出该逻辑结构的正向邻接表和逆向邻接表。