对于长度为n的线性表,在最坏情况下,下列各种排序法所对应的比较次数中,正确的是( )。
A.冒泡排序为n/2
B.冒泡排序为n
C.快速排序为n
D.快速排序为n(n-1)/2
参考答案:D
解析: 在最坏情况下,冒泡排序和快速排序的比较次数都是n(n-1)/2。
[知识拓展] 所谓冒泡排序,就是将相邻的两个数据比较,如前面的数据大于后面的,则位置互换。这样不停地比较、互换,其实就是把大的数往后排,小的数往前排(就像冒泡一样冒出来了)。
对于长度为n的线性表,在最坏情况下,下列各种排序法所对应的比较次数中,正确的是( )。
A.冒泡排序为n/2
B.冒泡排序为n
C.快速排序为n
D.快速排序为n(n-1)/2
参考答案:D
解析: 在最坏情况下,冒泡排序和快速排序的比较次数都是n(n-1)/2。
[知识拓展] 所谓冒泡排序,就是将相邻的两个数据比较,如前面的数据大于后面的,则位置互换。这样不停地比较、互换,其实就是把大的数往后排,小的数往前排(就像冒泡一样冒出来了)。
阅读以下某前台销售子系统的技术说明和UML图,根据要求回答问题1~问题4。
[说明]
某超市管理系统的前台销售子系统以最基本的方式处理销售业务。系统的功能需求如下:
①记录每种商品的编号、单价和现有数量;
②为顾客选购的商品计价、收费,并打印清单;
③帮助商家找出哪种商品将脱销,从而及时补充货源;
④随时按上级系统的要求报告当前的款货数量、增减商品的种类或修改商品定价;
⑤交接班时结算货款数目和商品数目。
每台收款机可以处理任何数目的销售事件,但一个销售事件只能由一台收款机处理。每个销售事件从收款机响应收款人员的指令开始,先向商品发送检索请求消息来查找将被出售的商品。如果该商品的数量少于下限,则向供货员发送缺货登记消息。每名供货员可以提供一种或多种商品,同一品牌的商品只能由一位供货员来提供。接着收款机发送计价和入账消息请求售出操作,再由销售事件发送记账消息给相应的账册,并控制流程返回收款机等待下一次销售操作。每本销售账册可以记录任何数目的销售事件,但一个销售事件只能由一本销售账册记录。
该销售子系统采用面向对象方法开发,系统中的类及类之间的关系用UML类图表示,图1-11是该系统类图中的一部分;系统的动态行为采用UML序列图表示,图1-12是销售事件部分的序列图。
[问题3] 识别关联的多重度是面向对象建模过程中的一个重要步骤。请根据说明中给出的描述,将图1-11中 (1)~(8)空缺处的内容填写完整。 |