设计并实现一个集合数据结构Set

如果 set 中尚未存在指定的元素o，则添加此元素。

(1)boolean addAll(Set c)

如果 set 中没有指定集合c中的所有元素，则将其添加到此 set 中。 (1)void clear()

移除 set 中的所有元素。

boolean contains(E o)

如果 set 包含指定的元素o，则返回 true。

boolean containsAll(Set c)

如果此 set 包含指定集合c中的所有元素，则返回 true。 boolean isEmpty()

如果 set 不包含元素，则返回 true。 boolean remove(E o)

如果 set 中存在指定的元素o，则将其移除。 boolean removeAll(Set c)

移除 set 中那些包含在指定集合c中的元素。 boolean retainAll(Set c)

仅保留 set 中那些包含在集合c中的元素。 int size()

返回 set 中的元素数（其容量）。

E[] toArray()

返回包含此 set 中所有元素的数组 要求：

1用类或函数实现集合数据结构的存储和运算，实现的类或函数放在一个头文件“Set.h”中，可以被别的函数使用；

2设计另外的函数，利用已实现的“Set.h”中集合的相关功能，实现任意两个集合的并、交、差和补运算。

2 List工具设计

一个列表（List）是一个元素的序列，元素可以重复。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。List支持下列运算： (1)boolean add(E o)

向列表的尾部追加指定的元素。 (2)void add(int index, E element) 在列表的指定位置插入指定元素。 (3)void clear()

从列表中移除所有元素（可选操作）。 (4)boolean contains(E o)

如果列表包含指定的元素，则返回 true。 (5)E get(int index)

返回列表中指定位置的元素。

(6)int indexOf(E o)

返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。

(7)boolean isEmpty()

如果列表不包含元素，则返回 true。

(8)int lastIndexOf(E o)

返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回 -1。 (9)E remove(int index)

移除列表中指定位置的元素。 (10)boolean remove(E o)

移除列表中出现的首个指定元素。

(11)boolean removeAll(List c)

从列表中移除指定List c中包含的所有元素（可选操作）。 (12)E set(int index, E element)

用指定元素替换列表中指定位置的元素。

(13)int size()

返回列表中的元素数。 要求：

1用类或函数实现List数据结构的存储和运算，实现的类或函数放在一个头文件“List.h”中，可以被别的函数使用；

2设计另外的函数，利用已实现的“List.h”中的相关功能，实现任意两个列表的合并运算。 3 LinkedList工具设计

LinkedList是List的链式实现，其具体的功能和实现要求同List。 4 Stack和Queue工具设计

Stack 是后进先出（LIFO）的堆栈。它支持以下运算： boolean empty() 测试堆栈是否为空。 1E peek()

查看栈顶元素而不移除它。

2E pop()

移除栈顶元素并作为此函数的值返回该元素。

3E push(E item) 把项压入栈顶。

Queue 是先进先出（FIFO）的队列。它支持以下运算： 1boolean empty() 测试队列是否为空。 2E peek()

查看队头元素而不移除它。

3E DeQueue()

移除队头元素并作为此函数的值返回该元素。

4E DeQueue(E item) 把元素插入队尾。 要求：

1用类或函数实现Stack和Queue数据结构的存储和运算，实现的类或函数分别放在头文件“Stack.h”和“Queue.h”中，可以被别的函数使用；

2设计一个函数，利用已经实现的“Stack.h” 中Stack的相关功能，实现一个任意序列的逆置操作；设计另外的一个函数，利用已经实现的“Queue.h” 中Queue.的相关功能，实现任意两个队列的合并运算。

5 HashTable工具设计

实现一个哈希表HashTable将键映射到相应的值。它支持以下运算： void clear()

将此哈希表清空，使其不包含任何键。 E get(Object key)

返回此哈希表中指定键所映射到的值。 boolean isEmpty() 测试此哈希表是否为空。

K[] keys()

返回此哈希表中的所有的键的集合。

E put(K key, V value)

将指定 key 映射到此哈希表中的指定 value。 E remove(Object key)

从哈希表中移除该键及其相应的值。 int size()

返回此哈希表中的键的数量。

String toString()

返回此 Hashtable 元素的字符串表示形式，其形式为 ASCII 字符 “, ” （逗号加空格）分隔开的、括在括号中的一组条目。

E[] values()

返回此 Hashtable 中所包含值的 集合。 要求：

1用类或函数实现HashTable数据结构的存储和运算，实现的类或函数放在头文件“HashTable.h”中，可以被别的函数使用；

2设计一个函数，利用已经实现的“HashTable.h” 中的相关功能，实现一个集体中人名的哈希表。

6 Tree工具设计

实现一个二叉树BinaryTree,它支持以下运算： BiTree InitBiTree() 构造空二叉树。 Void DestroyBiTree () 销毁二叉树。

BiTree CreateBiTree () 创建一棵非空二叉树。 Boolean IsEmpty() 判断二叉树是否为空。 BiTree Root()

返回此二叉树的根节点。 E Value(BiTree p)

返回此二叉树中节点p的值。 Void Assign(BiTree p, E e) 将此二叉树中节点p的值赋为e。 BiTree Parent(BiTree p)

返回此二叉树中节点p的双亲。 BiTree LeftChild(BiTree p)

返回此二叉树中节点p的左孩子。

BiTree RightChild(BiTree p) 返回此二叉树中节点p的右孩子。

Void InsertLChild(BiTree p, BiTree c) （可选操作）

向此二叉树插入一棵子树c（c的右子树为空）作为p的左孩子，p原来的左子树变为c的右子树。

Void InsertRChild(BiTree p, BiTree c) （可选操作）

向此二叉树插入一棵子树c（c的右子树为空）作为p的右孩子，p原来的右子树变为c的右子树。

Void DeleteLChild(BiTree p) （可选操作） 删除此二叉树中p节点的左子树。

Void DeleteRChild(BiTree p) （可选操作） 删除此二叉树中p节点的左子树。 int Depth()

返回此二叉树的深度。 String PreOrderTraverse() 返回二叉树的先序遍历序列。 String InOrderTraverse() 返回二叉树的中序遍历序列。 String PostOrderTraverse() 返回二叉树的后序遍历序列。

String LevelOrderTraverse() 返回二叉树的层次遍历序列。 要求：

1用类或函数实现BinaryTree数据结构的存储和运算，实现的类或函数放在头文件“BinaryTree.h”中，可以被别的函数使用；

2设计一个函数，利用已经实现的“BinaryTree.h”中的相关功能，输出一棵二叉树的所有叶子节点。

7 BinarySortTree工具设计

实现一个二叉排序树BinarySortTree,它支持以下运算： BiTree InitBSTree() 构造空二叉排序树。 Void DestroyBSTree () 销毁二叉排序树。

BiTree SearchBSTree (key)

查找二叉排序树中关键字等于key的元素，若找到，返回该元素在树中的位置，否则返回空。

Void InsertBSTree(E e)

若此二叉排序树中不存在关键字等于e.key的元素，则插入e。 Void DeleteBSTree(E e)

若此二叉排序树中存在关键字等于e.key的元素，则删除之。

String TraverseBSTree() 返回此二叉树的中序遍历序列。 要求：

1用类或函数实现BinarySortTree数据结构的存储和运算，实现的类或函数放在头文件“BinarySortTree.h”中，可以被别的函数使用； 2利用已经实现的“BinaryTree.h”中的相关功能，对一个已知的学生成绩表文件按照学号为关键字生成对应的二叉排序树索引文件，并利用该文件实现相应的查找操作。 8 BTree工具设计

实现一个B-树BTree,它支持以下运算： BTree InitBTree() 构造空B-树。

Void DestroyBTree () 销毁B-树。

BTree SearchBTree(key)

查找B-树中关键字等于key的元素，若找到，返回该元素在树中的位置，否则返回空。 Void InsertBTree(E e)

若此B-树中不存在关键字等于e.key的元素，则插入e。 Void DeleteBTree(E e)

若此B-树中存在关键字等于e.key的元素，则删除之。

String TraverseBTree()

返回此B-树的中序遍历序列。 要求：

1用类或函数实现BTree数据结构的存储和运算，实现的类或函数放在头文件“BTree.h”中，可以被别的函数使用；

2利用已经实现的“BTree.h”中的相关功能，对一个已知的学生成绩表文件按照学号为关键字生成对应的B-树索引文件，并利用该文件实现相应的查找操作。

9 简明汉语词典

编制一个简单的词典系统，该系统要求实现词典的建立、词条的追加、维护、查询功能。 要求：

（1） 词典用一个的文件存放，词条信息包括：词名、读音、词性、词义等；

（2） 词典建立索引，该索引用分块索引或建树实现，索引也作为的文件放在外存； （3） 系统要求有简单的界面实现在词条追加、更改和查询时的人机交互。 10 基于顺序索引的通讯录

编写一个简单的通讯录管理, 要求实现查询、排序、修改等功能。 要求 ① 通讯录用一个的文件存放； ② 建立索引，索引也作为的文件放在外存；

③ 录入或修改：录入或修改通讯信息 ④ 查询/统计: 按关键字查询或统计。

11 基于顺序索引的员工管理

每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。实现对员工信息的查询、更新、插入、删除等功能。 要求

（1） 录入：录入员工的信息，并存放于文件中 （2）建立索引，索引也作为的文件放在外存； （3） 查询：按特定条件查找员工。

（4） 更新：按编号对某个员工的某项信息进行修改。 （5） 插入：加入新员工的信息。

（6） 删除：按编号删除已离职的员工的信息。

12 基于二叉排序树的文件索引

建立一个学生档案文件，利用二叉排序树建立文件的索引，并实现如下操作： 要求

（1） 录入：录入学生的档案信息，并存放于文件中

（2） 建立索引：用二叉排序树建立索引，索引也作为的文件放在外存； （3） 查询：按特定条件查找学生。

（4） 更新：按编号对某个学生的某项信息进行修改。 （5） 插入：加入新学生的信息。 （6） 删除：按编号删除学生的信息。

13 一元稀疏多项式计算器

p(. 设计一个一元稀疏多项式简单计算器。 要求

一元稀疏多项式计算器的基本功能是： （1）输入并建立多项式

（2）输出多项式，多项式的输出形式为类数学表达式。例如，x15+(-8)x7-14的输出形式为x＾15-8x＾7-14。序列按指数降序排列； （3）多项式ａ和ｂ相加，建立多项式ａ＋ｂ （4）多项式ａ和ｂ相减，建立多项式ａ－ｂ （5）计算多项式在ｘ处的值。

14 文章编辑器

实现一个简单的文章编辑器，使其能够录入、统计、插入、删除、查找/替换等功能。 要求

（1）能够录入或载入一页文字，设每页文字共N行，每行最多不超过80个字符； （2）能够对录入或修改后的文字存盘；

（3）实现简单的统计功能：统计出其中英文字母数和空格数及整篇文章总字数； （4）插入某一字符串：并将后面的字符后移； （5）删除某一字符串：并将后面的字符后移；

（6）查找/替换：查找某一子串在文章中的位置，并能替换为其它内容。

15 停车场管理

p(. 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 要求

1 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。 16 赫夫曼编/译码器

p(. 利用赫夫曼编码进行通信可大大提高信道利用率，缩短信息传输时间。试编写一个赫夫曼编/译码系统。 要求

（1）I:初始化(Initialization)。从终端读入字符集大小ｎ，以及ｎ个字符和ｎ个权值，建立赫夫曼树。

（2） E: 编码(Encoding)。利用已建好的赫夫曼树对文件ToBeTran中的正文进行编码，然后将结果存入CodeFile文件中。

（3） D: 译码(Decoding)。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入TextFile中。

（4） P: 打印(Print)。打印CodeFile和TextFile中的内容。

17 校园导游

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。 要求

（1） 查询各景点的相关信息；

（2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间的所有路径。 （4） 增加、删除、更新有关景点和道路的信息。

18 算术表达式求值

p(. 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。

19 算术表达式形式转换

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。

假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程实现将一个中缀表达式转换为相应的前缀或后缀表达式形式。

20 迷宫求解 以一个mn的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

21 n皇后问题

在nXn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。设计一个程序，求出n后问题中的所有解。

22 Hanoi塔递归过程演示

演示Hanoi塔的递归执行过程，要求：

1对Hanoi塔递归过程中的栈的变化情况以及塔的变化情况都进行演示；

2可以编程实现，或采用powerpoint的内置动画功能以及其它动画工具进行演示。 23 查找算法演示

对下面的查找算法，演示它们的执行过程： 1）带监视哨的顺序查找 2）折半查找 3）分块查找 要求：

1对这些查找方法中的查找的每一步进行演示；

2可以编程实现，或采用powerpoint的内置动画功能以及其它动画工具进行演示。 24 排序算法演示

从下面排序方法中选择3种排序算法，演示它们的执行过程： 1）直接插入排序 2）2-路插入排序 3）shell排序 4）起泡排序 5）快速排序 6）简单选择排序 7）堆排序 8）归并排序 9）基数排序 要求：

1对这些排序方法中的排序的每一趟进行演示；

2可以编程实现，或采用powerpoint的内置动画功能以及其它动画工具进行演示。 25 内部排序算法比较

p(. 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时

间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。要求

（1） 对以下7种常用的内部排序算法进行比较：直接插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序。

（2） 待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）,稳定性等。

26 基于堆的最大元输出

已知一组随机产生的数值序列，其元素个数不断增加。用堆实现： 1输出初始的数值序列中的最大元；

2在元素增加后，重新筛选，输出最大元。