2017年沈阳建筑大学数据结构考研复试核心题库
● 摘要
一、应用题
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）动态存储分配伙伴系统的基本思想
在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
（若）
，
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若）。
第 2 页，共 39 页 空间。起始地址为P ，
大小为的内存块，其伙伴的起始地址为：
（2）和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。
3． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式
给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。
4． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
5． 对于后序线索二叉树，怎样査找任意结点的直接后继? 对于中序线索二叉树，怎样査找任意结点的直接前驱？
【答案】（1）后序线索树中结点的后继的方法如下：根结点无后继：当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩于且双亲无右孩时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树种最左下的叶结点是其后继。
（2）对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则其前驱是其左子树上按中序遍历的最后一个结点。
6． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素
在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？
【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，
时间复杂度为若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置（下标）放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中顺序（或折半）查找该元素，这时时间复杂度为
第 3 页，共 39 页 请
7． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
8． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。
图1
【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：
图2 图3
二、算法设计题
9． 给定next ）, data （已生成）一个带表头结点的单链表，设head 为头指针，结点的结构为（data ，为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。
【答案】算法如下：
第 4 页，共 39 页
相关内容
相关标签