2018年北京市培养单位数学与系统科学研究院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
2． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:
{二叉树根结点的指针}
【答案】算法如下:
生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写
)
是二叉树结点指针的一维数组，容量足够大
一维数组最后元素的下标
第 2 页，共 31 页
求左子树表示的子表达式的值
求右子树表示的子表达式的值
元素或虚结点
根结点
双亲结点和子女结点用指针链上
结束
3． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
申请结点
弧结点中权值域
算法结束
4． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
若t 是
第 3 页，共 31 页
的右孩子，返回1, 否则返回
后序遍历中序线索二叉树
bt
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
转向当前结点右分支
结束
5． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。
【答案】算法如下:
//la是结点的元素为整数的单链表。本算法判断从第二结点开始
//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回
false
//P是工作指针，初始指向链表的第二项
//pre是p 所指结点的前驱指针
//i是la 链表中结点的序号，初始值为
2
//结点值间的关
系符合题目要求
//当前结点的值不等于其序号的平方减去前驱的值
//未查到表尾就结束了
//成功返回
//算法结束
//假设无头结点，初始P 指向第一元素结点
第 4 页，共 31 页
相关内容
相关标签