2018年浙江大学光电信息工程学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 2． 设排序二叉树中结点的结构为下述三个域构成: Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。 【答案】算法如下: 非递归删除以r 为根的二叉排序树 栈，容量足够大，栈中元素是二叉排序树结点的指针 沿左分枝向下 出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间 第 2 页，共 35 页 在二叉排序树T 中删除所有小于等于x 的结点 根结点的值小于等于 x 删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止 沿根结点左分支向下，査小干等于x 的结点 q 记P 的双亲 结点的值小于等于 x 再査原P 的右子树中小于等于x 的结点 3． 给定一个整数数组求出b 中最长平台的长度。 【答案】算法如下: //求具有N 个元素的整型数组b 中最长平台的长度。 //局部最长平台 //新平台起点 (“最长平台长度 4． 试编写一算法对二叉树按前序线索化。 【答案】算法如下: 设置前驱 对以线索链表为存储结构的二叉树BT 进行前序线索化 设置左线索 第 3 页，共 35 页 b 中连续的相等元素构成的子序列称为平台。试设计算法， 在b 数组中起始下标为”，1， k) 设置前驱的右线索 为建立右链做准备 前驱后移 左子树前序线索化 右子树前序线索化 结束 ) 区分在遍 5． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。 【答案】算法如下: 在增加双亲指针 和标志域 的二叉树中，不用栈后序遍历二叉树 历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍 向左 向右 访问根结点 找被访问结点的双亲 结束 二、应用题 6． 在一棵表示有序集S 的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S 分为3部分:在该路径左边结点中的元素组成的集合S1; 在该路径上的结点中的元素组成的集合S2; 在该路径右边结点中的元素组成的集合S3; 有 ？为什么？ 【答案】该结论不成立。例如，本题中对于任一f 的左子树上。对于从a 到根结点路径上的所有均有a 第 4 页，共 35 页 。若对于任意的是否总 ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在 b 的右子树上，这时a>b，因此a
相关内容
相关标签