2018年第二军医大学训练部408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 2． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素 在C 中的存放位置下标的公式。 //本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置 第 2 页，共 34 页 ，则编号 求各顶点的入度 和B 的 【答案】算法如下: //算法结束 3． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A) 【答案】算法如下: 以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序 树 在调用时， T=null f 是P 的双亲 申请结点空间 根结点 左子女 右子树根结点的值大于等于根 结点的值 算法结束 4． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。 【答案】算法如下: 求以双亲表示法作为存储结构的树的深度 深度加1, 并取新的双亲 最大深度更新 返回树的深度 ’结束Depth 5． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为 【答案】算法如下: 第 3 页，共 34 页 中，试写出依次取A 中各值构造一棵二叉排序 ，其中，2为排序树中所含结点数，m 为输出的关键字个数。 从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素 二、应用题 6． 假定某计算机的CPU 主频为80MHz , CPI 为4, 并且平均每条指令访存之间交换的块大小为168, Cache 的命中率为 次, 主存与Cache , 存储器总线宽度为32位。请回答下列问题。 (1)该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下, 主存带宽至少达到多少才能满足CPU 的访存要求？ (2)假定在Cache 缺失的情况下访问主存时, 存在式, 磁盘少是多少？ (3)CPU和DMA 控制器同时要求使用存储器总线时, 哪个优先级更高? 为什么？ (4)为了提高性能, 主存采用4体交叉存储模式, 工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns , 则该主存能提供的最大带宽是多少？ 【答案】(1)平均每秒CPU 执行的指令数为:平均每秒Cache 缺失的次数为:为 : 。 在不考虑DMA 传输的情况下, 主存带宽至少达到(2)平均每秒钟“缺页”异常次数为:均每秒磁盘DMA 请求的次数至少为:得不到及时响应, 传输数据可能会丢失。 。 次; 。 才能满足CPU 的访存要求。 , 故MIPS 数为20; 接口的数据缓冲寄存器为32位, 则磁盘 的缺页率, 则CPU 平均每秒产生多少接口平均每秒发出的DMA 请求次数至 次缺页异常? 若页面大小为4KB , 每次缺页都需要访问磁盘, 访问磁盘时DMA 传送采用周期挪用方 当Cache 缺失时, CPU 访问主存, 主存与Cache 之间以块为单位传送数据, 此时, 主存带宽 因为存储器总线宽度为32位, 所以, 每传送32位数据, 磁盘控制器发出一次DMA 请求, 故平(3)CPU和DMA 控制器同时要求使用存储器总线时, DMA 请求优先级更高; 因为若DMA 请求(4)4体交叉存储模式能提供的最大带宽为: 7． 某网络中的路由器运行OSPF 路由协议, 下表是路由器R1维护的主要链路状态信息(LSI), 下图是根据下表及R1的接口名构造出来的网络拓扑。 表 R1所维护的LSI 第 4 页，共 34 页
相关内容
相关标签