1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 8及答案与解析 一、选择题 1 一棵二叉树共有 25个结点，其中 5个是叶子结点，则度为 1的结点数为 （ A） 16 （ B） 10 （ C） 6 （ D） 4 2 设循环队列存储空间为 Q(1： 50)。初始状态为 front=rear=50。经过一系列入队和退队操作后， front=14， rear=19，则该循环队列中的元素个数为 （ A） 46 （ B） 45 （ C） 6 （ D） 5 3 下列链表中，其逻辑结构属于非线性结构的是 （ A）二叉链表 （ B） 循环链表 （ C）双向链表 （ D）带链的栈 4 设循环队列的存
2、储空间为 Q(1： 35)，初始状态为 front=rear=35。现经过一系列入队与退队运算后， front=15， rear=15，则循环队列中的元素个数为 （ A） 15 （ B） 16 （ C） 20 （ D） 0或 35 5 下列关于栈的叙述中，正确的是 （ A）栈底元素一定是最后入栈的元素 （ B）栈顶元素一定是最先入栈的元素 （ C）栈操作遵循先进后出的原则 （ D）以上三种说法都不对 6 设二叉树共有 150个结点，其中度为 1的结点有 10个，则该二叉树中的叶子结点数为 （ A） 71 （ B） 70 （ C） 69 （ D）不可能有这样的二叉树 7 下列叙述中正确的是 （
3、A）程序执行的效率与数据的存储结构密切相关 （ B）程序执行的效率只取决于程序的控制结构 （ C）程序执行的效率只取决于所处理的数据量 （ D）以上都不正确 8 下列与队列结构有关联的是 （ A）函数的递归调用 （ B）数组元素的引用 （ C）多重循环的执行 （ D）先到先服务的作业调度 9 对如下图所示的二叉树 进行前序遍历的结果为 （ A） DYBEAFCZX （ B） YDEBFZXCA （ C） ABDYECFXZ （ D） ABCDEFXYZ 10 一个栈的初始状态为空。现将元素 1， 2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是 （ A） 1， 2,3， A,B,
4、C （ B） C,B,A， 1， 2,3 （ C） C,B,A,3,2， 1 （ D） 1， 2,3,C,B,A 11 下列叙述中正确的是 （ A）一个算法的空间复杂度大，则其时间复杂度也必定大 （ B）一个算法的空间复杂度大，则其时间复杂度必定小 （ C）一个算法的时间复杂度大，则其空间复杂度必定小 （ D）算法的时间复杂度与空间复杂度没有直接关系 12 下列叙述中正确的是 （ A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 （ B）循环队列中的元素个数随队头指针的变化而动态变化 （ C）循环队列中的元素个数随队尾指针的变化而动态变化 （ D）循环队列中的元素个数不会变化 13
5、 一棵二叉树中共有 80个叶子结点与 70个度为 1的结点，则该二叉树中的总结点数为 （ A） 219 （ B） 229 （ C） 230 （ D） 231 14 对长度为 10的线性表进行冒泡排序，最坏情况下需要比较的次 数为 （ A） 9 （ B） 10 （ C） 45 （ D） 90 15 下列叙述中正确的是 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无关 （ B）算法的时间复杂度是指执行算法所需要的计算工作量 （ C）数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一定相关 16 下列叙述中正确的是 （ A）线性表链式存储结构的存储空间一般要少于
6、顺序存储结构 （ B）线性表链式存储结构与顺序存储结构的存储空间都是连续的 （ C）线性表链式存储结构的存储空间可以是连续的，也可以是不 连续的 （ D）以上都不正确 17 某二叉树共有 12个结点，其中叶子结点只有 1个。则该二叉树的深度为 (根结点在第 1层 ) （ A） 3 （ B） 6 （ C） 8 （ D） 12 18 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 （ A） n （ B） n一 1 （ C） n(n一 1) （ D） n(n-1) 2 19 下列叙述中正确的是 （ A）有且只有一个根结点的数据结构一定是线性结构 （ B）每一个结点最多有一个前件也最多有一个
7、后件的数据结构一定是线性结构 （ C）有且只有一个根结点的数据结构一定 是非线性结构 （ D）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构 20 下列叙述中错误的是 （ A）在双向链表中，可以从任何一个结点开始直接遍历到所有结点 （ B）在循环链表中，可以从任何一个结点开始直接遍历到所有结点 （ C）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 （ D）在二叉链表中，可以从根结点开始遍历到所有结点 21 某二叉树共有 13个结点，其中有 4个度为 1的结点，则叶子结点数为 （ A） 5 （ B） 4 （ C） 3 （ D） 2 22 设栈的顺序存储空 间为 s(1
8、： 50)，初始状态为 top=0。现经过一系列入栈与退栈运算后， top=20，则当前栈中的元素个数为 （ A） 30 （ B） 29 （ C） 20 （ D） 19 23 下列叙述中正确的是 （ A）栈与队列都只能顺序存储 （ B）循环队列是队列的顺序存储结构 （ C）循环链表是循环队列的链式存储结构 （ D）以上三项均错误 24 设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 25 下列排序方法中，最坏情况 下时间复杂度最小的是 （ A）冒泡排序 （ B）快速排序 （ C）堆排序 （ D）
9、直接插入排序 26 为了对有序表进行对分查找，则要求有序表 （ A）只能顺序存储 （ B）只能链式存储 （ C）可以顺序存储也可以链式存储 （ D）任何存储方式 27 设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 28 下列叙述中正确的是 （ A）存储空间不连续的所有链表一定是非线性结构 （ B）结点中有多个指针域的所有链表一 定是非线性结构 （ C）能顺序存储的数据结构一定是线性结构 （ D）带链的栈与队列是线性结构 29 算法时间复杂度的度量方法是 （ A）算法程序的长度 （ B）执行算法
10、所需要的基本运算次数 （ C）执行算法所需要的所有运算次数 （ D）执行算法所需要的时间 30 设循环队列为 Q(1： m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后， front=rear=1，则该循环队列中的元素个数为 （ A） 1 （ B） 2 （ C） m-1 （ D） 0或 m 31 设顺序表的长度为 40，对该 表进行冒泡排序。在最坏情况下需要的比较次数为 （ A） 780 （ B） 820 （ C） 40 （ D） 41 国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 8答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 根据二叉树
11、的性质，在任意二叉树中，度为 O的结点 (即叶子结点 )总是比度为 2的结点多一个，故此度为 1的结点个数：总结点数叶子节点数度为 2的节点数 =25-5-4=16。 【知识模块】 数据结构与算法 2 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引 15位置开始到索引 19位置，共有 5元素。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 二叉链表作为
12、树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 【知识模块】 数据结构与算法 4 【正确答案】 D 【试题解析】 循 环队列的队头指针和尾指针都等于 15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达 15，此时元素个数为 O：第二种情况是队头指针第一次到达 15，而尾指针第二次到达 15，此时元素个数为 35。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出 ”的规则操作元素。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析
13、】 根据二叉树的性质 3，在任意一颗二叉树中，度为 0的 结点 (即叶子结点 )总是比度为 2的结点多一个。即有 n0=n2+1。对于这个题来说，总结点数150=n0+n1+n2=n2+1+10+n2=2n2+11，所以 2n2=139，度为 2个结点个数不能确定。 【知识模块】 数据结构与算法 7 【正确答案】 A 【试题解析】 影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。 【知识模块】 数据结构与算法 8 【正确 答案】 D 【试题解析】 队列中最先插入的
14、元素将最先被删除，最后插入的元素将最后被删除。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则： 访问根结点； 前序遍历左子树； 前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是 ABDYECFXZ。 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 栈是按照 “先进后出 ”或 “后进 先出 ”的原则组织数据的。所以出栈顺序是 CBA321。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 算法的复杂度主要包括时间复杂度和
15、空间复杂 度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中 n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。 【知识模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 所谓循环结 构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环
16、队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针 front指向的后一个位置与队尾指针 rear指向位置之间的元素数量。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个，故总结点数 =叶子节点数 +度为 2的节点数 +度为 1的节点数 =80+79+70=229。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 线性表的长度为 n，最坏情况下冒泡排序需要比较的次数为 n(n一1)
17、 2。 【知识模块】 数据结构与算法 15 【正确答案】 B 【试题解析】 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数，算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑 结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。 【知识模块】 数据结构与算法 16 【正确答案
18、】 C 【试题解析】 线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于 存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。 【知识模块】 数据结构与算法 17 【正确答案】 D 【试题解析】 根据二叉树的性质，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个。题目中的二叉树的叶子结点为 1，因此度为 2的结点的数目为 0，故该二叉树为 12层，每层只有一个结点。 【知识模块】 数据结构与算法 1
19、8 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描 和 n 2遍的从后往前的扫描，需要的比较次数为 n(n-1)2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与算法 19 【正确答案】 D 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分这两大类型：线性结构与非线性结构。如果一个非空的数据结构满足两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。称该数据结构为线性结构，又称为线性表。对于这个题目来
20、说，有且只有一个根 结点的数据结构可能是线性结构，也可能是非线性结构。具有一个根结点的树就是一个非线性结构，选项 D正确。 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项 C的描述是错误的。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 根据二叉树性质，在任意一颗二叉树中，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个，即有 n0=n2+1。本题总结点数 ：13=n0+n1+n2=n2+1+4+n2=2n2+5， n2=4，所以叶子结
21、点数等于 4+1=5，选项 A正确。 【知识模块】 数据结构与算法 22 【正确答案】 C 【试题解析】 栈是允许在栈顶进行插入和删除的线性表，不允许在栈底进行插入与删除。通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。对栈的操作有入栈和退栈两种。入栈运算：首先将栈顶指针进一 (即 top加 1)，然后将新元素插入到栈顶指针指向的位置。退栈运算：首先将栈顶元素 (栈顶指针指向的元素 )赋给一个指定的变量，然后将栈顶 指针退一 (即 top减 1)。因为初始状态为top=0，经过入栈和退栈操作后栈中的元素个数就是 too指针指向的位置。选项 C正确。 【知识模块】 数据结构与算
22、法 23 【正确答案】 B 【试题解析】 栈和队列是按数据的逻辑结构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。线性结构的数据可以按顺序存储结构存储，也可以按链式存储结构存储，而循环队列是队列的顺序存储结构。选项B正确。 【知识模块】 数据结构与算法 24 【正确答案】 B 【试题解析】 二叉树的前 序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在
23、按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定 A为根， A在中序中的位置，可以确定 CB为 A的左子树上的结点，没有右子树。确定 A之后，再看中序第二个值为 B，查看 B在中序中的位置， C在 B左边，确定 C为 B的左子树。因此，后序是 CBA。 【知识模块】 数据结构与算法 25 【正确答案】 C 【试题解析】 排序方法中最坏情况下时间复杂度的大小如下表： 根据上表可知选项 C正确。 【知识模块】 数据结构与算法 26 【正确答案】 A 【试题解析】 有序表的对分查找条件是有序表为顺序存储。 顺序查找： 如果线性表为无序表 (即表中元素的排序是无序的 )，则无论是顺
24、序存储结构还是链式存储结构，都只能用顺序查找； 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。分块查找 (又称索引顺序查找 )：分块有序表结 构分为两部分， 线性表本身采用顺序存储结构； 在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值：一是指针域。用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。 【知识模块】 数据结构与算法 27 【正确答案】 C 【试题解析】 二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问
25、根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树 ，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定 A为根结点；根据 B在中序中的位置，可以确定 A没有左子树， BC为 A的右子树， C为 B的右子树。本题的具体二叉树如下： 因此，这棵二叉树的前序是 ABC，选项 C正确。 【知识模块】 数据结构与算法 28 【正确答案】 D 【试题解析】 计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储 ，可以分为顺序存储和链式存储
26、。数据的逻辑结构与存储结构之间没有对应的关系。所以选项 ABC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。 【知识模块】 数据结构与算法 29 【正确答案】 B 【试题解析】 算法的时间复杂度：分析算法时，语句总执行次数 T(n)是关于问题规模 n的函数，进而分析 T(n)随 n的变化情况并确定 T(n)。算法的时间复杂度也就是算法的时间量度，记作 T(n)=O(f(n)。它表示问题输入规模 n的增大，算法执行时间的增长率和 f(n)的增长率相同，因此称作渐近时间复杂度， 也称作时间复杂度。 f(n)是问题规模 n的某个函数。选项 B正确。 【知识模块】 数据结构与算法 30 【正确答
27、案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间，所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队列满时有 front=rear，而当循环队列空时也有front=rear。即在循环队列中，当 front=rear时，不能确定是队 列满、还是队列空。当 front=rear=1，要么队列为空，队列中的元素个数为 0，要么队列为满，队列中元素个数为 m。选项 D正确。 【知识模块】 数据结构与算法 31 【正确答案】 A 【试题解析】 冒泡排序 (Bubble Sort)，是一种计算机科学领域的较简单的排序算法。冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个：持 续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡排序的最坏时间复杂度为 (n*(n1) 2=780。 【知识模块】 数据结构与算法
