浙江理工大学
2017年硕士研究生招生考试初试试题
考试科目：数据结构与数据库技术代码：938
（请考生在答题纸上答题，在此试题纸上答题无效）
第一部分：数据结构（本部分共90分）
一、程序设计题
1．已知单链表lnode结构如下，其头结点为head，data为结点的值域。

假设单链表中已存在若干个结点，试编写程序算法，输入一个整数，在单链表中找到首个值比它大的结点，在该结点之前插入这个整数。

如果找不到值比它大的结点，则将该整数插入到链表的尾部。

（本题20分）
struct lnode {
int data;
struct lnode *next;
}
2．已知二叉树的根结点为t，其二叉链表结构如下：
struct node {
int data;
struct node *lch, *rch;
}
这里，data为结点的值域，lch为结点的左孩子，rch为结点的右孩子。

试编写一个非递归的程序算法，将树中每个结点的左孩子值与右孩子进行交换，使得左孩子值总是不大于右孩子值。

（本题25分）
3.试编写一个程序算法，在一个根结点为t的二叉排序树中查找某个关键字k，计算查找这个关键字所需要的次数，并分析算法的时间复杂度（最大查找长度和平均查找长度）。

（本题25分）
4. 对于一组关键字r[n]，有一种排序算法的思想如下：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中；第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…，依次下去，直到待排序列为递增序列为止。

试编写程序实现上述算法。

（本题20分）
第 1 页，共4 页。