2018年中国刑事警察学院声像资料检验技术系408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
2． 对给定关键字序号j(1 。现要求将K n 放在将元素排序后 的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 设排序二叉树中结点的结构为下述三个域构成: Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。 【答案】算法如下: 非递归删除以r 为根的二叉排序树 栈，容量足够大，栈中元素是二叉排序树结点的指针 沿左分枝向下 出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间 在二叉排序树T 中删除所有小于等于x 的结点 根结点的值小于等于 x 删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止 沿根结点左分支向下，査小干等于x 的结点 q 记P 的双亲 结点的值小于等于 x 再査原P 的右子树中小于等于x 的结点 4． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。 【答案】算法如下: 利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成 树 数组存放生成树 数组存放顶点是否找到最短路径 初始化, 设顶点信息就是编号 从v0开始，求其最小生成树 是尚未到最小生成树的顶点的集合 循环n －1次 顶点u 已找到最短路径下，下面修改相关顶点的最短路径 算法结束 5． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为； 。其中，data 存放结点的值；lc 、rc 为指向左、 右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。 【答案】算法如下: 先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在 设P 指向二叉树的根结点 结束 在中序线索二叉树T 中,, 求给定值为x 的结点的 后继结点 首先在T 树上査找给定值为x 的结点，由p 指向 ' 若P 的右标志为1, 则P 的rc 指针指向其后继 结点P 的右子树中最左边的结点是结点P 的中序后继 结库 . 二、应用题
相关内容
相关标签