【计算机类职业资格】国家二级ACCESS机试（选择题）模拟试卷112及答案解析.doc

1、国家二级 ACCESS机试（选择题）模拟试卷 112及答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.某二叉树共有 7个节点，其中叶子节点只有 1个，则该二叉树的深度为(假设根节点在第 1层)( )。（分数：2.00）A.3B.4C.6D.72.某二叉树共有 l2个节点，其中叶子节点只有 1个。则该二叉树的深度为(假设根节点在第 1层)( )。（分数：2.00）A.3B.6C.8D.123.设树 T的深度为 4，其中度为 1，2，3，4 的节点个数分别为 4，2，l，lo 则 T中的叶子节点数为( )。（分数：2.00）A.8B.7C.6D.5

2、4.设一棵完全二叉树共有 700个节点，则此二叉树中的叶子节点数为( )。（分数：2.00）A.85B.120C.250D.3505.在深度为 7的满二叉树中，叶子节点的个数为( )。（分数：2.00）A.32B.31C.64D.636.下列叙述中正确的是( )。（分数：2.00）A.循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B.循环队列中的元素个数随队头指针的变化而动态变化C.循环队列中的元素个数随队尾指针的变化而动态变化D.循环队列中的元素个数不会变化7.下列关于线性链表的叙述中，正确的是( )。（分数：2.00）A.各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序

3、必须一致B.各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素D.以上都不正确8.下列叙述中正确的是( )。（分数：2.00）A.线性表链式存储结构的存储空间一般要少于顺序存储结构B.线性表链式存储结构与顺序存储结构的存储空间都是连续的C.线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D.以上都不正确9.下列叙述中正确的是( )。（分数：2.00）A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C.线性表的链式存储结构所需要的存储空间一般要少于顺序存

4、储结构D.以上都不正确10.下列对于线性链表的描述中正确的是( )。（分数：2.00）A.存储空间不一定连续，且各元素的存储顺序是任意的B.存储空间不一定连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的11.算法的有穷性是指( )。（分数：2.00）A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用12.下列叙述中正确的是( )。（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可

5、靠性D.以上三种说法都不对13.算法的空间复杂度是指( )。（分数：2.00）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数14.算法的时间复杂度是指( )。（分数：2.00）A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数15.下列叙述中正确的是( )。（分数：2.00）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复

6、杂度一定相关16.某二叉树中有 n个度为 2的节点，则该二叉树中的叶子节点数为( )。（分数：2.00）A.n+1B.n1C.2nD.n/217.某二叉树有 5个度为 2的节点，则该二叉树中的叶子节点数是( )。（分数：2.00）A.10B.8C.6D.418.棵二叉树共有 31个节点，其中 8个是叶子节点，则度为 1的节点数为( )。 （分数：2.00）A.16B.10C.6D.419.一棵二叉树中共有 80个叶子节点与 70个度为 1的节点，则该二叉树中的总节点数为( )。（分数：2.00）A.219B.229C.230D.23120.一棵二叉树中共有 70个叶子节点与 80个度为 1的节

7、点，则该二叉树中的总节点数为( )。（分数：2.00）A.219B.221C.229D.23121.设循环队列的存储空间为 Q(1：35)，初始状态为 front=rear=35 0现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为( )。（分数：2.00）A.15B.16C.20D.0或 3522.在一个容量为 15的循环队列中，若头指针 front=6，尾指针 rear=9，则循环队列中的元素个数为( )。（分数：2.00）A.2B.3C.4D.523.下列叙述中正确的是( )。（分数：2.00）A.栈是一种先进先出的线性表B.队列是一种后进先出的线性

8、表C.栈与队列都是非线性结构D.栈与队列都是线性结构24.下列叙述中正确的是( )。（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是线性结构D.有序线性表不可以采用顺序存储结构25.下列与队列结构有关联的是( )。（分数：2.00）A.函数的递归调用B.数组元素的引用C.多重循环的执行D.先到先服务的作业调度26.对下列二叉树( )。 （分数：2.00）A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZD.ABCDEFXYZ27.对如下二叉树 （分数：2.00）A.ABCDEFB.DBEAFCC.BDECFD.DEBFCA28.对长度为

9、 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为( )。（分数：2.00）A.log 2 nB.n/2C.nD.n+129.在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为( )。（分数：2.00）A.63B.64C.6D.730.下列叙述中正确的是( )。（分数：2.00）A.对长度为 n的有序链表进行查找，最坏情况下需要的比较次数为 nB.对长度为 n的有序链表进行对分查找，最坏情况下需要韵比较次数为(n/2)C.对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为(log 2 n)D.对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为(n

10、log 2 n)31.用树形结构表示实体之间联系的模型是( )。（分数：2.00）A.关系模型B.网状模型C.层次模型D.以上三个都是32.数据库设计过程不包括( )。（分数：2.00）A.概念设计B.逻辑设计C.物理设计D.算法设计国家二级 ACCESS机试（选择题）模拟试卷 112答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.某二叉树共有 7个节点，其中叶子节点只有 1个，则该二叉树的深度为(假设根节点在第 1层)( )。（分数：2.00）A.3B.4C.6D.7 解析：解析：根据二叉树的性质，度为 0的节点(叶子节点)总是比度为 2的节

11、点多一个。题目中的二叉树的叶子节点为 1因此度为 2的节点的数目为 0。故该二叉树为 7层，每层只有一个节点。2.某二叉树共有 l2个节点，其中叶子节点只有 1个。则该二叉树的深度为(假设根节点在第 1层)( )。（分数：2.00）A.3B.6C.8D.12 解析：解析：根据二叉树的性质，度为 0的节点(叶子节点)总是比度为 2的节点多一个。题目中的二叉树的叶子节点为 1，因此度为 2的节点的数目为 0。故该二叉树为 12层，每层只有一个节点。3.设树 T的深度为 4，其中度为 1，2，3，4 的节点个数分别为 4，2，l，lo 则 T中的叶子节点数为( )。（分数：2.00）A.8 B.7C

12、.6D.5解析：解析：在一棵树中，节点总数=总分支数目+1，n 0 +4+2+1+1=( n 0 xO+lx4+2x2+3 x1+4xl )+1，则 n 0 =8，其中 n 0 表示叶子节点。4.设一棵完全二叉树共有 700个节点，则此二叉树中的叶子节点数为( )。（分数：2.00）A.85B.120C.250D.350 解析：解析：(1)具有 n个节点的完全二叉树的深度为log 2 n, +1，计算出该完全二叉树的深度为 10。 (2)设度为 0的节点(叶子节点)为 n 0 ，度为 1的节点为 n 1 ，度为 2的节点为 n 2 ，总节点数为 n，深度为 k。n,=n 1 +n 2 +n 0

13、 ，由于 n 0 =n 2 +1则 n 2 =n 0 1，故 n=n 1 +n 0 1+n 0 =n 1 +2n 0 一1。由于完全二叉树中度为 1的节点数只有两种可能：0 或 1。 (3)假设度为 1的节点数为 0即满二叉树，根据满二叉树的定义，其 2 m 一 1个节点，根据以上计算所得的深度 10来计算，应有 2 10 1=10241=1023个节点，显然与题目中 700个节点不符。因此，度为 1的节点数必然为 1。故 n=n 1 +2n 0 1=1+2n 0 1=2n 0 ，则 n 0 =n/2=700/2=3505.在深度为 7的满二叉树中，叶子节点的个数为( )。（分数：2.00）A

14、.32B.31C.64 D.63解析：解析：所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有节点都有两个子节点。也就是在满二叉树中，每一层上的节点数都是最大节点数，即在满二叉树的第 k层上有 2 k1 个节点，深度为 m的满二叉树有 2 m 1个节点。对于深度为 7的满二叉树，叶子节点所在的是第 7层，一共有 2 71 =64个叶子节点。全部节点共 2 7 1=127个。6.下列叙述中正确的是( )。（分数：2.00）A.循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 B.循环队列中的元素个数随队头指针的变化而动态变化C.循环队列中的元素个数随队尾指针的变化而动态变化D

15、.循环队列中的元素个数不会变化解析：解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针 front指向的后一个位置与队尾指针 rear指向位置之间的元素数量。7.下列关于线性链表的叙述中，正确的是( )。（分数：2.00）A.各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素 D.以

16、上都不正确解析：解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。8.下列叙述中正确的是( )。（分数：2.00）A.线性表链式存储结构的存储空间一般要少于顺序存储结构B.线性表链式存储结构与顺序存储结构的存储空间都是连续的C.线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 D.以上都不正确解析：解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分：

17、一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。9.下列叙述中正确的是( )。（分数：2.00）A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.以上都不正确解析：解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部

18、分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。10.下列对于线性链表的描述中正确的是( )。（分数：2.00）A.存储空间不一定连续，且各元素的存储顺序是任意的 B.存储空间不一定连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的解析：解析：一般来说，在线性表的链式存储结构中各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系是由各节点的指针域来指示的。指向线性表中第一个节点

19、的指针 head称为头指针，当 head=NULL(或 0)时称为空表。11.算法的有穷性是指( )。（分数：2.00）A.算法程序的运行时间是有限的 B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用解析：解析：算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。12.下列叙述中正确的是( )。（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对 解析：解析：所谓算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都

20、是有效的，且是明确的，此顺序将在有限的次数下终止。算法不等于程序，也不等于计算方法。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。13.算法的空间复杂度是指( )。（分数：2.00）A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。14.算法的时间复杂度是指( )。（分数：2.00）A.算法的执行时间B.算法所处理的数据量C.

21、算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数 解析：解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程巾所需基本运算的执行次数来度量。15.下列叙述中正确的是( )。（分数：2.00）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量 C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关解析：解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一

22、般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。16.某二叉树中有 n个度为 2的节点，则该二叉树中的叶子节点数为( )。（分数：2.00）A.n+1 B.n1C.2nD.n/2解析：解析：在任意一棵二叉树中，度为 0的节点，即叶子节点。总是比度为 2的节点多一个。所以该二叉树的叶子节点数等于 n+1。17.某二叉树有 5个度为

23、2的节点，则该二叉树中的叶子节点数是( )。（分数：2.00）A.10B.8C.6 D.4解析：解析：根据二叉树的性质，在任意二叉树中，度为 O的节点(叶子节点)总是比度为 2的节点多一个。18.棵二叉树共有 31个节点，其中 8个是叶子节点，则度为 1的节点数为( )。 （分数：2.00）A.16 B.10C.6D.4解析：解析：根据二叉树的性质，在任意二叉树中，度为 0的节点(叶子节点)总是比度为 2的节点多一个。故此度为 I的节点个数=总节点数一叶子节点数一度为 2的节点数=3187=16。19.一棵二叉树中共有 80个叶子节点与 70个度为 1的节点，则该二叉树中的总节点数为( )。（

24、分数：2.00）A.219B.229 C.230D.231解析：解析：根据二叉树的性质，在任意二叉树中，度为 0的节点(叶子节点)总是比度为 2的节点多一个，总节点数=叶子节点数+度为 2的节点数+度为 1的节点数=80+79+70=229。20.一棵二叉树中共有 70个叶子节点与 80个度为 1的节点，则该二叉树中的总节点数为( )。（分数：2.00）A.219 B.221C.229D.231解析：解析：在二叉树中，叶子节点个数为 n 0 ，度为 2的节点数 n 2 =n 0 1。本题中叶子节点的个数为 70，所以度为 2的节点个数为 69。总节点数=叶子节点数+度为 1的节点数+度为 2的

25、节点数=70+80+69=219。21.设循环队列的存储空间为 Q(1：35)，初始状态为 front=rear=35 0现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为( )。（分数：2.00）A.15B.16C.20D.0或 35 解析：解析：循环队列的队头指针和尾指针都等于 15，此循环队列中元素的个数有两种情况：第一种情况是队头指针和尾指针都是第一次到达 15，此时元素个数为 0；第二种情况是队头指针第一次到达 15，而尾指针第二次到达 15，此时元素个数为 35。22.在一个容量为 15的循环队列中，若头指针 front=6，尾指针 rear=

26、9，则循环队列中的元素个数为( )。（分数：2.00）A.2B.3 C.4D.5解析：解析：循环队列中，rear 表示尾指针，front 表示头指针，当有元素入队时，rear=rear+1，而元素出队的时候，front=front+1，当 rear值大于 front值时，队列中的元素个数为 rearfront，当 rear的值小于 front时，列队中的元素个数为 rearfront+m(m表示队列的容量)。23.下列叙述中正确的是( )。（分数：2.00）A.栈是一种先进先出的线性表B.队列是一种后进先出的线性表C.栈与队列都是非线性结构D.栈与队列都是线性结构 解析：解析：栈是先进后出，队

27、列是先进先出。栈和队列都是一种线性表，属于线性结构。24.下列叙述中正确的是( )。（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是线性结构 D.有序线性表不可以采用顺序存储结构解析：解析：栈是“先进后出”队列是“先进先出”。栈和队列都是一种线性表，属于线性结构。有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。采用链式存储结构的线性表称之为线性链表。25.下列与队列结构有关联的是( )。（分数：2.00）A.函数的递归调用B.数组元素的引用C.多重循环的执行D.先到先服务的作业调度 解析：解析：队列中最先插入的元素将最先被删除，最后插入的元素

28、将最后被删除。26.对下列二叉树( )。 （分数：2.00）A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZ D.ABCDEFXYZ解析：解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则，访问根节点；前序遍历左子树；前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是 ABDYECFXZ。27.对如下二叉树 （分数：2.00）A.ABCDEFB.DBEAFCC.BDECFD.DEBFCA 解析：解析：所谓后序遍历是指在访问根据节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节

29、点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根点。因此，后序遍历二叉树的过程也是一个递归过程。其简单描述为：若二叉树为空，则结束返回；否则，先后序遍历左子树，然后后序遍历右子树，最后访问根节点。对于后序遍历，第一个访问的节点一定是最左下的节点，最后一个访问的节点一定是根节点，故 D)选项正确。28.对长度为 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为( )。（分数：2.00）A.log 2 nB.n/2C.n D.n+1解析：解析：在进行顺序查找过程中，如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中

30、的所有元素进行比较，这是顺序查找的最坏情况，需要比较的次数为 n次。29.在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为( )。（分数：2.00）A.63B.64 C.6D.7解析：解析：顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示找到(即查找成功)，若线性表中所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(即查找失败)。如果线性表中的第一个元素就是要查找的元素，则只需要做一次比较就查找成功，但如果要查找的元素是线性表中的最后一个元素

31、或者要查找元素不在线性表中，则需要与线性表中所有元素进行比较，这是顺序查找的最坏情况，比较次数为线性表的长度。30.下列叙述中正确的是( )。（分数：2.00）A.对长度为 n的有序链表进行查找，最坏情况下需要的比较次数为 n B.对长度为 n的有序链表进行对分查找，最坏情况下需要韵比较次数为(n/2)C.对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为(log 2 n)D.对长度为 n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog 2 n)解析：解析：本题主要考查的知识点为查找技术。顺序查找的使用情况：线性表为无序表；表采用键式存储结构。二分法查找只适用于顺序存储的有序表，并不适用于线性链表。31.用树形结构表示实体之间联系的模型是( )。（分数：2.00）A.关系模型B.网状模型C.层次模型 D.以上三个都是解析：解析：层次模型的基本结构是树形结构，这种结构方式在现实世界中很普遍，它们自顶向下、层次分明。32.数据库设计过程不包括( )。（分数：2.00）A.概念设计B.逻辑设计C.物理设计D.算法设计 解析：解析：数据库设计的四个阶段是：需求分析、概念设计、逻辑设计和物理设计。