1、国家二级 ACCESS机试选择题(数据结构与算法)模拟试卷 5及答案解析(总分:60.00,做题时间:90 分钟)一、选择题(总题数:30,分数:60.00)1.设顺序表的长度为 n。下列算法中,最坏情况下比较次数小于 n的是(分数:2.00)A.寻找最大项B.堆排序C.快速排序D.顺序查找法2.设栈的顺序存储空间为 S(1:m),初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后,top=0;则栈中的元素个数为(分数:2.00)A.不可能B.m+1C.1D.m3.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到右)的序列为(分数:2.00)
2、A.FEDCBAB.CBAFEDC.DEFCBAD.ABCDEF4.循环队列的存储空间为 Q(1:200),初始状态为 front=rear=200。经过一系列正常的入队与退队操作后,front=rear=1,则循环队列中的元素个数为(分数:2.00)A.0或 200B.1C.2D.1995.设栈的顺序存储空间为 S(1:m),初始状态为 top=0。现经过一系列正常的入栈与退栈操作后,top=m+1,则栈中的元素个数为(分数:2.00)A.不可能B.m+1C.0D.m6.下列排序法中,最坏情况下时间复杂度最小的是(分数:2.00)A.堆排序B.快速排序C.希尔排序D.冒泡排序7.某二叉树的前
3、序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到右)的序列为(分数:2.00)A.ABCDEFB.BCDEFAC.FEDCBAD.DEFABC8.下列叙述中正确的是(分数:2.00)A.对数据进行压缩存储会降低算法的空间复杂度B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性9.设数据结构 B=(D,R),其中 D=a,b,c,d,e,D R=(a,b),(b,c),(c,(d),(d,e),(e,D,(f,(a)该数据结构为(分数:2.00)A.非线性结构B.循环队列C.循环链表D.线性结构10.下列排
4、序法中,每经过一次元素的交换会产生新的逆序的是(分数:2.00)A.快速排序B.冒泡排序C.简单插入排序D.简单选择排序11.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后,front=rear=10。该队列中的元素个数为(分数:2.00)A.1B.0C.1或 0D.不确定12.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为(分数:2.00)A.ABDHECFGB.ABCDEFGHC.HDBEAFCGD.HDEBFGCA13.下列叙述中正确的是(分数:2.00)A.有的二叉树也能用顺序存储结构表示B.有两个
5、指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构14.下列各排序法中,最坏情况下时间复杂度最小的是(分数:2.00)A.堆排序B.快速排序C.希尔排序D.冒泡排序15.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后,front=10,rear=5。该队列中的元素个数为(分数:2.00)A.不确定B.5C.4D.616.某二叉树的前序序列为 ABDFHCEG,中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为(分数:2.00)A.ABCDEFGHB.HFDBGECAC.HGFEDCBAD.ACEGBD
6、FH17.某带链栈初始状态为 top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=10,bottom=20,该栈中的元素个数为(分数:2.00)A.不确定B.10C.1D.018.设表的长度为 15。则在最坏情况下,快速排序所需要的比较次数为(分数:2.00)A.105B.55C.15D.7519.设循环队列的存储空间为 Q(1:100),初始状态为空。现经过一系列正常操作后,front=49,则循环队列中的元素个数为(分数:2.00)A.不确定B.49C.51D.5020.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为(分数
7、:2.00)A.HDBEAFCGB.HDEBFGCAC.ABDHECFGD.ABCDEFGH21.下列叙述中正确的是(分数:2.00)A.解决一个问题可以有不同的算法,且它们的时间复杂度可以是不同的B.解决一个问题可以有不同的算法,但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关22.设表的长度为 n。下列查找算法中,在最坏情况下,比较次数最少的是(分数:2.00)A.有序表的二分查找B.顺序查找C.寻找最大项D.寻找最小项23.某带链栈的初始状态为 top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=bottom=20。该
8、栈中的元素个数为(分数:2.00)A.1B.0C.20D.不确定24.某二叉树的前序序列为 ABDFHCEG,中序序列为 HFDBACEG。该二叉树的后序序列为(分数:2.00)A.HFDBGECAB.ABCDEFGHC.HGFEDCBAD.ACEGBDFH25.下列叙述中错误的是(分数:2.00)A.算法的时间复杂度与问题规模无关B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算法的空间复杂度与算法运行输出结果的数据量无关26.设表的长度为 20。则在最坏情况下,冒泡排序的比较次数为(分数:2.00)A.90B.20C.19D.19027.在带链栈中,经
9、过一系列正常的操作后,如果 top=bosom,则栈中的元素个数为(分数:2.00)A.1B.0C.0或 ID.栈满28.设一棵树的度为 3,共有 27个结点,其中度为 3,2,0 的结点数分别为 4,1,10。该树中度为 l的结点数为(分数:2.00)A.1 1B.12C.13D.不可能有这样的树29.设数据结构 B=(D,R),其中 D=a,b,c,d,e,fR=(f,(a),(d,b),(e,(d),(c,e),(a,c)该数据结构为(分数:2.00)A.线性结构B.循环队列C.循环链表D.非线性结构30.下列叙述中错误的是(分数:2.00)A.循环队列空的条件是队头指针与队尾指针相同B
10、.若二叉树没有叶子结点,则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素,则队头指针与队尾指针必定相同国家二级 ACCESS机试选择题(数据结构与算法)模拟试卷 5答案解析(总分:60.00,做题时间:90 分钟)一、选择题(总题数:30,分数:60.00)1.设顺序表的长度为 n。下列算法中,最坏情况下比较次数小于 n的是(分数:2.00)A.寻找最大项 B.堆排序C.快速排序D.顺序查找法解析:解析:如果顺序表是线性存储的(不包括线性的链式表),那么元素要不就是从大到小,要不就是小到大的顺序,假设第一个数就是最大值,那么需要比较 1次,n 一 1应该是最
11、坏情况下要比较的次数,所以选项 A正确。2.设栈的顺序存储空间为 S(1:m),初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后,top=0;则栈中的元素个数为(分数:2.00)A.不可能 B.m+1C.1D.m解析:解析:栈是向上增长的,每次压入一个元素,栈的 TOP指针向上移动一位,即 top-1。对于这个题目,由于 top初始值等于 m+1,此时入栈一个元素,top 值减 1,即 m+1-1=m,依次类推,当栈满时,top的值等于 1,不会出现 top的值等于 0。所以选项 A正确。3.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到
12、右)的序列为(分数:2.00)A.FEDCBA B.CBAFEDC.DEFCBAD.ABCDEF解析:解析:后序遍历次序:左右根;中序遍历次序:左根右。由定义可知:后序遍历中最后一个是树的根结点,即 F结点;在中序遍历中,根结点左边的是左子树集,右边的是右子树集,即 ABCDE是根结点 F的左子树集合。问题就会转化为:求后序遍历是 ABC。DE,中序遍历是 ABCDE的子树。方法同上,因为中序遍历中,E 结点右边没有结点了,所以 E结点不包含右子树,否则就会被分为 2个子问题。以下是这道题的详细推理过程:步骤 1:由 ABCDEF。得出根结点为 F,由中序遍历可知:ABCDEF,右子树为空;步
13、骤 2:由 ABCDE得出左子树集合的根节点为 E,由中序可知:ABCDE,右子树为空;步骤 3:同理,二叉树更新后如下。4.循环队列的存储空间为 Q(1:200),初始状态为 front=rear=200。经过一系列正常的入队与退队操作后,front=rear=1,则循环队列中的元素个数为(分数:2.00)A.0或 200 B.1C.2D.199解析:解析:循环队列中,由于入队时尾指针 rear向前追赶头指针 front;出队时头指针 front向前追赶尾指针 rear,造成队空和队满时头尾指针均相等。因此,无法通过条件 front=rear来判别队列是“空”还是“满”。对于这个题目来说,经
14、过一系列正常的入队与退队操作后,front=rear=1,此时,要么队列为空(元素个数为 0),要么队列为满(元素个数为 200)。所以选项 A正确。5.设栈的顺序存储空间为 S(1:m),初始状态为 top=0。现经过一系列正常的入栈与退栈操作后,top=m+1,则栈中的元素个数为(分数:2.00)A.不可能 B.m+1C.0D.m解析:解析:栈是向上增长的,每次压入一个元素,栈的 TOP指针向上移动一位,即 top-1。对于这个题目,由于 top初始值等于 0,此时入栈一个元素,top 值减 1,即 01=-1,出现下溢错误,所以选项 A正确。6.下列排序法中,最坏情况下时间复杂度最小的是
15、(分数:2.00)A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析:解析:假设线性表的长度为 n,则在最坏情况下,冒泡排序需要经过 n2 遍的从前往后扫描和n2 遍的从后往前扫描,需要比较次数为 n(n1)2。快速排序法的最坏情况比较次数也是 n(n-1)2。简单插入排序,无论是否最坏都需要 n(n一 1)2 比较。堆排序,无论是否最坏情况都是比较O(nlog 2 n)次。所以选项 A正确。7.某二叉树的前序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到右)的序列为(分数:2.00)A.ABCDEF B.BCDEFAC.FEDCBAD.DEFABC解析:解析:前
16、序遍历次序:根左右;中序遍历次序:左根右。由定义可以知道:前序遍历中第一个就是树根结点,即 A结点;在中序遍历中,根结点左边的是左子树集,右边的是右子树集,即 BCDEF是根结点 A的右子树集合。问题就会转化为:求前序遍历是 BCDEF,中序遍历是 BCDEF的子树,方法同上。详细推理过程: 步骤 1:由 ABCDEF得出根结点为 A,由中序遍历可知:左子树为空,ABCDE F; 步骤2:由 BCDEF得出右子树集合的根节点为 B,由中序可知:左子树为空,BCDEF; 步骤 3:同理,二叉树更新后如下。8.下列叙述中正确的是(分数:2.00)A.对数据进行压缩存储会降低算法的空间复杂度 B.算
17、法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性解析:解析:算法的空间复杂度是指执行这个算法所需要的内存空间,包括 3个部分:输入数据所占的存储空间;程序本身所占的存储空间;算法执行过程中所需要的额外空间。为了降低算法的空间复杂度,主要应减少输入数据所占的存储空间以及额外空间,通常采用压缩存储技术,A 选项正确。9.设数据结构 B=(D,R),其中 D=a,b,c,d,e,D R=(a,b),(b,c),(c,(d),(d,e),(e,D,(f,(a)该数据结构为(分数:2.00)A.非线性结构 B.循环队列C.循环链表D.线性结构解析
18、:解析:该逻辑结构为非线性结构,在 R=(a,b),(b,c),(c,d),(d,e),(e,f),(f,a)中,各结点之间形成一个循环链。10.下列排序法中,每经过一次元素的交换会产生新的逆序的是(分数:2.00)A.快速排序 B.冒泡排序C.简单插入排序D.简单选择排序解析:解析:冒泡排序只交换相令昏元素,但不是每次移动都产生新韵逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序,因为当不会有新的逆序产生时,本轮比较结束。故选项 A正确。11.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后,front=rear=1
19、0。该队列中的元素个数为(分数:2.00)A.1 B.0C.1或 0D.不确定解析:解析:循环队列用数组 A0;m-1存放其元素值,已知其头尾指针分别是 front和 rear,则当前队列的元素个数是(rear-front+m)m=1,所以选项 A正确。12.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为(分数:2.00)A.ABDHECFG B.ABCDEFGHC.HDBEAFCGD.HDEBFGCA解析:解析:完全二叉树的特点是除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。根据上述的特点,完全二叉树按层次输出(同
20、一层从左到右)的序列为 ABCDEFGH,可以得到其结构如下:13.下列叙述中正确的是(分数:2.00)A.有的二叉树也能用顺序存储结构表示 B.有两个指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构解析:解析:完全二叉树如果“根”从 1开始编号,则第 i结点的左孩子编号为 2i,右孩子为 2i+1,双亲编号为(i2)下取整,空间紧密,适合顺序存储结构。所以选项 A正确。小提示:取整是指取不超过实数 x的最大整数,称为 x的整数部分。上取整就是对实数取大于当前实数的第一个整数;下取整就是对当前实数去掉小数取整。14.下列各排序法中,最坏情况下时间复杂度最小的是
21、(分数:2.00)A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析:解析:快速排序、冒泡排序最坏情况下时间复杂度是 O(n 2 ):希尔排序最坏情况下时间复杂度是O(n 1.2 )。堆排序最坏情况下时间复杂度是 O(nlog 2 n),所以选项 A正确。15.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后,front=10,rear=5。该队列中的元素个数为(分数:2.00)A.不确定 B.5C.4D.6解析:解析:循环队列用数组 A0:m-1存放其元素值,己知其头尾指针分别是 front和 rear,则当前队列的元素个数是(rear-front+m)
22、m=(5-10+m)m=(m-5)m。因为本题中的 m值不确定,所以(m-5)m的值不能确定。所以选项 A正确。16.某二叉树的前序序列为 ABDFHCEG,中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为(分数:2.00)A.ABCDEFGH B.HFDBGECAC.HGFEDCBAD.ACEGBDFH解析:解析:由于二叉树的前序序列 ABDFHCEG,可以确定这个二叉树的根结点是 A。再由中序序列HFDBACEG,可以得到,HFDB 为 A的左子树,CEG 为 A的右子树。同理依次对左子树 HFDB和右子树 CEG进行同样的推理,得到这个二叉树的结构如下17.某带
23、链栈初始状态为 top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=10,bottom=20,该栈中的元素个数为(分数:2.00)A.不确定 B.10C.1D.0解析:解析:对于链栈而言,使用了链表来实现栈,链表中的元素存储在不连续的地址。所以当top=10,bottom=20 时,不能确定栈中的元素个数,所以选项 A正确。18.设表的长度为 15。则在最坏情况下,快速排序所需要的比较次数为(分数:2.00)A.105 B.55C.15D.75解析:解析:假设线性表的长度为 n,在最坏情况下,快速排序法的比较次数是 n(n-1)2。题中 n=15,所以 15*142=10
24、5。所以选项 A正确。19.设循环队列的存储空间为 Q(1:100),初始状态为空。现经过一系列正常操作后,front=49,则循环队列中的元素个数为(分数:2.00)A.不确定 B.49C.51D.50解析:解析:循环队列用数组 Q1:100存放其元素值,已知其头尾指针分别是 front和 rear,则当前队列的元素个数是(rearfront+100)100,题目中首指针 rear的值未知,所以循环队列中的元素个数不能确定。所以选项 A正确。20.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为(分数:2.00)A.HDBEAFCG B.HDEBF
25、GCAC.ABDHECFGD.ABCDEFGH解析:解析:完全二叉树的特点是除最后一层外,每一层上的节点数均达到最大值:在最后一层上只缺少右边的若干结点。根据上述特点,完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。可以得到其结构如下:21.下列叙述中正确的是(分数:2.00)A.解决一个问题可以有不同的算法,且它们的时间复杂度可以是不同的 B.解决一个问题可以有不同的算法,但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关解析:解析:算法的时间复杂度和问题有关系,因为一个问题很有可能有许多类算法,但是它们的时间复杂度不同,如排序
26、问题就有 10种左右算法,它们复杂度显然是不一样的。所以选项 A正确。22.设表的长度为 n。下列查找算法中,在最坏情况下,比较次数最少的是(分数:2.00)A.有序表的二分查找 B.顺序查找C.寻找最大项D.寻找最小项解析:解析:有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是:将被查元素 x与线性表的中间项进行比较,若中间项的值等于 x,则说明查到;若小于中间项的值则在线性表的前半部分以相同的方法进行查找;若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下,二分查找需要比较 log 2 n次。顺序查找、寻找最大项、寻找最小项,在最坏情况下,比较次数都是
27、n次。所以选项 A正确。23.某带链栈的初始状态为 top=bottom=NULL,经过一系列正常的入栈与退栈操作后,top=bottom=20。该栈中的元素个数为(分数:2.00)A.1B.0C.20D.不确定 解析:解析:对于链栈而言,使用了链表来实现栈,链表中的元素存储在不连续的地址。所以当top=bottom=20时,不能确定栈中的元素个数。所以选项 D正确。24.某二叉树的前序序列为 ABDFHCEG,中序序列为 HFDBACEG。该二叉树的后序序列为(分数:2.00)A.HFDBGECA B.ABCDEFGHC.HGFEDCBAD.ACEGBDFH解析:解析:由于二叉树的前序序列
28、ABDFHCEG,可以确定这个二叉树的根结点是 A。再由中序序列HFDBACEG,可以得到,HFDB 为 A的左子树,CEG 为 A的右子树子同理依次对左子树。HFDB 和右子树 CEG进行同样的推理,得到这个二叉树的结构如下:25.下列叙述中错误的是(分数:2.00)A.算法的时间复杂度与问题规模无关 B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算法的空间复杂度与算法运行输出结果的数据量无关解析:解析:一般情况下,算法中基本操作重复执行的次数是问题规模 n的某个函数,用 T(n)表示,若有某个辅助函数 f(n),使得当 n趋近于无穷大时,T(n)f(
29、n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。记作 T(n)=O(f(n),称 O(f(n)为算法的渐进时间复杂度,简称时间复杂度。所以选项 A正确。26.设表的长度为 20。则在最坏情况下,冒泡排序的比较次数为(分数:2.00)A.90B.20C.19D.190 解析:解析:假设线性表的长度为 n,则在最坏情况下,冒泡排序的比较次数为 n(n一 1)2。本题中,n=20,所以 20*192=190。所以选项 D正确。27.在带链栈中,经过一系列正常的操作后,如果 top=bosom,则栈中的元素个数为(分数:2.00)A.1B.0C.0或 I D.栈满解析:解析:链栈
30、就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底,指针指向的存储单元中存有 1元素,则当 top=bottom时,栈中的元素个数为 1;如果栈底指针指向的存储单元中没有存元素,则当 top=bottom时,栈中的元素个数为 0。所以选项 C正确。28.设一棵树的度为 3,共有 27个结点,其中度为 3,2,0 的结点数分别为 4,1,10。该树中度为 l的结点数为(分数:2.00)A.1 1B.12 C.13D.不可能有这样的树解析:解析:因为任一棵树中,结点总数:总分支数目+1,所以:27=(0*10+n 1 *1+2*1+3*4)+1。运算结果 n 1 =12。其
31、中,n 1 表示叶子结点,所以选项 B正确。29.设数据结构 B=(D,R),其中 D=a,b,c,d,e,fR=(f,(a),(d,b),(e,(d),(c,e),(a,c)该数据结构为(分数:2.00)A.线性结构 B.循环队列C.循环链表D.非线性结构解析:解析:由结点之间的关系 R=(f,a),(d,b),(e,d),(c,e),(a,c)可以得到,该数据结构为:“fa-c-e-d-b”。由此可知结点 f没有前驱,结点 b没有后继结点,并且其它的结点只有一个前驱结点和一个后继结点,所以该数据结构为线性结构。所以应选 A选项。30.下列叙述中错误的是(分数:2.00)A.循环队列空的条件
32、是队头指针与队尾指针相同 B.若二叉树没有叶子结点,则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素,则队头指针与队尾指针必定相同解析:解析:初始化建空队时,令 front=rear=0,当队空时:front=rear;当队满时:front=rear 亦成立。因此,只凭等式 front=rear无法判断队空还是队满。有两种方法处理上述问题:另设一个标志位以区别队列是空还是满;少用一个元素空间,约定以“队列头指针 front在队尾指针 rear的下一个位置上”作为队列“满”状态的标志。即:队空时:front=rear;队满时:(rear+1)maxsize=front。所以选项 A正确。