2018年北京市培养单位遥感与数字地球研究所862计算机学科综合(非专业)之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中，根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
结束:
2． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素
在C 中的存放位置下标的公式。
//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置
//算法结束
第 2 页，共 40 页
和是两个序列首、尾
和B 的
【答案】算法如下:
3． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
算法结束
4． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 ， ，那么left 域中存放的是该结点的按中 ，那么right 域中存放的是该结点的右儿子结点的地址。 ，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 第 3 页，共 40 页 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 5． 试编写一算法对二叉树按前序线索化。 【答案】算法如下: 设置前驱 对以线索链表为存储结构的二叉树BT 进行前序线索化 设置左线索 设置前驱的右线索 为建立右链做准备 前驱后移 左子树前序线索化 右子树前序线索化 结束 二、应用题 6． 在改进了的(无回溯) 字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。 {在模式P 中求nextval 数组的值 } 第 4 页，共 40 页
相关内容
相关标签