1、国家二级 VB机试（数据结构与算法、程序设计基础）模拟试卷 2及答案与解析 一、选择题 1 算法的有穷性是指 ( )。 （ A）算法程序的运行时间是有限的 （ B）算法程序所处理的数据量是有限的 （ C）算法程序的长度是有限的 （ D）算法只能被有限的用户使用 2 下列叙述中正确的是 ( )。 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无关 （ B）算法的时间复杂度是指执行算法所需要的计算工作量 （ C）数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一 定相关 3 定义无符号整数类为 UInt，下面可以作为类 UInt实例化值的是 ( )。 （ A）
2、-369 （ B） 369 （ C） 0 369 （ D）整数集合 1， 2， 3， 4， 5 4 下列叙述中正确的是 ( )。 （ A）算法就是程序 （ B）设计算法时只需要考虑数据结构的设计 （ C）设计算法时只需要考虑结果的可靠性 （ D）以上三种说法都不对 5 下列关于线性链表的叙述中，正确的是 ( )。 （ A）各数据节点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致 （ B）各数 据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续 （ C）进行插入数据与删除数据时，不需要移动表中的元素 （ D）以上说法均不对 6 下列叙述中正确的是 ( )。 （ A）线性表的
3、链式存储结构与顺序存储结构所需要的存储空间是相同的 （ B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 （ C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 （ D）线性表的链式存储结构与顺序存储结构在存储空间的需求上没有可比性 7 一个栈的初始状态为空。现将元素 l、 2、 3、 4、 5、 A、 B、 C、 D、 E依次入栈，然后再依次出栈，则元素出栈的顺序是 ( )。 （ A） 12345ABCDE （ B） EDCBA54321 （ C） ABCDEl2345 （ D） 54321EDCBA 8 下列叙述中正确的是 ( )。 （ A）栈是一种 “先进先出
4、”的线性表 （ B）队列是一种 “后进先出 ”的线性表 （ C）栈与队列都是非线性结构 （ D）以上三种说法都不对 9 一个栈的初始状态为空。现将元素 1， 2， 3， A， B， C依次入栈，然后再依次出栈，则元素出栈的顺序是 ( )。 （ A） 1， 2， 3， A， B， C （ B） C， B， A， 1， 2， 3 （ C） C， B， A， 3， 2， 1 （ D） 1， 2， 3， C， B， A 10 下列叙述中正确的是 ( )。 （ A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 （ B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 （ C）在循
5、环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 （ D）循环队列中元素的个数是由队头指针和队尾指针共同决定 11 下列数据结构中，能够按照 “先进后出 ”原则存取数据的是 ( )。 （ A）循环队列 （ B）栈 （ C）队列 （ D）二叉树 12 下列关于栈叙述中正确的是 ( )。 （ A）栈顶元素能最先被删除 （ B）栈底元素最后才能被删除 （ C）栈底元素永远不能被删除 （ D）栈底元素是最先被删除 13 下列叙述中正确的是 ( )。 （ A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 （ B）循环队列中的元素个数随队头指针的变化而动态变化 （ C）循环队列中的元素
6、个数随队尾指针的变化而动态变化 （ D）以上说法都不对 14 下列叙述中正确的 是 ( )。 （ A）线性表链式存储结构的存储空间一般要少于顺序存储结构 （ B）线性表链式存储结构与顺序存储结构的存储空间都是连续的 （ C）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 （ D）以上说法均错误 15 支持子程序调用的数据结构是 ( )。 （ A）栈 （ B）树 （ C）队列 （ D）二叉树 16 某二叉树有 5个度为 2的节点，则该二叉树中的叶子节点数是 ( )。 （ A） 10 （ B） 8 （ C） 6 （ D） 4 17 一棵二叉树共有 25个节点，其中 5各 是叶子节点，则
7、度为 1的节点数为 ( )。 （ A） 16 （ B） 10 （ C） 6 （ D） 4 18 一棵二叉树中共有 80个叶子节点与 70个度为 1的节点，则该二叉树中的总节点数为 ( )。 （ A） 219 （ B） 229 （ C） 230 （ D） 231 19 对下图二叉树 进行前序遍历的结果为 ( )。 （ A） DYBEAFCZX （ B） YDEBFZXCA （ C） ABDYECFXZ （ D） ABCDEFXYZ 20 对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n-1) 2的排序方 法是 ( )。 （ A）快速排序 （ B）冒泡排序 （ C）直接插入排序 （ D
8、）堆排序 21 对长度为 10的线性表进行冒泡排序，最坏情况下需要比较的次数为 ( )。 （ A） 9 （ B） 10 （ C） 45 （ D） 90 22 结构化程序设计的基本原则不包括 ( )。 （ A）多态性 （ B）自顶向下 （ C）模块化 （ D）逐步求精 23 结构化程序设计中，下面对 goto语句使用描述正确的是 ( )。 （ A）禁止使用 goto语句 （ B）使用 goto语句程序效率高 （ C）应 避免滥用 goto语句 （ D）以上说法均错误 24 在面向对象方法中，不属于 “对象 ”基本特点的是 ( )。 （ A）一致性 （ B）分类性 （ C）多态性 （ D）标识唯一
9、性 25 面向对象方法中，继承是指 ( )。 （ A）一组对象所具有的相似性质 （ B）一个对象具有另一个对象的性质 （ C）各对象之间的共同性质 （ D）类之间共享属性和操作的机制 国家二级 VB机试（数据结构与算法、程序设计基础）模拟试卷 2答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 算法原则 上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性是指算法程序的运行时间是有限的。 【知识模块】 数据结构与算法 2 【正确答案】 B 【试题解析】 算法的效率与问题的规模和数据的存储结构都有关， A错误。算法的时间复杂度，是指执行算法所需要的计算工作量， B正确。由于
10、数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此数据的逻辑结构和存储结构不是一一对应的， C错误。算法的时间复杂度和空间复杂度没有直接的联系， D错误。 【知识模块】 数据结构与算法 3 【正确答案】 B 【试题解析】 只有 B选项 369可以用无符号整数来表示和存储。 A选项一 369有负号，选项 C 0 369是小数都不能用无符号整数类存储。选项 D是一个整数集合得用数组来存储。 【知识模块】 数据结构与算法 4 【正确答案】 D 【试题解析】 算法是解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以 A错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑
11、算法的控制结构。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 一般来说，在线性表的链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插入和删除都不需要移动表中的元素，只需要改变节点的指针域即可。 【知识模块】 数据结构与算法 6 【正确答案】 B 【试题解析】 线性链式存储结构中每个节点都由数据域与指针域两部分组成，增加了存储空间，所以一般要多于顺序存储结构。 【知识模块】 数据结构与算法 7 【正确答案】 B 【试题解析】 栈是按 “先进后出 ”的原则组织数据的，所以入栈 最早的最后出栈，所以选择 B。
12、【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 栈是一种 “先进后出 ”的线性表，队列是一种先进先出的线性表，栈与队列都是线性结构。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 栈的修改是按 “后进先出 ”的原则进行的，所以顺序应与入栈顺序相反，故选 C。 【知识模块】 数据结构与算法 10 【正确答案】 D 【试题解析】 循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的，所以 A错误。在循环队 列中只需要队头指针与队尾两个指针来共同反映队列中元素的动态变化情况，所以 B与 C错误。 【知识模块】 数据结构与算法 11 【正确答案】 B 【试题解
13、析】 栈是按 “先进后出 ”的原则组织数据的。队列是先进先出的原则组织数据。 【知识模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 栈是 “先进后出 ”的数据结构，所以栈顶元素是最后入栈最先被删除。栈底元素最先进却最后被删除。所以选择 A。 【知识模块】 数据结构与算法 13 【正确答案】 A 【试题解析】 在 循环队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向排头元素的前一个位置。因此，从队头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素均为队列中的元素。所以循环队列中的元素个数与队头指针和队尾指针的变化而变化， A
14、正确。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 线性表的顺序存储结构具备如下两个基本特征： (1)线性表中的所有元素所占的存储空间是连续的； (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。用一 组任意的存储单元来依次存放线性表的节点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此 C正确。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时首先要保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到
15、主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为 A。 【知识模块】 数据结构与算法 16 【正 确答案】 C 【试题解析】 根据二叉树的基本性质 3：在任意一棵二叉树中，度为 0的叶子节点总是比度为 2的节点多一个，所以本题中是 5+1=6个。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 根据二叉树的性质 3：在任意一棵二又树中，度数为 0的叶子节点总是比度数为 2的节点多一个，所以本题中度数为 2的节点时 5-1=4个，所以度数为 1的节点的个数时 25-5-4=16个。 【知识模块】 数据结构与算法 18 【正确答案】 B 【试题解析
16、】 二叉树中，度为 0的节 点数等于度为 2的节点数加 1，即 n2=n0-1，叶子节点即度为 0，则 n2=79，总节点数为 n0+n1+n2=80+70+79=229，答案为B。 【知识模块】 数据结构与算法 19 【正确答案】 C 【试题解析】 前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树。并且，在遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作。否则： 访问根节点； 前序遍历左子树； 前序遍历右子树，故 C正确。 【知识模块】 数据结构与算法 20 【正确答案】 D
17、【试题解析】 除了堆排序算法的比较次数是 0(nlog2n)，其他的都是 n(n-1) 2。 【知识模块】 数据结构与算法 21 【正确答案】 C 【试题解析】 冒泡法是在扫描过程中逐次比较相邻两个元素的大小，最坏的情况是每次比较都要将相邻的两个元素互换，需要互换的次数为9+8+7+6+5+4+3+2+1=45，选 C。 【知识模块】 数据结构与算法 22 【正确答案】 A 【试题解析】 结构化程序设计的思想 包括：自顶向下、逐步求精、模块化、限制使用 goto语句，所以选择 A。 【知识模块】 程序设计基础 23 【正确答案】 C 【试题解析】 结构化程序设计中，要注意尽量避免 goto语句的使用，故选 C。 【知识模块】 程序设计基础 24 【正确答案】 A 【试题解析】 对象有如下一些基本特点：标识唯一性、分类性、多态性、封装性、模块独立性好。所以选择 A。 【知识模块】 程序设计基础 25 【正确答案】 D 【试题解析】 继承是面向对象的方法的一个主要特征，是使用已有 的类的定义作为基础建立新类的定义技术。广义的说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们，所以说继承是指类之间共享属性和操作的机制。 【知识模块】 程序设计基础
