2018年辽宁石油化工大学计算机与通信工程学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
2． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 第 2 页，共 35 页 ，则编号 求各顶点的入度 3． 已知一具有n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组 和 中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递 归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。 【答案】算法如下: 由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树 和 为栈，容量足够大 分別是中序序列和后序序列第一和最后元素的下标，初始调用时 ， 初始化 取出栈顶数据 在中序序列中査等于 . 根结点的值 无左子树 将建立左子树的数据入栈 无右子树 的结点 右子树数据入 结束 : 4． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为； 。其中，data 存放结点的值；lc 、rc 为指向左、 右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。 【答案】算法如下: 先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在 第 3 页，共 35 页 设P 指向二叉树的根结点 结束 在中序线索二叉树T 中,, 求给定值为x 的结点的 后继结点 首先在T 树上査找给定值为x 的结点，由p 指向 ' 若P 的右标志为1, 则P 的rc 指针指向其后继 结点P 的右子树中最左边的结点是结点P 的中序后继 结库 5． 当一棵有n( . ) 个结点的二叉树按顺序存储方式存储在 中时，试写一个算法，求 出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。 【答案】算法如下: 二叉树顺序存储在数组 中，本算法求结点i 和j 的最近公共祖先结点的值 下标为i 的结点的双亲结点的下标 下标为j 的结点的双亲结点的下标 所査结点的最近公共祖先的下标是 整型 ，值是 设元素类型为 二、应用题 6． 某程序中有如下循环代码段 P 起始地址为0804 8100H, 对应的汇编代码和机器代码如下表所示 。假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中, 数组A 的首地址在寄存器R3中, 程序段 表 第 4 页，共 35 页