国家二级MSOffice高级应用机试（数据结构与算法）模拟试卷2（共103题）

国家二级MSOffice高级应用机试（数据结构与算法）模拟试卷2（共4套）（共103题）国家二级MSOffice高级应用机试（数据结构与算法）模拟试卷第1套一、选择题(本题共24题，每题1.0分，共24分。)1、下列叙述中正确的是()。A、算法的复杂度包括时间复杂度与空间复杂度B、算法的复杂度是指算法控制结构的复杂程度C、算法的复杂度是指算法程序中指令的数量D、算法的复杂度是指算法所处理的数据量标准答案：A知识点解析：算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。2、下列叙述中正确的是()。A、解决同一个问题的不同算法的时间复杂度一般是不同的B、解决同一个问题的不同算法的时间复杂度必定是相同的C、对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同D、对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定相同标准答案：A知识点解析：解决同一个问题的不同算法的时间复杂度，可能相同也可能不相同。算法的时间复杂度与数据存储结构无关，对同一批数据作同一种处理或者不同处理，数据存储结构相同或者不同，算法的时间复杂度都可能相同或者不同。3、下列叙述中错误的是()。A、向量是线性结构B、非空线性结构中只有一个节点没有前件C、非空线性结构中只有一个节点没有后件D、具有两个以上指针域的链式结构一定属于非线性结构标准答案：D知识点解析：双向链表每个节点有两个指针，一个为左指针，用于指向其前件节点；一个为右指针，用于指向其后件节点，再加上头指针，具有两个以上的指针，但双向链表属于线性结构。非空线性结构中第一个节点没有前件，最后一个节点无后件，其余节点最多有一个前件，也最多有一个后件。向量也满足这个条件，属于线性结构。4、在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数()。A、不同，但元素的存储顺序与逻辑顺序一致B、不同，且其元素的存储顺序可以与逻辑顺序不一致C、相同，元素的存储顺序与逻辑顺序一致D、相同，但其元素的存储顺序可以与逻辑顺序不一致标准答案：C知识点解析：在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。5、设栈的顺序存储空间为S(1：m)，初始状态为top＝m＋1，则栈中的数据元素个数为()。A、top－m＋1B、m－top＋1C、m－topD、top－m标准答案：B知识点解析：栈的初始状态top＝m＋1，说明栈空时top＝m＋1(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。6、设栈的存储空间为S(1：50)，初始状态为top＝51。现经过一系列正常的入栈与退栈操作后，top＝20，则栈中的元素个数为()。A、31B、30C、21D、20标准答案：A知识点解析：栈的初始状态top＝51，故本栈是51在栈底，入栈时栈顶指针是减操作(top＝top－1)，退栈时栈顶指针是加操作(top＝top＋1)。当top＝20时，元素存储在(20：50)空间中，因此共有50－20＋1＝31个元素。7、下列叙述中正确的是()。A、循环队列是顺序存储结构B、循环队列是链式存储结构C、循环队列空的条件是队头指针与队尾指针相同D、循环队列的插入运算不会发生溢出现象标准答案：A知识点解析：循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。8、设循环队列的存储空间为Q(1：50)，初始状态为front＝rear＝50。经过一系列正常的操作后，front－1＝rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为()。A、48B、49C、1D、0标准答案：A知识点解析：该题中rear－front＝front－1－front＜0，则该循环队列中的元素个数为REAR－front＋50＝front－1－front＋50＝49。在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为49－1＝48。9、线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有()。A、节省存储空间B、插入与删除运算效率高C、便于查找D、排序时减少元素的比较次数标准答案：B知识点解析：线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。10、下列叙述中正确的是()。A、带链栈的栈底指针是随栈的操作而动态变化的B、若带链队列的队头指针与队尾指针相同，则队列为空C、若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D、不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的标准答案：A知识点解析：由于带链栈利用的是计算机存储空间中的所有空闲存储节点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。11、某带链的队列初始状态为front＝rear＝NULL。经过一系列正常的入队与退队操作后，front＝rear＝10。该队列中的元素个数为()。A、0B、1C、1或0D、不确定标准答案：B知识点解析：带链队列空时，头指针和尾指针都为null；队列中只有一个元素时，头指针和尾指针都指向这个元素。12、某带链的队列初始状态为。front＝rear＝NULL。经过一系列正常的入队与退队操作后，front＝10，rear＝5。该队列中的元素个数为()。A、4B、5C、6D、不确定标准答案：D知识点解析：带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当front＝10，rear＝5时，不能确定队列中元素的个数。13、下列结构中为非线性结构的是()。A、树B、向量C、二维表D、矩阵标准答案：A知识点解析：由定义可以知道，树为一种简单的非线性结构。在数这种数据结构中，所有数据元素之间的关系具有明显的层次特性。14、设某棵树的度为3，其中度为2，1，0的节点个数分别为3，4，15。则该树中总节点数为()。A、不可能有这样的树B、30C、22D、35标准答案：A知识点解析：设树的总节点数为n，则度为3的节点数为n－3－4－15＝n－22，根据树中的节点数＝树中所有节点的度之和＋1，得3×(n－22)＋2×3＋1×4＋0×15＋1＝n，则n＝27．5，求出的节点数不为整数，故不可能有这样的树存在。15、某二叉树中共有350个节点，其中200个为叶子节点，则该二叉树中度为2的节点数为()。A、不可能有这样的二叉树B、150C、199D、149标准答案：A知识点解析：叶子节点数为200，根据在二叉树中度为0的节点(叶子节点)总比度为2的节点多一个，则度为2的节点数为199，199＋200＞350，故不存在这样的二叉树。16、度为3的一棵树共有30个节点，其中度为3，1的节点个数分别为3，4。则该树中的叶子节点数为()。A、14B、15C、16D、不可能有这样的树标准答案：B知识点解析：设叶子节点数为n，则度为2的节点数为30－3－4－n＝23－n，根据树中的节点数＝树中所有节点的度之和＋1，得3×3＋2×(23－n)＋1×4＋0×n＋1＝30，则n＝15。17、在具有2n个节点的完全二叉树中，叶子节点个数为()。A、nB、n＋1C、n－1D、n/2标准答案：A知识点解析：由二叉树的定义可知，树中必定存在度为0的节点和度为2的节点，设度为0节点有a个，根据度为0的节点(即叶子节点)总比度为2的节点多一个，得度为2的节点有a－1个。再根据完全二叉树的定义，度为1的节点有0个或1个，假设度1节点为0个，a＋0＋a－1＝2n，得2a＝2n－1，由于节点个数必须为整数，假设不成立；当度为1的节点为1个时，a＋1＋a－1＝2n，得a＝n，即叶子节点个数为n。18、有二叉树如下图所示：则前序序列为()。A、ABDEGCFHB、DBGEAFHCC、DGEBHFCAD、ABCDEFGH标准答案：A知识点解析：前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。故本题前序序列是ABDEGCFH。中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。故本题的中序序列是DBGEAFHC。后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。故本题的后序序列是DGEBHFCA。19、某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为()。A、HGFEDCBAB、HFDBGECAC、ABCDEFGHD、ACEGBDFH标准答案：C知识点解析：二叉树的前序序列为ABDFHCEG，可以确定这个二叉树的根节点是A；再由中序序列HFDBACEG，可以得到HFDB为根节点A的左子树，CEG为根节点A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到该二叉树的结构如下：该二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。20、设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为()。A、n(n－1)/2B、nC、nlog2nD、log2n标准答案：D知识点解析：有序线性表的长度为n，设被查找元素为x，则二分查找的方法如下：将x与线性表的中间项比较：若中间项的值等于x，则说明查到，查找结束；若x小于中间项的值，则在线性表的前半部分(即中间项以前的部分)以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。21、在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为()。A、nB、3n/4C、n/2D、n/4标准答案：B知识点解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。这是找到元素的情况。如果没有找到元素，则要比较n次。因此，平均需要比较：找到元素的情况×1/2＋未找到元素的情况×1/2＝，大约为。22、在希尔排序法中，每经过一次数据交换后()。A、不会产生新的逆序B、只能消除一个逆序C、能消除多个逆序D、消除的逆序个数一定比新产生的逆序个数多标准答案：C知识点解析：希尔排序法的基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。在子序列中每进行一次比较就有可能移去整个线性表中的多个逆序，从而改善整个排序过程的性能。23、在快速排序法中，每经过一次数据交换(或移动)后()。A、只能消除一个逆序B、能消除多个逆序C、不会产生新的逆序D、消除的逆序个数一定比新产生的逆序个数多标准答案：B知识点解析：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。快速排序的思想是：从线性表中选取一个元素，设为T，将线性表中后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成两部分(称两个子表)，T插入到其分割线的位置处，这个过程称为线性表的分割，然后再用同样的方法对分割出的子表再进行同样的分割。快速排序不是对两个相邻元素进行比较，可以实线通过一次交换而消除多个逆序，但由于均与T(基准元素)比较，也可能会产生新的逆序。24、在长度为97的顺序有序表中作二分查找，最多需要的比较次数为()。A、48B、96C、7D、6标准答案：C知识点解析：对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。本题中n＝97，最多需要的比较次数为10g297，6＜log297＜7，故需要比较7次。国家二级MSOffice高级应用机试（数据结构与算法）模拟试卷第2套一、选择题(本题共27题，每题1.0分，共27分。)1、下列叙述中正确的是A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D、循环队列中元素的个数是由队头指针和队尾指针共同决定标准答案：D知识点解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。2、支持子程序调用的数据结构是A、栈B、树C、队列D、二叉树标准答案：A知识点解析：栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。3、一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为A、0B、1C、180D、181标准答案：B知识点解析：对于一个具有n个结点的完全二叉树，其深度为[log2n]+10本题中这个二叉树的深度为[log2360]+1=8+1l=9。根据满二叉树的性质，深度为8的满二叉树其结点数为28-1=256．1=255。这个完全二叉树的第9层的结点数为360-255=105。完全二叉树的性质非叶子结点的子结点都为2，105除以2其商为52余数为l。因此该二叉树中度为1的结点个数为1。选项B正确。4、下列叙述中正确的是A、有一个以上根结点的数据结构不一定是非线性结构B、只有一个根结点的数据结构不一定是线性结构C、循环链表是非线性结构D、双向链表是非线性结构标准答案：B知识点解析：在数据结构中，树这类的数据结构只有一个根结点，但它不是线性结构。5、下列链表中，其逻辑结构属于非线性结构的是A、二叉链表B、循环链表C、双向链表D、带链的栈标准答案：A知识点解析：二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。6、一个栈的初始状态为空。现将元素1，2，3，A，B,C依次入栈，然后再依次出栈，则元素出栈的顺序是A、1，2，3，A，B，CB、C，B，A，1，2，3C、C，B，A，3，2，1D、1，2，3，C，B，A标准答案：C知识点解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是CBA321。7、某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为(根结点在第l层)A、3B、6C、8D、12标准答案：D知识点解析：根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，故该二叉树为12层，每层只有一个结点。8、设某二二叉树的前序序列为ABC，中序序列为CBA，则该二叉树的后序序列为A、BCAB、CBAC、ABCD、CAB标准答案：B知识点解析：二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二个值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。本题的具体二叉树如下，因此，后序是CBA。9、在最坏情况下A、快速排序的时间复杂度比冒泡排序的时间复杂度要小B、快速排序的时间复杂度比希尔排序的时间复杂度要小C、希尔排序的时间复杂度比直接插入排序的时间复杂度要小D、快速排序的时间复杂度与希尔排序的时间复杂度是一样的标准答案：C知识点解析：按平均时间将排序分为四类：①平方阶(O(n2))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(nlog2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。根据以上4点，可以判断选项C正确。10、下列叙述中错误的是A、算法的时间复杂度与算法所处理数据的存储结构有直接关系B、算法的空间复杂度与算法所处理数据的存储结构有直接关系C、算法的时间复杂度与空间复杂度有直接关系D、算法的时间复杂度与空间复杂度没有必然的联系标准答案：C知识点解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。11、下列叙述中正确的是A、在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B、在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构C、在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D、在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构标准答案：B知识点解析：选项A叙述是错误的，例如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项C叙述也是错误的，例如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项D叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项B正确。12、下列各序列中不是堆的是A、(91，85，53，36，47，30，24，12)B、(91，85，53，47，36，30，24，12)C、(47，91，53，85，30，12，24，36)D、(91，85，53，47，30，12，24，36)标准答案：C知识点解析：堆可以看成一棵完全二叉树：任一根节点＞=左右孩子(或者＜=)，(大的叫大根堆，小的叫小根堆)。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的根，而选项C是“左根右”的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，所以选项C不是堆。13、线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有A、节省存储空间B、插入与删除运算效率高C、便于查找D、排序时减少元素的比较次数标准答案：B知识点解析：顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大(=1)，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点问关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小(＜1)，存储空间利用率低，故选项B正确。14、某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为A、BADCB、DCBAC、CDABD、ABCD标准答案：B知识点解析：在二叉树前序遍历中ABCD中A是根节点，而在后序遍历中根结点位于最后，所以选项B正确。15、设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是A、中序序列B、前序序列C、后序序列D、前序序列或后序序列标准答案：A知识点解析：中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而左子树结点值＜根节点节点值≤右子树节点值，是有序序列，因此选项A正确。16、下列叙述中正确的是A、在循环队列中，队头指针和队尾指针的动态变化决定队列的长度B、在循环队列中，队尾指针的动态变化决定队列的长度，C、在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D、在带链的栈中，栈顶指针的动态变化决定栈中元素的个数标准答案：A知识点解析：循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。循环队列中计算元素的个数公式为：。所以选项A正确。17、设表的长度为n。下列算法中，最坏情况下比较次数小于n的是A、二分查找法B、堆排序C、快速排序D、顺序查找法标准答案：A知识点解析：二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到：若小于中间项的值则在线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log2n次。所以选项A正确。18、循环队列的存储空间为Q(1：200)，初始状态为front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为A、0或200B、1C、2D、199标准答案：A知识点解析：循环队列中，由于入队时尾指针rear向前追赶头指针front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于本题来说，经过一系列正常的入队与退队操作后，front=rear=1。此时，要么队列为空(元素个数为0)，要么队列为满(元素个数为200)。所以选项A正确。19、某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为A、1B、0C、1或0D、不确定标准答案：A知识点解析：循环队列用数组A[0；m－1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear－front+m)％m=1，所以选项A正确。20、设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为A、105B、55C、15D、75标准答案：A知识点解析：假设线性表的长度为n，在最坏情况下，快速排序法的比较次数是n(n－1)／2。题中n=15，所以15*14／2=105。所以选项A正确。21、下列叙述中错误的是A、算法的时间复杂度与问题规模无关B、算法的时间复杂度与计算机系统无关C、算法的时间复杂度与空间复杂度没有必然的联系D、算法的空间复杂度与算法运行输出结果的数据量无关标准答案：A知识点解析：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)／f(n)的极限值为不等于零的常数，则称16(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。所以选项A正确。22、设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：A知识点解析：因为任一棵树中，结点总数=总分支数目+1，所以：6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果n3=1。其中，n3表示度为3的结点数，所以选项A正确。23、带链队列空的条件是A、front=rear=NULLB、front=rear=－1C、front=NULL且rear=－1D、front=－1且rear=NULL标准答案：A知识点解析：带链队列空的条件有两个：一个是front=rear，一个是它们都等于空。24、下列叙述中错误的是A、循环链表中有一个表头结点B、循环链表的存储空间是连续的C、循环链表实现了空表与非空表运算的统一D、循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点标准答案：B知识点解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。25、下列叙述中正确的是A、矩阵是非线性结构B、数组是长度固定的线性表C、对线性表只能作插入与删除运算D、线性表中各元素的数据类型可以不同标准答案：B知识点解析：所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。26、下列叙述中正确的是A、循环队列是队列的链式存储结构B、能采用顺序存储的必定是线性结构C、所有的线性结构都可以采用顺序存储结构D、具有两个以上指针的链表必定是非线性结构标准答案：C知识点解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。所有的线性结构都可以采用顺序存储结构。27、设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ标准答案：A知识点解析：前序遍历中，第一个字母是根结点，也就是A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中，B在A的后面，中序中在左子树中，可知B为A的左结点。中序中D在B的前面，前序中在B的后面，可知D为B的左结点，GEH为B的右子树。前序中顺序为EGH，由此可知，E为B的右结点，G为E的左结点、H为E的右结点。右子树中，前序中C在最前，因为右子树根结点，也就是A的右结点，根据前序中的子树FIJ和中序中的IFJ子树可知F为C的右结点，I为F的左结点、J为F的右结点。由此可画出这个二叉树，然后根据二叉树可的后序序列为DGHEBIJFCA。国家二级MSOffice高级应用机试（数据结构与算法）模拟试卷第3套一、选择题(本题共24题，每题1.0分，共24分。)1、下列叙述中正确的是()。A、所谓算法就是计算方法B、程序可以作为算法的一种描述方法C、算法设计只需考虑得到计算结果D、算法设计可以忽略算法的运算时间标准答案：B知识点解析：算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。2、为了降低算法的空间复杂度，要求算法尽量采用原地工作(inplace)。所谓原地工作是指()。A、执行算法时不使用额外空间B、执行算法时不使用任何存储空间C、执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化D、执行算法时所使用的额外空间固定(即不随算法所处理的数据空间大小的变化而变化)标准答案：D知识点解析：对于算法的空间复杂度，如果额外空间量相对于问题规模(即输入数据所占的存储空间)来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。3、下列叙述中错误的是()。A、数据结构中的数据元素可以是另一数据结构B、数据结构中的数据元素不能是另一数据结构C、空数据结构可以是线性结构也可以是非线性结构D、非空数据结构可以没有根节点标准答案：B知识点解析：数据元素是一个含义很广泛的概念，它是数据的“基本单位”，在计算机中通常作为一个整体进行考虑和处理。数据元素可以是一个数据，也可以是被抽象出的具有一定结构的数据集合，所以数据结构中的数据元素可以是另一数据结构。满足有且只有一个根节点并且每一个节点最多有一个前件，也最多有一个后件的非空的数据结构认为是线性结构，不满足条件的结构为非线性结构。空数据结构可以是线性结构也可以是非线性结构。非空数据结构可以没有根节点，如非性线结构“图”就没有根节点。4、下列叙述中正确的是()。A、矩阵是非线性结构B、数组是长度固定的线性表C、对线性表只能作插入与删除运算D、线性表中各元素的数据类型可以不同标准答案：B知识点解析：矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。5、设栈的存储空间为S(1：50)，初始状态为top＝－1。现经过一系列正常的入栈与退栈操作后，top＝30，则栈中的元素个数为()。A、20B、19C、31D、30标准答案：D知识点解析：栈的初始状态为top＝－1表示栈为空，经过一系列正常的入栈与退栈操作后top＝30，则空间(1：30)中插入了元素，共30个。6、设栈的存储空间为S(1：m)，初始状态为top＝m＋1。经过一系列入栈与退栈操作后，top＝m。现又在栈中退出一个元素后，栈顶指针top值为()。A、0B、m－1C、m＋1D、产生栈空错误标准答案：C知识点解析：栈的顺序存储空间为S(1：m)，初始状态top＝m＋1，所以这个栈是m在栈底(也可理解为开口向下的栈)。经过一系列入栈与退栈操作后top＝m，则栈中有1个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到m＋1的位置。7、下列叙述中正确的是()。A、在循环队列中，队尾指针的动态变化决定队列的长度B、在循环队列中，队头指针和队尾指针的动态变化决定队列的长度C、在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D、在带链的栈中，栈顶指针的动态变化决定栈中元素的个数标准答案：B知识点解析：在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。带链的栈和带链的队列均采用链式存储结构，而在这种结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。8、设循环队列为Q(1：m)，其初始状态为front＝rear＝m。经过一系列入队与退队运算后，front＝30，rear＝10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为()。A、19B、20C、m－19D、m－20标准答案：D知识点解析：front＝30，rear＝10，front＞rear，则队列中有10－30＋m＝m－20个元素，在作顺序查找时，最坏情况下(最后一个元素才是要找的元素或没有要查找的元素)比较次数为m－20次。9、设循环队列的存储空间为Q(1：m)，初始状态为空。现经过一系列正常的入队与退队操作后，front＝m，rear＝m＝1，此后从该循环队列中删除一个元素，则队列中的元素个数为()。A、m－1B、m－2C、0D、1标准答案：B知识点解析：在循环队列中，如果rear－front＞0，则队列中的元素个数为rear－front个；如果rear－front＜0，则队列中的元素个数为rear－front＋m。该题中m－1＜m，即rear－front＜0，则该循环队列中的元素个数为(m—1)－m＋m＝m－1。此后从该循环队列中删除一个元素，则队列中的元素个数为m－1－1＝m－2。10、带链的栈与顺序存储的栈相比，其优点是()。A、入栈与退栈操作方便B、可以省略栈底指针C、入栈操作时不会受栈存储空间的限制而发生溢出D、所占存储空间相同标准答案：C知识点解析：带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出(不需考虑栈满的问题)。11、带链队列空的条件是()。A、front＝rear＝NULLB、font＝－1且rear＝NULLC、front＝NULL且rear＝－1D、front＝rear＝－1标准答案：A知识点解析：带链的队列就是用一个单链表来表示的队列，队列中的每一个元素对应链表中的一个节点。队列空时，头指针和尾指针都为NULL。12、某带链的队列初始状态为front＝rear＝NULL。经过一系列正常的入队与退队操作后，front＝rear＝10。该队列中的元素个数为()。A、0B、1C、1或0D、不确定标准答案：B知识点解析：带链队列空时，头指针和尾指针都为NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。13、下列叙述中错误的是()。A、循环链表中有一个表头节点B、循环链表是循环队列的存储结构C、循环链表的表头指针与循环链表中最后一个节点的指针均指向表头节点D、循环链表实现了空表与非空表运算的统一标准答案：B知识点解析：循环链表是指在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，最后一个节点的指针域的值由NULL改为指向表头节点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。14、设一棵树的度为3，其中没有度为2的节点，且叶子节点数为5。该树中度为3的节点数为()。A、3B、1C、2D、不可能有这样的树标准答案：C知识点解析：设树的节点数为m，度为3的节点数为n，则度为1的节点数为m－n－5，根据树中的节点数＝树中所有节点的度之和＋1，得3×n＋1×(m－n－5)＋5×0＋1＝m，则n＝2。15、某二叉树共有730个节点，其中度为1的节点有30个，则叶子节点个数为()。A、1B、351C、350D、不存在这样的二叉树标准答案：D知识点解析：设叶子节点数为n，根据在二叉树中度为0的节点(叶子节点)总比度为2的节点多一个，则度为2的节点数为n－1，n＋n－1＋30＝730，得n＝350．5。由于节点数只能为整数，所以不存在这样的二叉树。16、某棵树中共有25个节点，且只有度为3的节点和叶子节点，其中叶子节点有7个，则该树中度为3的节点数为()。A、6B、7C、8D、不存在这样的树标准答案：D知识点解析：根据题意，树中只有度为3的节点和叶子节点(7个)，则度为3的节点有25－7＝18个；又根据树中的节点数＝树中所有节点的度之和＋1，设度为3的节点数为n，则3n＋1＝25。得n＝8。两种方式得到的度为3的节点数不同，故不存在这样的树。17、某完全二叉树共有256个节点，则该完全二叉树的深度为()。A、7B、8C、9D、10标准答案：C知识点解析：根据完全二又树的性质：具有n个节点的完全二叉树的深度为[log2n]＋1。本题中完全二叉树共有256个节点，则深度为[log2，256]＋1＝8＋1＝9。18、设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为()。A、ABCDHGFEB、DCBAHGFEC、EFGHABCDD、HGFEDCBA标准答案：D知识点解析：二叉树的前序序列与中序序列均为ABCDEFGH，可知二叉树根节点为A，且根节点A只有右子树，没有左子树。同理，可以推出节点B只有右子树无左子树。依此类推，该二叉树除叶子节点外，每个节点只有右子树无左子树。因此该二叉树的后序序列为HGFEDCBA。19、某二叉树的前序序列为ABCDEG，中序序列为DCBAEFG，则该二叉树的深度(根节点在第1层)为()。A、2B、3C、4D、5标准答案：C知识点解析：二叉树的前序序列为ABCDEFG，则A为根节点；中序序列为DCBAEFG，可知节点D、C、B位于根节点的左子树上，节点E、F、G位于根节点的右子树上。另外，节点B、C、D在前序序列和中序序列中顺序相反，则说明这三个节点依次位于前一个节点的左子树上；节点E、F、G顺序未变，则说明这三个节点依次位于前一个节点的右子树上。故二叉树深度为4。20、设二叉树中共有15个节点，其中的节点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为()。A、4B、6C、15D、不存在这样的二叉树标准答案：C知识点解析：在具有n个节点的二叉树中，如果各节点值互不相同，若该二叉树的前序序列与中序序列相同，则说明该二叉树只有右子树，左子树为空，二叉树的深度为n；若该二叉树的后序序列与中序序列相同，则说明该二叉树只有左子树，右子树为空，二叉树的深度为n。故本题中二叉树的深度为15。21、在长度为n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为()。A、n/4B、nC、3n/4D、(n＋1)/2标准答案：D知识点解析：在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为n。则平均比较次数：(1＋2＋…＋n)/n＝(n(n＋1)/2)/n＝(n＋1)/2。22、下列叙述中正确的是()。A、二分查找法只适用于顺序存储的有序线性表B、二分查找法适用于任何存储结构的有序线性表C、二分查找法适用于有序循环链表D、二分查找法适用于有序双向链表标准答案：A知识点解析：二分查找法(又称对分查找法)只适用于顺序存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列(即从小到大，但允许相邻元素值相等)。23、下列各排序法中，最坏情况下的时间复杂度最低的是()。A、堆排序B、快速排序C、希尔排序D、冒泡排序标准答案：A知识点解析：最坏情况下，堆排序需要比较nlog2n次，希尔排序需要比较nr(1＜r＜2)次，快速排序、冒泡排序均需要比较n(n1－1)/2次。故堆排序时间复杂度最低。24、设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为()。A、120B、60C、30D、15标准答案：A知识点解析：简单插入排序在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n(n－1)/2，移动次数为n(n－1)/2。本题中n＝16，16×(16－1)÷2＝8×15＝120。国家二级MSOffice高级应用机试（数据结构与算法）模拟试卷第4套一、选择题(本题共28题，每题1.0分，共28分。)1、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n一1)／2的排序方法是A、快速排序B、冒泡排序C、直接插入排序D、堆排序标准答案：D知识点解析：各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序nf=(n-1)／2、快速排序n(n-1)／2、简单插入排序n(n-1)／2、希尔排序O(n1．5)、简单选择排序n(n-1)／2、堆排序O(nlog2n)。2、对于循环队列，下列叙述中正确的是A、队头指针是固定不变的B、队头指针一定大于队尾指针C、队头指针一定小于队尾指针D、队头指针可以大于队尾指针，也可以小于队尾指针标准答案：D知识点解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当rear或front等于队列的长度加1时，就把rear或front值置为1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。3、下列叙述中正确的是A、栈是“先进先出”的线性表B、队列是“先进后出”的线性表C、循环队列是非线性结构D、有序线性表既可以采用顺序存储结构，也可以采用链式存储结构标准答案：D知识点解析：本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。4、下列叙述中正确的是A、在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B、在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C、在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D、上述三种说法都不对标准答案：C知识点解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底栈跟队列不同，元素只能在栈顶压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。5、下列叙述中正确的是A、循环队列是队列的一种链式存储结构B、循环队列是队列的一种顺序存储结构C、循环队列是非线性结构D、循环队列是一种逻辑结构标准答案：B知识点解析：本题主要考套循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是一一种逻辑结构，而循环队列是一种顺序存储结构的队列。6、设二叉树共有150个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为A、71B、70C、69D、不可能有这样的二叉树标准答案：D知识点解析：根据二叉树的性质3，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。即有n0=n2+1。对于这个题来说，总结点数150=n0+n1+n2=n2+10+n2=2n2+11，所以2n2=139，度为2个结点个数不能确定。选项D正确。7、一棵二叉树中共有80个叶子结点与70个度为l的结点，则该二叉树中的总结点数为A、219B、229C、230D、231标准答案：B知识点解析：根据二叉树的性质，在任意二叉树中，度为O的结点(即叶子结点)总是比度为2的结点多一个，故总结点数=叶子节点数+度为2的节点数+度为1的节点数=80+79+70=229。8、下列叙述中错误的是A、在双向链表中，可以从任何一个结点开始直接遍历到所有结点B、在循环链表中，可以从任何一个结点开始直接遍历到所有结点C、在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D、在二叉链表中，可以从根结点开始遍历到所有结点标准答案：C知识点解析：线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项C的描述是错误的。9、设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为A、BCAB、CBAC、ABCD、CAB标准答案：C知识点解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。本题的具体二叉树如下，因此，这棵二叉树的前序是ABC，选项C确。10、算法空间复杂度的度量方法是A、算法程序的长度B、算法所处理的数据量C、执行算法所需要的工作单元D、执行算法所需要的存储空间标准答案：D知识点解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。11、下列叙述中正确的是A、存储空间连续的数据结构一定是线性结构B、存储空间不连续的数据结构一定是非线性结构C、没有根结点的非空数据结构一定是线性结构D、具有两个根结点的数据结构一定是非线性结构标准答案：D知识点解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A)、B)和C)都不能判定是否是线性结构，选项D)正确。12、下列叙述中正确的是A、链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构B、线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C、线性表的链式存储结构中，每个结点只能有一个指向后件的指针D、线性表的链式存储结构中，叶子结点的指针只能是空标准答案：A知识点解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项B)、C)、D)说法错误。选项A)中，例如双向链表就具有两个指针，也属于线性结构，所以选项A正确。13、下列叙述中正确的是A、循环队列是顺序存储结构B、循环队列是链式存储结构C、循环队列是非线性结构D、循环队列的插入运算不会发生溢出现象标准答案：A知识点解析：循环队列属于队列的特例和栈同属于线性结构，所以选项C不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；川页序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出：假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项A正确，选项B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项D不正确。14、设有二叉树如下图所示，则后序序列为A、ABDEGCFHB、DBGEAFHCC、DGEBHFCAD、ABCDEFGH标准答案：C知识点解析：后序遍历(LRD)首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项C正确。15、设栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为A、1B、0C、50D、49标准答案：A知识点解析：栈的存储空间为S(1：50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中有51-50=1个元素，选项A正确。16、在具有2n个结点的完全二叉树中，叶子结点个数为A、nB、n+1C、n－1D、n／2标准答案：A知识点解析：在具有2n个结点的完全二叉树中，叶子结点个数为：(2n+1)／2取整，其值等于n。所以选项A正确。17、在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为A、(3+n)／4B、nC、n／2D、n／4标准答案：A知识点解析：在长度为n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n次找到。那么平均长度为：(1+2+…+n)／n=(n(n+1)／2)／n=(n+1)／2本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为((1+n)／2+1)／2=(3+n)／4。所以选项A正确。18、循环队列的存储空间为Q(1：100)，初始状态为front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为A、0或100B、1C、2D、99标准答案：A知识点解析：循环队列中，由于入队时尾指针。rear向前追赶头指针：front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正