1、国家二级 ACCESS机试选择题（公共基础知识）模拟试卷 3及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）带链栈的栈底指针是随栈的操作而动态变化的 （ B）若带链队列的队头指针与队尾指针相同，则队列为空 （ C）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 （ D）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的 2 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=bottom=20，该栈中的元素个数 为 ( )。 （ A） 0 （ B） 1 （ C） 20 （ D）不确定 3 某带链栈的初始状
2、态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=10， bottom=20。该栈中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 10 （ D）不确定 4 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=rear=10。该队列中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） l或 0 （ D）不确定 5 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=10， rear=5。该队列中的元素个数为 ( )。 （ A） 4 （
3、B） 5 （ C） 6 （ D）不确定 6 下列叙述中错误的是 ( )。 （ A）循环链表中有一个表头结点 （ B）循环链表是循环队列的存储结构 （ C）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 （ D）循环链表实现了空表与非空表运算的统一 7 某棵树中共有 25个结点，且只有度为 3的结点和叶子结点， 其中叶子结点有 7个，则该树中度为 3的结点数为 ( )。 （ A） 6 （ B） 7 （ C） 8 （ D）不存在这样的树 8 度为 3的 棵树共有 30个结点其中度为 3， 1的结点个数分别为 3， 4。则该树中的叶子结点数为 ( )。 （ A） 14 （ B） 15
4、 （ C） 16 （ D）不可能有这样的树 9 深度为 7的二叉树共有 127个结点，则下列说法中错误的是 ( )。 （ A）该二叉树是满二叉树 （ B）该二叉树有一个度为 1的结点 （ C）该二叉树是完全二叉树 （ D）该二叉树有 64个叶子结点 10 深度为 5的完全二叉树的结点数不可能是 ( )。 （ A） 15 （ B） 16 （ C） 17 （ D） 18 11 某完全二叉树共有 256个结点，则该完全二叉树的深度为 ( )。 （ A） 7 （ B） 8 （ C） 9 （ D） 10 12 在具有 2n个结点的完全二叉树中，叶子结点个数为 ( )。 （ A） n （ B） n+1 （
5、 C） n 1 （ D） n/2 13 下列叙述中正确的是 ( )。 （ A）非完全二叉树可以采用顺序存储结构 （ B）有两个指针域的链表就是二叉链表 （ C）有的二叉树也能用顺序存储结构表示 （ D）顺序存储结构一定是线性结构 14 有二叉树如下图所示： 则前序序列为 ( )。 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 15 设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为 ( )。 （ A） JIHGFEDCBA （ B） DGHEBUFCA （ C） GHIJDEFBCA （
6、D） ABCDEFGHIJ 16 某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBEDA，则前序遍历序列为 ( )。 （ A） CBADE （ B） CBEDA （ C） ABCDE （ D） EDCBA 17 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度 (根结点在第 1层 )为 ( )。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 18 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出 (同一层从左到右 )的序列为 ( )。 （ A） HGFEDCBA （ B） HFDBGECA （ C）
7、ABCDEFGH （ D） ACEGBDFH 19 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的前序序列为 ( )。 （ A） ABCDEFGH （ B） ABDHECFG （ C） HDBEAFCG （ D） HDEBFGCA 20 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是 ( )。 （ A）前序序列 （ B）中序序列 （ C）后序序列 （ D）前序序列或后序序列 21 设二叉树中共有 15个结点，其中的结点值互不相同。如果该二叉树的
8、前序序列与中序序列相同，则该二叉树的深度为 ( )。 （ A） 4 （ B） 6 （ C） 15 （ D）不存在这样的二叉树 22 在长度为 n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为( )。 （ A） n/4 （ B） n （ C） 3n/4 （ D） (n+1)/2 23 在长度为 n的顺序表中查找一个元素，假设需要 查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为 ( )。 （ A） n （ B） 3n/4 （ C） n/2
9、 （ D） n/4 24 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是 ( )。 （ A）在顺序存储的线性表中寻找最大项 （ B）在顺序存储的线性表中进行顺序查找 （ C）在顺序存储的有序表中进行对分查找 （ D）在链式存储的有序表中进行查找 25 线性表的长度为 n。在最坏情况下，比 较次数为 n 1的算法是 ( )。 （ A）顺序查找 （ B）同时寻找最大项与最小项 （ C）寻找最大项 （ D）有序表的插入 26 下列叙述中正确的是 ( )。 （ A）二分查找法只适用于顺序存储的有序线性表 （ B）二分查找法适用于任何存储结构的有序线性表 （ C）二分查找法适
10、用于有序循环链表 （ D）二分查找法适用于有序双向链表 27 在快速排序法中，每经过一次数据交换 (或移动 )后 ( )。 （ A）只能消除一个逆序 （ B）能消除多个逆序 （ C）不会产生新的逆序 （ D）消 除的逆序个数一定比新产生的逆序个数多 28 下列序列中不满足堆条件的是 ( )。 （ A） (98 ， 95 ， 93 ， 94 ， 89 ， 90 ， 76 ， 80 ， 55 ， 49) （ B） (98 ， 95 ， 93 ， 94 ， 89 ， 85 ， 76 ， 64 ， 55 ， 49) （ C） (98 ， 95 ， 93 ， 94 ， 89 ， 90 ， 76 ， 64
11、 ， 55 ， 49) （ D） (98 ， 95 ， 93 ， 96， 89， 85 ， 76， 64 ， 55 ， 49) 29 下列各组排序法中，最坏情况下比较次数相同的是 ( )。 （ A）简单选择排序与堆排序 （ B）简单插入排序与希尔排序 （ C）冒泡排序与快速排序 （ D）希尔排序与堆排序 30 设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为 ( )。 （ A） 120 （ B） 60 （ C） 30 （ D） 15 31 学生选课成绩表的关系模式是 SC(S#， C#， G)，其中 S#为学号， C#为课程号，G为成绩，关系 T=1TS#， C#
12、(SC)/C表示 ( )。（ A）全部学生的学号 （ B）选修了表 C中全部课程的学生学号 （ C）选修了课 程 C1或 C2的学生学号 （ D）所选课程成绩及格的学生学号 32 关系模型中的关系模式至少应是 ( )。 （ A） 1NF （ B） 2NF （ C） 3NF （ D） BCNF 33 某图书集团数据库中有关系模式 R(书店编号，书籍编号，库存数量，部门编号，部门负责人 )，其中要求 (1)每个书店的每种书籍只在该书店的一个部门销售； (2)每个书店的每个部门只有一个负责人； (3)每个书店的每种书籍只有一个库存数量。 则关系模式 R最高是 ( )。 （ A） 1NF （ B） 2
13、NF （ C） 3NF （ D） BCNF 国家二级 ACCESS机试选择题（公共基础知识）模拟试卷 3答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。 【知识模块】 公共基础知识 2 【正确答案】 B 【试题解析】 带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为 NULL;栈中只有一个元素时，头指针和尾指 针都指向这个元素。 【知识模块】 公共基础知识 3 【正确答案】 D 【试题解析】
14、 带链的栈使用了链表来表示栈，而链表中的元素存储在不连续的地址中，因此当 top=10， bottom=20时，不能确定栈中元素的个数。 【知识模块】 公共基础知识 4 【正确答案】 B 【试题解析】 带链队列空时，头指针和尾指针都为 NULL;队列中只有一个元素时，头指针和尾指针都指向这个元素。 【知识模块】 公共基础知识 5 【正确答案】 D 【试题解析】 带链的队列使用了链表来表 示队列，而链表中的元素存储在不连续的地址中，因此当 front=10， rear=5时，不能确定队列中元素的个数。 【知识模块】 公共基础知识 6 【正确答案】 B 【试题解析】 循环链表是指在单链表的第一个结
15、点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由 NULL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。 【知识模块】 公共基础知识 7 【正确答案】 D 【试题解析】 根据题意，树中只有度为 3的结点和叶子结点 (7个 )，则度为 3的结点有 25 7： 18个；又根据树中的结点数 =树中所有结点的度之和 +1，设度为 3的结点数为 n，则 3n+1=25，得 n=8。两种方式得到的度为 3的结点数不同，故不存在这样的树。 【知识模块】 公共基础知识 8 【正确答案】 B 【试题解析】 设叶子结点数为 n，则度为 2的结点数为
16、30 3 4 n =23 n，根据树中的结点数 =树中所有结点的度之和 +1，得 33 +2(23 n)+14+0n+1=30，则 n=15。 【知识模块】 公共基础知识 9 【正确 答案】 B 【试题解析】 满二叉树满足深度为 m的二叉树最多有 2n1个结点，本题中二叉树深度为 7且有 127个结点，满足 27 1 =127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第 k层上有 2k1结点，则该二叉树的叶子结点数为 271= 64个。满二叉树不存在度为 1的结点。 【知识模块】 公共基础知识 10 【正确答案】 A 【试题解析】 设完全二叉树的结点数为 n，根据深度为 k的
17、二叉树至多有 2k 1个结点，再根据完全二叉树的定义可知， 2k11 n2k1。本题中完全二叉树的深度为 5，则 2511 n251， 15 n31。因此，结点数不能为 15。 【知识模块】 公共基础知识 11 【正确答案】 C 【试题解析】 根据完全二叉树的性质：具有 n个结点的完全二叉树的深度为log： n+1。本题中完全二叉树共有 256个结点，则深度为 log2256+1=8+1=9。 【知识模块】 公共基础知识 12 【正确答案】 A 【试题解析】 由二叉树的定义可知，树中必定存在度为 O的结点和度为 2的结点，设度为 O结点有 a个，根据度为 0的结点 (即叶子结点 )总比度为 2
18、的结点多一个，得度为 2的结点有 a1个。再根据完全二叉树的定义，度为 1的结点有 0个或 1个，假设度 1结点为 0个， a+0+a1=2n，得 2a =2n 1，由于结点个数必须为整数，假设不成立；当度为 1的结点为 1个时， a+1+a 1=2n，得 a=n，即叶子结点个数为 n。 【知识模块】 公共基础知识 13 【正确答案】 C 【试题解析】 在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此 A项错误， C项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此 D项错误。双向链表也有两个指针域，
19、因此 B项错误。 【知识模块】 公共基础知识 14 【正确答案】 A 【试题解析】 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是 ABDFGCFH。 中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列 是 DBGEAFHC。 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是 DGEBHFCA。 【知识模块】 公共
20、基础知识 15 【正确答案】 B 【试题解析】 二叉树的前序序列为 ABDFJGHCFIJ，由于前序遍历首先访问根结点，可以确定该二叉树的根结点是 A。再由中序序列为 DBGEHACIFJ，可以得到结点 D、 B、 C、 E、 H位于根结点的左子树上，结点 C、 I、 F、 J位于根结点的右子树上。由于中序遍历和后 序遍历都是先遍历左子树，故本题后序遍历首先访问 D结点；再由后序遍历是最后访问根结点，故本题后序遍历最后访问的结点是根结点 A。采用排除法可知，后续序列为 DGHEBIJFCA。 【知识模块】 公共基础知识 16 【正确答案】 C 【试题解析】 二叉树的后序遍历序列为 CBEDA，
21、由于后序遍历最后访问根结点，可以确定该二叉树的根结点是 A。再由中序遍历序列为 CBADE，可以得到子序列 (CB)一定在左子树中，子序列 (DE)一定在右子树中。结点 C、 B在中序序列和后序序列中顺序未变，说明结点 B是结点 C的父 结点；结点 D、 E在中序序列和后序序列中顺序相反，说明结点 D是结点 E的父结点。因此该二叉树的前序遍历序列为 ABCDE。 【知识模块】 公共基础知识 17 【正确答案】 C 【试题解析】 二叉树的前序序列为 ABCDEFG，则 A为根结点；中序序列为DCBAEFG，可知结点 D、 C、 B位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上。另
22、外，结点 B、 C、 D在前序序列和中序序列中顺序相反，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子 树上。故二叉树深度为 4。 【知识模块】 公共基础知识 18 【正确答案】 C 【试题解析】 二叉树的前序序列为 ABDFHCEG，可以确定这个二叉树的根结点是 A;再由中序序列 HFDBACEG，可以得到 HFDB为根结点 A的左子树， CEG为根结点 A的右子树。同理依次对左子树 HFDB和右子树 CEG进行同样的推理，得到该二叉树的结构如下： 该二叉树按层次输出 (同一层从左到右 )的序列为 ABCDFFGH。 【知
23、识模块】 公共基础知识 19 【正确答案】 B 【试题解析】 完全二叉树的特点是除最后一 层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。根据这一特点，再根据题意输出序列为 ABCDEFGH，可以得到该二叉树的结构如下： 故此完全二叉树的前序序列为 ABDHECFG。 【知识模块】 公共基础知识 20 【正确答案】 B 【试题解析】 中序遍历的次序是先遍历左子树，再遍历根结点，最后遍历右子树。而在排序二叉树中，左子树结点值根结点值 右子树结点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。 【知识模块】 公共基础知识 21 【正确答案】 C 【试题解析】 在具
24、有 n个结点的二叉树中，如果各结点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只自右子树，左子树为空，二叉树的深度为 n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深度为 n。故本题中二叉树的深度为 15。 【知识模块】 公共基础知识 22 【正确答案】 D 【试题解析】 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。则平均比较次数： (1+2+n) n=(n(n+1) 2) n=(n+1)/2。 【知识模块】 公共基础知识 23 【正确答案】 B 【
25、试题解析】 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。这是找到元素的情况。如果没有找到元素，则要比较 n次。因此，平均需要比较：找到元素的情况 +未找到元素的情况 =(1+2+n)/n 【知识模块】 公共基础知识 24 【正确答案】 A 【试题解析】 寻找最大项，无论如 何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与要找的数据和原始的数据排列情况有关，最好情况是第 1次查看的一个数据恰好
26、是要找的数据，只需要比较 1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是 n和 log2n，平均情况则是 “1最坏情况 ”的平均，因而是不同的。 【知识模块】 公共基础知识 25 【正 确答案】 C 【试题解析】 顺序查找要逐个查看所有元素，会比较 n次。在最坏情况下，寻找最大项无论如何需要查看表中的所有元素， n个元素比较次数为 n1。同时寻找最大项和最小项，需要为判断较大值和较小值分别进行比较，会有更多的比较次数。有序表的插入最坏情况下是插入到表中的最后一个元素的后面位置，则会比较 n次。 【知识模块
27、】 公共基础知识 26 【正确答案】 A 【试题解析】 二分查找法 (又称对分查找法 )只适用于顺序存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列 (即从小到大， 但允许相邻元素值相等 )。 【知识模块】 公共基础知识 27 【正确答案】 B 【试题解析】 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是：从线性表中选取一个元素，设为 T，将线性表中后面小于 T的元素移到前面，而前面大于 T的元素移到后面，结果就将线性表分成两部分 (称两个子表 )， T插入到其分割线的位置处，这个过程称为线性表的分割，然后再用同
28、样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较，可以实线通过一 次交换而消除多个逆序，但由于均与 T(基准元素 )比较，也可能会产生新的逆序。 【知识模块】 公共基础知识 28 【正确答案】 D 【试题解析】 根据堆的定义， n个元素的序列 (h1， h2， h 。 )，当且仅当 hih2i且hih2i+1时为小顶堆，当且仅当 hih2i且 hih2i+1时为大顶堆。 D项中， h2=95，h4=96， h2 h4，但 h5=89， h2 h5，不满足小顶堆和大顶堆条件。 【知识模块】 公共基础知识 29 【正确答案】 C 【试题解析】 对于长度为 n的线性表，最坏
29、情况 下查找或排序的次数如下表：【知识模块】 公共基础知识 30 【正确答案】 A 【试题解析】 简单插入排序在最坏情况下，即初始排序序列是逆序的情况下，比较次数为 n(n1)/2，移动次数为 n(n1)/2。本题中 n=16， 16(16 1)2=815 =120。 【知识模块】 公共基础知识 31 【正确答案】 B 【试题解析】 S#， C#(SC)表示从关系 SC中取出 S#、 C#两列，得到的结果与关系C进行除运算，表示选修了表 C中全部课程的学生学号。 【知识模块】 公 共基础知识 32 【正确答案】 A 【试题解析】 关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同的
30、范式。满足最低要求的叫第一范式，简称 1NF。在满足第一范式的基础上，进一步满足更多要求规范则是第二范式。然后在满足第二范式的基础上，还可以再满足第三范式，以此类推。 对于关系模式，若其中的每个属性都已不能再分为简单项，则它属于第一范式。 若某个关系 R为第一范式，并且 R中每一个非主属性完全依赖于 R的某个候选键，则称其为第二范式。第二范式消除了非主属性对主键的部分依赖。 如果关系 R是第二范 式，并且每个非主属性都不传递依赖于 R的候选键，则称 R为第三范式。 (传递依赖：在关系模式中，如果 YX ， XA ，且 X不决定 Y和 A不属于 X，那么 YA 是传递依赖。 ) 比第三范式更高级
31、的 BCF范式，它要求所有属性都不传递依赖于关系的任何候选键。 【知识模块】 公共基础知识 33 【正确答案】 B 【试题解析】 由题可知关系模式 R有三个函数依赖： (书店编号，书籍编号 ) 部门编号 (书店编号，部门编号 ) 负责人 (书店编号，书籍编号 ) 库存数量 由此可知， (书店编号，书籍编号 )可以唯一标识关系模式 R中的每个元组，因此属于关系模式的主键。在此关系模式中，每个属性都是不可再分的， R属于 1NF，且 “书店编号 ”和 “书籍编号 ”单独之一都不能决定其他非主属性，所以 R属于 2NF;但 (书店编号，书籍编号 )可以决定 “部门编号 ”， “部门编号 ”又可决定 “部门负责人 ”，存在传递依赖，所以不属于 3NF，更不是 BCNF。 【知识模块】 公共基础知识
