1、国家二级 VB机试（数据结构与算法、程序设计基础）模拟试卷 1及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）循环队列是队列的一种链式存储结构 （ B）循环队列是队列的一种顺序的存储结构 （ C）循环队列是非线性结构 （ D）循环队列是一种逻辑结构 2 下列叙述中正确的是 ( )。 （ A）一个算法的空间复杂度大，则其时间复杂度也必定大 （ B）一个算法的空间复杂度大，则其时间复杂度必定小 （ C）一个算法的时间复杂度大，则其空间复杂度必定小 （ D）算法的时间复杂度与空间 复杂度没有直接关系 3 算法的空间复杂度是指 ( )。 （ A）算法在执行过程中所需要的计算机存储空
2、间 （ B）算法所处理的数据量 （ C）算法程序中的语句或指令条数 （ D）算法在执行过程中所需要的临时工作单元数 4 下列叙述中正确的是 ( )。 （ A）程序执行的效率与数据的存储结构密切相关 （ B）程序执行的效率只取决于程序的控制结构 （ C）程序执行的效率只取决于所处理的数据量 （ D）以上说法均错误 5 下列叙述中正确的是 ( )。 （ A）有一个以上根节点的数据结构不一定 是非线性结构 （ B）只有一个根节点的数据结构不一定是线性结构 （ C）循环链表是非线性结构 （ D）双向链表是非线性结构 6 下列叙述中正确的是 ( )。 （ A）顺序存储结构的存储一定是连续的，链式存储结构
3、的存储空间不一定是连续的 （ B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 （ C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 （ D）链式存储结构比顺序存储结构节省存储空间 7 下列关于栈的叙述正确的是 ( )。 （ A）栈按 “先进先出 ”组织数据 （ B）栈 按 “先进后出 ”组织数据 （ C）只能在栈底插入数据 （ D）不能删除数据 8 下列叙述中正确的是 ( )。 （ A）栈是 “先进先出 ”的线性表 （ B）队列是 “先进后出 ”的线性表 （ C）循环队列是非线性结构 （ D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 9 下列关于栈的叙述中
4、，正确的是 ( )。 （ A）栈底元素一定是最后入栈的元素 （ B）栈顶元素一定是最先入栈的元素 （ C）栈操作遵循先进后出的原则 （ D）以上说法均错误 10 下列与队列结构有关联的是 ( )。 （ A）函数的递归调用 （ B）数组元素的引用 （ C）多重循环的执行 （ D）先到先服务的作业调度 11 下列数据结构中，属于非线性结构的是 ( )。 （ A）循环队列 （ B）带链队列 （ C）二叉树 （ D）带链栈 12 对于循环队列，下列叙述中正确的是 ( )。 （ A）队头指针是固定不变的 （ B）队头指针一定大于队尾指针 （ C）队头指针一定小于队尾指针 （ D）队头指针可以大于队尾指针
5、，也可以小于队尾指针 13 设循环队列的存储空间为 Q(1： 35)，初始状态为 front=rear=35。现经过一系列入队与退队运算后， front=15， rear=15，则循环队列中的元素个数为 ( )。 （ A） 15 （ B） 16 （ C） 20 （ D） 0或 35 14 下列叙述中正确的是 ( )。 （ A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 （ B）在栈中，栈顶指针不变，栈巾元素随栈底指针的变化而动态变化 （ C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而变化 （ D）以上说法均不对 15 下列链表中，其逻辑结构属于非线性结构的是 ( )。 （ A）
6、二叉链表 （ B）循环链表 （ C）双向链表 （ D）带链的栈 16 某系统总体结构图如下图所示，该系统总体结构图的深度是 ( )。（ A） 7 （ B） 6 （ C） 3 （ D） 2 17 下列关于二叉树的叙述中，正确的是 ( )。 （ A）叶子节点总是比度为 2的节点少一个 （ B）叶子节点总是比度为 2的节点多一个 （ C）叶子节点数是度为 2的节点数的两倍 （ D）度为 2的节点数是度为 1的节点数的两倍 18 某二叉树共有 7个节点，其中叶子节点有 1个，则该二叉树的深度为 (假设根节点在第 1层 )( )。 （ A） 3 （ B） 4 （ C） 6 （ D） 7 19 某二叉树共
7、有 12个节点，其中叶子节点只有 1个。则该二叉树的深度为 (根节点在第 1层 )( )。 （ A） 3 （ B） 6 （ C） 8 （ D） 12 20 在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。 （ A） O(n) （ B） O(n2) （ C） O(log2n) （ D） O(nlog2n) 21 下列排序方法中，最坏情况下比较次数最少的是 ( )。 （ A）冒泡排序 （ B）简单选择排序 （ C）直接插入排序 （ D）堆排序 22 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 ( )。 （ A） n （ B） n-1 （ C） n(n-1)
8、（ D） n(n-1) 2 23 结构化程序所要求的基本结构不包括 ( )。 （ A）顺序结构 （ B） goto跳转 （ C）选择 (分支 )结构 （ D）重复 (循环 )结构 24 下列选项中属于面向对象设计方法主要特征的是 ( )。 （ A）继承 （ B）自顶向下 （ C）模块化 （ D）逐步求精 25 下面对对象概念描述正确的是 ( )。 （ A）对象间的通信靠消息传递 （ B）对象是名字和方法的封装体 （ C）任何对象必须有继承性 （ D）对象的多态性是指一个对象有多个操作 国家二级 VB机试（数据结构与算法、程序设计基础）模拟试卷 1答案与解析 一、选择题 1 【正确答案】 B 【
9、试题解析】 循环队列是队列的一种顺序存储结构，用队尾指针指向队列中的队尾元素，用排头指针指向排头元素的前一个位置。因此可以说，队列的顺序存储结构一般采用循环队列的形式。故答案为 B。 【知识模块】 数据结构与算法 2 【正确答案 】 D 【试题解析】 算法的空间复杂度是指算法在执行过程中所需要的内存空间，算法的时间复杂度是指执行算法所需要的计算工作量，两者之间并没有直接关系，答案为 D。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 算法的空间复杂度是指算法在执行过程中所需要的内存空间。所以选择 A。 【知识模块】 数据结构与算法 4 【正确答案】 A 【试题解析】 程序执
10、行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。 【知识模块】 数据结构与算法 5 【正确答案】 B 【试题解析】 线性结构应满足：有且只有一个根节点与每个节点最多有一个前件，也最多有一个后件，所以 B正确。所以有一个以上根节点的数据结构一定是非线性结构，所以 A错误。循环链表和双向链表都是线性结构的数据结构。 【知识模块】 数据结构与算法 6 【正确答案】 A 【试题解析】 链式存储结构既可以针对线性结构也可以针对非线性结构，所以 B与 C错误。链式存储结构中每个节点都由数据域与指针域两部分组成，增加了存储空间，所以 D错误。 【知识模块】 数据结构与算法 7
11、 【正确答案】 B 【试题解析】 栈是按 “先进后出 ”的原则组织数据的，数据的插入和删除都在栈顶进行操作。 【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 栈是 “先进后出 ”的线性表，所以 A错误。队列是 “先进先出 ”的线性表，所以 B错误。循环队列是线性结构的线性表，所以 C错误。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元 素，从而也是最后才能被删除的元素。栈的修改是按 “后进先出 ”的原则进行的。因此，栈称为 “先进后出 ”表，或 “后进先出 ”表，所以选择C。
12、 【知识模块】 数据结构与算法 10 【正确答案】 D 【试题解析】 队列的修改是依 “先进先出 ”的原则进行的， D正确。 【知识模块】 数据结构与算法 11 【正确答案】 C 【试题解析】 树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。 【知识模块】 数据结构与算法 12 【正确答案】 D 【试题解析】 循环队列的队 头指针与队尾指针都不是固定的，随着人队与出队操作要进行变化。因为是循环利用的队列结构，所以对头指针有时可能大于队尾指针，有时也可能小于队尾指针。 【知识模块】 数据结构与算法 13 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中
13、的队尾元素，用队头指针 front指向队头元素的前一个位置。在循环队列中进行出队、入队操作时，头尾指针仍要加 1，朝前移动。只不过当头尾指针指向向量上界时，其加 1操作的结果是指向向量的下界 0。由于入队时尾指针向前追赶头指针。出队时头指针向前追赶 尾指针，故队空和队满时，头尾指针均相等。答案为 D选项。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 栈是 “先进后出 ”的数据结构，在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来操作，所以选择 C。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 在定义的链表中，若只含有一个指针域来存放
14、下一个元素地址，称这样的链表为单链表或线性链表。带链的栈可以用来收集计算机存储空间中所有空闲的存储节点，是线性表。在单链表中的节点中增加一 个指针域指向它的直接前件，这样的链表，就称为双向链表 (一个节点中含有两个指针 )，也是线性链表。循环链表具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。属于线性链表。二叉链表是二叉树的物理实现，是一种存储结构，不属于线性结构。答案为 A选项。 【知识模块】 数据结构与算法 16 【正确答案】 C 【试题解析】 根据总体结构图可以看出该树的深度为 3，比如： XY系统 功能 2功能 2 1，就是最深的度
15、数的一个表现。 【知识模块】 数据结构 与算法 17 【正确答案】 B 【试题解析】 根据二叉树的基本性质 3：在任意一棵二叉树中，度为 0的叶子节点总是比度为 2的节点多一个。所以选择 B。 【知识模块】 数据结构与算法 18 【正确答案】 D 【试题解析】 根据二叉树的性质 3：在任意一棵二叉树中，度为 0的叶子节点总比度为 2的节点多一个，所以本题中度为 2的节点为 1-1=0个，所以知道本题目中的二叉树的每个节点都有一个分支，所以 7个节点共 7层，即度为 7。 【知识模块】 数据结构与算法 19 【正确答案】 D 【试 题解析】 二叉树中，度为 0的节点数等于度为 2的节点数加 1，
16、即 n2=n0-1，叶子节点即度为 0， n0=1，则 n2=0，总节点数为 12=n0+n1+n2=1+n1+0，则度为 1的节点数 n1=11，故深度为 12，选 D。 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为 n的有序线性表，在最坏情况卞，二分法查找只需要比较 log2n次，而顺序查找需要比较 n次。 【知识模块】 数据结构与算法 21 【正确答案】 D 【试题解析】 冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较 n(n-1) 2次，而堆排序在最坏情况下需要比较的次数是 nlog2
17、n。 【知识模块】 数据结构与算法 22 【正确答案】 D 【试题解析】 快速排序最坏情况就是每次选的基准数都和其他数做过比较，共需比较 (n-1)+(n-2)+1=n(n -1) 2，选 D。 【知识模块】 数据结构与算法 23 【正确答案】 B 【试题解析】 1966年 Boehm和 Jaeopini证明了程序设计语言仅仅使用顺序、选择和 重复三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。 【知识模块】 程序设计基础 24 【正确答案】 A 【试题解析】 面向对象基本方法的基本概念有对象、类和实例、消息、继承与多态性，所以选择 A。 【知识模块】 程序设计基础 25 【正确答案】 A 【试题解析】 对象之间进行通信的构造叫做消息， A正确。多态性是指同一个操作可以是不同对象的行为。 D错误。对象不一定必须有继承性， C错误。封装性是指从外面看只能看到对象的外部特征，而不知道也无须知道数据的具体结构以及实现 操作， B错误。 【知识模块】 程序设计基础
