2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列，容量足够大
结束本题
2． 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值；left :给出本结点的左儿子结点的地址；right :给出本结点的右儿子结点的地址。设data 域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序，实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈，容量足够大，栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈，沿栈顶结点的右子树向下刪除，释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ，删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下，査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
3． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
4． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
满足下述性质
:
当且仅当存在某个顶点
且
22
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
5． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下:
在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回
确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情
况
返回第一邻接点，
和
中必有一个等于
i
取第一个边结点
二、应用题
6． 用单链表保存m 个整数, 节点的结构为(data, link) , 且余绝对值相等的节点。
例如若给定的单链表head 如下表
表
删除节点后的head 为
表
要求
(1)给出算法的基本思想 (2)使用c 或
语言, 给出单链表节点的数据类型定义。
(3)根据设计思想, 采用c 或C++语言描述算法, 关键之处给出注释。 (4)说明所涉及算法的时间复杂度和空间复杂度。 【答案】(1)算法思想:
(n为正整数) 。现要求设计一个
时间复杂度尽可能高效地算法, 对于链表中绝对值相等的节点, 仅保留第一次出现的节点而删除其