2018年北京大学地球与空间科学学院907计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
2． 设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中(注:按层从上到下，由左到右) 。
【答案】算法如下:
是结点在一维数组中的编
号
队列，容量足够大
本算法将二叉树的二叉链表存储结构转换为顺序存储结构
seq
初始化，#代表虚结点
根结点入队
存入顺
序存储结构
左
子女入队
右
子女人队
3． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，
当
时，将
入栈；当
时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给
出相应的信息。
【答案】算法如下
:
栈空间容量
//s是元素为整数的栈，本算法进行入栈和出栈操作
//top为栈顶指针，定义top ＝0时为栈空
//n个整数序列进行处理
//从键盘读入整数序列
//读入的整数不等于﹣1时人栈
//读入的整数等于﹣1时出栈
//算法结束。
中，试写出依次取A 中各值
构造一棵二叉排序
4． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)
【答案】算法如下:
以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序
树
在调用时，
T=null
f 是P 的双亲
申请结点空间
根结点
左子女
右子树根结点的值大于等于根
结点的值
算法结束
5． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
若t 是
后序遍历中序线索二叉树
bt
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
转向当前结点右分支
结束
的右孩子，返回1, 否则返回
二、应用题
6． 某网络中的路由器运行OSPF 路由协议, 下表是路由器R1维护的主要链路状态信息(LSI), 下图是根据下表及R1的接口名构造出来的网络拓扑。
表 R1所维护的LSI