2018年北京语言大学软件工程825数据结构与程序设计[专业硕士]之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 2． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。 【答案】算法如下: 将满二叉树的后序序列转为前序序列， 标。 根结点 左子树或右子树的结点数 将左子树前序序列转 为后序序列 将右子树前序序列转为 后序序列 第 2 页，共 38 页 是序列初始和最后结点的下 3． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。 【答案】算法如下: 求以双亲表示法作为存储结构的树的深度 深度加1, 并取新的双亲 最大深度更新 返回树的深度 ’结束Depth 4． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。 【答案】算法如下: 在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置 否则返回-1表示失败 元素序号 结束 ，查找失败的平均查找 期望值分析:在等概率情况下，则查找成功的平均查找长度为等，则查找成功时和关键字比较的个数的期望值约为。 5． 元素集合已存入整型数组中，试写出依次取A 中各值树T 的非递归算法:CSBT(r，A) 【答案】算法如下: 以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序 树 在调用时，T=null 第 3 页，共 38 页 长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相 构造一棵二叉排序 f 是P 的双亲 申请结点空间 根结点 左子女 右子树根结点的值大于等于根 结点的值 算法结束 二、应用题 6． 主机H 通过快速以太网连接Internet , IP 地址为 表 a , 服务器S 的IP 地址为 。 H 与S 使用TCP 通信时, 在H 上捕获的其中5个IP 分组如表a 所示。 请回答下列问题。 (1)表a 中的IP 分组中, 哪几个是由H 发送的? 哪几个完成了TCP 连接建立过程? 哪几个在通过快速以太网传输时进行了填充？ (2)根据表b 中的IP 分组, 分析S 已经收到的应用层数据字节数是多少？ (3)若表a 中的某个IP 分组在S 发出时的前40字节如表b 所列, 则该IP 分组到达H 时经过了多少个路由器？ 表 b 注:IP 分组头和TCP 段头结构分别如图a 、图b 所示: 第 4 页，共 38 页
相关内容
相关标签