2018年东华大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下:
利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成
树
数组存放生成树
数组存放顶点是否找到最短路径
初始化, 设顶点信息就是编号
从v0开始，求其最小生成树
是尚未到最小生成树的顶点的集合
循环n －1次
顶点u 已找到最短路径下，下面修改相关顶点的最短路径
算法结束
2． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
3． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
在b 数组中起始下标为
”，1，
k)
b 中连续的相等元素构成的子序列称为平台。试设计算法，
4． 设记录的关键字为。，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
5． 试编写一算法对二叉树按前序线索化。
【答案】算法如下:
设置前驱
对以线索链表为存储结构的二叉树BT 进行前序线索化
设置左线索
设置前驱的右线索
为建立右链做准备
前驱后移
左子树前序线索化
右子树前序线索化
结束
二、应用题
6． KMP 算法(字符串匹配算法) 较Brute(朴素的字符串匹配) 算法有哪些改进？
【答案】朴素的模式匹配(Brute.Force)时间复杂度是
，KMP 算法有一定改进，时间复
相关内容
相关标签