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