发布时间 : 星期日 文章DS复习题更新完毕开始阅读34159958f111f18582d05a1e
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;