2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研仿真模拟五套题
● 摘要
一、综合题
1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】(1)最高位优先(MSD)法
先对最高位关键字K 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的
K 0值，然后，分别就每个子序列对关键字K 1进行排序，按K 1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。
(2)最低位优先(LSD)法 先对最低位关键字
进行排序，然后对高一级关键字进行排序，依次重复，直至对最高
位关键字K 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，
但对
排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序
时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。 2． 设将n(n>l)个整数存放到一维数组R 中. 试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P(0 中的数据由 . 要求: (1)给出算法的基本设计思想. (2)根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 【答案】(1)算法的基本设计思想:先将n 个数据由得到最终得到结果 (2)用C 语言算法描述如下: 第 2 页，共 35 页 变换为 原地逆置， 然后 ， 再将数组R 中的前，ti-P 个数和后P 个数分别原地逆置， (3)说明算法的复杂性:上述算法中3个Reverse 函数的的时间复杂度分别为O(p/2)、O((p-2)/2)为0(n/2)，故算法的时间复杂度为O(n)，算法的空间复杂度为0(1). 3． 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和, 给定一棵二叉树T , 采用二叉链表存储, 节点结构为: 其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针, 设计求T 的WPL 的算法。要求: (1)给出算法的基本设计思想; (2)使用C 或 语言, 给出二叉树结点的数据类型定义; 语言描述算法, 关键之处给出注释。 (3)根据设计思想, 采用C 或 【答案】(1)算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度, 如果当前节点不是叶子节点, 那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和, 对于此函数要传入一个当前节点的树高的形参, 那么递归调用孩子节点时只需要将这个形参加一即可。 (2)typedef struct BiNode (3)具体算法实现如下: 第 3 页，共 35 页 如果当前节点为空节点 如果当前节点的左右孩子节点都为空, 即当前节点为叶子节点, 直接返回当前节点的 WPL 如果当前节点不是叶子节点, 则对当前节点的左右子树进行递归, 返回左右子树WPL 之 和 4． KMP 算法(字符串匹配算法) 较Brute(朴素的字符串匹配) 算法有哪些改进？ 【答案】朴素的模式匹配(Brute.Force)时间复杂度是 ，KMP 算法有一定改进，时间复 杂度达到O(m＋n) 。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。 5． 某计算机的CPU 主频为500MHz ，CPI 为5(即执行每条指令平均需要5个时钟周期) 。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。 (1)在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？ (2)当该外设的数据传输率达到5MB/S时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B ，且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CPU 时间的百分比是多少？(假设DMA 与CPU 之间没有访存冲突) 【答案】(1)已知主频为500MHz , 则时钟周期＝1÷500MHz ＝2ns , 因为CPI ＝5, 所以每条指令平均5×2＝10ns 。又已知每中断一次传送32位(4个字节) ，数据传输率为 CPU 用于 该外设I/0共需20条指令(中断服务程序包括18条指令＋其他开销折合2条指令) ，花费时间＝20×l0＝200ns 。 CPU 用于该外设I/O的时间占整个CPU 时间的百分比预处理和后处理的总开销时间 (2)改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间＝5000B ÷5MB/s＝lms 。 CPU 用于该外设I/O时间占整个CPU 时间的百分比 ＝预处理和后处理的总开销时间+传送数据的时间 所以传送时间 第 4 页，共 35 页
相关内容
相关标签