哈希表设计[问题描述]针对某个集体中人名设计一个哈希表,使得平均查找长度不超过R,并完成相应的建表和查表程序。[基本要求]假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。[测试数据]取读者周围较熟悉的30个人名。[选作内容](1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合作实验)。(2) 研究这30个人名的特点,努力找一个哈希函数,使得对于不同的拼音名一定不发生地址冲突。(3) 在哈希函数确定的前提下尝试各种不同处理冲突的方法,考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
查看答案
内部排序算法比较[问题描述]各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。[基本要求](1) 对以下10种常用的内部排序算法进行比较:直接插入排序;折半折入排序;二路插入排序;希尔排序;起泡排序;快速排序;简单选择排序;堆排序;归并排序;基数排序。(2) 待排序表的表长不少于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字移动次数(关键字交换计为3次移动)。[测试数据]由随机产生器决定。[实现提示]主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。[选作内容]对不同的输入表长做试验,观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。
统计成绩[问题描述]给出n个学生的m门考试的成绩表,每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计,并打印统计表。[基本要求](1) 按总数高低次序,打印出名次表,分数相同的为同一名次;(2) 按名次打印出每个学生的学号、姓名、总分以及各科成绩。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。[选作内容]对各科成绩设置不同的权值。
算术表达式与二叉树【问题描述】一个表达式和一棵二叉树之间,存在着自然的对应关系。写一个程序,实现基于二叉树表示的算术表达式的操作。【实现提示】假设算术表达式Expression内可以含有变量(a~z)、常量(0~9)和二元运算符(+,-,*,/,^(乘幂))。实现以下操作:【测试数据】
银行业务模拟与离散事件模拟【问题描述】假设某银行有4个窗口对外接待客户,从早晨银行开门(开门9:00am,关门5:00pm)起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需要在每个窗口前顺次排队,对于刚进入银行的客户(建议:客户进入时间使用随机函数产生),如果某个窗口的业务员正空闲,则可上前办理业务;反之,若4个窗口均有窗户所占,他便会排在人数最少的队伍后面。【实现提示】【测试数据】由随机数产生器生成