2018年北京市培养单位生物物理研究所862计算机学科综合(非专业)之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。
【答案】算法如下:
//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反
//空链表
//奇数序号结点在L1中
//偶数序号
结点逆置插入到L2中
//置L1
表尾
2． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下:
关键字
链指针
用链地址法解决冲突，构造哈希表，哈希函数用
第 2 页，共 34 页
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
图构造的哈希表
查找成功时的平均查找长度
。
中找到关键字从小到大排在第j 位上的记
3． 对给定关键字序号j(1 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 第 3 页，共 34 页 4． 写出按后序序列遍历中序线索树的算法。 【答案】算法如下: 求结点t 最左子孙的左线索 沿左分支向下 求结点t 最右子孙的右线索 沿右分支向下 若t 是 后序遍历中序线索二叉树 bt 沿左分支向下 左孩子为线索，右孩子为链，相当从左返回 P 为叶子, 相当从右返回 访问结点 修改P 指向双亲 是左子女，用最右子孙的右线索找双亲 . 转向当前结点右分支 结束 5． 试编写一算法对二叉树按前序线索化。 【答案】算法如下: 设置前驱 对以线索链表为存储结构的二叉树BT 进行前序线索化 第 4 页，共 34 页 的右孩子，返回1, 否则返回