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