第8章怎样研究算法排序算法示例练习题答案解析

第8章怎样研究算法:排序算法示例1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。(A)大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多；(B)大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多；(C)对无序数据集合，两个算法X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢；(D)上述说法有不正确的；答案：C解释：本题考核排序算法的研究在大规模数据集合中查找，有序数据集合有利算法进行和判断，要比无序数据集合查找的快，对于（C）选项，Y算法尽管需要排序后再处理，但排序处理后的数据查找更加快捷，因此可能Y算法比X算法更快。具体内容请参考排序算法以及第八章课件。2、下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。学生学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44【算法A1】StartofalgorithmA1Step1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step2。Step2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。EndofalgorithmA1【算法A2】StartofalgorithmA2Step1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step2和Step3。Step2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。EndofalgorithmA2【算法A3】StartofalgorithmA3Step1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step2.计算中间记录位置I=(Start+Finish)/2，读取第I条记录。Step3.判断第I条记录的成绩与给定查找分数：(3.1)如果是小于关系，则调整Finish=I-1；如果StartFinish则结束，否则继续做Step2；(3.2)如果是大于关系，则调整Start=I+1；如果StartFinish则结束，否则继续做Step2；(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。EndofalgorithmA3针对上述三个算法，回答下列问题：(1)关于算法A1,A2,A3的快慢问题，下列说法正确的是_____。(A)算法A1快于算法A2，算法A2快于算法A3；(B)算法A2快于算法A1，算法A2快于算法A3；(C)算法A3快于算法A2，算法A2快于算法A1；(D)算法A1快于算法A3，算法A3快于算法A2；(E)上述都不正确。答案：C解释：本题考核排序算法的研究首先，数据是有序排列的，从大到小。算法A1依次搜索，穷举。算法A2与A1一样，穷举，不同的是它利用数据是从大到小排序的特点，因此，如果当前数据比如果小于目标数，那么说明只有的也一定小于，则目标不在序列中。因此，A2比A1快。算法A3利用数据有序特点，采用二分查找，每次将目标数与中间值比较，缩小搜索范围，因此A3比A2快。综上，答案选（C）。具体内容请参考排序算法以及第八章课件。(2)关于算法A3，下列说法正确的是_____。(A)对数据表中的任何数据，算法A3都适用；(B)对数据表中任何已排序的数据，算法A3都适用；(C)对已按成绩排序的数据表，算法A3都适用；(D)对已按成绩进行降序排列的数据表，算法A3都适用；(E)上述都不正确。答案：D解释：本题考核排序算法的研究算法A3需求的数据应该是排序的，而且是对成绩排序的，因此排除（A）（B）。其次，按照算法A3，应该是降序排序的数据才可用，因为升降序决定了算法二分查找的重订搜索范围实在中间值的左边还是右边，对于算法A3,要求是降序的。因此选择（D）。具体内容请参考排序算法以及第八章课件。(3)关于算法A3和算法A1，下列说法正确的是_____。(A)如果数据表中记录数越多，则算法A3相比算法A1的优势越明显，即查找时间越短；(B)如果数据表中记录数越多，则算法A1相比算法A3的优势越明显；即查找时间越短；(C)算法A3和算法A1的执行时间差异不会随数据表中记录数多少而变化；(D)上述都不正确。答案：A解释：本题考核排序算法的研究数据越多，算法A1穷举，查找时间正比增加，算法A3二分查找，每次可缩小一半的查找范围，数据越多，优势越明显，算法A1时间复杂度是O(n),算法A3时间复杂度是O(log2n)，因此选择（A）。具体内容请参考排序算法以及第八章课件。(4)关于三个算法的复杂性，下列说法正确的是_____。(A)算法A1、A2和A3的时间复杂性都为O(n)；(B)算法A1和A2的时间复杂性为O(1)，算法A3的时间复杂性为O(n)；(C)算法A1的时间复杂性为O(n)，算法A2的时间复杂性为O(n/2)，算法A3的时间复杂性为O(n/4)；(D)算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为O(log2n)；(E)上述都不正确。答案：D解释：本题考核排序算法的研究数据越多，算法A1穷举，线性查找，平均比较次数(n+1)/2，时间复杂度O(n)。算法A2同样是线性查找，只是多了对剩余数据的判断，时间复杂度和A1一样，同样是O(n)。算法A3二分查找，每次可缩小一半的查找范围，算法A3时间复杂度是O(log2n)，因此选择（D）。具体内容请参考排序算法以及第八章课件。(5)针对按成绩降序排列的数据表，假设记录数为n，关于算法A2，下列说法正确的是_____。(A)算法A2在任何情况下都需要读取n条记录，才能得到结果；(B)算法A2在任何情况下都需要读取n/2条记录，才能得到结果；(C)算法A2在最好的情况下是读取1条记录，在最差的情况是读取n条记录，才能得到结果；(D)算法A2在任何数据分布情况下，平均要读取n/2条记录才能得到结果；(E)上述都不正确。答案：C解释：本题考核排序算法的研究对于算法A2，最好情况：读取1条记录，刚好等于目标数，算法结束；或者读取1条记录，该记录小于目标数，因成绩降序排列，剩余数据都小于目标，所以记录中没有目标查询数，算法结束。最坏情况：读取了n条记录，最后一条记录等于，则返回结果，不等于，则不在记录中。算法结束。综上，选择（C）。具体内容请参考排序算法以及第八章课件。3、关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。(1)若要在n个全文文档中(n可能很大)查找有无某个关键词的文档，为提高检索效率，最好的做法是_____。(A)直接用给定关键词来匹配每一份文档中的每一个词汇。若该文档存在匹配成功的词汇，则输出该文档；否则，不输出该文档。(B)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。(C)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”。(D)选项(B)(C)比选项(A)的做法好，但选项(B)(C)没有效率上的差别。答案：C解释：本题考核排序算法的研究由题意知，n个全文文档数据量很大，若全文搜索，检索效率会很低，因此排除（A）。建立“关键字”索引表，并包含“文档编号”，可以有效的缩小查找范围。同时，对索引表进行排序，可以有效的提高查找效率。因此，选择（C）。具体内容请参考查找，排序算法以及第八章课件。(2)若要在n个全文文档中(n可能很大)查找与某个关键词最相关的文档，为提高检索效果和检索效率，最好的做法是_____。(A)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”。(B)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。(C)对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。(D)选项(B)(C)比选项(A)的做法好，但选项(B)(C)在执行效果和执行效率方面没有什么差别。答案：C解释：本题考核排序算法的研究由题意知，要寻找与关键词最相关的文档，做法是以关键词出现次数为评判标准。建立索引表，包含“关键词”，因要查找与关键词最相关的文档，所以需求相关文档中出现的“次数”，故而排除（A）选项，对于（B）（C），（C）选项中对关键词相同的文档进一步按“次数”进行降序排序，可以提高检索效率，因此选择（C）选项。具体内容请参考查找，排序算法以及第八章课件。(3)针对下列问题求解方法：对n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找次数最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。问该方法涉及到几类算法，说法正确的是_____。(A)涉及字符串的字母序排序算法；(B)涉及数值属性排序算法；(C)涉及字符串匹配算法；(D)涉及数值属性查找算法；(E)涉及上述全部算法；答案：E解释：本题考核排序算法的研究查找关键词，设计字符串匹配算法。对索引表按关键字进行字母序的排序，设计字符串的字母序排序算法。关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序，涉及数值属性排序算法。寻找次数最多的m个索引项，涉及数值属性查找算法。综上，选择（E）。具体内容请参考查找算法以及第八章课件。(4)上图给出了一种“自动获取文档关键词”的方法，关于该方法的表述，最好的是_____。(A)文档中出现次数最多的词汇必定是关键词；(B)文档中去掉标点符号后，出现次数最多的词汇必定是关键词；(C)文档中去掉标点符号和一些辅助词汇，出现次数最多的词汇必定是关键词；(D)文档中去掉标点符号和一些辅助词汇，出现次数最多且次数达到一定数值的词汇必定是关键词；(E