2018年北京市培养单位信息工程研究所408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 给定nxm 矩阵
并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
2． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
在中序线索树t 上，求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
若后继是头结点，则转到根结点
根结点无双亲
找最右结点的过程中回找到P
第 2 页，共 32 页
元素\n"，x) ；
准备到左子树中找
P
结束FFA
3． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
【答案】算法如下:
4． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
申请结点
弧结点中权值域
算法结束
第 3 页，共 32 页
5． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。
【答案】定义队列:
//循环队列占m 个存储单元
//rear指向队尾元素，length 为元素个数
(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:
//cq为循环队列，本算法进行队列初始化
//算法结束 (3)队列的插入:
//cq是已如上定义的循环队列，本算法将元素x 入队
//队满
.
//计算插入元素位置
//将元素x 入队列
//修改队列长度
//算法结束
//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素
//队空
；//出队元素位置
//修改队列长度
//返回队头元素
//算法结束
(4)队列的删除:
时队列空，当
时队列满。
二、应用题
6． 已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M), 下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里)
第 4 页，共 32 页
相关内容
相关标签