DS复习题 下载本文

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;