2018年北京市培养单位遥感与数字地球研究所866计算机原理之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
【答案】算法如下:
2． 结点类型和存储结构如下:
试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。
【答案】算法如下:
对存储在数组R 中的记录进行排序
初始化
设R[0]作监视哨，Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
3． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)
【答案】算法如下:
以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序
树
在调用时，
T=null
f 是P 的双亲
申请结点空间
根结点
左子女
右子树根结点的值大于等于根
结点的值
算法结束
4． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为
【答案】算法如下:
从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素
，其中，2为排序树中所含结点数，m 为输出的关键字个数。
中，试写出依次取A 中各值构造一棵二叉排序
5． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
二、应用题
6． 设G=(V, E) 以邻接表存储，如图所示，试画出图的深度优先生成树和广度优先生成树。
图
【答案】设从顶点1开始遍历，则深度优先生成树如图1所示，广度优先生成树如图2所示:
图
1
图2
7． 画出对算术表达式表所示。
表 操作数栈和运算符栈的变化过程
F 求值时操作数栈和运算符栈的变化过程。
F 求值，过程如
【答案】设操作数栈是opnd ，运算符栈是optt ，对算术表达式
相关内容
相关标签