《第三章整理.doc》由会员分享，可在线阅读，更多相关《第三章整理.doc（10页珍藏版）》请在三一文库上搜索。
1、（三）1 单选 (2 分)关于问题与问题求解，下列说法正确的是（）。A.在问题求解中，提出假设就是对问题求解结果的一种假设。B.问题求解是人们为寻求问题答案而进行的一系列思维活动。C.问题是客观存的，提出问题与发现问题与人对事情的好奇心和求知欲无关。D.所有问题都是有科学研究价值的。E.人类进行问题求解的一般思维过程可分为问题分析、提出假设和检验假设。F.问题的发现与人的好奇心和求知欲有关，与人的知识和经验无关。正确答案：B、E2 单选 (2 分)关于贪心算法，下列叙述中正确的是（）。A.贪心算法所做出的选择只是在某种意义上的局部最优选择。B.贪心算法并不从整体最优考虑。C.贪心算法无法求得问
2、题的最优解。D.贪心算法的时间效率最高。E.选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。正确答案：A、E3 单选 (2 分)关于数学模型（ Mathematical Model ）和数学建模（ Mathematical Modeling），下列说法正确的是（）。A.数学建模包括模型准备、模型假设和模型建立三个基本步骤。B.数学模型是问题求解的逻辑模型，与时间变量无关。C.数学模型是研究和掌握系统运动规律的有力工具，可以对实际问题进行分析、预测和求解。D.数学建模是对实际问题进行抽象、提炼出数学模型的过程。E.数学模型是对实际问题的数学抽象，是用数学符号、数学式子等对实际问题本质属性
3、的抽象而又简洁的刻画。正确答案：D、E4 单选 (2 分)1关于问题的算法复杂性，下列叙述正确的是（）。A.NP 问题就是时间复杂性为O(2n)的问题。B.NP 问题都是不可解的。C.问题求解算法的时间复杂度是该问题实例规模n 的多项式函数，则这种可以在多项式时间内解决的问题称为P 类问题。D.NP 问题虽然不能在多项式时间内求解，但对于所有解，都可以在多项式时间内验证它是否为问题的解。E.NP问题就是时间复杂性为O(n！)的问题。F.不能在多项式时间内求解的问题为NP 问题。正确答案：C、F5 单选 (2 分)设数据表共有 n=10 个元素，其关键值为 2，5，6，10，15，21，26，3
4、0， 56，78，要查找的关键字为K=30，则查找成功时，所做的比较操作的次数是（）。A.8 次B.3 次C.2次D.1 次E.4 次正确答案：C6 单选 (2 分)关于算法（ Algorithm ），下列叙述正确的是（）。A.在算法设计中，设计师和程序员之间采用流程图工具。B.在算法描述中，自然语言、流程图和伪代码不能混合使用。C.算法是问题求解方法及求解过程的描述。D.自然语言描述常用于细节的描述。E.在算法设计中，用户和分析师常采用伪代码描述算法，沟通思想。正确答案：C7 单选 (2 分)2算法的时间复杂性是指（）。A.所有算法都与问题的规模有关，问题规模越大，时间复杂性越大。B.同一个
5、算法，可以编写不同的程序，程序的执行时间不同，因此一个算法可以有多种不同的时间复杂性。C.时间复杂性是衡量一个算法优劣的唯一标准。D.指根据该算法编写的程序在运行过程中，从开始到结束所需要的时间。E.通常以算法的元操作重复执行的次数作为算法的时间度量。F.算法时间复杂性越低，算法就越好。正确答案：D、E8 单选 (2 分)在计算机问题求解中，下列叙述正确的是（）。A.在计算机问题求解中，计算机通过执行求解算法从而得到问题的解。B.利用计算机进行问题求解，就是用机器代替人，属于计算机的人工智能应用。C.计算机问题求解主要适应于自然系统，社会系统无法建模。D.计算机进行问题求解把问题分成了数据和算
6、法两个方面。正确答案：D9 单选 (2 分)关于枚举法，下列叙述中正确的是（）。A.枚举类算法的时间复杂性是O（n！）。B.利用计算机的高速度，枚举法都是轻而易举的。C.理论上讲，枚举法一定可以求得问题的解。D.枚举类算法的时间复杂性是O（2n）。E.枚举法的基本思想就是枚举所有可能的情况，并逐个测试，从而找出符合问题条件的解。F.枚举法算法都是NP-hard 的。正确答案：C、E10单选 (2分)关于查找和排序，下列叙述正确的是（）。A.排序只能对数字进行。3B.冒泡排序属于选择排序。C.所有的排序类算法，其效率与对象的原始状态无关。D.折半查找只能在有序数据序列中进行。E 查找类算法的元操
7、作是比较。正确答案：D、E11多选 (3分)下列方法属于问题分析的是（）。A.提出假设B.问题归约C.检验假设D.问题抽象E 形式化描述正确答案： B、D、E12多选 (3分)考察一个算法，应该考察的方面有（）。A.空间复杂性B.正确性C.时间复杂性D.文件大小E 程序质量F 压缩比正确答案：A、B、C13多选 (3分)关于递推法和递归算法，下列说法正确的是（）。A.递推法是一种根据递推关系来一步步递推求解的问题求解策略。B.递推法都是从已知条件出发，逐步推导出结论。4C.递归法是一种问题规模的递推，属于一种编程技术。D.递推法比递归算法效率更高。E 递归法算法的程序更加简洁，时间效率更高。正
8、确答案： A、C、D14多选 (3分)提高一个查找类算法的时间效率，需要考虑的因素是（）。A.对象比较的次数B.对象的查找概率C.对查找对象排序D.对象的数据类型E 高性能计算机正确答案： A、B、C15多选 (3分)关于冒泡排序（ Bubbles Sorting），下列说法正确的是（）。A.冒泡排序算法的时间复杂性为O（n*n ）。B.冒泡排序每一遍都选出最小的数，因此属于选择类排序。C.冒泡排序属于标准交换分类。D.冒泡排序在最好情况下可以不进行任何交换。E 在最坏情况下，算法需要进行n 遍比较和交换操作。正确答案：A、C、D16判断 (1分)问题求解是人们为寻求问题答案而进行的一系列思维
9、活动。A. ×B.正确答案：B17判断 (1分)问题归约就是对问题进行归纳和简化，从而把一个复杂问题转换为相对简单的问题。5A.B. ×正确答案： A18判断 (1分)对于同一个问题，如果可以用递推算法和递归算法来求解，递推算法的运行效率更高。A.B. ×正确答案： A19判断 (1分)从思维的角度，计算机进行问题求解和人工问题求解之间毫无联系。A. ×B.正确答案：A20判断 (1分)采用启发式问题求解策略，一定可以得到问题的解。A.B. ×正确答案： B21填空 (3分)指将一个记录插入到一个已经排序好的有序序列中，从而得到一个新的、记录个
10、数加1 的有序序列，这样的排序称为（）。正确答案：插入排序或Insert Sorting或insert sorting22填空 (3分)根据心理学的研究结果，问题求解策略分为算法式和启发式两大类，按照逻辑来求解问题的策略称（）。正确答案：算法式23填空 (3分)设算法的时间复杂性为O (n3)，设该算法每 ms 执行一次基本运算，则计算机在1 秒钟内可求解的问题长度约为（）。6正确答案： 3124填空 (3分)若算法的执行时间与问题长度无关，则该算法的时间复杂度为（）。正确答案： O(1)或o(1)或O（1）或o（1）25填空 (3分)在问题求解中，“试探失败返回再试探”的问题求解方法称为（）
11、。正确答案：回溯法5 单选 (2 分)在“八皇后问题”的问题求解中，采用“试探失败返回再试探”的问题求解方法，该方法属于（）。A.分治法B.枚举法C.贪心法D.回溯法E 递推法正确答案： D12多选 (3分)关于哥尼斯堡七桥问题，下列叙述正确的是（）。A.欧拉通过数学建模，找出了哥尼斯堡七桥问题的解。B.欧拉将哥尼斯堡七桥问题抽象成了一个图的问题。C.哥尼斯堡七桥问题是由大数学家欧拉提出的。D.欧拉在解答哥尼斯堡七桥问题的同时，开创了一个新的数学分支图论。正确答案：B、C、D16判断 (1分)抽象是一种重要的方法，它是产生概念，认识万千世界的工具。A.7B. ×正确答案： A正确答案
12、：A18判断 (1分)人类的思维是一个生理和心理的自然属性，与哲学和数学训练无关。A.B. ×正确答案： B20判断 (1分)对于长度为 n 的序列，采用冒泡排序法进行排序，一定要进行n-1 遍比较和交换操作。A.B. ×正确答案： B22填空 (3分)对于长度为 n=1000 的线性表，假设查找每个元素的概率相等，采用顺序查找，则查找成功的平均检索长度约为（）。正确答案： 500或500.523填空 (3分)算法中的每一条指令必须有确定的含义，不能产生二义性，称为算法的（）。正确答案：确定性24填空 (3分)美国数据加密标准DES采用长度为 64 位的密钥（实际密钥56
13、位， 8 位用于奇偶校验），采用穷举搜索密钥，设计算机每秒钟判断一亿个密码是否正确，则要穷举所有的可能密钥需要花费的时间约为（）年。正确答案： 22.85或22或22.8或232 单选 (2 分)将多个有序序列合并成一个有序序列，属于（）。8A.归并排序B.选择排序C.插入排序D.基数排序E 交换排序正确答案： A8 单选 (2 分)关于抽象（ Abstraction），下列说法正确的是（）。A.抽象是一种重要的思维方法。B.抽象就是把那些空洞不易捉摸的事物，描述成具体的事物。C.抽象是对本质特征的抽象，本质特征是确定的，因此抽象是唯一的。D.抽象是产生概念，认识万千世界的工具，对事物进行抽象具有特定的模式。E 抽象是从众多的事物中抽取出共同的、本质性的特征，而舍弃其非本质的特征。正确答案： A、E11多选 (3分)对事物进行抽象没有一个固定的模式，下列方法属于抽象所采用的方法是（）。A.简略B.假设C.形式化D.分离正确答案：A、D14多选 (3分)关于排序，下列说法正确的是（）。A.排序可以提高检索效率B.排序就是指按照指定的关键字排列成一个有序文件（或表）的过程C.排序只能对数字进行9D.受计算机内存大小的限制，排序类算法只能对有限数量的数据进行排序。正确答案：A、B10