1、国家二级 ACCESS机试（选择题）模拟试卷 112及答案与解析 一、选择题 1 某二叉树共有 7个节点，其中叶子节点只有 1个，则该二叉树的深度为 (假设根节点在第 1层 )( )。 （ A） 3 （ B） 4 （ C） 6 （ D） 7 2 某二叉树共有 l2个节点，其中叶子节点只有 1个。则该二叉树的深度为 (假设根节点在第 1层 )( )。 （ A） 3 （ B） 6 （ C） 8 （ D） 12 3 设树 T的深度为 4，其中度为 1， 2， 3， 4的节点个数分别为 4， 2， l， lo则 T中的叶子节点数为 ( )。 （ A） 8 （ B） 7 （ C） 6 （ D） 5 4
2、设一棵完全二叉树共有 700个节点，则此二叉树中的叶子节点数为 ( )。 （ A） 85 （ B） 120 （ C） 250 （ D） 350 5 在深度为 7的满二叉树中，叶子节点的个数为 ( )。 （ A） 32 （ B） 31 （ C） 64 （ D） 63 6 下列叙述中正确的是 ( )。 （ A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 （ B）循环队列中的元素个数随队头指针的变化而动态变化 （ C）循环队列中的元素个 数随队尾指针的变化而动态变化 （ D）循环队列中的元素个数不会变化 7 下列关于线性链表的叙述中，正确的是 ( )。 （ A）各数据节点的存储空间可以
3、不连续，但它们的存储顺序与逻辑顺序必须一致 （ B）各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续 （ C）进行插入与删除时，不需要移动表中的元素 （ D）以上都不正确 8 下列叙述中正确的是 ( )。 （ A）线性表链式存储结构的存储空间一般要少于顺序存储结构 （ B）线性表链式存储结构与顺序存储结构的存储空间都是连续 的 （ C）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 （ D）以上都不正确 9 下列叙述中正确的是 ( )。 （ A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 （ B）线性表的链式存储结构所需要的存储空间一般要多于顺序存
4、储结构 （ C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 （ D）以上都不正确 10 下列对于线性链表的描述中正确的是 ( )。 （ A）存储空间不一定连续，且各元素的存储顺序是任意的 （ B）存储空间不一定连续，且前 件元素一定存储在后件元素的前面 （ C）存储空间必须连续，且前件元素一定存储在后件元素的前面 （ D）存储空间必须连续，且各元素的存储顺序是任意的 11 算法的有穷性是指 ( )。 （ A）算法程序的运行时间是有限的 （ B）算法程序所处理的数据量是有限的 （ C）算法程序的长度是有限的 （ D）算法只能被有限的用户使用 12 下列叙述中正确的是 ( )。 （
5、 A）算法就是程序 （ B）设计算法时只需要考虑数据结构的设计 （ C）设计算法时只需要考虑结果的可靠性 （ D）以上三种说法都不 对 13 算法的空间复杂度是指 ( )。 （ A）算法在执行过程中所需要的计算机存储空间 （ B）算法所处理的数据量 （ C）算法程序中的语句或指令条数 （ D）算法在执行过程中所需要的临时工作单元数 14 算法的时间复杂度是指 ( )。 （ A）算法的执行时间 （ B）算法所处理的数据量 （ C）算法程序中的语句或指令条数 （ D）算法在执行过程中所需要的基本运算次数 15 下列叙述中正确的是 ( )。 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无
6、关 （ B）算 法的时间复杂度是指执行算法所需要的计算工作量 （ C）数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一定相关 16 某二叉树中有 n个度为 2的节点，则该二叉树中的叶子节点数为 ( )。 （ A） n+1 （ B） n1 （ C） 2n （ D） n/2 17 某二叉树有 5个度为 2的节点，则该二叉树中的叶子节点数是 ( )。 （ A） 10 （ B） 8 （ C） 6 （ D） 4 18 棵二叉树共有 31个节点，其中 8个是叶子节点，则度为 1的节点数为( )。 （ A） 16 （ B） 10 （ C） 6 （ D） 4 19 一棵二叉树中共有
7、 80个叶子节点与 70个度为 1的节点，则该二叉树中的总节点数为 ( )。 （ A） 219 （ B） 229 （ C） 230 （ D） 231 20 一棵二叉树中共有 70个叶子节点与 80个度为 1的节点，则该二叉树中的总节点数为 ( )。 （ A） 219 （ B） 221 （ C） 229 （ D） 231 21 设循环队列的存储空间为 Q(1： 35)，初始状态为 front=rear=35 0现经过一系列入队与退队运算后， front=15， rear=15，则循环队列中的元素个数为 ( )。 （ A） 15 （ B） 16 （ C） 20 （ D） 0或 35 22 在一个容
8、量为 15的循环队列中，若头指针 front=6，尾指针 rear=9，则循环队列中的元素个数为 ( )。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 23 下列叙述中正确的是 ( )。 （ A）栈是一种先进先出的线性表 （ B）队列是一种后进先出的线性表 （ C）栈与队列都是非线性结构 （ D）栈与队列都是线性结构 24 下列叙述中正确的是 ( )。 （ A）栈是 “先进先出 ”的线性表 （ B）队列是 “先进后出 ”的线性表 （ C）循环队列是线性结构 （ D）有序线性表不可以采用顺序存储结构 25 下列与队列结构有关联的是 ( )。 （ A）函数的递归调用 （ B）数组元素的
9、引用 （ C）多重循环的执行 （ D）先到先服务的作业调度 26 对下列二叉树 ( )。 进行前序遍历的结果是 （ A） DYBEAFCZX （ B） YDEBFZXCA （ C） ABDYECFXZ （ D） ABCDEFXYZ 27 对如下二叉树 进行后序遍历的 结果为 ( )。 （ A） ABCDEF （ B） DBEAFC （ C） BDECF （ D） DEBFCA 28 对长度为 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 ( )。 （ A） log2n （ B） n/2 （ C） n （ D） n+1 29 在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较
10、的次数为( )。 （ A） 63 （ B） 64 （ C） 6 （ D） 7 30 下列叙述中正确的是 ( )。 （ A）对长度为 n的有序链表进行查找，最坏情况下需要的比较次数为 n （ B）对长度为 n的有序链表进行对分查找，最坏情况下需要韵比较次数为 (n/2) （ C）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (log2n) （ D）对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为 (nlog2n) 31 用树形结构表示实体之间联系的模型是 ( )。 （ A）关系模型 （ B）网状模型 （ C）层次模型 （ D）以上三个都是 32 数据库设计过程不包
11、括 ( )。 （ A）概念设计 （ B）逻辑设计 （ C）物理设计 （ D）算法设计 国家二级 ACCESS机试（选择题）模拟试卷 112答案与解析 一、选择题 1 【正确答案】 D 【试题解析】 根据二叉树的性质，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。题目中的二叉树的叶子节点为 1因此度为 2的节点的数目为 0。故该二叉树为 7层，每层只有一个节点。 2 【正确答案】 D 【试题解析】 根据二叉树的性质，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。题目中的二叉树的叶子节点为 1，因此度为 2的节点的数目为 0。故该二叉树为 12层，每层只有一个节点。 3 【
12、正确 答案】 A 【试题解析】 在一棵树中，节点总数 =总分支数目 +1，n0+4+2+1+1=( n0xO+lx4+2x2+3 x1+4xl )+1，则 n0=8，其中 n0表示叶子节点。 4 【正确答案】 D 【试题解析】 (1)具有 n个节点的完全二叉树的深度为 log2n, +1，计算出该完全二叉树的深度为 10。 (2)设度为 0的节点 (叶子节点 )为 n0，度为 1的节点为 n1，度为2的节点为 n2，总节点数为 n，深度为 k。 n,=n1+n2+n0，由于 n0=n2+1则 n2=n01，故 n=n1+n01+n0=n1+2n0一 1。由于完全二叉树中度为 1的节点数只有两种
13、可能： 0或 1。 (3)假设度为 1的节点数为 0即满二叉树，根据满二叉树的定义，其2m一 1个节点，根据以上计算所得的深度 10来计算，应有 2101=10241=1023个节点，显然与题目中 700个节点不符。因此，度为 1的节点数必然为 1。故n=n1+2n01=1+2n01=2n0，则 n0=n/2=700/2=350 5 【正确答案】 C 【试题解析】 所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有节点都有两个子节点。也就是在满二叉树中，每一层上的节点数都是最大节点数，即在满二叉树的第 k层上有 2k1个节点，深度为 m的满二叉树有 2m1个节点。对于深度为 7的满
14、二叉树，叶子节点所在的是第 7层，一共有 271=64个叶子节点。全部节点共 271=127个。 6 【正确答案】 A 【试题解析】 所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针 rear指向 队列中的队尾元素，用队头指针 front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针 front指向的后一个位置与队尾指针 rear指向位置之间的元素数量。 7 【正确答案】 C 【试题解析】 线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的
15、逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 8 【正确答案】 C 【试题解析】 线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的 存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。 9 【正确答案】 B 【试题解析】 线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分：一部分用于存储数据元素的值
16、，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线 性表的链式存储方式比顺序存储方式的存储空间要大一些。 10 【正确答案】 A 【试题解析】 一般来说，在线性表的链式存储结构中各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各节点的指针域来指示的。指向线性表中第一个节点的指针 head称为头指针，当 head=NULL(或 0)时称为空表。 11 【正确答案】 A 【试题解析】 算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 12 【正确答案】 D 【试题
17、解析】 所谓算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法不等于程序，也不等于计算方法。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。 13 【正确答案】 A 【试题解析】 算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。 14 【正确答案】 D 【试题解析】 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程巾所需基本运算的执行次数来度量。 15 【
18、正确答案】 B 【试题解析】 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机 的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。 16 【正确答案】 A 【试题解析】 在任意一棵二叉树中，度为 0的节点，即叶子节点。总是比
19、度为 2的节点多一个。所以该二叉树的叶子节点数等于 n+1。 17 【正确答案】 C 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 O的节点 (叶子节点 )总是比度为 2的节点多一个。 18 【正确答案】 A 【试题解析】 根据二叉树的性质，在 任意二叉树中，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。故此度为 I的节点个数 =总节点数一叶子节点数一度为2的节点数 =3187=16。 19 【正确答案】 B 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个，总节点数 =叶子节点数 +度为 2的节点数 +度为 1的节点
20、数 =80+79+70=229。 20 【正确答案】 A 【试题解析】 在二叉树中，叶子节点个数为 n0，度为 2的节点数 n2=n01。本题中叶子节点的个数为 70，所以度为 2的节点个 数为 69。总节点数 =叶子节点数 +度为 1的节点数 +度为 2的节点数 =70+80+69=219。 21 【正确答案】 D 【试题解析】 循环队列的队头指针和尾指针都等于 15，此循环队列中元素的个数有两种情况：第一种情况是队头指针和尾指针都是第一次到达 15，此时元素个数为 0；第二种情况是队头指针第一次到达 15，而尾指针第二次到达 15，此时元素个数为 35。 22 【正确答案】 B 【试题解析
21、】 循环队列中， rear表示尾指针， front表示头指针，当有元素入队时， rear=rear+1，而元素出队 的时候， front=front+1，当 rear值大于 front值时，队列中的元素个数为 rearfront，当 rear的值小于 front时，列队 中的元素个数为 rearfront+m(m表示队列的容量 )。 23 【正确答案】 D 【试题解析】 栈是先进后出，队列是先进先出。栈和队列都是一种线性表，属于线性结构。 24 【正确答案】 C 【试题解析】 栈是 “先进后出 ”队列是 “先进先出 ”。栈和队列都是一种线性表，属于线性结构。有序线性表既可以采用顺序存储结构，也
22、可以采用链式存储结构。采用链 式存储结构的线性表称之为线性链表。 25 【正确答案】 D 【试题解析】 队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。 26 【正确答案】 C 【试题解析】 二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则， 访问根节点； 前序遍历左子树； 前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是 ABDYECFXZ。 27 【正确答案】 D 【试题解析】 所谓后序遍历是指在访问根据节点、遍历左子树与遍 历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节点，并且，在遍历左、右
23、子树时，仍然先遍历左子树，然后遍历右子树，最后访问根点。因此，后序遍历二叉树的过程也是一个递归过程。其简单描述为：若二叉树为空，则结束返回；否则，先后序遍历左子树，然后后序遍历右子树，最后访问根节点。对于后序遍历，第一个访问的节点一定是最左下的节点，最后一个访问的节点一定是根节点，故 D)选项正确。 28 【正确答案】 C 【试题解析】 在进行顺序查找过程中，如果被查的元素是线性表中的最后一个元素，或者被查元素根本不 在线性表中，则为了查找这个元素需要与线性表中的所有元素进行比较，这是顺序查找的最坏情况，需要比较的次数为 n次。 29 【正确答案】 B 【试题解析】 顺序查找又称顺序搜索。顺序
24、查找一般是指在线性表中查找指定的元素，其基本方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示找到 (即查找成功 )，若线性表中所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素 (即查找失败 )。如果线性表中的第一个元素就是要查找的元素，则只需要做一次比较就查找成功，但如 果要查找的元素是线性表中的最后一个元素或者要查找元素不在线性表中，则需要与线性表中所有元素进行比较，这是顺序查找的最坏情况，比较次数为线性表的长度。 30 【正确答案】 A 【试题解析】 本题主要考查的知识点为查找技术。顺序查找的使用情况： 线性表为无序表； 表采用键式存储结构。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。 31 【正确答案】 C 【试题解析】 层次模型的基本结构是树形结构，这种结构方式在现实世界中很普遍，它们自顶向下、层次分明。 32 【正确答案】 D 【试题解析】 数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和物理设计。
