2018年广西民族大学信息科学与工程学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
当前元素是红色
当前元素是白色
当前元素是蓝色
2． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
且
满足下述性质
:
2
当且仅当存在某个顶点
2
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
3． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 4． 试将下列递归过程改写为非递归过程。 【答案】算法如下: 5． 设排序二叉树中结点的结构为下述三个域构成: Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结 ，则编号 求各顶点的入度 点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。 【答案】算法如下: 非递归删除以r 为根的二叉排序树 栈，容量足够大，栈中元素是二叉排序树结点的指针 沿左分枝向下 出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间 在二叉排序树T 中删除所有小于等于x 的结点 根结点的值小于等于 x 删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止 沿根结点左分支向下，査小干等于x 的结点 q 记P 的双亲 结点的值小于等于 x 再査原P 的右子树中小于等于x 的结点 二、应用题 6． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求P 1P 2......P j 为P 1P 2......P j 两头匹配的真子串？且为最大真子串？ 【答案】失败函数(即next) 的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k(即next[j])个字符与第i 个相比，有 为了不因 模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j ﹣k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
相关内容
相关标签