2017年曲阜师范大学信息科学与工程学院858数据结构与操作系统之数据结构考研冲刺密押题
● 摘要
一、算法设计题
1． 已知二叉树T ，试写出复制该二叉树的算法（t →T ）。
【答案】算法如下：
BiTree Copy（BiTree t）//复制二叉树t 的非递归算法
/ /Q是二叉树的结点指针的队列，容量足够大
else
}//结束本题
2． 线性表中元素存放在向量和最小元素。
【答案】算法如下：
3． 设记录
的关键字为
树结点
的败者树，要求除
指向败者记录，
和
为全胜记以外，只用
中，元素是整型数。试写出递归算法求出A 中的最大
录下标。写一算法产生对应上述
辅助空间。 【答案】算法如下：
4． 设键盘输入n 个英语单词，输入格式为n , 试编一程序，建立一个单向链表，实现：
（1）如果单词重复出现，则只在链表上保留一个。
其中n 表示随后输入英语单词个数，
（2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前
个单词。
（1）算法如下：
【答案】定义结点数据类型如下：
（2）算法如下：
5． 有n 个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法（注：双向起泡排序即相邻两趟排序向相反方向起泡。
【答案】算法如下：