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