二级MS Office基础题库.数据结构与算法

[单选题]1.下列叙述中正确的是（

）。A.程序可以作为算法的一种描述方法B.算法设计可以忽略算法的运算时间C.所谓算法就是计算方法D.算法设计只需考虑得到计算结果答案：A解析：解析：算法可以用程序、伪代码、流程图来描述，故A选项正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，故B选项错误。算法是一组有穷指令集，是解题方案的准确而完整的描述，故C选项错误。算法设计时要考虑算法的复杂度，问题规模越大越是如此，故D选项错误。2.深度为5的完全二叉树的结点数不可能是（

）。A.17B.16C.15D.18答案：C解析：解析：根据二叉树的性质，除最后一层，每一层上的结点数均达到最大值，所以前4层共有25-1-1=15个结点，而第5层至少有一个叶子结点，所以总结点数至少16，不可能是15，故本题答案为C。3.有二叉树如下图所示：则前序序列为（

）。A.A、ABDEGCFHB.B、DBGEAFHCC.C、DGEBHFCAD.D、ABCDEFGH答案：A解析：解析：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，故本题答案为A。4.下列叙述中正确的是（

）。A.循环队列是链式存储结构B.循环队列是顺序存储结构C.循环队列的插入运算不会发生溢出现象D.循环队列是非线性结构答案：B解析：解析：在顺序队列中,由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，故A选项错误，B选项正确。循环队列虽然能解决由于假溢出，却不能解决在顺序队列中,由于数组空间不够而产生的溢出的真溢出，故选项C错误。循环队列属于队列的特例，和栈同属于线性结构，D选项错误。5.下列叙述中正确的是（

）。A.没有根结点或没有叶子结点的数据结构一定是非线性结构B.所有数据结构必须有终端结点（即叶子结点）C.所有数据结构必须有根结点D.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构答案：A解析：解析：只有一个空节点的结构也属数据结构，所以B、C选项错误；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，故D选项错误。故本题答案为A。6.下列关于算法的描述中错误的是（

）。A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法的优劣取决于运行算法程序的环境D.算法设计必须考虑算法的复杂度答案：C解析：解析：算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故本题答案为C。7.设有二叉树如下图所示：则中序序列为（

）。A.A、DGEBHFCAB.B、ABCDEFGHC.C、DBGEAFHCD.D、ABDEGCFH答案：C解析：解析：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树，故本题答案为C。8.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（

）。A.节省存储空间B.排序时减少元素的比较次数C.便于查找D.插入与删除运算效率高答案：D解析：解析：顺序存储时，所有元素所占的存储空间是连续的（逻辑与物理统一），优点是存储空间利用率高，缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放指向该结点的前一个或后一个结点的指针，这样的优点是插入或删除元素时效率高，缺点是需要额外的空间（指针域）来表示数据之间的逻辑关系，存储空间利用率低。故本题答案为D。9.深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（

）。A.65B.64C.62D.63答案：D解析：解析：深度为6的满二叉树，结点个数为26-1=63，则第7层共有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，加上第6层的最后1个叶子结点，共有63个叶子结点，故本题答案为D。10.下列叙述中正确的是（

）。A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.任何存储方式的有序表均能采用二分法进行查找C.有序表可以用链接存储方式存储在不连续的存储空间内D.有序表只能顺序存储在连续的存储空间内答案：C解析：解析：有序是指元素按递增/递减顺序排列，与空间无关，A选项错误。能使用二分法查找的线性表必须满足是有序的顺序存储结构，B选项错误。有序表可以顺序存储也可以链式存储，D选项错误。故本题答案为C。11.设有二叉树如下图所示：则后序序列为（

）。A.A、DGEBHFCAB.B、ABCDEFGHC.C、ABDEGCFHD.D、DBGEAFHC答案：A解析：解析：后序遍历首先遍历左子树，然后访问遍历右子树，最后访问根结点，故本题答案为A。12.下列叙述中正确的是（

）。A.二叉树只能采用链式存储结构B.循环链表是非线性结构C.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构D.结点中具有两个指针域的链表一定是二叉链表答案：C解析：解析：二叉树通常采用链式存储结构，也可采用顺序存储结构，故A选项错误；循环链表是线性结构，故B选项错误；双向链表是线性结构，二叉树为非线性结构，二者结点中均有两个指针域，C选项正确；具有两个指针域的链表可能是双向链表，D选项错误13.设某二叉树中共有140个结点，其中有40个度为1的结点。则（

）。A.该二叉树中有50个度为2的结点B.该二叉树中有51个叶子结点C.该二叉树中有50个叶子结点D.不可能有这样的二叉树答案：D解析：解析：在二叉树中，只存在度为0、1、2的结点，度为1的结点为40，所以度为0和度为2的结点总数为100，而根据二叉树的性质，度为0的结点总是比度为2的结点多一个，所以不可能出现两者相加为100的情况，故不存在这样的二叉树。14.带链的栈与顺序存储的栈相比，其优点是（

）。A.入栈与退栈操作方便B.可以省略栈底指针C.入栈操作时不会受栈存储空间的限制而发生溢出D.以上说法均不正确答案：C解析：解析：带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故本题答案为C。15.某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（

）。A.A、CDABB.B、BADCC.C、ABCDD.D、DCBA答案：D解析：解析：根据前序序列为ABCD，可知A为根结点；再由中序序列为DCBA可知DCB是A的左子树。根据前序序列可知B是CD的根结点。再根据中序序列可知DC是结点B的左子树。根据前序序列可知，C是D的根结点，故后序序列为DCBA，D选项正确。16.下列关于算法复杂度叙述正确的是（

）。A.最坏情况下的时间复杂度一定高于平均情况的时间复杂度B.对同一个问题，采用不同的算法，则它们的时间复杂度是相同的C.时间复杂度与采用的算法描述语言有关D.时间复杂度与所用的计算工具无关答案：D解析：解析：算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节所影响，但算法的时间复杂度与这些因素无关，故D选项正确，C选项错误；最坏情况下的时间复杂度可以与平均情况的时间复杂度相同(比如冒泡排序)，A选项错误；不同的算法时间复杂度一般不相同，B选项错误。17.设有栈S和队列Q，初始状态均为空。首先依次将A,B,C,D,E,F入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为（

）。A.A、FEDZYXCBAB.B、DEFZYXABCC.C、FEDXYZCBAD.D、DEFXYZABC答案：A解析：解析：栈称为“后进先出”表或“先进后出”的线性表；队列称为“先进先出”或“后进后出”的线性表。A,B,C,D,E,F依次入栈，然后前三个元素出栈顺序为F,E,D，后续X,Y,Z入栈后重新全部出栈，顺序为Z,Y,X,D,C,B,A，按照出栈顺序入队，队列顺序为F,E,D,Z,Y,X,D,C,B,A，因为队列是先进先出的，退队顺序和入队顺序相同，所有退队元素的顺序为FEDZYXCBA。故本题答案为A。18.下列叙述中正确的是（

）。A.带链的栈有栈顶指针和栈底指针，因此又称为双重链表B.结点中具有多个指针域的链表称为多重链表C.有两个指针域的链表称为二叉链表D.循环链表是循环队列的链式存储结构答案：B解析：解析：双重链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，而栈中虽然存在栈顶指针和栈底指针，但每个栈元素只有一个指针域，故A选项错误；结点中具有多个指针域的链表就称为多重链表，B选项正确；双向链表中的结点也有两个指针域，但它并不属于二叉链表，故C选项错误；循环链表属于存储结构的概念，循环队列是属于逻辑结构的概念，循环队列既可以采用顺序存储，也可以采用链式存储，两者没有必然关联。故D选项不正确。19.某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为（

）。A.400B.754C.756D.不确定答案：C解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，即度为2的结点有44个，所以度为1的结点个数为845-45-44=756个。20.设数据元素的集合D={1，3，5，7，9}，D上的关系为R，下列数据结构B=（D，R）中为非线性结构的是（

）。A.R={(5,1),(7,9),(1,7),(9,3)}B.R={(1,3),(3,5),(5,9)}C.R={(9,7),(1,3),(7,1),(3,5)}D.R={(1,9),(9,7),(7,5),(5,3)}答案：B解析：解析：线性结构要求只有一个根结点和一个叶子结点，除根结点和叶子结点外，其它结点只有一个前件也只有一个后件。A选项的结构可以写成5→1→7→9→3，B选项是1→3→5→9，元素7没有前件和后件，C选项是9→7→1→3→5，D选项是1→9→7→5→3.三者都是线性结构，故本题答案为B。21.深度为7的二叉树共有127个结点，则下列说法中错误的是（

）。A.该二叉树有64个叶子结点B.该二叉树是完全二叉树C.该二叉树是满二叉树D.该二叉树有一个度为1的结点答案：D解析：解析：根据二叉树的性质，深度为m的二叉树最多有2m-1个结点，由题意可知，该二叉树的结点数27-1=127已达到最大值，所以该树是满二叉树，满二叉树没有度为1的结点，有64个叶子结点，故本题答案为D。22.下列叙述中正确的是（

）。A.非线性结构只能用多重链表表示B.有的非线性结构也能采用顺序存储结构C.所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D.非线性结构只能采用链式存储结构答案：B解析：解析：链式存储方式即可用于表示线性结构，也可用于表示非线性结构，非线性结构也可以用连续存储空间顺序存储。所以A、D选项错误，在所有的数据结构中并非所有的结构都能用顺序存储结构和采用链式存储结构表示，所以C选项也错误，故本题答案为B。23.某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为（

）。A.A、BADCB.B、ABCDC.C、BDCAD.D、DCBA答案：B解析：解析：从二叉树后序遍历为DCBA中可知A是根节点，在前序遍历中根结点位于首位，故本题答案为B。24.设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为（

）。A.n(n-1)/2B.nlog2nC.C、nD.log2n答案：D解析：解析：对于长度为n的有序线性表，最坏情况需要比较log2n次，故本题答案为D。25.某完全二叉树有256个结点，则该二叉树的深度为（

）。A.7B.8C.10D.9答案：D解析：解析：根据深度为k的二叉树至多有2k-1个结点，二叉树的第i层至多有2i-1个结点；因为前八层的结点就有28-1=255个，所以第九层的结点数是256-255=1个，故本题答案为D。26.设序列长度为n，在最坏情况下比较次数低于O(n2)的排序方法是（

）。A.直接插入排序B.希尔排序C.冒泡排序D.快速排序答案：B解析：解析：最坏情况下，冒泡排序、快速排序、直接插入排序、简单选择排序需要的比较次数为O(n2)；希尔排序需要的比较次数为O(n1.5)。27.某二叉树的前序序列为ABCD，中序序列为BDCA，则该二叉树的深度为（

）。A.3B.2C.4D.不确定答案：C解析：解析：先由前序遍历可知A是根结点，再由中序遍历可知BDC是左子树，没有右子树；对于子树BDC，由前序序列可知B是子树的根节点，所以DC是B的右子树。据此画出二叉树图形后，可知该二叉树的深度为4，故本题答案为C。28.设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则（

）。A.该循环队列已满B.该循环队列已空C.该循环队列中有1个元素D.该循环队列已空或已满答案：D解析：解析：当头指针和尾指针指向同一个元素时，循环队列为空或满，故本题答案为D。29.设序列长度为n，在最坏情况下，时间复杂度为O(log2n)的算法是（

）。A.二分法查找B.哈希查找C.分块查找D.顺序查找答案：A解析：解析：二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次，而顺序查找需要比较n次。故本题答案为A。30.某二叉树的深度为7，其中有64个叶子结点，则该二叉树中度为1的结点数为（

）。A.1B.0C.2D.63答案：B解析：解析：根据二叉树的性质，该树的第7层的节点数是27-1=64，已达到最大值，所以除了叶子结点，每个结点都有两个子结点，即每个结点都是度为2的，所以不存在度为1的结点，故本题答案为B。31.堆排序最坏情况下的时间复杂度为（

）。A.O(n1.5)B.O(log2n)C.O(nlog2n)D.O(n(n-1)/2)答案：C解析：解析：堆排序的平均和最坏情况时间复杂度都为O(nlog2n)，故本题答案为C。32.在线性表的链式存储结构中，其存储空间一般是不连续的，并且（

）。A.前件结点的存储序号小于后件结点的存储序号B.前件结点的存储序号可以小于也可以大于后件结点的存储序号C.前件结点的存储序号大于后件结点的存储序号D.以上说法均不正确答案：B解析：解析：链式存储结构使得节点在内存中不受位置的限制，结点存储号可以是任意的，故本题答案为B。33.设数据元素的集合D={1,2,3,4,5}，则满足下列关系R的数据结构中为线性结构的是（

）。A.R={(1,3),(4,1),(3,2),(5,4)}B.R={(1,2),(2,4),(4,5),(2,3)}C.R={(1,2),(3,2),(5,1),(4,5)}D.R={(1,3),(2,4),(3,5),(1,2)}答案：A解析：解析：线性结构要求只有一个根结点和一个叶子结点，除根结点和叶子结点外，其它结点只有一个前件也只有一个后件。B选项2的后面有4、3两个数值，C选项2的前面有1、3两个数值，D选项1的后面有3、2两个数值，所以B、C、D选项是非线性结构，故本题答案为A。34.某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（

）。A.32B.46C.48D.49答案：C解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，所以度为0的一共有17个，总的结点数即17+15+16=48个。35.下列叙述中正确的是（

）。A.每一个结点有两个指针域的链表一定是非线性结构B.循环链表是循环队列的链式存储结构C.所有结点的指针域都为非空的链表一定是非线性结构D.线性结构的存储结点也可以有多个指针答案：D解析：解析：当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，指针域为非空的链表也可以是线性结构，链式存储方式即可用于表示线性结构，也可用于表示非线性结构。故A、B、C选项不完全正确。线性结构的存储结点可以由多个指针只有保证有且只有指向一个前驱结点和一个后继结点就是线性结构。故本题答案为D。36.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（

）。A.相同，元素的存储顺序与逻辑顺序一致B.不同，但元素的存储顺序与逻辑顺序一致C.不同，且其元素的存储顺序可以与逻辑顺序不一致D.相同，但其元素的存储顺序可以与逻辑顺序不一致答案：A解析：解析：线性表的顺序存储结构具有以下两个基本特点：(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。另在线性表中数据元素所占的字节数都是一致的，故本题答案为A。37.设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=30，rear=10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（

）。A.m-19B.19C.m-20D.20答案：C解析：解析：循环队列为Q(1:m)，其初始状态为front=rear=m，则节点个数为m-(front-rear),且顺序查找的比较次数与实际节点个数一致，故本题答案为C。38.某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为（

）。A.434B.64C.436D.66答案：A解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，故本题答案为A。39.非空循环链表所表示的数据结构（

）。A.没有根结点也没有叶子结点B.有根结点也有叶子结点C.没有根结点但有叶子结点D.有根结点但没有叶子结点答案：B解析：解析：循环链表的第一个结点就是根结点，最后一个结点就是叶子结点，故本题答案为B。40.某棵树只有度为3的结点和叶子结点，其中度为3的结点有8个，则该树中的叶子结点数为（

）。A.15B.17C.不存在这样的树D.16答案：B解析：解析：在树结构中，树中的结点数即为树中所有结点的度数之和再加1。本题中该树总度数为3×8=24，所以结点总数为25个，则该树中叶子结点个数为25-8=17，故本题答案为B。41.某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m，rear=m-1，则该循环队列中的元素个数为（

）。A.1B.B、mC.m-1D.0答案：C解析：解析：由于存储空间可以存储m个结点，而头指针指向m，所以第一个结点就在第1个位置上，而最后一个结点在m-1的位置上，所以该循环队列共有m-1个结点。42.在排序过程中，每一次数据元素的移动会产生新的逆序的排序方法是（

）。A.快速排序B.冒泡排序C.简单插入排序D.以上说法均不正确答案：A解析：解析：在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序只交换相邻元素，不是每次移动都产生新的逆序。简单插入排序每一次比较后最多移掉一个逆序。快速排序是选出一个结点，然后将大于该结点的数据移到后面，将小于该结点的数据移到前面，所以会产生一个新的逆序，当不会有新的逆序产生时，本轮比较结束。43.某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m-1，rear=m，则该循环队列中的元素个数为（

）。A.A、mB.1C.m-1D.0答案：B解析：解析：设循环队列的存储空间为Q(1:m)，初始状态为空。在循环队列运转起来后，如果rear-front>0，则队列中的元素个数为rear-front个；如果rear-front0，则元素个数为m-(m-1)=1。44.某棵树中共有25个结点，且只有度为3的结点和叶子结点，其中叶子结点有7个，则该树中度为3的结点数为（

）。A.7B.8C.6D.不存在这样的树答案：D解析：解析：如果叶子结点有7个，那么度为3的结点数是25-7=18个，但如果度为3的结点有18个，因为树中的结点数即为树中所有结点的度数之和再加1，那么该树的总结点数是18*3+1=55个，与题目相矛盾，故本题答案为D。45.在最坏情况下，二分查找法的时间复杂度为（

）。A.A、nB.(n/2)log2nC.n/2D.log2n答案：D解析：解析：最坏情况下，二分法查找的时间复杂度是log2n。46.下列序列中不满足堆条件的是（

）。A.(98,95,93,94,89,90,76,80,55,49)B.(98,95,93,94,89,90,76,64,55,49)C.(98,95,93,96,89,85,76,64,55,49)D.(98,95,93,94,89,85,76,64,55,49)答案：C解析：解析：若有n个元素的序列，将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆：大根堆，所有结点的值大于或等于其左右子结点的值；小根堆，所有结点的值小于或等于其左右子结点的值。A、B、D选项属于大根堆。C选项由于98>95，判断属于大根堆，但9547.下列叙述中正确的是（

）。A.算法的复杂度用于衡量算法的控制结构B.算法的效率与数据的存储结构无关C.程序可以作为算法的一种表达方式D.算法的有穷性是指算法的规模不能太大答案：C解析：解析：算法可以用程序、伪代码、流程图来描述；而算法的有穷性是指算法能够在有限时间内完成，即执行有限步骤后能够终止；算法的复杂度用来衡量算法的好坏；算法的效率与数据的存储结构和逻辑结构都有关，故本题答案为C。48.某棵树的度为4，且度为4、3、2、1的结点个数分别为1、2、3、4，则该树中的叶子结点数为（

）。A.8B.10C.9D.11答案：D解析：解析：在树结构中，树中的结点数即为树中所有结点的度数之和再加1。本题中该树总度数为4*1+3*2+2*3+1*4=20，所以结点总数为21个，则该树中叶子结点个数为21-1-2-3-4=11个，故本题答案为D。49.设二叉树中共有15个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为（

）。A.6B.15C.4D.不存在这样的二叉树答案：B解析：解析：如果该二叉树前序序列与中序序列相同，说明该二叉树没有左子结点，只有右子结点，即所有结点结成一串，所以该二叉树深度为15，故本题答案为B。50.设循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为（

）。A.3B.52C.1D.2答案：D解析：解析：当头指针和尾指针指向同一个元素时，队列为空或队列为满，此时如果正常地插入两个元素，说明队列为空（为满的话插入元素会产生溢出错误），所以插入后元素个数为2，故本题答案为D。51.设数据元素集合为{A，B，C，D，E，F}，下列关系为线性结构的是（

）。A.A、R={(D,F),(E,C),(B,C),(A,B),(C,F)}B.B、R={(D,E),(E,A),(B,C),(F,B),(C,F)}C.C、R={(A,B),(C,D),(B,A),(E,F),(F,A)}D.D、R={(D,E),(E,A),(B,C),(A,B),(C,F)}答案：D解析：解析：线性结构要求只有一个根结点和一个叶子结点，除根结点和叶子结点外，其它结点只有一个前件也只有一个后件。对各个选项分析可以得出D选项符合要求，故本题答案为D。52.下列处理中与队列有关的是（

）。A.执行程序中的过程调用B.操作系统中的作业调度C.执行程序中的循环控制D.以上说法均不正确答案：B解析：解析：在计算机系统中，如果一次只能执行一个程序，则在多个用户程序需要执行时，这些用户程序必须按照到来的顺序进行排队等待。即操作系统中的作业调度使用的是队列的先进先出思想，故本题答案为B。53.下列数据结构中，属于非线性结构的是（

）。A.双向链表B.二叉链表C.循环队列D.循环链表答案：B解析：解析：树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构，而二叉链表是二叉树的链式存储结构，故本题答案为B。54.设二叉树中共有31个结点，其中的结点值互不相同。如果该二叉树的后序序列与中序序列相同，则该二叉树的深度为（

）。A.16B.17C.5D.31答案：D解析：解析：如果该二叉树后序序列与中序序列相同，说明该二叉树没右子结点，只有左子结点，即所有结点结成一串，所以该二叉树深度为31，故本题答案为D。55.下列叙述中错误的是（

）。A.空数据结构可以是线性结构也可以是非线性结构B.数据结构中的数据元素可以是另一数据结构C.数据结构中的数据元素不能是另一数据结构D.非空数据结构可以没有根结点答案：C解析：解析：数据结构中的数据元素可以是另外一种数据结构，故本题答案为C。56.为了降低算法的空间复杂度，要求算法尽量采用原地工作(inplace)。所谓原地工作是指（

）。A.执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）B.执行算法时不使用任何存储空间C.执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化D.执行算法时不使用额外空间答案：A解析：解析：原地工作原理是执行算法时使用固定的额外空间，降低了算法的空间复杂度，故本题答案为A。57.设栈的存储空间为S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=1。现又要将一个元素进栈，栈顶指针top值变为（

）。A.A、mB.发生栈满的错误C.2D.0答案：B解析：解析：初始状态为top=m+1，说明栈底是m，栈顶是1，当top=1时，指针已经指向栈顶，栈已经满了，再增加就会产生溢出错误，故本题答案为B。58.设某二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为（

）。A.A、DCBAHGFEB.B、EFGHABCDC.C、HGFEDCBAD.D、ABCDEFGH答案：C解析：解析：当二叉树的后序遍历与中序遍历相同时，说明该二叉树各结点都是只有左子结点，所以前序遍历的结果与后序遍历的结果正好相反，故本题答案为C。59.设栈的存储空间为S(1:m)，初始状态为top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针top值为（

）。A.m-1B.产生栈空错误C.m+1D.0答案：C解析：解析：在该栈中，初始状态是空栈，经过若干次操作后，指针指向m，意味着栈中还有一个元素，如果此时退出一个元素，那么再次成为空栈，所以top=m+1，故本题答案为C。60.下列叙述中正确的是（

）。A.数据结构中的数据元素只能是另一种线性结构B.数据结构中的数据元素只能是另一种非线性结构C.数据结构中的数据元素可以是另一种数据结构D.以上说法均不正确答案：C解析：解析：数据结构中的数据元素可以是另外一种数据结构，故本题答案为C。61.下列叙述中正确的是（

）。A.二分查找法适用于有序双向链表B.二分查找法只适用于顺序存储的有序线性表C.二分查找法适用于有序循环链表D.二分查找法适用于任何存储结构的有序线性表答案：B解析：解析：二分查找法只适用于顺序存储的有序线性表，故本题答案为B。62.设某二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为（

）。A.A、HGFEDCBAB.B、ABCDEFGHC.C、EFGHABCDD.D、DCBAHGFE答案：A解析：解析：当二叉树的前序遍历与中序遍历相同时，说明该二叉树各结点都是只有右子结点，所以前序遍历的结果与后序遍历的结果正好相反，故本题答案为A。63.设循环队列的存储空间为Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为（

）。A.0B.1C.m-2D.m-1答案：C解析：解析：由于存储空间可以存储m个结点，而头指针指向m，所以第一个结点就在第1个位置上，而最后一个结点在m-1的位置上，所以该循环队列共有m-1个结点，此后又删除一个元素，所以最后队列中元素个数为m-2，故本题答案为C。64.某二叉树共有730个结点，其中度为1的结点有30个，则叶子结点个数为（

）。A.351B.不存在这样的二叉树C.350D.1答案：B解析：解析：在二叉树中，只存在度为0、1、2的结点，度为1的结点为30，所以度为0和度为2的结点总数为700，而根据二叉树的性质，度为0的结点总是比度为2的结点多一个，所以不可能出现两者相加为700的情况，故不存在这样的二叉树。65.能从任意一个结点开始没有重复地扫描到所有结点的数据结构是（

）。A.循环链表B.双向链表C.二叉链表D.有序链表答案：A解析：解析：循环列表可以实现不重复地扫描到所有结点，故本题答案为A。66.若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是（

）。A.前序序列B.中序序列C.后序序列D.以上答案均不正确答案：B解析：解析：该二叉树中，根结点大于左子结点，而小于右子结点，所以只要先遍历左子树，然后访问根结点，最后遍历右子，即可满足有序，也就是中序遍历，故本题答案为B。67.设循环队列的存储空间为Q(1:m)，初始状态为空。现经过一系列正常的入队与退队操作后，front=m-1，rear=m，此后再向该循环队列中插入一个元素，则队列中的元素个数为（

）。A.2B.1C.m-1D.D、m答案：A解析：解析：设循环队列的存储空间为Q(1:m)，初始状态为空。在循环队列运转起来后，如果rear-front>0，则队列中的元素个数为rear-front个；如果rear-front0，则元素个数为m-(m-1)=1，此后又插入一个元素，则循环队列中共有2个元素，故本题答案为A。68.某二叉树共有530个结点，其中度为2的结点有250个，则度为1的结点数为（

）。A.251B.30C.249D.29答案：D解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，即度为0的结点有251个，所以度为1的结点个数为530-250-251=29个。69.下列叙述中正确的是（

）。A.对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同B.解决同一个问题的不同算法的时间复杂度必定是相同的C.解决同一个问题的不同算法的时间复杂度一般是不同的D.对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定相同答案：C解析：解析：一般来说，不同算法的时间复杂度是不同的，而且时间复杂度也受数据的存储结构影响，故本题答案为C。70.在最坏情况下，堆排序的时间复杂度是（

）。A.O(n1.5)B.O(nlog2n)C.O(log2n)D.O(n2)答案：B解析：解析：堆排序的平均和最坏情况时间复杂度都为O(nlog2n)，故本题答案为B。71.下列叙述中正确的是（

）。A.压缩数据存储空间不会降低算法的空间复杂度B.算法的空间复杂度是指算法程序控制结构的复杂程度C.算法的空间复杂度与算法所处理的数据存储空间有关D.算法的空间复杂度是指算法程序中指令的条数答案：C解析：解析：算法的空间复杂度是执行算法所需的内存空间，它与算法所处理的数据存储空间有关，故本题答案为C。72.下列各组排序法中，最坏情况下比较次数相同的是（

）。A.简单插入排序与希尔排序B.简单选择排序与堆排序C.希尔排序与堆排序D.冒泡排序与快速排序答案：D解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为O(n2)；希尔排序需要的比较次数为O(n1.5)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；二分法查找需要的比较次数为O(log2n)。73.设数据元素的集合D={1,2,3,4,5}。下列数据结构B=(D,R)中为非线性结构的是（

）。A.R={(1,2),(2,3),(3,4),(4,5)}B.R={(1,2),(2,3),(4,3),(3,5)}C.R={(5,4),(4,3),(3,2),(2,1)}D.R={(2,5),(5,4),(3,2),(4,3)}答案：B解析：解析：线性结构要求只有一个根结点和一个叶子结点，除根结点和叶子结点外，其它结点只有一个前件也只有一个后件。分析各个选项可知只有B选项是非线性结构，故本题答案为B。74.某二叉树共有400个结点，其中有100个度为1的结点，则该二叉树中的叶子结点数为（

）。A.150B.149C.不存在这样的二叉树D.151答案：C解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，由题意可知，叶子结点和度为2的结点个数总和为400-100=300，无法满足该性质，故不存在这样的二叉树。所以本题答案为C。75.设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=20，则栈中的元素个数为（

）。A.21B.20C.30D.31答案：D解析：解析：初始状态为top=51，说明栈底的地址为50，栈顶的位置为1，经过一系列操作后，top=20，则说明20-50位置都有元素，共计31个，故本题答案为D。76.下列叙述中正确的是（

）。A.有多个指针域的链表一定是非线性结构B.只有一个根结点的数据结构一定是线性结构C.有多个指针域的链表有可能是线性结构D.有两个指针域的链表一定是二叉树的存储结构答案：C解析：解析：线性结构应满足：(1)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件；那么该结构就是线性结构，与结点有几个指针域没有必然关系，结点在有多个指针域的情况下，只要满足只有一个指针域有具体的值，其他都为空，那么仍然可以构成线性结构，故本题答案为C。77.某二叉树共有150个结点，其中有50个度为1的结点，则（

）。A.该二叉树有49个叶子结点B.该二叉树有51个叶子结点C.该二叉树有50个叶子结点D.不存在这样的二叉树答案：D解析：解析：在二叉树中，只存在度为0、1、2的结点，度为1的结点为50，所以度为0和度为2的结点总数为100，而根据二叉树的性质，度为0的结点总是比度为2的结点多一个，所以不可能出现两者相加为100的情况，故不存在这样的二叉树。78.循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又正常地插入了一个元素，则循环队列中的元素个数为（

）。A.49B.50C.51D.1答案：D解析：解析：当头指针和尾指针指向同一个元素时，队列为空或队列为满，此时如果正常地插入一个元素，说明队列为空（为满的话插入元素会产生溢出错误），插入后元素个数为1，故本题答案为D。79.某二叉树的前序遍历序列为ABCDE，中序遍历序列为CBADE，则后序遍历序列为（

）。A.A、EDCBAB.B、CBADEC.C、CBEDAD.D、EDABC答案：C解析：解析：由前序遍历可以得出A是根结点，结合中序遍历知道CB是左子树，DE是右子树；再回到前序遍历，CB这棵左子树B是根结点，由中序遍历知道C是B的左子结点；同理可得出DE右子树的情况；还原出此二叉树的原形后，再进行后序遍历，可以得出后序遍历的顺序是CBEDA，故本题答案为C。80.下列叙述中正确的是（

）。A.循环队列是队列的一种存储结构B.所有二叉树均不适合用顺序存储结构C.二分查找适用于任何存储方式的有序表D.有两个指针域的链表一定是二叉树的存储结构答案：A解析：解析：循环队列是队列的一种顺序存储结构，A选项正确。并不是所有二叉树都要采用链式存储，所以B选项错误。二分法查找适用于顺序存储的有序表，所以C选项错误。一个数据结构是不是二叉树，并不是由结点包含几个指针域决定的，而是有几个后件决定的，所以D选项错误。81.下列叙述中正确的是（

）。A.算法复杂度是指算法控制结构的复杂程度B.算法设计只需考虑结果的可靠性C.算法复杂度是用算法中指令的条数来度量的D.数据的存储结构会影响算法的效率答案：D解析：解析：算法的复杂度有时间复杂度、空间复杂度，两者分别表示执行算法所需要的计算工作量、执行算法所需的内存空间，故A选项和C选项错误。算法设计时要考虑算法的复杂度，问题规模越大越是如此，故B选项错误。算法的逻辑结构和存储结构都会影响算法的效率，故本题答案为D。82.循环队列的存储空间为Q(1:40)，初始状态为front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又正常地退出了一个元素，则循环队列中的元素个数为（

）。A.14B.16C.39D.9答案：C解析：解析：当头指针和尾指针指向同一个元素时，队列为空或队列为满，此时如果正常退出一个元素，说明当时是队满，队满的情况下，此循环队列可以有40个元素，退出1个后，还有39个，故本题答案为C。83.某二叉树的中序遍历序列为CBADE，后序遍历序列为CBEDA，则前序遍历序列为（

）。A.A、CBADEB.B、ABCDEC.C、CBEDAD.D、EDCBA答案：B解析：解析：先由后序遍历可知A是根结点，再由中序遍历可知CB是左子树，DE是右子树；再根据后序遍历可知B和D分别是左右子树中的根结点，由中序遍历可知C是B的左子结点，E是D的右子结点，据此画出二叉树图形后，再进行前序遍历，可得到ABCDE，故本题答案为B。84.下列叙述中正确的是（

）。A.没有根结点的一定是非线性结构B.只有一个根结点的必定是线性结构或二叉树C.只有一个根结点和一个叶子结点的必定是线性结构D.非线性结构可以为空答案：D解析：解析：一个空的数据结构既可以是线性结构也可以是非线性结构，所以D选项正确，A选项错误。线性结构要求只有一个根结点和一个叶子结点，并且中间结点有且只有一个前件和一个后件，所以B选项和C选项错误，故本题答案为D。85.设栈的存储空间为S(1:60)，初始状态为top=61。现经过一系列正常的入栈与退栈操作后，top=25，则栈中的元素个数为（

）。A.36B.25C.35D.26答案：A解析：解析：初始状态为top=61,说明栈空时top=61；入栈时栈顶指针是减操作，即每入栈一个元素，栈顶指针top的值减1，则入栈元素的个数等于61-top；当top的值为25时，栈中元素的个数为36，故本题答案为A。86.下列排序方法中，最坏情况下时间复杂度（即比较次数）最低的是（

）。A.快速排序B.冒泡排序C.希尔排序D.简单插入排序答案：C解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为O(n2)；希尔排序需要的比较次数为O(n1.5)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；二分法查找需要的比较次数为O(log2n)，故本题答案为C。87.下列叙述中错误的是（

）。A.非线性结构中至少有一个根结点B.有一个以上叶子结点的必定是非线性结构C.有一个以上根结点的必定是非线性结构D.非线性结构中可以没有根结点与叶子结点答案：A解析：解析：线性结构应满足：(1)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件；所以B、C选项正确，一个空的数据结构既可以是线性结构也可以是非线性结构，所以D选项正确，A选项错误。88.某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为（

）。A.不可能有这样的二叉树B.150C.149D.199答案：A解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，叶子结点有200个，那么度为0的结点就应该有199个，总数已经超过350个，与题意矛盾，故本题答案为A。89.下列排序方法中，最坏情况下时间复杂度（即比较次数）低于O(n2)的是（

）。A.冒泡排序B.快速排序C.堆排序D.简单插入排序答案：C解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为O(n2)；希尔排序需要的比较次数为O(n1.5)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；二分法查找需要的比较次数为O(log2n)，故本题答案为C。90.下列算法中，最坏情况下时间复杂度最低的是（

）。A.顺序查找法B.堆排序C.二分查找法D.快速排序答案：C解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为O(n2)；希尔排序需要的比较次数为O(n1.5)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；二分法查找需要的比较次数为O(log2n)，故本题答案为C。91.下列叙述中错误的是（

）。A.所有二叉树都只能用二叉链表表示B.有多个指针域的链表也有可能是线性结构C.二分查找法只适用于顺序存储的线性有序表D.循环队列是队列的存储结构答案：A解析：解析：一般来说，二叉树采用链式存储结构，但由于完全二叉树的特点，采用顺序存储也能方便地访问其中的每一个元素。故A选项错误。92.某二叉树共有400个结点，其中有99个度为1的结点，则该二叉树中的叶子结点数为（

）。A.151B.149C.不可能有这样的二叉树D.150答案：A解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，由题意可知，叶子结点和度为2的结点个数总和为400-99=301，所以叶子结点个数为151个，度为2的结点个数为150个，故本题答案为A。93.循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，则循环队列中的元素个数为（

）。A.49B.0或50C.26D.25答案：B解析：解析：当队头和队尾指针指向同一个元素时，队列为空或队列为满，故本题答案为B。94.设数据元素的集合D={1,2,3,4,5,6}。下列数据结构B=(D,R)中为线性结构的是（

）。A.R={(1,2),(2,3),(6,5),(3,6),(5,4)}B.R={(5,4),(3,4),(3,2),(4,3),(5,6)}C.R={(1,2),(2,3),(3,4),(4,5),(6,5)}D.R={(1,2),(2,3),(4,3),(4,5),(5,6)}答案：A解析：解析：线性结构要求只有一个根结点和一个叶子结点，除根结点和叶子结点外，其它结点只有一个前件也只有一个后件。B选项5的后面有4、6两个数值，C选项5的前面有4、6两个数值，D选项4的后面有3、5两个数值，所以B、C、D选项是非线性结构，故本题答案为A。95.设栈的顺序存储空间为S(1:m)，初始状态为top=m+1，则栈中的数据元素个数为（

）。A.A、m-topB.m-top+1C.C、top-mD.top-m+1答案：B解析：解析：栈的初始状态top=m+1，说明栈空时top=m+1，入栈时栈顶指针是减操作(top=top-1)，出栈时栈顶指针是加操作(top=top+1)。本题可以假设栈中有x个元素，当x=0时，即栈中没有元素，top=m+1;当x=m时，即栈满，则top=1，所以可得top=m+1-x，即x=m-top+1。96.某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则前序遍历序列为（

）。A.A、CBAFEDB.B、DEFCBAC.C、FEDCBAD.D、ABCDEF答案：C解析：解析：后序遍历与中遍历相同，说明该二叉树除了叶子结点外，所有结点都只有左子结点，依据题目中的结点情况，可以得出其前序遍历的结果为FEDCBA，故本题答案为C。97.在具有n个结点的二叉树中，如果各结点值互不相同，但前序遍历序列与中序遍历序列相同，则该二叉树的深度为（根结点在第1层）（

）。A.n-1B.n/2+1C.C、nD.n+1答案：C解析：解析：前序遍历和中序遍历相同说明该树除了叶子结点外，每个结点只有右子结点，也就是该二叉树是深度为n，结点个数为n的二叉树，故本题答案为C。98.下列叙述中错误的是（

）。A.不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的B.顺序栈的栈底指针在操作过程中是固定不变的C.不管是顺序栈还是带链的栈，在操作过程中其栈顶指针均是动态变化的D.带链栈的栈底指针在操作过程中是有可能改变的答案：A解析：解析：带链栈其栈底指针是动态变化的，故本题答案为A。99.某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则后序遍历序列为（

）。A.A、BCDEFAB.B、FEDCBAC.C、DEFABCD.D、CDEFAB答案：B解析：解析：如果二叉树的前序遍历和中序遍历相同，那么说明此二叉树除叶子结点外，所有结点都是只有右子结点。根据上述说法画出二叉树可知，其后序遍历序列为FEDCBA，故本题答案为B。100.下列叙述中正确的是（

）。A.堆可以用完全二叉树表示，其中序遍历序列是有序序列B.任何二叉树只能采用链式存储结构C.多重链表必定是非线性结构D.排序二叉树的中序遍历序列是有序序列答案：D解析：解析：排序二叉树中，左子树上的值均小于其根结点，右子树上的值均大于其根结点，所以排序二叉树的中序遍历一定是有序序列，故本题答案为D。101.下列叙述中正确的是（

）。A.算法的时间复杂度与运行算法时特定的输入有关B.算法的时间复杂度与算法程序编制者的水平有关C.算法的时间复杂度与计算机的运行速度有关D.算法的时间复杂度与算法程序中的语句条数成正比答案：A解析：解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法程序执行的具体时间和算法的时间复杂度并不是一致的。算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节所影响，而算法的时间复杂度与这些因素无关。因此B、C、D选项错误。通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。故本题答案为A。102.设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为（

）。A.50B.1C.0D.49答案：B解析：解析：初始状态为top=51,说明栈空时top=51；入栈时栈顶指针是减操作，即每入栈一个元素，栈顶指针top的值减1，则入栈元素的个数等于51-top；当top的值为50时，栈中元素的个数为1，故本题答案为B。103.某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为（

）。A.198B.199C.不存在这样的二叉树D.200答案：D解析：解析：根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，题目中度为2的结点为199个，则叶子结点为199+1=200。故本题答案为D。104.下列叙述中错误的是（

）。A.算法的时间复杂度与实现算法过程中的具体细节无关B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.对于各种特定的输入,算法的时间复杂度是固定不变的答案：D解析：解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法所执行的基本运算次数与问题的规模有关。对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，故本题答案为D。105.在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（

）。A.n/4B.3n/4C.C、nD.(n+1)/2答案：D解析：解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。两种情况平均即(1+n)/2。故本题答案为D。106.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（

）。A.后序序列B.前序序列或后序序列C.前序序列D.中序序列答案：D解析：解析：由题目可知，根结点的值一定大于左子树的结点，并且一定小于右子树的结点，所以要想排序，只能是先左子树，再根结点，再右子树，即采用中序遍历，故本题答案为D。107.循环队列的存储空间为Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（

）。A.26B.51C.1，或50且产生上溢错误D.2答案：C解析：解析：当头指针和尾指针指向同一个元素时，队列为空或队列为满，此时如果插入一个元素，若队列为满时产生溢出错误，若队列为空则成功插入一个元素，故本题答案为C。108.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（

）。A.在顺序存储的线性表中寻找最大项B.在顺序存储的有序表中进行对分查找C.在顺序存储的线性表中进行顺序查找D.在链式存储的有序表中进行查找答案：A解析：解析：在顺序存储的线性表中查找最大项时，最坏情况下比较次数为n-1，顺序查找的平均情况时间复杂度为O(n)，故本题答案为A。109.在具有2n个结点的完全二叉树中，叶子结点个数为（

）。A.A、nB.n+1C.n/2D.n-1答案：A解析：解析：关于完全二叉树的特殊性质：假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则n=n0+n1+n2（其中n为完全二叉树的结点总数）；又因为二叉树的基本性质（n0=n2+1）,所以得n=2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2或n0=(n+1)/2。简便来算，就是n0=n/2（n为奇数时结果向上取整）。由题可知，结点总数为2n，故n0=2n/2=n，本题答案为A。110.下列叙述中正确的是（

）。A.在循环链表中，头指针和链尾指针的动态变化决定链表的长度B.在线性链表中，头指针和链尾指针的动态变化决定链表的长度C.在栈中，栈顶指针的动态变化决定栈中元素的个数D.在循环队列中，队尾指针的动态变化决定队列的长度答案：C解析：解析：在循环队列中，队头指针和队尾指针都是动态变化的，所以循环队列中的元素个数由队头指针和队尾指针共同决定；在循环链表中，前一个结点指向后一个结点，而最后一个结点指向头结点，只有头结点是固定的；线性链表中，由于前一个结点包含下一个结点的指针，尾结点指针为空，要插入删除元素，只需要改变相应位置的结点指针即可，头指针和尾指针无法决定链表长度；在栈中，栈底保持不变，有元素入栈，栈顶指针增加；有元素出栈，栈顶指针减小。故本题答案为C。111.循环队列的存储空间为Q(1:40)，初始状态为front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为（

）。A.40B.39，或0且产生下溢错误C.14D.15答案：B解析：解析：当头指针和尾指针指向同一个元素时，队列为空或队列为满，此时执行退出元素操作，若队列为满时40个元素减去1个还剩39个，若队列为空则产生下溢错误，故本题答案为B。112.某二叉树的中序遍历序列为CBADE，后序遍历序列为CBADE，则前序遍历序列为（

）。A.A、EDABCB.B、EDCBAC.C、CBEDAD.D、CBADE答案：A解析：解析：先由后序遍历可知E是根结点，再由中序遍历可知CBAD都是左子树；再根据后序遍历可知D是左子树CBAD中的根结点，同理根据中序遍历可知CBA都是左子树，再根据后序遍历可知A是第三层根节点，同理往下判断CB，据此画出二叉树图形后，再进行前序遍历，可得到EDABC，故本题答案为A。113.下列叙述中正确的是（

）。A.在循环队列中，队尾指针的动态变化决定队列的长度B.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数C.在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度答案：D解析：解析：在循环队列中，队头指针和队尾指针都是动态变化的，所以循环队列中的元素个数由队头指针和队尾指针共同决定；在循环链表中，前一个结点指向后一个结点，而最后一个结点指向头结点，只有头结点是固定的；线性链表中，由于前一个结点包含下一个结点的指针，尾结点指针为空，要插入删除元素，只需要改变相应位置的结点指针即可，头指针和尾指针无法决定链表长度。故本题答案为D。114.设栈的存储空间为S(1:60)，初始状态为top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（

）。A.60B.59C.1D.0答案：A解析：解析：初始状态为top=61,说明栈空时top=61；入栈时栈顶指针是减操作，即每入栈一个元素，栈顶指针top的值减1，则入栈元素的个数等于61-top；当top的值为1时，栈中元素的个数为60，故本题答案为A。115.设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)/2的是（

）。A.冒泡排序B.快速排序C.简单插入排序D.堆排序答案：D解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为n(n-1)/2；堆排序需要的比较次数为nlog2n。故本题答案为D。116.在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（

）。A.n/4B.3n/4C.n/2D.D、n答案：B解析：解析：因为查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，二分之一情况下平均比较次数为n，总的平均比较次数为(n/2+n)/2=3n/4。故本题答案为B。117.设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为（

）。A.10B.11C.12D.不可能有这样的树答案：A解析：解析：在树结构中，树中的结点数即为树中所有结点的度数之和再加1。本题中该树总度数为3×4+2×1+1×3=17，所以结点总数为18个，则该树中叶子结点个数为18-4-1-3=10，故本题答案为A。118.设栈的存储空间为S(1:50)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为（

）。A.50B.不可能C.1D.0答案：B解析：解析：初始状态栈顶指针top=0，存储空间为S(1:50)，则说明1为栈底，50为栈顶，当top=51时栈已经溢出。故本题答案为B。119.设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)/2的是（

）。A.寻找最大项B.堆排序C.快速排序D.顺序查找答案：C解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为n(n-1)/2；堆排序需要的比较次数为nlog2n；顺序查找需要查找n次；顺序表中，寻找最大项需要比较n-1次。故本题答案为C。120.设表的长度为n。下列算法中，最坏情况下比较次数小于n的是（

）。A.堆排序B.快速排序C.顺序查找法D.二分查找法答案：D解析：解析：最坏情况下，冒泡排序、快速排序、直接插入排序、简单选择排序需要的比较次数为O(n2)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；二分法查找需要的比较次数为O(log2n)。故本题答案为D。121.下列叙述中错误的是（

）。A.栈是线性结构B.二叉链表是二叉树的存储结构C.循环链表是循环队列的存储结构D.循环队列是队列的存储结构答案：C解析：解析：循环队列是队列的顺序存储结构，所以C选项说法错误。122.设一棵树的度为4，其中度为4，3，2，1的结点个数分别为2，3，3，0。则该棵树中的叶子结点数为（

）。A.不可能有这样的树B.16C.15D.17答案：B解析：解析：在树结构中，树中的结点数即为树中所有结点的度数之和再加1。本题中该树总度数为4×2+3×3+2×3+1×0=23，所以结点总数为24个，则该树中叶子结点个数为24-2-3-3=16，故本题答案为B。123.循环队列的存储空间为Q(1:100)，初始状态为front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（

）。A.2B.0或100C.99D.1答案：B解析：解析：当队头和队尾指针指向同一个元素时，队列为空或队列为满，故本题答案为B。124.设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是（

）。A.堆排序B.寻找最大项C.顺序查找法D.快速排序答案：B解析：解析：最坏情况下，冒泡排序、快速排序、直接插入排序、简单选择排序需要的比较次数为O(n2)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；寻找最大项只要比较n-1次。故本题答案为B。125.设栈的顺序存储空间为S(1:m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（

）。A.m+1B.1C.C、mD.不可能答案：D解析：解析：初始状态栈顶指针top=m+1，存储空间为S(1:m)，则说明m为栈底，1为栈顶，当top=0时栈已经溢出。故本题答案为D。126.某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为（

）。A.A、FEDCBAB.B、CBAFEDC.C、ABCDEFD.D、DEFCBA答案：A解析：解析：二叉树的中序遍历序列和后序遍历序列均为ABCDEF，可知该树只有左子树结点，没有右子树结点，F为根结点。中序遍历序列与后序遍历序列相同说明该树只有左子树没有右子树，因此该树有6层，从顶向下从左向右依次为FEDCBA。故本题答案为A。127.循环队列的存储空间为Q(1:200)，初始状态为front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（

）。A.1B.2C.199D.0或200答案：D解析：解析：当队头和队尾指针指向同一个元素时，队列为空或队列为满，故本题答案为D。128.设栈的顺序存储空间为S(1:m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（

）。A.m+1B.不可能C.0D.D、m答案：B解析：解析：初始状态栈顶指针top=0，存储空间为S(1:m)，则说明1为栈底，m为栈顶，当top=m+1时栈已经溢出。故本题答案为B。129.某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为（

）。A.A、DEFABCB.B、FEDCBAC.C、BCDEFAD.D、ABCDEF答案：D解析：解析：二叉树的中序遍历序列和前序遍历序列均为ABCDEF，可知该树只有右子树结点，没有左子树结点，A为根结点。中序遍历序列与前序遍历序列相同说明该树只有右子树没有左子树，因此该树有6层，从顶向下从左向右依次为ABCDEF。故本题答案为D。130.下列叙述中正确的是（

）。A.数值型算法只需考虑计算结果的可靠性B.算法的复杂度与问题的规模无关C.算法的优化主要通过程序的编制技巧来实现D.对数据进行压缩存储会降低算法的空间复杂度答案：D解析：解析：算法的空间复杂度是执行算法所需的内存空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术。由于在编程时要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。算法执行时所需要的计算机资源越多，算法复杂度越高，因此算法的复杂度和问题规模成正比。算法设计时要考虑算法的复杂度，问题规模越大越是如此。故本题答案为D。131.设数据结构B=(D,R)，其中D={a,b,c,d,e,f}R={(a,b),(b,c),(c:d),(d,e),(e,f),(f,a)}该数据结构为（

）。A.循环链表B.非线性结构C.线性结构D.循环队列答案：B解析：解析：满足下列两个条件的非空数据结构称为线性结构：1.有且只有一个根结点；2.每一个结点最多有一个前件，也最多有一个后件。如果一个数据结构不是线性结构，则称之为非线性结构。本题数据结构中没有根节点，因此它是非线性结构，故本题答案为B。132.下列排序法中，每经过一次元素的交换会产生新的逆序的是（

）。A.冒泡排序B.简单选择排序C.快速排序D.简单插入排序答案：C解析：解析：在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序只交换相邻元素，不是每次移动都产生新的逆序。简单插入排序每一次比较后最多移掉一个逆序。快速排序是选出一个结点，然后将大于该结点的数据移到后面，将小于该结点的数据移到前面，所以会产生一个新的逆序，当不会有新的逆序产生时，本轮比较结束。简单选择排序的基本思想是先从所有n个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换，这样做不会产生逆序。故本题答案为C。133.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为（

）。A.1或0B.1C.0D.不确定答案：B解析：解析：往队列的队尾插入一个元素为入队，从队列的排头删除一个元素称为退队。初始时front=rear=0，front总是指向队头元素的前一位置，入队一次rear+1，退队一次front+1。队列队头队尾指针相同时队列为空。而带链的队列，由于每个元素都包含一个指针域指向下一个元素，当带链队列为空时front=rear=NULL，插入第1个元素时，rear+1指向该元素，front+1也指向该元素，插入第2个元素时rear+1，front不变，删除1个元素时front+1。即front=rear不为空时带链的队列中只有一个元素。故本题答案为B。134.某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH。该完全二叉树的前序序列为（

）。A.A、HDEBFGCAB.B、ABCDEFGHC.C、ABDHECFGD.D、HDBEAFCG答案：C解析：解析：完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。由此根据层次输出结果画出对应的二叉树，如下图故前序序列为ABDHECFG。135.下列叙述中正确的是（

）。A.顺序存储结构一定是线性结构B.多重链表一定是非线性结构C.有的二叉树也能用顺序存储结构表示D.有两个指针域的链表就是二叉链表答案：C解析：解析：所有结点都只有一个子结点的特殊二叉树可以用顺序结构存储，故本题答案为C。136.下列各排序法中，最坏情况下时间复杂度最小的是（

）。A.希尔排序B.冒泡排序C.快速排序D.堆排序答案：D解析：解析：最坏情况下，冒泡排序、快速排序、简单插入排序、简单选择排序需要的比较次数为O(n2)；希尔排序需要的比较次数为O(n1.5)；堆排序需要的比较次数为O(nlog2n)；顺序查找需要的比较次数为O(n)次；二分法查找需要的比较次数为O(log2n)，故本题答案为D。137.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=10,rear=5。该队列中的元素个数为（

）。A.4B.不确定C.5D.6答案：B解析：解析：在链式存储方式中，每个结点有两部分组成，一部分为数据域，一部分为指针域，当front=rear时可判断只有一个元素，其他情况无法判断。故本题答案为B。138.某二叉树的前序序列