1、国家二级 VF机试（数据结构与算法）模拟试卷 1及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）循环队列是队列的一种链式存储结构 （ B）循环队列是队列的一种顺序存储结构 （ C）循环队列是非线性结构 （ D）循环队列是一种逻辑结构 2 算法的有穷性是指 ( )。 （ A）算法程序的运行时间是有限的 （ B）算法程序所处理的数据量是有限的 （ C）算法程序的长度是有限的 （ D）算法只能被有限的用户使用 3 下列叙述中正确的是 ( )。 （ A）一个算法的空间 复杂度大，则其时间复杂度也必定大 （ B）一个算法的空间复杂度大，则其时间复杂度必定小 （ C）一个算法的时间复杂
2、度大，则其空间复杂度必定小 （ D）算法的时间复杂度与空间复杂度没有直接关系 4 下列叙述中正确的是 ( )。 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无关 （ B）算法的时间复杂度是指执行算法所需要的计算工作量 （ C）数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一定相关 5 算法的空间复杂度是指 ( )。 （ A）算法在执行过 程中所需要的计算机存储空间 （ B）算法所处理的数据量 （ C）算法程序中的语句或指令条数 （ D）算法在执行过程中所需要的临时工作单元数 6 定义无符号整数类为 UInt，下面可以作为类 UInt实例化值的是 ( )。
3、 （ A）一 369 （ B） 369 （ C） 0 369 （ D）整数集合 1， 2， 3， 4， 5 7 下列叙述中正确的是 ( )。 （ A）程序执行的效率与数据的存储结构密切相关 （ B）程序执行的效率只取决于程序的控制结构 （ C）程序执行的效率只取决于所处理的数据量 （ D）以上说法均错误 8 下列叙述正确的是 ( )。 （ A）算法就是程序 （ B）设计算法时只需要考虑数据结构的设计 （ C）设计算法时只需要考虑结果的可靠性 （ D）以上三种说法都不对 9 下列叙述中正确的是 ( )。 （ A）有一个以上根节点的数据结构不一定是非线性结构 （ B）只有一个根节点的数据结构不一定
4、是线性结构 （ C）循环链表是非线性结构 （ D）双向链表是非线性结构 10 下列关于线性链表的叙述中，正确的是 ( )。 （ A）各数据节点的存储空间可以不连续，但它们 的存储顺序与逻辑顺序必须一致 （ B）各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续 （ C）进行插入数据与删除数据时，不需要移动表中的元素 （ D）以上说法均不对 11 下列叙述中正确的是 ( )。 （ A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 （ B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 （ C）顺序存储结构能存储有序表，链式存储结构不能存储有序表
5、（ D）链式存储结构比顺序存储结构节省存储空间 12 下列叙述中正确的 是 ( )。 （ A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 （ B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 （ C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 （ D）线性表的链式存储结构与顺序存储结构在存储空间的需求上没有可比性 13 下列关于栈的叙述正确的是 ( )。 （ A）栈按 “先进先出 ”组织数据 （ B）栈按 “先进后出 ”组织数据 （ C）只能在栈底插入数据 （ D）不能删除数据 14 一个栈的初始状态为空。现将元素 1、 2、 3、 4、 5、 A
6、、 B、 C、 D、 E依次入栈，然后再依次出栈，则元素出栈的顺序是 ( )。 （ A） 12345ABCDE （ B） EDCBA54321 （ C） ABCDE12345 （ D） 54321EDCBA 15 下列叙述中正确的是 ( )。 （ A）栈是 “先进先出 ”的线性表 （ B）队列是 “先进后出 ”的线性表 （ C）循环队列是非线性结构 （ D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 16 下列叙述中正确的是 ( )。 （ A）栈是一种先进先出的线性表 （ B）队列是一种后进先出的线性表 （ C）栈与队列都是非线性结构 （ D）以上三种说法都不对 17 下列关于栈
7、的叙述中，正确的是 ( )。 （ A）栈底元素一定是最后入栈的元素 （ B）栈顶元素一定是最先入栈的元素 （ C）栈操作遵循先进后出的原则 （ D）以上说法均错误 18 一个栈的初始状态为空。现将元素 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 19 下列与队列结构有关联的是 ( )。 （ A）函数的递归调用 （ B）数组元素的引用 （ C）多重循环的执行 （ D）先到先服务的
8、作业调度 20 下列叙述中正确的是 ( )。 （ A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 （ B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 （ C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 （ D）循环队列中元素的个数是由队头指针和队尾指针共同决定 21 下列数据结构中， 属于非线性结构的是 ( )。 （ A）循环队列 （ B）带链队列 （ C）二叉树 （ D）带链栈 22 下列数据结构中，能够按照 “先进后出 ”原则存取数据的是 ( )。 （ A）循环队列 （ B）栈 （ C）队列 （ D）二叉树 23 对于循环队列，下列叙述中正
9、确的是 ( )。 （ A）队头指针是固定不变的 （ B）队头指针一定大于队尾指针 （ C）队头指针一定小于队尾指针 （ D）队头指针可以大于队尾指针，也可以小于队尾指针 24 下列关于栈叙述中正确的是 ( )。 （ A）栈顶元素最先能被删除 （ B）栈底元素最后才能被删除 （ C）栈底元素永远不能被删除 （ D）栈底元素最先被删除 25 设循环队列的存储空间为 Q(1： 35)，初始状态为 front=rear=35。现经过一系列入队与退队运算后， front=15， rear=15，则循环队列中的元素个数为 ( )。 （ A） 15 （ B） 16 （ C） 20 （ D） 0或 35 26
10、 下列叙述中正确的是 ( )。 （ A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 （ B）循环队列中的元素个数随 队头指针的变化而动态变化 （ C）循环队列中的元素个数随队尾指针的变化而动态变化 （ D）以上说法都不对 27 下列叙述中正确的是 ( )。 （ A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 （ B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 （ C）在栈中栈底指针不变，栈中元素随栈顶指针的变化而变化 （ D）以上说法均不对 28 下列叙述中正确的是 ( )。 （ A）线性表链式存储结构的存储空间一般要少于顺序存储结构 （ B）线性表链式存
11、储结构与顺序存储结 构的存储空间都是连续的 （ C）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 （ D）以上说法均错误 29 下列链表中，其逻辑结构属于非线性结构的是 ( ) （ A）二叉链表 （ B）循环链表 （ C）双向链表 （ D）带链的栈 30 支持子程序调用的数据结构是 ( )。 （ A）栈 （ B）树 （ C）队列 （ D）二叉树 31 某系统总体结构图如下图所示： 该系统总体结构图的深度是 ( )。 （ A） 7 （ B） 6 （ C） 3 （ D） 2 32 某二叉树有 5个度为 2的节点，则该二叉树中的叶子节点数是 ( )。 （ A） 10 （ B） 8 （
12、C） 6 （ D） 4 33 下列关于二叉树的叙述中，正确的是 ( )。 （ A）叶子节点总是比度为 2的节点少一个 （ B）叶子节点总是比度为 2的节点多一个 （ C）叶子节点数是度为 2的节点数的两倍 （ D）度为 2的节点数是度为 1的节点数的两倍 34 一棵二叉树共有 25个节点，其中 5个是叶子节点，则度为 1的节点数为 ( )。 （ A） 16 （ B） 10 （ C） 6 （ D） 4 35 某二叉树共有 7个节点，其 中叶子节点有 1个，则该二叉树的深度为 (假设根节点在第 1层 )( )。 （ A） 3 （ B） 4 （ C） 6 （ D） 7 36 一棵二叉树中共有 80个
13、叶子节点与 70个度为 1的节点，则该二叉树中的总节点数为 ( )。 （ A） 219 （ B） 229 （ C） 230 （ D） 231 37 某二叉树共有 12个节点，其中叶子节点只有 1个，则该二叉树的深度为 (根节点在第 1层 )( )。 （ A） 3 （ B） 6 （ C） 8 （ D） 12 38 对下列二叉树 进行前序遍历的结果为 ( )。 （ A） DYBEAFCZX （ B） YDEBFZXCA （ C） ABDYECFXZ （ D） ABCDEFXYZ 39 在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。 （ A） O(n) （ B） O(n2
14、) （ C） O(log2n) （ D） O(nlog2n) 40 对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n一 1) 2的排序方法是 ( )。 （ A）快速排序 （ B）冒泡排序 （ C）直接插入排序 （ D）堆排序 41 下列排序方法中，最坏情况下比较次 数最少的是 ( )。 （ A）冒泡排序 （ B）简单选择排序 （ C）直接插入排序 （ D）堆排序 42 对长度为 10的线性表进行冒泡排序，最坏情况下需要比较的次数为 ( )。 （ A） 9 （ B） 10 （ C） 45 （ D） 90 43 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 ( )。 （ A
15、） n （ B） n一 1 （ C） n(n1) （ D） n(n一 1) 2 国家二级 VF机试（数据结构与算法）模拟试卷 1答案与解析 一、选择题 1 【正确答案】 B 【 试题解析】 循环队列是队列的一种顺序存储结构用队尾指针指向队列中的队尾元素，用排头指针指向排头元素的前一个位置。因此可以说，队列的顺序存储结构一般采用循环队列的形式。故答案为 B。 【知识模块】 数据结构与算法 2 【正确答案】 A 【试题解析】 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性是指算法程序的运行时间是有限的。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题解析】 算
16、法的空间复杂度是指算法在执行过程中所需要的内存空间，算法的 时间复杂度，是指执行算法所需要的计算工作量，两者之间并没有直接关系，答案为 D。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 算法的效率与问题的规模和数据的存储结构都有关， A错误。算法的时间复杂度，是指执行算法所需要的计算工作量， B正确。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此数据的逻辑结构和存储结构不是一一对应的， C错误。算法的时间复杂度和空间复杂度没有直接的联系， D错误。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 算法的空间复杂度是指算法在执行过程中所需
17、要的内存空间。所以选择 A。 【知识模块】 数据结构与算法 6 【正确答案】 B 【试题解析】 只有 B选项 369可以用无符号整数来表示和存储。 A选项一 369有负号， C选项 0 369是小数都不能用无符号整数类存储。 D选项是一个整数集合得用数组来存储。 【知识模块】 数据结构与算法 7 【正确答案】 A 【试题解析】 程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。 【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 算法是解析题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以 A错误。设计算法时不仅要考虑对数据对象的
18、运算和操作，还要考虑算法的控制结构。 【知识模块】 数据结构与算法 9 【正确答案】 B 【试题解析】 线性结构应满足：有且只有一个根节点与每个节点最多有一个前件，也最多有一个后件，所以 B正确。所以有一个以上根节点的数据结构一定是非线性结构。所以 A)错误。循环链表和双向链表都是线性结构的数据结构。 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 一般来说，在线性表的链式存储结构中，各个数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插入和删除都不需要移动表中的元素，只需要改变节点的指针域即可。 【知识模块】 数据结构与算
19、法 11 【正确答案】 A 【试题解析】 链式存储结构既可以针对线性结构也可以针对非线性结构，所以 B与 C错误。链式存储结构中每个节点都由数据域与指针域两部分组成，增加了存储空间，所以 D错误。 【知识 模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 线性链式存储结构中每个节点都由数据域与指针域两部分组成，增加了存储空间，所以一般要多于顺序存储结构。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 栈是按 “先进后出 ”的原则组织数据的，数据的插入和删除都在栈顶进行操作。 【知识模块】 数据结构与算法 14 【正确答案】 B 【试题解析】 栈是先进后出的原则
20、组织数据，所以人栈最早的最后出栈，所以选择 B。 【知识模块】 数据结构与算 法 15 【正确答案】 D 【试题解析】 栈是先进后出的线性表，所以 A错误；队列是先进先出的线性表，所以 B错误；循环队列是线性结构的线性表，所以 C错误。 【知识模块】 数据结构与算法 16 【正确答案】 D 【试题解析】 栈是一种先进后出的线性表。队列是一种先进先出的线性表，栈与队列都是线性结构。 【知识模块】 数据结构与算法 17 【正确答案】 C 【试题解析】 栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能 被删除的元素。栈的修改是按后进先出的原则进行
21、的。因此，栈称为先进后出表，或 “后进先出 ”表，所以选择C。 【知识模块】 数据结构与算法 18 【正确答案】 C 【试题解析】 栈的修改是按后进先出的原则进行的，所以顺序应与入栈顺序相反，故选 C。 【知识模块】 数据结构与算法 19 【正确答案】 D 【试题解析】 队列的修改是依先进先出的原则进行的，所以 D正确。 【知识模块】 数据结构与算法 20 【正确答案】 D 【试题解析】 循环队列有队头和队尾两个指针，但是循 环队列仍是线性结构的，所以 A错误；在循环队列中只需要队头与队尾两个指针来共同反映队列中元素的动态变化情况，所以 B与 C错误。 【知识模块】 数据结构与算法 21 【正
22、确答案】 C 【试题解析】 树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。 【知识模块】 数据结构与算法 22 【正确答案】 B 【试题解析】 栈是按先进后出的原则组织数据的。队列是按先进先出的原则组织数据的。 【知识模块】 数据结构与算法 23 【正确答案】 D 【试题解析】 循 环队列的队头指针与队尾指针都不是固定的，随着人队与出队操作要进行变化。因为是循环利用的队列结构，所以对头指针有时可能大于队尾指针，有时也可能小于队尾指针。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 栈是先进后出的数据结构，所以栈顶元素是最后入栈最先被删除。栈底元素最先进却
23、最后被删除。所以选择 A。 【知识模块】 数据结构与算法 25 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排头元素的 前一个位置。在循环队列中进行出队、入队操作时，头尾指针仍要加 l，朝前移动。只不过当头尾指针指向向量上界时，其加 l操作的结果是指向向量的下界 0。由于人队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时，头尾指针均相等。答案为 D选项。 【知识模块】 数据结构与算法 26 【正确答案】 A 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排
24、头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所 有的元素均为队到中的元素。所以循环队列中的元素个数与队头指针和队尾指针的变化而变化， A正确。 【知识模块】 数据结构与算法 27 【正确答案】 C 【试题解析】 栈是先进后出的数据结构，在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来操作，所以选择 C。 【知识模块】 数据结构与算法 28 【正确答案】 C 【试题解析】 线性表的顺序存储结构具备如下两个基本特征： (1)线性表中的所有元素所占的存储空间是连续的； (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存 放的。
25、用一组任意的存储单元来依次存放线性表的节点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此 C正确。 【知识模块】 数据结构与算法 29 【正确答案】 A 【试题解析】 在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。带链的栈可以用来收集计算机存储空间中所有空闲的存储节点，是线性表。在单链表中的节点中增加一个指针域指向它的直接前件，这样的链表，就称为双向链表 (一个节点中含有两个指针 )，也是线性链表。循环链表 具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活，
26、属于线性链表。二叉链表是二叉树的物理实现，是一种存储结构，不属于线性结构。答案为 A选项。 【知识模块】 数据结构与算法 30 【正确答案】 A 【试题解析】 栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为 A。 【知识模块】 数据结构与算法 31 【正确答案】 C 【试题解析】 根据总体结构图可以看出该树的深度为 3，比如： XY系统 功能 2功能 2 1，就是最深的度数的一个表现。 【知识模块】 数据结构
27、与算法 32 【正确答案】 C 【试题解析】 根据二叉树的基本性质 3：在任意一棵二叉树中，度为 0的叶子节点总是比度为 2的节点多一个，所以本题中是 5+1=6个。 【知识模块】 数据结构与算法 33 【正确答案】 B 【试题解析】 根据二叉树的基本性质 3：在任意一棵二 叉树中，度为 0的叶子节点总是比度为 2的节点多一个。所以选择 B。 【知识模块】 数据结构与算法 34 【正确答案】 A 【试题解析】 根据二叉树的性质 3：在任意一棵二又树中，度数为 0的叶子节点总是比度数为 2的节点多一个。所以本题中度数为 2的节点是 51=4个，所以度数为 1的节点的个数是 2554=16个。 【
28、知识模块】 数据结构与算法 35 【正确答案】 D 【试题解析】 根据二叉树的性质 3：在任意一棵二叉树中，度为 0的叶子节点总比度为 2的节点多一个，所以本题中度为 2的节点为 1一 1=0个，所以知道本题目中的二叉树的每个节点都有一个分支，所以 7个节点共 7层，即度为 7。 【知识模块】 数据结构与算法 36 【正确答案】 B 【试题解析】 二叉树中，度为 0的节点数等于度为 2的节点数加 1，即 n2=n0一1，叶子节点即度为 0，则 n2=79，总节点为 n0+n1+n2=80+70+79=229，答案为B。 【知识模块】 数据结构与算法 37 【正确答案】 D 【试题解析】 二又树
29、中，度为 0的节点数等于度为 2的节点数加 1，即 n2=n0一1，叶子节点即度为 0， n0=1，则 n2=0，总节点数为 12=no+n1+n2=1+n1+0，则度为 l的节点数 n1=11，故深度为 12，选 D。 【知识模块】 数据结构与算法 38 【正确答案】 C 【试题解析】 前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作。否则： 访问根节点； 前序遍历左子树； 前序遍历右子树， C正确。 【知识模块】 数
30、据结构与算法 39 【正确答案】 C 【试题解析】 当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为 n的有序线性表，在最坏情况下，二分法查找只需要比较 log2n次，而顺序查找需要比较 n次。 【知识模块】 数据结构与算法 40 【正确答案】 D 【试题解析】 除了堆排序算法的比较次数是 O(nlog2n)，其他的都是 n(n一 1)2。 【知识模块】 数据结构与算法 41 【正确答案】 D 【试题解析】 冒泡排序、简单插入排序与简单选择排序法在最坏情况下均需要比较 n(n一 1) 2次，而堆排序在最坏情况下需要比较的次数是 nlog2n。 【知识模块】 数据结构与算法 42 【正确答案】 C 【试题解析】 冒泡法是在扫描过程中逐次比较相邻两个元素的大小，最坏的情况是每次比较都要将相邻的两个元素互换，需要互换的次数为9+8+7+6+5+4+3+2+1=45，选 C。 【知识模块】 数据结构与算法 43 【正确答案】 D 【试题解析】 快速排序最坏情况就是每次选的基准数都和其他数做过比较，共需比较 (n一 1)+(n一 2)+1=n(n 1) 2，选 D。 【知识模块】 数据结构与算法
