2018年西安电子科技大学网络与信息安全学院951数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。
【答案】算法如下:
从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树
申请结点空间
结点赋值，其线
索初始化
查找结点的插入位置
f 是P 的双亲
根结点
左子女
修改线索
右子树根结点的值大于等于根结点的值
修改线索
读入下个数
第 2 页，共 33 页
，
，那么left 域中存放的是该结点的按中
，那么right
域中存放的是该结点的右儿子结点的地址。
，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。
算法结束
2． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
//字符串结尾标记
//结束算法InvertStore
3． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。
(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。
【答案】(1)算法如下:
按关键字第一个字母在字母表中的顺序输出各关键字
哈希地址
1~26
设哈希表初始值为
null
取关键字第一字母在字母表中的序号
(2)算法如下:
求链地址解决冲突的哈希表査找不成功时平均査找长度
记査找不成功的总的次数
按我们约定，査找不成功指到空指针为止
第 3 页，共 33 页
-
4． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
将建立左子树的数据入栈
无右子树
右子树数据入
结束
:
5． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
的结点
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
第 4 页，共 33 页
相关内容
相关标签