2017年北京科技大学546计算机综合之数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：
2． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图2所示：
图2
3． 如果输入序列为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。
4． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
5． 已知n 阶下三角矩阵A （即当，按照压缩存储的思想，可以将其主对角线以时，有）
下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。
【答案】2
阶下三角矩阵元素
第1列到第列是梯形，元素数为第1列有n 个元素，第j 列有而在第j 列上的位置是为
6． 假定某计算机的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 ，则该主存能提供的最大带宽是多少？
【答案】
个元素，所以n 阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：
个存储周期启动一个体。若
（1）平均每秒CPU 执行的指令数为：
平均每秒Cache 缺失的次数为：
为
：
足CPU 的访存要求。
（2）平均每秒钟“缺页”异常次数为：
故平均每秒磁盘DMA 请求的次数至少为：
请求得不到及时响应，传输数据可能会丢失。 故MIPS 数为20; =300000; 才能满当Cache 缺失时，CPU 访问主存，主存与Cache 之间以块为单位传送数据，此时，主存带宽在不考虑DMA 传输的情况下，主存带宽至少达到 因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA 请求，CPU 和DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为若DMA （3）
（4）4体交叉存储模式能提供的最大带宽为：
7． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。
图1
【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：
图2 图3
8． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）判定树如图所示：