1、国家二级公共基础知识（数据结构与算法、软件工程基础）模拟试卷1及答案与解析 一、选择题 下列各题 A、 B、 C、 D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。 1 下列叙述中正确的是 （ A）对长度为 n的有序链表进行查找，最坏情况下需要的比较次数为 n （ B）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (n 2) （ C）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (log2n) （ D）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (nlog2n) 2 在长度为 n的有序线性表中进行二分查找，最坏情况
2、下需要比较的次数是 （ A） O(n) （ B） 0(n2) （ C） O(log2n) （ D） O(nlog2n) 3 下列数据结构中，能用二分法进行查找的是 （ A）顺序存储的有序线性表 （ B）线性链表 （ C）二叉链表 （ D）有序线性链表 4 冒泡排序在最坏情况下的比较次数是 （ A） n(n+1) 2 （ B） nlog2n （ C） n(n一 1) 2 （ D） n 2 5 对长度为 10的线性表进行冒泡排序，最坏情况下需要比较 的次数为 （ A） 9 （ B） 10 （ C） 45 （ D） 90 6 对于长度为 n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的
3、是 （ A）冒泡排序为 n 2 （ B）冒泡排序为 n （ C）快速排序为 n （ D）快速排序为 n(n-1) 2 7 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 （ A） n （ B） n-1 （ C） n(n1) （ D） n(n1) 2 8 对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n一 1) 2的排序方法是 （ A）快速排序 （ B）冒泡 排序 （ C）直接插入排序 （ D）堆排序 9 下列排序方法中，最坏情况下比较次数最少的是 （ A）冒泡排序 （ B）简单选择排序 （ C）直接插入排序 （ D）堆排序 10 下列叙述中正确的是 （ A）程序执行的效率
4、与数据的存储结构密切相关 （ B）程序执行的效率只取决于程序的控制结构 （ C）程序执行的效率只取决于所处理的数据量 （ D）以上都不正确 11 下列描述中，不符合良好程序设计风格要求的是 （ A）程序的效率第一，清晰第二 （ B）程序的可读性好 （ C）程序中要有必要的注释 （ D）输入数据前要有提示信息 12 结构化程序所要求的基本结构不包括 （ A）顺序结构 （ B） GOTO跳转 （ C）选择 (分支 )结构 （ D）重复 (循环 )结构 13 下列选项中不属于结构化程序设计原则的是 （ A）可封装 （ B）自顶向下 （ C）模块化 （ D）逐步求精 14 结构化程序设计的基本原则不包
5、括 （ A）多元性 （ B）自顶向下 （ C）模块化 （ D）逐步求精 15 下列选项中不属于结构化程序设计方法的是 （ A）自顶向下 （ B）逐步求精 （ C）模块化 （ D）可复用 16 结构化程序设计中，下面对 goto语句使用描述正确的是 （ A）禁止使用 goto语句 （ B）使用 goto语句程序效率高 （ C）应避免滥用 goto语句 （ D） goto语句确实一无是处 17 下列选项中不符合良好程序设计风格的是 （ A）源程序要文档化 （ B）数据说明的次序要规范化 （ C）避免滥用 goto语句 （ D）模块设计要保证高耦合、高内聚 18 面向对象方法中，继承是指 （ A）一
6、组对象所具有的相似性质 （ B）一个对象具有另一个对象的性质 （ C）各对象之间的共同性质 （ D） 类之间共享属性和操作的机制 19 下列选项中属于面向对象设计方法主要特征的是 （ A）继承 （ B）自顶向下 （ C）模块化 （ D）逐步求精 20 在面向对象方法中，不属于 “对象 ”基本特点的是 （ A）一致性 （ B）分类性 （ C）多态性 （ D）标以唯一性 21 定义无符号整数类为 UInt，下面可以作为类 UInt实例化值的是 （ A） -369 （ B） 369 （ C） 0 369 （ D）整数集合 1， 2， 3， 4， 5 22 下面对对象概念描述正确的是 （ A）对象间的
7、通信靠消息传递 （ B）对象是名字和方法的封装体 （ C）任何对象必须有继承性 （ D）对象的多态性是指一个对象有多个操作 23 在面向对象方法中，实现信息隐蔽是依靠 （ A）对象的继承 （ B）对象的多态 （ C）对象的封装 （ D）对象的分类 24 下列选项中不属于面向对象程序设计特征的是 （ A）继承性 （ B）多态性 （ C）类比性 （ D）封装性 国家二级公共基础知识（数据结构与算法、软件工程基础）模拟试卷1答案与解析 一、选择题 下列各题 A、 B、 C、 D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。 1 【正确答案】 A 【试题解析】 本题主要考查的知
8、识点为查找技术。顺序查找的使用情况： 线性表为无序表； 表采用链式存储结构。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。 【知识模块】 数据结构与算法 2 【正确答案】 C 【试题解析】 对于长度为 n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较 n次。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 二分法查找只适应于顺序存储的有序表。 有序表是指线性表中的元素按值非递减排序 (即从小到大，但允许相邻元素值相等 )的表。 【知识模块】 数据结构与算法 4 【正确答案】 C 【试题解析】 对 n个结点的线性表采用冒泡排序，在最坏情
9、况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为n(n-1) 2。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 线性表的长度为 n，最坏情况下冒泡排序需要比较的次数为 n(n-1) 2。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为 n(n-1)2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与算法 7 【正确答
10、案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫 描和 n 2遍的从后往前的扫描，需要的比较次数为 n(n-1)2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序 n(n-1) 2、快速排序 n(n-1) 2、简单插入排序 n(n-1) 2、希尔排序 O(n1.5)、简单选择排序 n(n-1) 2、堆排序 O(nlog2n)。 【知识模块】 数据结构与算法 9 【正确答案】 D
11、 【试题 解析】 冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为： n(n-1) 2。而堆排序法在最坏的情况下需要比较的次数为 O(nlog2n)。其中堆排序的比较次数最少。 【知识模块】 数据结构与算法 10 【正确答案】 A 【试题解析】 影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。 【知识模块】 程序设计基础 11 【正确答案】 A 【试题解析】 一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序设计风格总体而言应该
12、强调简单和清晰，程序必须是可以理解的。著名的 “清晰第一，效率第二 ”的论点已成为当今主导的程序设计风格。 【知识模块】 程序设计基础 12 【正确答案】 B 【试题解析】 结构化程序的基本结构有：顺序结构、选择结构和循环结构，没有GOTO跳转结构。 【知识模块】 程序设计基础 13 【正确答案】 A 【试题解析】 结构化设计方法的主要原则可以概括为自顶向下、逐步求精、模块化 、限制使用 goto语句。 【知识模块】 程序设计基础 14 【正确答案】 A 【试题解析】 结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化和限制使用 GOTO语句，其中不包括多态性。 【知识模块】
13、程序设计基础 15 【正确答案】 D 【试题解析】 结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化，限制使用 goto语句。自顶向下是指程序设计时应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。逐步求精是指对复杂问题应设计一些子目标过渡 ，逐步细化。模块化是把程序要解决的总目标先分解成分目标，再进一步分解成具体的小目标，把每个小目标称为一个模块。可复用性是指软件元素不加修改成稍加修改便可在不同的软件开发过程中重复使用的性质。软件可复用性是软件工程追求的目标之一，是提高软件生产效率的最主要方法，不属于结构化程序设计方法。 【知识模块】 程序设计基础 16 【正确答案
14、】 C 【试题解析】 滥用 goto语句确实有害，应尽量避免；完全避免使用 goto语句并非是明智的方法。有些地方使用 goto语句会使程序流程更清楚、效率更高；争论的焦 点不应该放在是否取消 goto语句，而应该放在用在什么程序结构上。 【知识模块】 程序设计基础 17 【正确答案】 D 【试题解析】 一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序设计风格总体而言应该强调简单和清晰，程序必须是可以理解的。可以认为，著名的 “清晰第一、效率第二 ”的论点已成为当今主导的程序设计风格。良好的程序设计风格主要应注重和考虑下列几个因素： 源程序文档化，包括下列三个方面： A
15、)符号的命名应具有一定的含义： B)正确的注释能够帮助读者理解程序； C)视觉组 织，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。 数据说明的方法，包括下列三个方面： A)数据说明的次序规范化； B)说明语句中变量安排有序化； C)使用汴释来说明复杂数据的结构。 语句的结构应该简单直接，不应该为提高效率而把语句复杂化。 输入和输出方式和风格应尽可能方便用户的使用。 【知识模块】 程序设计基础 18 【正确答案】 D 【试题解析】 面向对象方法中，继承是使用已有的类定义作为基础建立新类的定义技术。广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。 【知识模块】 程序设
16、计基础 19 【正确答案】 A 【试题解析】 而向对象设计方法的主要特征订封装性、继承性和多态性。而结构化程序设计方法的主要原则有自顶向下，逐步求精，模块化，限制使用 goto语句。 【知识模块】 程序设计基础 20 【正确答案】 A 【试题解析】 对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。 【知识模块】 程序设计基础 21 【正确答案】 B 【试题解析】 UInt表示的是无符号整数类，所以它的每个实例都是一个无符号整 数，所以排除选项 A)和选项 C)，选项 D)是整数集合，所以也排除。 【知识模块】 程序设计基础 22 【正确答案】 A 【试题解析】 对象是面向对象
17、方法中最基本的概念。操作描述了对象执行的功能，通过消息传递，还可以为其他对象使用。操作过程是被封装在对象中，用户看不到，称之为对象的封装性。对象的多态性是指同一个操作可以是不同对象的行为。不是所有的对象都必须有继承性。 【知识模块】 程序设计基础 23 【正确答案】 C 【试题解析】 对象的封装性是指从外部看只能看剑对象的外部特征 ，即只需知道数据的取值范围和可以对该数据施加的操作，而不需要知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。 【知识模块】 程序设计基础 24 【正确答案】 C 【试题解析】 而向对象程序设计的三个主要特征是：封装性、继承性和多态性。封装性即只需知道数据的取值范围和可以对该数据施加的操作，而无需知道数据的具体结构以及实现操作的算法。继承性是指使用已有的类定 义作为基础建市新类的定义技术。对象根据所接受的消息而做出动作，同样的消息被不同的刘象接受时可导致完伞不同的行动，该现象称为多态性。 【知识模块】 程序设计基础
