2021年12月/2022年3月计算机二级公共基础知识押题71-100 71.在长度为n的顺序表中查找一个素，假设需要查找的素一定在表中，并且素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（ ） A)n/4 B)n C)3n/4 D)(n+1)/2【解析】在顺序表中查找，最好情况下第一个素就是要查找的素，则比较次数为1；在最坏情况下，最后一个素才是要找的素，则比较次数为n。则平均比较次数：（1+2+┉+n）/n=(n(n+1)/2)/n=(n+1)/2。 72.在长度为n的顺序表中查找一个素，假设需要查找的素有一半的机会在表中，并且如果素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（ ） A)n B)3n/4 C)n/2 D)n/4【解析】在顺序表中查找，最好情况下第一个素就是要查找的素，则比较次数为1；在最坏情况下，最后一个素才是要找的素，则比较次数为n。这是找到素的情况。如果没有找到素，则要比较n次。因此，平均需要比较：找到素的情况×1/2+未找到素的情况×1/2=（1+2+┉+n）/n×1/2+n×1/2=(3n+1)/4，大约为3n/4。 73.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（ ） A)在顺序存储的线性表中寻找最大项 B)在顺序存储的线性表中进行顺序查找 C)在顺序存储的有序表中进行对分查找 D)在链式存储的有序表中进行查找【解析】寻找最大项，无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第1次查看的一个数据恰好是要找的数据，只需要比较1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是n和log2n，平均情况则是1~最坏情况的平均，因而是不同的。 74.线性表的长度为n。在最坏情况下，比较次数为n-1的算法是（ ） A)顺序查找 B)同时寻找最大项与最小项 C)寻找最大项 D)有序表的插入【解析】顺序查找要逐个查看所有素，会比较n次。在最坏情况下，寻找最大项无论如何需要查看表中的所有素，n个素比较次数为n-1。同时寻找最大项和最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个素的后面位置，则会比较n次。 75.下列叙述中正确的是（ ） A)二分查找法只适用于顺序存储的有序线性表 B)二分查找法适用于任何存储结构的有序线性表 C)二分查找法适用于有序循环链表 D)二分查找法适用于有序双向链表【解析】二分查找法（又称对分查找法）只适用于顺序存储的有序表。在此所说的有序表是指线性表的中素按值非递减排列（即从小到大，但允许相邻素值相等）。 76.设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为（ ） A)
B) C) D) 【解析】有序线性表的长度为n，设被查找素为x，则二分查找的方法如下：将x与线性表的中间项比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个素）为止。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较 次。 77.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为（ ） A)48 B)96 C)7 D)6【解析】对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较次。本题中n=97,最多需要的比较次数为，6<<7,故需要比较7次。 78.设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是（） A)顺序查找 B)寻找最大项 C)寻找最小项 D)有序表的二分查找【解析】在最坏情况下的比较次数：顺序查找为n，寻找最大项和最小项均为n-1，有序表的二分查找为。 79.设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为（ ） A)40 B)41 C)780 D)820【解析】对长度为n的线性表排序，在最坏情况下，冒泡排序需要经过 遍的从前住后的扫描和n/2遍的从后住前的扫描，需要比较的次数为。本题中n=40，故比较次数为40×（40-1）÷2=780。 80.在快速排序法中，每经过一次数据交换（或移动）后（ ） A)只能消除一个逆序 B)能消除多个逆序 C)不会产生新的逆序 D)消除的逆序个数一定比新产生的逆序个数多【解析】在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是：从线性表中选取一个素，设为T，将线性表中后面小于T的素移到前面，而前面大于T的素移到后面，结果就将线性表分成两部分（称两个子表），T插入到其分割线的位置处，这个过程称为线性表的分割，然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻素进行比较，可以实线通过一次交换而消除多个逆序，但由于均与T（基准素）比较，也可能会产生新的逆序。 81.设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为（ ） A)120 B)60 C)30 D)15【解析】简单插入排序在最坏情况下，即初始排序序列是逆序的情况下，比较次数为 ，移动次数为 。本题中n=16，16×（16-1）÷2=8×15=120。 82.在希尔排序法中，每经过一次数据交换后（ ） A)不会产生新的逆序 B)只能消除一个逆序 C)能消除多个逆序 D)消除的逆序个数一定比新产生的逆序个数多【解析】希尔排序法的基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。在子序列中每进行一次比较就有可能移去整个线性表中的多个逆序，从而改善整个排序过程的性能。 83.下列序列中不满足堆条件的是（ ） A)（98，95，93，94，89，90，76，80，55，49） B)（98，95，93，94，89，85，76，64，55，49） C)（98，95，93，94，89，90，76，64，55，49） D)（98，95，93，96，89，85，76，64，55，49）【解析】根据堆的定义，n个素的序列（ ,,…），当且仅当≤且≤时为小根堆，当且仅当 ≥ 且 ≥时为大根堆。D项中，=95，=96， <，但=89，>，不满足小根堆和大根堆条件。 84.设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)/2的是（ ） A)快速排序 B)堆排序 C)顺序查找 D)寻找最大项【解析】对于长度为n的线性表，最坏情况下查找或排序的次数如下表：
85.下列各组排序法中，最坏情况下比较次数相同的是（ ） A)简单选择排序与堆排序 B)简单插入排序与希尔排序 C)冒泡排序与快速排序 D)希尔排序与堆排序【解析】最坏情况下比较次数：简单选择排序为 ，堆排序为 ，简单插入排序为，希尔排序为，冒泡排序为，快速排序为。故比较次数相同的是冒泡排序与快速排序。 86.下列排序方法中，最坏情况下时间复杂度（即比较次数）最低的是（ ） A)快速排序 B)希尔排序 C)简单插入排序 D)冒泡排序【解析】最坏情况下，希尔排序需要比较 次，快速排序、简单插入排序、冒泡排序均需要比较 次，故希尔排序时间复杂度最低。 87.下列各排序法中，最坏情况下的时间复杂度最低的是（ ） A)堆排序 B)快速排序 C)希尔排序 D)冒泡排序【解析】最坏情况下，堆排序需要比较次，希尔排序需要比较次，快速排序、冒泡排序均需要比较次。故堆排序时间复杂度最低。 88.下面属于良好程序设计风格的是（ ） A)源程序文档化 B)程序效率第一 C)随意使用无条件转移语句 D)程序输入输出的随意性【解析】要形成良好的程序设计风格，主要应注意和考虑：源程序文档化；数据说明的次序规范化，说明语句中变量安排有序化，使用注释来说明复杂数据的结构；程序编写要做到清晰第一、效率第二，先保证程序正确再要求提高速度，避免不必要的转移；对所有的输入数据都要进行检验，确保输入数据的合法性。 89.下面不属于结构化程序设计原则的是（ ） A)逐步求精 B)自顶向下 C)模块化 D)可继承性【解析】结构化程序设计方法的原则包括：自顶向下、逐步求精、模块化、限制使用goto语句。可继承性是面向对象方法的特点。 90.结构化程序设计风格强调的是（ ） A)程序的执行效率 B)程序的易读性 C)不考虑goto语句的限制使用 D)程序的可移植性【解析】按结构化程序设计方法设计出的程序清晰易读，可理解性好，程序员能够进行逐步求精、程序证明和测试，以确保程序的正确性，程序容易阅读并被人理解，便于用户使用和维护。可见结构化程序设计风格强调的是易读性。 91.结构化程序的三种基本控制结构是（ ） A)顺序、选择和调用 B)过程、子程序和分程序 C)顺序、选择和重复（循环） D)调用、返回和转移【解析】1966年Boehm和Jacopini证明了程序设计语言仅仅使用顺序、选择和重复三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。 92.不属于对象构成成份的是（ ） A)规则 B)属性 C)方法（或操作） D)标识【解析】对象由一组表示其静态特征的属性和它执行的一组操作组成，对象名唯一标识一个对象。 93.下面对“对象”概念描述正确的是（ ） A)属性就是对象 B)操作是对象的动态属性 C)任何对象都必须有继承性 D)对象是对象名和方法的封装体【解析】对象是由描述该对象属性的数据以及可以对这些数据施加的所有操作封装在一起构成的统一体。对象可以做的操作表示它的动态行为，通常也称为方法或服务，属性即对象所包含的信息。对象可以有继承性，但并不是任何对象都必须有继承性。 94.下面不属于对象主要特征的是（ ） A)对象唯一性 B)对象分类性 C)对象多态性 D)对象可移植性【解析】对象有如下一些基本特点：①标识唯一性：指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。②分类性：指可以将具有相同属性和操作的对象抽象成类。③多态性：指同一个操作可以是不同对象的行为，不同对象执行同一类操作产生不同的结果。④封装性：从外面看只能看到对象的外部特征，对象的内部对外是不可见的。⑤模块独立性好。 95.将自然数集设为整数类I，则下面属于类I实例的是（ ） A)-518 B)5.18 C)518 D)518E-2【解析】类是具有共同属性、共同方法的对象的集合。类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。自然数集是全体非负整数组成的集合，A项是负数实例，B项是浮点数实例，D项是用科学计数法表示的浮点数实例。 96.下面叙述中正确的是（ ） A)软件是程序、数据及相关文档的集合 B)软件中的程序和文档是可执行的 C)软件中的程序和数据是不可执行的 D)软件是程序和数据的集合【解析】计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完成集合。程序、数据和相关文档又称为软件的三要素。 97.下面对软件描述错误的是（ ） A)文档是不可执行的 B)程序和数据是可执行的 C)软件文档是与程序开发、维护和应用无关的资料 D)软件是程序、数据及相关文档的集合【解析】软件是程序、数据及相关文档的集合。其中，程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令（语句）序列；数据是使程序能正常操纵信息的数据结构；文档是与程序开发、维护和使用有关的图文资料。可见，软件有两部分组成：一是机器可执行的程序和数据；二是机器不可执行的文档。 98.下面对软件特点描述正确的是（ ） A)软件具有明显的制作过程 B)软件在使用中存在磨损、老化问题 C)软件复制不涉及知识产权 D)软件是一种逻辑实体，具有抽象性【解析】软件具有以下特点：软件是一种逻辑实体，而不是物理实体，具有抽象性；软件的生产与硬件不同，它没有明显的制作过程；软件在运行、使用期间不存在磨损、老化问题；软件的开发、运行对硬件和环境具有依赖性；软件复杂性高，成本昂贵；软件开发涉及诸多的社会因素（包括软件知识产权及法律等问题）。 99.下面属于系统软件的是（ ） A)UNIX系统 B)ERP系统 C)办公自动化系统 D)学生成绩管理系统【解析】软件按功能可以分为应用软件、系统软件和支撑软件(或工具软件)。系统软件是管理计算机的资源，提高计算机使用效率并服务于其他程序的软件，如操作系统，编译程序，汇编程序，数据库管理系统和网络软件等。UNIX系统属于操作系统，故属于系统软件。ERP系统、办公自动化系统、学生成绩管理系统属于应用软件。 100.下面属于应用软件的是（ ） A)编译程序 B)Android操作系统 C)汇编程序 D)财务报表统计软件【解析】应用软件是为解决特定领域的应用而开发的软件。例如，事务处理软件，工程与科学计算软件，实时处理软件，嵌入式软件，人工智能软件等应用性质不同的各种软件。编译程序、Android操作系统、汇编程序属于系统软件，财务报表统计属于应用软件。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/82091.html
