2018年北京市培养单位遥感与数字地球研究所864程序设计之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。
【答案】算法如下:
//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前
//用类C 语言编写，数组下标从0开始
//交换A[i]与
A[j]
//算法Arrange 结束
2． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
在中序线索树t 上，求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
若后继是头结点，则转到根结点
根结点无双亲
找最右结点的过程中回找到
P
结束FFA
第 2 页，共 36 页
准备到左子树中找
P
3． 当一棵有n() 个结点的二叉树按顺序存储方式存储在中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
4． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下:
关键字
链指针
用链地址法解决冲突，构造哈希表，哈希函数用
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
第 3 页，共 36 页
图构造的哈希表
查找成功时的平均查找长度
5． 给定一个整数数组求出b 中最长平台的长度。
【答案】算法如下:
//求具有N 个元素的整型数组b 中最长平台的长度。
//局部最长平台
//新平台起点
(“最长平台长度
在b 数组中起始下标为
”，1，
k)
。
b 中连续的相等元素构成的子序列称为平台。试设计算法，
二、应用题
6． 设哈希(Hash)表的地址范围为0〜17，哈希函数为:H(K)=KMOD16，K 为关键字，用线性探测再散列法处理冲突，输入关键字序列:(10，24，32，17，31，30，46，47，40，63，49) 造出哈希表，试回答下列问题:
(1)画出哈希表示意图；
(2)若查找关键字63，需要依次与哪些关键字比较？ (3)若查找关键字60，需要依次与哪些关键字比较？
(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】(1)哈希表不意图如表所示:
第 4 页，共 36 页