1、二叉排序树 [问题描述]
从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。 [基本要求]
建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度。 [测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。 [选作内容]
实现二叉排序树的插入、删除操作。
2、哈希表设计 [问题描述]
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 [基本要求]
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 [测试数据]
取读者周围较熟悉的30个人名。 [选作内容] （1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。
（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
3、内部排序算法比较 [问题描述]
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 [基本要求]
（1） 对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。
（2） 待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。 [测试数据]
由随机产生器决定。 [实现提示]
主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。
[选作内容]
对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。
3、统计成绩 [问题描述]
给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。 [基本要求]
（1） 按总数高低次序，打印出名次表，分数相同的为同一名次； （2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。 [测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。 [选作内容]
对各科成绩设置不同的权值。
附录2
实验报告示例
__________级 __________班 _______年_______月_____日 姓名____________ 学号____________ 电话_____________
1．实验题目
编制一个演示单链表插入、删除、查找等操作的程序 2．需求分析
本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数
② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 ③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 ④ 测试数据：
A． 插入操作中依次输入11，12，13，14，15，16，生成一个单链表 B． 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置 C． 删除操作中依次输入2，5，删除位于2和5的元素 3．概要设计
1）为了实现上述程序功能，需要定义单链表的抽象数据类型： ADT LinkList {
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,?,n,n≥0} 数据关系：R={|ai,ai+1 ∈D} 基本操作：
InitLinkList(&L)
操作结果：构造一个空的单链表L. InsLinkList(&L,pos,e) 初始条件：单链表L已存在
操作结果：将元素e插入到单链表L的pos位置 DelLinkList(&L,pos,&e) 初始条件：单链表L已存在
操作结果：将单链表L中pos位置的元素删除， 元素值置入e中返回 LocLinkList(L,e)
初始条件：单链表L依存在
操作结果：单链表L中查找是否元素e，
若存在，返回元素在表中的位置；若不存在，返回-1. Menu()
操作结果：在屏幕上显示操作菜单 2）本程序包含7个函数： ① 主函数main()
② 初始化单链表函数InitLinkList()
③ 显示操作菜单函数menu()
④ 显示单链表内容函数dispLinkList() ⑤ 插入元素函数InsLinkList() ⑥ 删除元素函数DelLinkList() ⑦ 查找元素函数LocLinkList() 各函数间关系如下：
4．详细设计
实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。 1) 结点类型和指针类型 typedef struct node { int data;
struct node *next; }Node,*LinkListl; 2) 单链表的基本操作
为了方便，在单链表中设头结点，其data域没有意义。 bool InitLinkList(LinkList &L) （伪码算法）
void DispLinkList(LinkList L) （伪码算法） void menu() （伪码算法）
bool InsLinkList(LinkList &L,int pos,int e) （伪码算法）
bool DelLinkList(LinkList &L,int pos,int &e) （伪码算法）
int LocLinkList(LinkList L,int e) （伪码算法）
3) 其他模块伪码算法 5．调试分析 (略)
6．使用说明
程序名为LinkList.exe，运行环境为DOS。程序执行后显示 ======================== 0----EXIT 1----INSERT 2----DELETE 3----LOCATE
======================= SELECT:
在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。
选择0：退出程序
选择1：显示“INSERT pos,e =” ，
要求输入要插入的位置和元素的值（都是整数）。 选择2：显示“DELETE pos =” ，
要求输入要删除元素的位置，执行成功后返回元素的值。 选择3：显示“LOCATE e = ” ，
要求输入要查找元素的值，执行成功后返回元素在表中的位置 7．测试结果
1） 建立单链表：
? 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到单链表（15，14，13，12，11） 2） 插入：
? 选择1输入（1，100），得到单链表（15，100，14，13，12，11） ? 选择1输入（-1，2），显示输入错误 ? 选择1输入（7，2），显示输入错误 ? 选择1输入（6，2），得到单链表（15，100，14，13，12，11，2） 3） 删除：
? 选择2，输入1。返回e=100，得到单链表（15，14，13，12，11，2） ? 选择2，输入0。返回e=15，得到单链表（14，13，12，11，2） ? 选择2，输入4。返回e=2，得到单链表（14，13，12，11） ? 选择2，输入5。返回输入错误 4） 查找
? 选择3，输入14。返回pos=0 ? 选择3，输入100。返回输入错误