第四章 常用算法与实例-高中信息科技合格考一本通

６３　 第四章　常用算法与实例 一、枚举算法 １􀆰枚举算法的基本概念 枚举算法:根据所需解决问题的条件,在给定的范围内给出该问题所有可能的解,把解全 部列举出来,并逐个检验出问题真正解的方法,枚举法也称为穷举法. ２􀆰枚举算法的实现方式 (１)确定范围:确定问题所涉及的情况有哪些,列举出所有可能的情况,不能重复,也不能 遗漏. (２)验证条件:这些情况需要满足什么条件才能成为问题的解答,通常是在循环和分支组 合结构中,过滤掉不符合条件的解,保留符合条件的解. 例４Ｇ１　一张单据上有一个五位数的编号,万位数是１,千位数是４,十位数是７,个位数是 ３,百位数已经模糊不清,只知道该五位数是５７或６７的倍数,找出所有满足这些条件的五位数 并输出.如图４Ｇ１所示,把流程图填写完整(　　). 　 ６４　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 　　　图４Ｇ１ 　　　　　 k＝０ whilek＜１０: 　　n＝１４０７３＋k∗１００ 　　ifn％５７＝＝０orn％６７＝＝０: 　　　 print(n) 　　k＝k＋１ 分析与解答:牧举算法要列举所有的可能条件,不能重复,不能遗漏.五位数上百位模糊 不清,根据流程图提示信息k∗１００,所以k的取值范围是０~９,而且此五位数是５７或６７的倍 数,所以第一空填为n％５７＝＝０orn％６７＝＝０,循环需要继续下去,所以第二空是k＝ k＋１.即答案是n％５７＝＝０orn％６７＝＝０,k＝k＋１. 例４Ｇ２　素数,也叫质数.判断一个数是否为素数,可以根据素数的定义,只能被１和它自 己本身整除,即一个素数除了它本身以外,不可能分解为其他自然数的乘积.找出２~１０００里 面所有的素数,请将流程图４Ｇ２空白横线处填写完整(　　). 　　　　　　图４Ｇ２ 　　　 importmath i＝２ whilei＜＝１０００: 　　p＝True 　　j＝int(math．sqrt(i))＋１ 　　forkinrange(２,j): 　　　 ifi％k＝＝０: 　　　　 p＝False 　　　　 break 　　ifp＝＝True: 　　　 print(i,＂isaprimenumber＂) 　　else: 　　　 print(i,＂isnotaprimenumber＂) 　　i＝i＋１ ６５　 分析与解答:判断素数需要用到二重循环,外层循环设置变量i从２~１０００,这层循环的作 用就是枚举所有可能的解不重复不遗漏.内层循环作用判断i是否是素数,开始默认i为素 数,若i能被k整除,则说明i不是素数,退出循环;设置布尔变量p置初始值为true,用来记录 i是否能被k整除,若循环遍历中i被k整除了,则置p为false;最后用布尔变量p的值来判断 输出i的素数情况,若２~sqrt(i)都不能整除,p值还是为true,没有被改变,则输出i是素数, 否则输出i不是素数.即答案是i％k＝＝０,p＝＝ True. 二、排序 １􀆰排序概念 把杂乱无章的数据变为有序的数据,这一过程称为排序.排序有升序和降序两种:升序, 即由小到大排列;降序,即大到小排列. ２􀆰冒泡排序的基本思想 第一轮操作,将待排序的n个数据存到列表中,从第一个元素开始,比较a[l]和a[２],若 a[l]＞a[２]成立,则交换a[l]和a[２],然后以同样的方法比较a[２]和a[３]􀆺a[n－１]和a[n], 经过n－l次比较和交换后,列表a中最大值被排出. 第二轮操作,还是从第一个元素开始,依次比较到a[１]和a[２]直到a[n－l],比上一轮操 作少一次比较.第二轮操作的结果是余下的n－１个数据的最大值被排出. 每一轮操作都比上一轮操作少一次比较,一共要经过n－１轮操作,最后列表a中的元素 就按升序排列好了.如果要采用降序排列,只需要把大于交换方式修改为小于交换即可. 冒泡排序的实现是通过二重循环,外循环是控制第几轮操作,内循环是控制本轮操作中相 邻数的比较和交换. 例１　对列表B采用冒泡排序方法排序见图４Ｇ３. 图４Ｇ３ 　 ６６　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ３􀆰选择排序的基本思想 首先找到列表中最小(最大)的那个元素;其次将它与列表中的第一个元素交换位置;接着 在剩余的元素中找到最小(最大)的元素,将它与列表中的第二个元素交换位置;如此往复,直 到完成所有的数据排序. 例２　对列表B采用选择排序方法排序见图４Ｇ４. 图４Ｇ４ 例４Ｇ３　对一列数据[４０、７、３７、２７、１８、６３、４９、１５]按升序排列,使用冒泡排序方法,第一、二 轮需进行相邻列表元素交换的次数一共为(　　). A．４次 B．５次 C．９次 D．７次 分析与解答:冒泡排序升序排列基本思想,从一列数据的第一个元素开始依次和相邻的元 素进行比较,若前面元素比后面元素大,就交换这两个元素.以上８个数据存放在列表a中, 如下详解８个元素的比较和交换过程: 第１次比较,a[l]＞a[２]成立,需交换　　　　　　　　７、４０、３７、２７、１８、６３、４９、１５ 第２次比较,a[２]＞a[３]成立,需交换 ７、３７、４０、２７、１８、６３、４９、１５ 第３次比较,a[３]＞a[４]成立,需交换 ７、３７、２７、４０、１８、６３、４９、１５ 第４次比较,a[４]＞a[５]成立,需交换 ７、３７、２７、１８、４０、６３、４９、１５ 第５次比较,a[５]＞a[６]不成立,不需交换 ７、３７、２７、１８、４０、６３、４９、１５ 第６次比较,a[６]＞a[７]成立,需交换 ７、３７、２７、１８、４０、４９、６３、１５ 第７次比较,a[７]＞a[８]成立,需交换 ７、３７、２７、１８、４０、４９、１５、６３ 由上详解过程可知共进行了６次交换,完成第一轮操作. 第１次比较,a[l]＞a[２]不成立,不需交换 ７、３７、２７、１８、４０、４９、１５、６３ 第２次比较,a[２]＞a[３]成立,需交换 ７、２７、３７、１８、４０、４９、１５、６３ 第３次比较,a[３]＞a[４]成立,需交换 ７、２７、１８、３７、４０、４９、１５、６３ ６７　 第４次比较,a[４]＞a[５]不成立,不需交换 ７、２７、１８、３７、４０、４９、１５、６３ 第５次比较,a[５]＞a[６]不成立,不需交换 ７、２７、１８、３７、４０、４９、１５、６３ 第６次比较,a[６]＞a[７]成立,需交换 ７、２７、１８、３７、４０、１５、４９、６３ 由上详解过程可知共进行了３次交换,完成第二轮操作.即答案是C. 例４Ｇ４　对一列数据[３８、９、６５、１４、１６、５２、６７、１５],若采用选择排序算法对其进行从小到大 排序,则需要(　　)轮交换完成排序. A．４ B．５ C．６ D．７ 表４Ｇ１ ３８ ９ ６５ １４ １６ ５２ ６７ １５ 第一轮排序 ９ ３８ ６５ １４ １６ ５２ ６７ １５ 第二轮排序 ９ １４ ６５ ３８ １６ ５２ ６７ １５ 第三轮排序 ９ １４ １５ ３８ １６ ５２ ６７ ６５ 第四轮排序 ９ １４ １５ １６ ３８ ５２ ６７ ６５ 第五轮排序 ９ １４ １５ １６ ３８ ５２ ６５ ６７ 　　分析与解答:选择排序升序排列的基本思想是在一列数据中选出最小的元素,把它与第一 个元素交换,然后在剩下的元素中再选出最小的元素与第二个数据交换,依此循环,直至所有 元素按照从小到大的排序完成.即答案是B. 三、查找 １􀆰查找的概念 查找是生活中最常见的查询数据或者信息的技术,即通过一定的方法找出与给定关键字 相同的数据元素的过程. ２􀆰顺序查找的基本思想 顺序查找是一种最基本、最简单的查找算法.即从列表的第一个元素开始,按列表元素的 顺序逐个将列表元素值与给定的值进行比较,若某个列表元素值和给定值相等,则查找成功, 找到所查数据的位置;反之,查找不成功. ３􀆰对分查找的基本思想 对分查找也称为二分查找,其基本思想是在有序的数据序列中,首先将要查找的数据与有 序列表内处于中间位置的列表元素进行比较,如果两者相等,则查找成功;否则根据列表元素 的有序性,就可确定该数据应该在列表的前半部分还是在后半部分继续进行查找;在新确定的 范围内,继续按上述方法进行查找,直至找到要查找的数据,则查找成功;或查到列表中不存 在,则查找不成功. 对分查找的条件是被查找的列表中的元素必须是有序的. 　 ６８　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ４􀆰顺序查找与对分查找效率比较 查找算法的效率取决于查找的次数,顺序查找的次数由所查找的元素在序列中的位置所 决定.而对分查找的效率要高得多,但是对分查找必须基于有序排列的数据.因此,针对查找 规模较小的无序数据,顺序查找也是一种常用的有效方法. 例３　用Python程序实现,使用对分查找,在有序列表中查找目标元素. List＝[１,３,５,７,９,１１,１３,１５,１６,１８] target＝８ first＝０ n＝len(list) last＝n－１ whilefirst＜＝last: mid＝(first＋last)//２ iflist[mid]＝＝target: print(list[mid]) break eliflist[mid]＞target: last＝mid－１ else: first＝mid＋１ iflist[mid]!＝target: 　　print(“cannotfindthetargetnumber”) 例４Ｇ５　用对分查找法从列表[２、４、６、８、１５、１６、２７、３３、５５]中找到数据１６的最少查找次数 是(　　)次. A．２ B．３ C．４ D．６ 分析与解答:这里共有９个数,依次序号为１~９,第一次中间处第５号为１５,查找目标１６ 大于第５号数据１５,所以确定在列表的后半部分查找,范围是６~９;第二次新范围中间处第７ 号为２７,查找目标１６小于第７号数据２７,最终缩小查找范围为６~６;第三次中间处第６号为 １６,查找目标１６等于第６号数据１６,所以查找次数为３次.即答案是B. 例４Ｇ６　(上海市信息科技学业水平考试题)下面是一组有序的列表,现进行对分查找,查 找joe所访问的过程是(　　). ６９　 １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ al bee car dad eye for get hen ink joe kea leo mar pig 　　A．get　kea　ink　joe B．　get　car　kea　joe C．get　kea　hen　joe D．　get　hen　kea　joe 分析与解答:本题主要考查对分查找,列表中共有１４个元素,第一次找到中间位置７号元 素get,确定目标元素joe在列表的后半部分即８号到１４号元素;继续对分查找,第二次在新范 围内找到中间位置１１号元素kea,确定目标元素joe在kea的前半部分,即列表新确定范围８ 号到１０号元素;第三次使用对分查找,找到８号元素到１０号元素中间元素ink,不是目标元素 joe;最后范围缩小到只剩下１０号元素joe,查找成功,如果列表中没有元素joe,则查找不成功. 即答案是 A. 例４Ｇ７　关于对分查找和顺序查找算法的叙述中,正确的是(　　). A．顺序查找需要排序,效率低;对分查找不需要排序,效率髙 B．顺序查找不需要排序,效率低;对分查找需要排序,效率高 C．顺序查找不需要排序,效率高;对分查找需要排序,效率低 D．顺序查找需要排序,效率高;对分查找不需要排序,效率低 分析与解答:本题主要考查对分查找与顺序查找效率问题.顺序查找的次数由所查找的 元素在序列中的位置所决定,顺序查找之前不需要对数据进行排序,仅仅适合小规模的数据查 找,效率低.对分查找是一种效率很高的查找方法,但被查找的数据必须是有序的.即答案 是B. １􀆰小明玩猜价格游戏,价格的范围是１０元到１７０元.他第一次猜９０元,低了;第二次猜１３０ 元,高了;第三次猜１１０元,又低了;第四次他猜１２０元􀆺􀆺小明在猜价格时采用的方法是 (　　). A．二分法 B．排序法 C．顺序法 D．随机法 ２􀆰对于有序的数据序列,可以使用的查找算法有(　　). A．顺序查找 B．对分查找 C．两者都是 D．两者都不是 ３􀆰图书管理系统对图书管理是按图书的序号从小到大进行管理的,若要查找一本已知序号的 书,则能快速地查找到的算法是(　　). A．枚举算法 B．选择排序 C．对分查找 D．冒泡排序 　 ７０　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ４􀆰已知在８个大小相同的小球中,有一个是废品球,废品球的重量比正品球轻.现有一台无 砝码的天平,试用二分查找算法,至少要称(　　)次才能找出废品球. A．３ B．４ C．５ D．７ ５􀆰关于对分查找和顺序查找算法的叙述,正确的是(　　). A．对分查找之前需要对数据进行排序,查找过程效率较低 B．顺序查找之前不需要对数据进行排序,查找过程效率较低 C．顺序查找之前需要对数据进行排序,查找过程效率较高 D．对分查找之前不需要对数据进行排序,查找过程效率较高 ６􀆰使用选择排序对一列数据[１１、８、３６、２５、６０]按升序排列,共需要几次列表元素之间的交换 (　　). A．２次 B．３次 C．４次 D．５次 ７􀆰对于列表[２、５、６、８、１０、１２、１３、１６、１７],分别用顺序查找和对分查找的方法在其中找数据８ 的最少次数是(　　). A．１、３ B．１、４ C．４、３ D．４、４ ８􀆰列表d中的数据存放情况如表４Ｇ２所示,则流程图４Ｇ５实现的功能是(　　). 图４Ｇ５ 表４Ｇ２ d[１] d[２] d[３] d[４] d[５] d[６] １２ ４５ ２３ １８ ６ １０ A．在列表d中顺序查找１８,找遍所有数据后,找到的则输出“win”,否则输出“lose” B．在列表d中顺序查找１８,一旦找到,则停止查找并输出“win” C．在列表d中顺序查找１８,找遍所有数据后,输出“lose” D．在列表d中顺序查找１８,一旦找到,则继续直至查找结束并输出“win” ７１　 ９􀆰列表a中存放了字符串,存放情况如下表４Ｇ４所示,现对列表a进行查找操作,以下表述中 正确的是(　　). 表４Ｇ４ a[１] a[２] a[３] a[４] a[５] a[６] a[７] cake fish meat pear rice soup wolf A．用顺序方式查找“pear”,需要比较４次才能找到 B．由于列表a中没有“pizza”,所以无法进行对分查找 C．用顺序方式查找“cake”,比较１次就能找到;而用对分方式,比较３次才能找到,所以可 以得出顺序查找一定比对分查找效率高的结论 D．用对分方式查找“rice”,依次被比较的字符串为“Pear”和“rice” １０􀆰要在以下两列表中(见表４Ｇ５)进行数据查找,下列选项中查找方法使用错误的是(　　). 表４Ｇ５ a[１] a[２] a[３] a[４] a[５] a[６] a[７] a[８] a[９] a[１０] ８８ ８５ ７６ ６１ ５５ ４９ ４６ ３２ ２１ １２ b[１] b[２] b[３] b[４] b[５] b[６] b[７] b[８] b[９] b[１０] ５４ ３１ ４３ １２ ３ ６ ５６ ８７ ９０ １００ A．列表a可以直接使用顺序查找 B．列表b可以直接使用对分查找 C．列表a可以直接使用对分查找 D．列表b可以直接使用顺序查找 １１􀆰现有８位同学的身高数据如列表[１５５、１６５、１６８、１７２、１７５、１７８、１８０、１８５],若用对分查找算 法查找数值１５５,则依次被访问到的数据是(　　). A．１５５ B．１６８、１５５ C．１７２、１６５、１５５ D．１７５、１６５、１５５ １２􀆰列表顺序列出了７个同学的身髙(单位:厘米)(见表４Ｇ６),若用对分查找算法查找数值 １６８,则依次被访问到的数据是(　　). 表４Ｇ６ １８８ １７７ １７５ １７２ １６８ １６６ １５５ A．１７２、１５５、１５８ B．１７２、１６６、１６８ C．１８８、１５５、１６８ D．１５５、１６６、１６８ １３􀆰表４Ｇ７列出了存放在列表d中的８个学生的考试成绩,若用选择排序算法升序排列,在第 三遍加工结束后,列表变量d[８]的值应该为 ,总共需要做 遍加工. 表４Ｇ７ d[１] d[２] d[３] d[４] d[５] d[６] d[７] d[８] ９０ ８０ ８５ ７３ ７２ ７１ ６６ ７０ １４􀆰若一个三位数x＝１００a＋１０b＋c(a、b、c都是个位数),满足a３＋ b３＋c３＝x,则x称为 水仙花数,找出所有的水仙花数.图４Ｇ６空白处填入合适表达式为 ,并完成 Python编码. 　 ７２　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 图４Ｇ６ １５􀆰幼儿园欲购买４０块三种不同品种的巧克力,价格分别为３元、２元和１元.每种巧克力都 买到,预算１００元,怎么样才能正好把这些钱用完? 图４Ｇ７空白处填入合适表达式为 ,并完成Python编码. 图４Ｇ７ ７３　 １６􀆰已知四位数３０２５有一个特殊的性质:它的前两位数３０和后两位数２５的和是５５,而５５的 平方正好等于３０２５.如图４Ｇ８所示,找出所有满足条件的四位数的算法,空白处填入合适 表达式为　　　　,并完成Python编码. 图４Ｇ８ １７􀆰一张票据上有一个五位数的票号,万位数是２,千位数是３,十位数是５,个位数和百位数已 经模糊不清.该五位数是３７和４７的倍数,找出所有满足条件的五位数并输出.图４Ｇ９空 白处填入合适表达式为 ,并完成Python编码. 图４Ｇ９ 　 ７４　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 １８􀆰用５到９这五个数字,组成两位数,在组成的数中不能有重复的数字.共可以组成多少组 数并输出所有符合条件的两位数,图４Ｇ１０空白处填入合适表达式为 ,并完成PyＧ thon编码. 图４Ｇ１０ １９􀆰用０、２、４、６、８这五个数字,组成两位数,数字可以重复使用,但个位数不能是６.共可以组 成多少组数并输出所有可能的两位数,图４Ｇ１１空白处填入合适表达式为 ,并完成 Python编码. 图４Ｇ１１ ７５　 ２０􀆰小明同学去邮局欲将一张面值为１００元的邮票等值换成５元、１元的小面值邮票共４０张, 要求每种邮票不少于１张,问５元和１元面值的邮票各多少张? 编写 Python程序实现 功能. ２１􀆰编写Python程序,该程序要实现的功能如下:一个n位正整数,如果它每一位上数字的n 次幂的和等于它本身,就称该数为自幂数.当n＝４时,这个四位的自幂数也称为四叶玫 瑰数,例如:１６３４＝１４＋６４＋３４＋４４,输出并统计２０００~９０００内所有的玫瑰数. ２２􀆰编写Python程序,该程序要实现的功能如下:求所有五位数中满足能被１７整除且十位数 字为５的数之总数. 　 ７６　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ２３􀆰编写Python程序,该程序要实现的功能如下:一个六位正整数x能同时被１５７和２３３整 除,且第一位和最后一位的数字恰好相同. ２４􀆰编写Python程序,该程序要实现的功能如下:求首尾两个数字相同的四位数中能被３除 余２的所有五位数之和. ２５􀆰编写Python程序,该程序要实现的功能如下:有一个整数,它加上１００后是一个完全平方 数,再加上１６８仍是一个完全平方数,请问该数是多少? 　 １５４　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 １５􀆰s＝０ n＝int(input(＂pleaseinputanumber:＂)) foriinrange(１０１,n＋１): s＝s＋１０/i print(s) １６􀆰n＝int(input(“pleaseinputanumber:”)) s＝０ t＝０ foriinrange(１,n): t＝t＋i s＝s＋i/t print(s) １７􀆰s＝０ forxinrange(１００,１０００): P１＝int(x/１００) P２＝int(x/１０)％１０ P３＝x％１０ ifP１＜P２andP２＜ P３: s＝s＋１ print(s) 第四章　常用算法与实例 巩固练习 １􀆰A　２．C　３．C　４．A　５．B　６．A　７．C　８．B　９．A　１０．B　１１．C　１２．B　１３．８０/６ １４􀆰x＝１００ a∗∗３＋b∗∗３＋c∗∗３＝＝x 完整Python程序: x＝１００ whilex＜＝９９９: a＝int(x/１００) b＝int((x％１００)/１０) c＝int(x％１００) ifa∗∗３＋b∗∗３＋c∗∗３＝＝x: １５５　 print(x) x＝x＋１ １５􀆰s＝＝１００andk＞０ i＝i＋１ 完整Python程序: i＝１ whilei＜＝３３: 　　n＝１ 　　whilen＜＝４０: 　　　　k＝４０－i－n 　　　　s＝i∗３＋n∗２＋k 　　　　ifs＝＝１００andk＞０: 　　　　　print(i,n,k) 　　　　n＝n＋１ 　　i＝i＋１ １６􀆰int(n/１００) n＝＝c∗c 完整Python程序: n＝１０００ whilen＜＝９９９９: a＝int(n/１００) b＝n％１００ c＝a＋b 　　ifn＝＝c∗c: 　　　 print(n) 　　n＝n＋１ １７􀆰n％３７＝＝０andn％４７＝＝０ k＝k＋１００ 完整Python程序: i＝１ whilei＜１０: k＝１００ 　　whilek＜１０００: 　 １５６　 　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 n＝２３０５０＋i＋k 　　　　ifn％３７＝＝０andn％４７＝＝０: 　　　　　 print(n) 　　　　k＝k＋１００ 　　i＝i＋１ １８􀆰n＝５ n!＝i 完整Python程序: k＝０ i＝５ whilei＜＝９: n＝５ 　　whilen＜＝９: 　　　　ifn!＝i: 　　　　 print(n) 　　　　 k＝k＋１ 　　　　n＝n＋１ 　　i＝i＋１ print(k) １９􀆰k＝０ k!＝６ 完整Python程序: i＝２ whilei＜＝８: k＝０ 　　whilek＜＝８: 　　　　ifk!＝６: 　　　　　 print(i∗１０＋k) 　　　　k＝k＋２ 　　i＝i＋２ ２０􀆰forxinrange(１,２０): y＝４０－x if５∗x＋y＝＝１００: print(x,y) １５７　 ２１􀆰x＝０ foriinrange(２０００,９０００): if(i//１０００)∗∗４＋(i//１００％１０)∗∗４＋(i％１００//１０)∗∗４＋(i％１０)∗∗４＝＝i: 　　　print(i) 　　　x＝x＋１ ２２􀆰s＝０ foriinrange(１００００,１０００００): ifi％１７＝＝０andi//１０％１０＝＝５: 　　 s＝s＋１ print(s) ２３􀆰foriinrange(１０００００,１００００００): ifint(i/１０００００)＝＝i％１０andi％１５７＝＝０andi％２３３＝＝０: print(i) ２４􀆰s＝０ forninrange(１０００,１００００): a＝n％１０ b＝n//１０００ ifa＝＝bandn％３＝＝２: 　　　s＝s＋n print(s) ２５􀆰importmath num＝１ whileTrue: ifmath．sqrt(num＋１００)－int(math．sqrt(num＋１００))＝＝０and\ math．sqrt(num＋２６８)－int(math．sqrt(num＋２６８))＝＝０: print(num) break 　 num＝num＋１ 　 (注:“\”续行符) 第五章　人工智能与信息社会 巩固练习 １􀆰D　２．A　３．B　４．A　５．D　６．C　７．A　８．A　９．A　１０．B １１􀆰D　１２．A　１３．B　１４．A　１５．B　１６．C　１７．B　１８．C　１９．A　２０．B ２１􀆰C　２２．B　２３．A　２４．C　２５．C　２６．B　２７．D　２８．D　２９．B　３０．B