while (low

low++;

if ( low

r［low］=x； /*将基准记录保存到low=high的位置*/ return low; /*返回基准记录的位置*/ } /* QKPass */

5．(1) 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表

仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

(2) 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、

C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。 (3) 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、

空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据

元素。

6．设计判断两个二叉树是否相同的算法。 7．已知带有表头结点的单链表，结点结构为:

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求： （1）描述算法的基本设计思想。

（2）根据设计思想，采用C程序设计语言描述算法，关键之处请给出简要注

释。 8．利用二叉树递归遍历算法，编写统计二叉树中叶子结点数目的算法。二叉树采用二叉链表存储的类型定义如下： typedef char datatype; typedef struct Node { datatype data;

struct Node *lchild,*rchild;

}BiTree;

9．设二叉排序树按照二叉链表存储，编写算法InsertBST(BSTree *&bst, KeyType

k)在二叉排序树中插入一个结点。二叉排序树的链式存储结构的类型定义如下：typedef int KeyType;

typedef struct Node

{ KeyType key;

struct Node *lchild,*rchild;

}BSTree;