东北大学98考研题

一．完成下列各小题（每小题10分，共计30分）。

1）知三个字符分别为s=’ab…abcaabcbca…a’ s’=’caab’, s’’=’bcb’ 利用所学字符串基本运算的函数得到结果串为 s’’’=’caabcbca…aca…a’ 要求写出得到上结果串S“‘所用的函数及执行算法。

2）知记录关键字集合为（53，17，19，61，98，75，79。63，49，46）要求散列到地址区间（100，101，102，103，104，105，106，107，108，109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况） 2）知一棵3阶B-树如下图所示： 1） 画出查入(18)的3阶B-树计算读结点/写结点次数。 2） 画处在插入（18）后的3阶B-树中删除（78）后的3阶B-树并计算读/写次数。

二．知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把

所有值为负数的元素移到全部正数元素前边的算法：（15分） 例：（x, -x, -x, x, x, -x …-x）变为（-x，-x, -x…x x x）

三．已知L为链表的头结地址，表中共有m(m>3)个结点，从表中第i个结点(1m个结点构成一个循环部分链表，设计将这部分循环链表所有结点顺序完全倒置的算法。（15分）

四．设有字母、数字共m个混合传输从甲站到乙站存储，字母、数字的个数不知，且不相等，希望从乙站输出时将字母与数字分开且字母保持原输入顺序，而数字与输入倒序， 要求在任何时刻只要已存元素个数之和小于M便能存储，试设计能满足上述要求的存储结构，并设计完成上述功能的算法，即乙接收甲传输及从乙输出的算法。（20分）

五．一棵高度为K且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t中，试

设计删除树中序号为i且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树（不一定是完全二叉树）的算法。（20分）