第8章怎样研究算法排序算法示例练习题答案解析.docx
《第8章怎样研究算法排序算法示例练习题答案解析.docx》由会员分享，可在线阅读，更多相关《第8章怎样研究算法排序算法示例练习题答案解析.docx（80页珍藏版）》请在冰点文库上搜索。
第8章怎样研究算法排序算法示例练习题答案解析
第8章怎样研究算法排序算法示例练习题答案解析．
第8章怎样研究算法:
排序算法示例
1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。
关于排序算法，下列说法不正确的是_____。
（A）大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多；
（B）大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多；
（C）对无序数据集合，两个算法X和Y：
X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述（A）、（B）两类问题，Y算法一定比X算法慢；
（D）上述说法有不正确的；
答案：
C
解释：
本题考核排序算法的研究有序数据集合有利在大规模数据集合中查找，算法进行和判断，要比无序数据集合查找的快，
算法尽管需要排序后再处理，选项，Y对于（C）Y但排序处理后的数据查找更加快捷，因此可能X算法更快。
算法比具体内容请参考排序算法以及第八章课件。
、下列三个算法是关于“大规模数据集合中查2“学生”针对一个找有无某些元素”问题的算法：
数据表，如下示意，找出“成绩”为某一分数的所有学生。
学生
学
12030095
07
1203001李94
03宁
1203001李88
01鹏
85
徐120300106
月．
1203001王79
02刚
1203001江77
09
12030073
10
12030069
0412030066
0544
12030008
A1】【算法StartofalgorithmA1
条记录开始，直到其最Step从数据表的第11.
后一条记录为止，读取每一条记录，做Step2。
对每一条记录，判断成绩是否等于给定Step2.
则输出；如果不是，则不输出。
如果是，的分数：
EndofalgorithmA1
A2【算法】StartofalgorithmA2
条记录开始，直到其最1从数据表的第1.Step
后一条记录为止，读取每一条记录，做Step2和Step3。
Step2.对每一条记录，判断成绩是否等于给定
的分数：
如果等于，则输出；如果不等于，则不输出。
Step3.判断该条记录的成绩是否小于给定的分数：
如果不是，则继续；否则，退出循环，算法结束。
EndofalgorithmA2
【算法A3】
StartofalgorithmA3
Step1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；
Step2.计算中间记录位置I=（Start+Finish）/2，读取第I条记录。
Step3.判断第I条记录的成绩与给定查找分数：
（3.1）如果是小于关系，则调整Finish=I-1；如果Start>Finish则结束，否则继续做Step2；（3.2）如果是大于关系，则调整Start=I+1；如果Start>Finish则结束，否则继续做Step2；
周围I如果是等于关系，则输出，继续读取（3.3）．
所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。
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（logn），因此选2择（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（logn）；2
（E）上述都不正确。
答案：
D
解释：
本题考核排序算法的研究
数据越多，算法A1穷举，线性查找，平均比较次数（n+1）/2，时间复杂度O（n）。
算法A2同样是线性查找，只是多了对剩余数据的判断，时间复杂度和A1一样，同样是O（n）。
算法A3二分查找，每次可缩小一半的查找范围，算法A3时间复杂度是O（logn），因此选择（D）。
2具体内容请参考排序算法以及第八章课件。
（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、关于“非结构化数据（文档）的查找与搜索”问题，参考下图，回答下列问题。
注意每份文档可能包含数千数万的词汇。
．
查找有无）个全文文档中（n可能很大
（1）若要在n最好的做为提高检索效率，某个关键词的文档，。
法是_____直接用给定关键词来匹配每一份文档中的（A）则每一个词汇。
若该文档存在匹配成功的词汇，输出该文档；否则，不输出该文档。
个文档，首先建立一个“关键词”n（B）对这索引表，该索引表记录着“关键词”及包含该关。
在此基础上，用给定关键键词的“文档编号”则词来匹配索引表中的关键词。
如果匹配成功，则输出否则，输出索引表中相对应的文档编号；信息“没有含该关键词的文档”。
个文档，首先建立一个“关键词”n对这（C）
索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。
在此基础上，用给定关键词来匹配索引表
中的关键词。
如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”。
（D）选项（B）（C）比选项（A）的做法好，但选项（B）（C）没有效率上的差别。
答案：
C
解释：
本题考核排序算法的研究
由题意知，n个全文文档数据量很大，若全文搜索，检索效率会很低，因此排除（A）。
建立“关键字”索引表，并包含“文档编号”，可以有效的缩小查找范围。
同时，对索引表进行排序，可以有效的提高查找效率。
因此，选择（C）。
具体内容请参考查找，排序算法以及第八章课件。
查找与某）可能很大（n个全文文档中n若要在
（2）．
个关键词最相关的文档，为提高检索效果和检索效率，最好的做法是_____。
（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）
答案：
D
解释：
本题考核排序算法的研究
“自动获取文档关键词”的方法是一个充分不必要条件。
关键词应排除标点符号和辅助词汇，因此排除（A）（B）。
出现次数最多，但不能对单个文档而言就凭次数判断关键词，必须达到一定的标准，故而选择（D）。
具体内容请参考排序算法以及第八章课件。
4、关于“内排序”算法和“外排序”算法，下列说法不正确的是_____。
（A）“内排序”算法通常是内存中数据排序常用的算法，而“外排序”算法通常是大规模数据排序常用的算法；
（B）“内排序”算法由于内存排序应用的频繁性，所以算法要考虑用尽可能少的步骤，而“外排序”算法由于要利用磁盘保存中间结果，所以算法主要考虑尽可能少的读写磁盘；
（C）无论是“内排序”算法，还是“外排序”算法，都需要考虑读写磁盘的代价问题；
（D）对一组需要排序的数据，能应用“内排序”
算法时，尽量不用“外排序”算法；
答案：
C
解释：
本题考核排序算法的研究
内排序：
待排序的数据可一次性地装入内存中，即排序者可以完整地看到和操纵所有数据；
外排序：
待排序的数据保存在磁盘上，不能一次性装入内存，即排序者不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理；
由上可知（A）（B）正确，（C）错误。
具体内容请参考排序算法以及第八章课件。
5、下列三种算法是经常应用的内排序算法：
插入排序、选择排序和冒泡排序。
阅读下列算法，回答下列问题。
INSERTION-SORT（A）．
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While（j>0andA[j]>key）do
5.{A[j+1]=A[j];
6.j=j-1;}
A[j+1]=key;7.
}8.
SELECTION-SORT（A）
1.fori=1toN-1
{k=i;2.
．orj=i+1toN
f3thenk=j;}{ifA[j]then5.ifk<>i
{
6.
temp=A[k];7.
A[k]=A[i];8.
A[i]=temp;9.
}10.
}11.
BUBBLE-SORT（A）
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j+1]=temp;
8.haschange=true;
9.}
10.}
11.if（haschange==false）then
break;
12.}
（1）关于INSERTION-SORT算法的基本思想，下列说法正确的是_____。
（A）一个元素一个元素的处理。
每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。
直到最后一个元素则算法结束。
一个轮次一个轮次的处理。
将元素集合分（B）．
成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。
在每一轮次，从未排序元素集合中找出最小值的元素，将其移
入已排序元素集合；直到未排序元素集合为空时则算法结束。
（C）一个轮次一个轮次的处理。
在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：
如不符合排序关系，则交换两个元素。
直到某一轮次没有元素交换发生则结束。
（D）上述说法都不正确。
答案：
A
解释：
本题考核排序算法的研究
（A）描述的是插入排序，（B）描述的是选择排序，（C）描述的是冒泡排序。
具体内容请参考内排序算法以及第八章课件。
（2）关于SELECTION-SORT算法的基本思想，下列说法正确的是_____。
一个元素一个元素的处理。
每次处理一个（A）
元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。
直到最后一个元素则算法结束。
（B）一个轮次一个轮次的处理。
将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。
在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。
（C）一个轮次一个轮次的处理。
在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：
如不符合排序关系，则交换两个元素。
直到某一轮次没有元素交换发生则结束。
（D）上述说法都不正确。
答案：
B
解释：
本题考核排序算法的研究
（A）描述的是插入排序，（B）描述的是选择排序，（C）描述的是冒泡排序。
具体内容请参考内排序算法以及第八章课件。
．
（3）关于BUBBLE-SORT算法的基本思想，下列说法正确的是_____。
（A）一个元素一个元素的处理。
每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。
直到最后一个元素则算法结束。
（B）一个轮次一个轮次的处理。
将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。
在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。
（C）一个轮次一个轮次的处理。
在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：
如不符合排序关系，则交换两个元素。
直到某一轮次没有元素交换发生则结束。
（D）上述说法都不正确。
答案：
C
解释：
本题考核排序算法的研究
（A）描述的是插入排序，（B）描述的是选择排序，（C）描述的是冒泡排序。
具体内容请参考内排序算法以及第八章课件。
（4）关于排序的选择法和冒泡法，下列说法不正确的是_____。
（A）“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，只是寻找最小值元素的方法不一样，在效率方面没有什么差别；
（B）“选择法”通过将所有未排序元素与当前轮次待寻找的最小值元素进行比较，获得当前轮次的最小值元素；而“冒泡法”通过相邻元素的两两比较，一个轮次完成也能获得一个最小值元素；
（C）虽然“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，但选择法每轮次仅比较，没有交换，直至找到最小值后做一次交换；而冒泡法每一轮次是通过相邻元素比较来找最小值，如果不满足排序，则交换相邻两个元素，交换可能频繁发生。
这样来看，选择法比冒泡法要快一些；
（D）上述说法有不正确的。
答案：
A
解释：
本题考核排序算法的研究
“选择”与“冒泡”都是每轮查找出最小值，方法不同（B）选项是正确的，但效率是有不同的，（C）中描述正确，选择排序调用swap要比冒泡排序少，因此，选择（A）
具体内容请参考内排序算法以及第八章课件。
（5）关于三种排序算法，下列说法正确的是_____。
2），所以三（A）三种算法的时间复杂度都为O（n种算法的执行效率是一样的；
2），O（n但（B）尽管三种算法的时间复杂度都为细致比较还是有差别的，例如冒泡法排序比选择法排序要快一些；
（C）尽管细致比较三种算法的执行时间是有差别的，但这种差别对内排序问题而言是可以忽略不计的；
尽管细致比较三种算法的执行时间是有差（D）
别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行。
答案：
D
解释：
本题考核排序算法的研究
2），但是细致三种算法的时间复杂度都是O（n比较是有差别的，（A）错误，如果被排序的记录很大，执行交换所需时间是客观的，将远远大于比较关键字和计算数组下标的时间。
冒泡和插入排序调用次数最多，为n（n-1）/2，选择排序每遍只在选出最小记录后进行一次交换，需调用n-1次，因此（B）错误，有因为内排序算法要被频繁执行，因此这种差别对内排序问题而言是重要的，故而选择（D）。
具体内容请参考内排序算法以及第八章课件。
（6）阅读INSERTION-SORT算法，关于第4.行至第6.行间程序段的作用，下列说法正确的是_____。
j依次与已经排序的第将当前待处理元素，（A）
个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置；
（B）将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置。
（C）将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向前移动一个位置。
（D）将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向后移动一个位置。
答案：
D
解释：
本题考核排序算法的研究
插入排序，算法中J从I-1到1，递减，排除的元素依次向后移动，key，将大于）C（）B（．
因而选择（D）。
具体内容请参考内排序算法以及第八章课件。
（7）阅读SELECTION-SORT算法，关于第3.行至第4.行间程序段的作用，下列说法正确的是_____。
（A）循环地在未排序元素集合中找最小值元素的位置，该位置保存在变量k中；
（B）循环地在未排序元素集合中找最小值元素，该元素保存在变量k中；
（C）循环地在未排序元素集合中找最大值元素的位置，该位置
升级会员 