早教吧 育儿知识 作业答案 考试题库 百科 知识分享

1.期中考试结束了,班长给学生按学分排队,一个小组原有六人,由于某小组组长的疏忽,把一个同学的学分遗漏了,现要把该学分插进去应怎么办?设排好的学分为有序列{1,3,6,

题目详情

1.期中考试结束了,班长给学生按学分排队,一个小组原有六人,由于某小组组长的疏忽,把一个同学的学分遗漏了,现要把该学分插进去应怎么办?

设排好的学分为有序列{1,3,6,7,9},该同学的学分为5分.同学们可以想象一下,假如学分顺序已经排好,恰好剩你一个人,怎么办?

2.若将上述例题中学生的学分顺序打乱,然后按从小到大的顺序排序,该如何做?不妨设乱序为{7,3,6,9,1}.

▼优质解答
答案和解析

  1.解法一:将5从右向左逐个与有序列中的数据进行比较,确定5在序列中的位置,并将其插入构成一个新的有序列,这个过程可以用下列步骤描述:

  (1)比较5与9,5<9;

  (2)比较5与7,5<7;

  (3)比较5与6,5<6;

  (4)比较5与3,5>3;

  (5)将5插到3与6之间得到新的有序列:{1,3,5,6,7,9}.

  解法二:要将5插入有序列{1,3,6,7,9},构成一个新的有序列.

  首先选择有序列的“中间位置”的数据a3=6,将5与a3比较,显然5<a3,所以5应排在a3的左边.如果还没有确定位置应再取余下数据列的“中间位置”的数据比较查找.

  感悟:(1)有序直接插入法中的“比较法”:将数据A与原有序列中的数据从右向左依次进行比较,直到发现某一数据ai,使得ai≤A,把A插入到ai的右边;如果数据A小于原有序列中的所有数据,则将A插入到原有序列的最左边.

  (2)折半插入法中的“二分法”:用折半插入排序法向有序列中插入新数据时,首先应确定原有序列中数据的个数是偶数2n还是奇数2n+1.若为偶数,则“中间位置”的数据是第n个数;若为奇数,则“中间位置”的数据为第n+1个数,然后用新数据与“中间位置”的数据比较,若新数据大于“中间位置”的数据,则在右半边进行下一步;若新数据小于“中间位置”的数据,则在左半边进行下一步;若新数据等于“中间位置”的数据,则将新数据插入到“中间位置”的数据的右边,依次类推,就可以确定新数据在有序列中的位置,这是二分法的具体应用.

  以上是在已经排好的有序列中插入一个新数据,但是生活中肯定会面临无序的数字串排序的问题,这种问题该怎么办?

  2.解法一:算法步骤为:

  (1)只有一个数的序列{7}是有序列;

  (2)将3插入有序数列{7}中,得到新序列:{3,7};

  (3)将6插入有序列{3,7}中,得到新序列:{3,6,7};

  (4)将9插入有序列{3,6,7}中,得到新序列:{3,6,7,9};

  (5)将1插入有序列{3,6,7,9}中,得到新序列:{1,3,6,7,9}.

  所以有序数列为{1,3,6,7,9}.

  解法二:算法步骤为:

  (1)在序列{7,3,6,9,1}中选出最小的数据1放在第1个位置上;

  (2)在序列{7,3,6,9}中选出最小数3放在第2位;

  (3)在序列{7,6,9}中选出最小数6放在第3位;

  (4)在序列{7,9}中选出最小数7放在第4位;

  (5)将9排在第5位.

  感悟:解法一中,第一个数据的选取,没有什么要求,只需按逐一比较排序;解法二中的第1步需选所有数据中的最小数作为基准,依次找最小数排序.体会两者的算法思想,学会处理问题的思维方法.

  总之,解决排序插入问题,应先判断所给题目是否有序,若有序用题1所用的两种思维方法排序,若无序可用题2所用的两种思维方法排序,这些都属于简单的排序问题,也是算法思想的具体应用.

看了1.期中考试结束了,班长给学生...的网友还看了以下:

在某个运行OSPF协议的广播型网络中已经选举产生了DR和BDR路由器,现在小王向这个网络中增加了一台  2020-05-31 …

《检讨书》关于学校的,下面我来介绍一下该怎么写什么内容,上周星期五的下午,我们考完试了.也许都应该  2020-06-10 …

英语翻译你的房间太乱了,该好好整理一下了,像猪窝这房间太小东西太多不太好整理  2020-06-15 …

当地时间8月6日,在喀山游泳世锦赛男子100米自由泳决赛中,以47秒84的成绩夺得金牌.他不仅刷新  2020-06-22 …

请文采好的帮我写一个道歉短语由于最好最好的朋友过生日,他已经跟我说了好几次了,而我由于一个不能说的  2020-06-29 …

穆勒:“个人的自由,以不侵犯他人的自由为自由。”应该这样理解[]A.个人要自由就必须以他人的自由为  2020-07-21 …

TTL的原始数值是多少?网工考试书上说:生存时间TTL指明了该IP分组的生命期,当IP分组通过一个路  2020-11-22 …

蚯蚓是我们人类的好朋友,我们应该好好保护它们.如图是蚯蚓的外形图,请据图作答:(1)结构B是蚯蚓的,  2020-11-25 …

蚯蚓是我们人类的好朋友,我们应该好好保护它们.如图是蚯蚓的外形图,请据图作答:(1)结构B是蚯蚓的,  2020-11-25 …

汉译英,也许到了该好好思考一下的时候:究竟什么是我们真正需要的?当付出了一切,才发现追求的只是最初所  2021-01-08 …