2018年北京市培养单位资源与环境学院866计算机原理[专业硕士]之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为:10，12，13，15，18，21，27，35，42。滤掉3个元素。
图
【答案】算法如下:
递增序输出二叉排序树中结点的值，滤去重复元素
中序遍历左子树
是当前访问结点的前驱，调用本算法时初值为
null
记重复元素，调用
本算法时初值为
前驱后移
中序遍历右子树
结束
算法
2． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
【答案】算法如下:
//L是带头结点的按访问频度递减的双向链表
//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中
//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置
//查找值为x 的结点
("不存在所査结点\n”) ；exit(0)；
//令元素值为x 的结点的freq 域加
1
//将P 结点从链表上摘下
//以下査找P 结点的插人位置
//将P 结点插人
//返回值为x 的结点的指针
//算法结束
3． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(
) 改造为(
【答案】算法如下:
//本算法将线性表
//q指向a 1结点
//r记住a l 结点的指
针
//先将a 1结点放到正确位置
//从a 2结点开始
//暂存后继
) 。
改造为
//对称放置
//恢复待处理结点
4． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下:
关键字
链指针
用链地址法解决冲突，构造哈希表，哈希函数用
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
图构造的哈希表