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