2017年辽宁大学计算机专业相关知识之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 假定某计算机的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 传输的情况下，主存带宽至少达到
2． 已知图的邻接矩阵为：
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历序列； （2）以顶点V1为出发点的唯一的广度优先遍历序列； （3）该图唯一的拓扑有序序列。
1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8 （3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO
3． 组织待检索文件的倒排表的优点是什么？
【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。
4． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。
例如若给定的单链表head 如下
删除节点后的head 为
要求
（1）给出算法的基本思想 （2）使用c 或
语言，给出单链表节点的数据类型定义。
语言描述算法，关键之处给出注释。
（n 为正整数）。现要求
设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节
（3）根据设计思想，采用c 或
（4）说明所涉及算法的时间复杂度和空间复杂度。 【答案】（1）算法思想：
定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。
（2）节点的数据结构定义如下：
（3）
全局数组标志节点的绝对值是否出现过
如果此绝对值已经在节点值的绝对值中出现过则删除该节点
否则，将flag 中对应的位置置为true ，并将指针指向下一个元素
，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）
为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。
5．
设与记录
对应的关键字分别是
如果存在
成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括为
又因
在
之前且
则
故
即说明
和
进行交换。
和
使得
且
【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极
是反序；设对于
和
之前全部记录
（其
的关键字一定
）中关键字最大为
，故经过起泡排序前i-2次比较后，
必定交换，证毕。
和Rf 为反序，由此可知