二级考试公共基础知识单元——数据结构与算法.docx

二级考试公共基础知识单元数据结构与算法A001：设二叉树中共有31个结点，其中的结点值互不相同，如果该二叉树的后序序列与中序序列相同，则该二叉树的深度为（）A、17 B、5 C、16 D、31参考答案D 【二叉树的后序序列与中序序列相同为左单支树，先序与中序相同时为右单支树】A002：下列处理中与队列有关的是（）A、操作系统中的作业调度 B、执行程序中的过程调用 C、执行程序中的循环控制参考答案AA003：下列数据结构中为非线性结构的是（）A、二叉链表 B、循环队列 C、双向链表 D、循环链表参考答案AA004：设数据元素集合为A,B,C,D,E,F，下列关系为线性结构的是（）A、R=(D,F),(E,C),(B,C),(A,B),(C,F) B、R=(D,E),(E,A),(B,C),(F,B),(C,F)C、R=(D,E),(E,A),(B,C),(A,B),(C,F) D、R=(A,B),(C,D),(B,A),(E,F),(F,A)参考答案CA051：下列叙述中正确的是（）A、带链的栈有栈顶指针和栈底指针，因此又称为双重链表 B、有两个指针域的链表称为二叉链表C、结点中具有多个指针域的链表称为多重链表 D、循环链表是循环队列的链式存储结构参考答案 :CA052：下列关于算法复杂度叙述正确的是（）A、最坏情况下的时间复杂度一定高于平均情况的时间复杂度B、对同一个问题，采用不同的算法，则它们的时间复杂度是相同的C、时间复杂度与采用的算法描述语句有关 D、时间复杂度与所用的计算工具无关参考答案DA053：设有栈S和队列Q，初始状体均为空。首先依次将A,B,C,D,E,F入栈，然后从栈中退出3个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为（）A、DEFZYXABC B、FEDZYXCBA C、FEDXYZCBA D、DEFXYZABC参考答案BA054：某二叉树共有845个结点，其中叶子节点有45个，则度为1的结点数为（）A、不确定 B、400 C、754 D、756参考答案DA092：深度为5的完全二叉树的结点数不可能是（）A、16 B、18 C、17 D、15参考答案DA093：下列叙述中正确的是（）A、算法设计可以忽略算法的运算时间 B、算法设计只需要考虑得到计算结果C、程序可以作为算法的一种描述方法 D、所谓算法就是计算方法参考答案CA094（图）：该二叉树如下：则前序序列为（）A、DBGEAFHC B、ABCDEFGH C、DGEBHFCA D、ABDEGCFH参考答案DA095：下列各序列中不是堆的是（）A、91,85,53,47,36,30,24,12 B、91,85,53,36,47,30,24,12C、91,85,53,47,30,12,24,36 D、47,91,53,85,30,12,24,36参考答案DA096（图）：某系统结构图如下图所示，该系统结构图的最大扇出数是（） A、3 B、1 C、4 D、n参考答案DA144：设循环队列的存储空间为Q(1,m),初始状态为空。则经过一系列正常的入队与退队操作后，front=m-1;rear=m,此后再向该循环队列中插入一个元素，则队列中的元素个数为（）A、m-1 B、2 C、1 D、m参考答案BA145：某二叉树共有530个结点，其中度为2的结点有250个，则度为1的结点数为（）A、251 B、249 C、30 D、29参考答案DA146：在最坏情况下，堆排序的时间复杂度是（） 参考答案DA147：下列叙述中正确的是（）A、对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间复杂度肯定相同B、解决同一个问题的不同算法的时间复杂度必定是相同的C、对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间复杂度肯定相同D、解决同一个问题的不同算法的时间复杂度一般是不同的参考答案DA184：某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为（）A、2n B、n+1 C、n-1 D、n/2参考答案CA185：设循环队列为Q（1：m），其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20，现要在该队列中寻找最大值的元素，最坏情况下需要比较的次数是（）A、m-6 B、4 C、6 D、m-5参考答案 BA186：下列叙述错误的是（ ）A、算法的时间复杂度与算法所处理数据的存储结构有直接关系B、算法的时间复杂度与空间复杂度有直接关系C、算法的空间复杂度与算法所处理数据的存储结构有直接关系参考答案 BA187：下列叙述中正确的是（）A、非线性结构只能采用链式存储结构 B、有的非线性结构也可以采用顺序存储结构C、双向链表是二叉树的链式存储结构 D、循环队列属于队列的链式存储结构参考答案BA224：下列叙述错误的是（）A、所有二叉树都只能用二叉链表表示 B、二分查找法只适用于顺序存储的线性有序表C、有多个指针域的链表也有可能是线性结构 D、循环队列是队列的存储结构参考答案AA225：某二叉树共有400个结点，其中有99个度为1的结点，则该二叉树中的叶子结点数为A、150 B、151 C、不可能有这样的二叉树 D、149参考答案BA226：循环队列的存储空间为Q（1:50），初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，则循环队列中的元素个数为（）A、49 B、0或50 C、26 D、25参考答案BA227：下列算法中，最坏情况下时间复杂度为O(log2n)的是（）A、顺序查找法 B、二分查找法 C、快速排序 D、堆排序参考答案BA264：在排序过程中，每一次数据元素的移动会产生新的逆序的排序方法是（）A 快速排序 B、冒泡排序 C、简单插入排序参考答案: AA265：非空循环链表所表示的数据结构（）A、没有根结点但有叶子结点 B、有根结点也有叶子结点C、没有根结点也没有叶子结点 D、有根结点但没有叶子结点参考答案:BA266：某棵树只有度为3的结点和叶子结点，其中度为3的结点有8个，则该树中的叶子结点数为（）A、16 B、不存在这样的树 C、15 D、17参考答案:DA267：某循环队列的存储空间为Q(1:m),初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m,rear=m-1,则该循环队列中的元素个数为（）A、1 B、m C、0 D、m-1参考答案:DA304：下列叙述中错误的是（）A、空数据结构可以是线性结构也可以是非线性结构 B、数据结构中的数据元素不能是另一数据结构C、非空数据结构可以没有根结点 D、数据结构中的数据元素可以是另一数据结构参考答案: BA305：设某二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为（）A、DCBAHGFE B、EFGHABCD C、ABCDEFGH D、HGFEDCBA参考答案: DA306：为了降低算法的空间复杂度，要求算法尽量采用原地工作(inplace)。所谓原地工作是指（）A、执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化B、执行算法时所使用的额外空间固定(即不随算法所处理的数据空间大小的变化而变化)C、执行算法时不使用任何存储空间 D、执行算法时不使用额外空间参考答案:BA307：设栈的存储空间为S(1:m),初始状态为top=m+1。经过一系列入栈与退栈操作后，top=1。现又要将一个元素进栈，栈顶指针top值变为（）A、0 B、m C、2 D、发生栈满的错误参考答案: AA345：对下列二叉树进行前序遍历的结果为（）A、ABCDEFXYZ B、ABDYECFXZ C、DYBEAFCZX D、YDEBFZXCA参考答案: .BA346：下列叙述中正确的是（）A、程序执行的效率与数据的存储结构密切相关 B、程序执行的效率只取决于所处理的数据量C、程序执行的效率只取决于程序的控制结构参考答案: AA347：下列与队列结构有关联的是（）A、函数的递归调用 B、多重循环的执行 C、先到先服务的作业调度 D、数组元素的引用参考答案:CA348：一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈，然后再依次出栈，则元素出栈的顺序是A、1,2,3,C,B,A B、C,B,A,3,2,1 C、C,B,A,1,2,3 D、1,2,3,A,B,C参考答案:BA384：下列叙述中正确的是( )A、循环队列的插入运算不会发生溢出现象 B、循环队列是非线性结构C、循环队列是链式存储结构 D、循环队列是顺序存储结构参考答案:DA385：下列关于算法的描述中错误的是( )A、算法设计必须考虑算法的复杂度 B、算法的优劣取决于运行算法程序的环境C、算法强调动态的执行过程，不同于静态的计算公式 D、算法必须能在有限个步骤之后终止参考答案:BA386：下列描述中，正确的是（ ）。A、所有数据结构必须有根结点B、没有根结点或没有叶子结点的数据结构一定是非线性结构C、只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D、所有数据结构必须有终端结点(即叶子结点)参考答案：BA387（图）：设二叉树如下，则中序序列为（）A、DGEBHFCA B、DBGEAFHC C、ABDEGCFH D、ABCDEFGH参考答案BA425:：某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为（假设根结点在第1层）_A、4 B、3 C、7 D、6参考答案CA426:：下列叙述正确的是_A、在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化B、在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化C、在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化参考答案BA427:：下列关于栈正确的是_A、栈顶元素最先被删除 B、栈底元素永远不能被删除 C、栈顶元素最后才能被删除参考答案AA465:：深度为7的二叉树共有127个结点，则下列说法中错误的是_A、该二叉树是完全二叉树 B、该二叉树有64个叶子结点C、该二叉树是满二叉树 D、该二叉树有一个度为1的结点参考答案DA466:：设数据集合为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=(1,9),(9,7),(7,5),(5,3) D、R=(9,7),(1,3),(7,1),(3,5)参考答案BA467:：下列叙述中正确的是_A、非线性结构只能采用链式存储结构 B、有的非线性结构也能采用顺序存储结构C、所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D、非线性结构只能用多重链表表示参考答案BA468:：某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为_A、DCBA B、ABCD C、BDCA D、BADC参考答案BA505:：下列叙述中错误的是_A、非线性结构中至少有一个根结点 B、非线程结构中可以没有根结点与叶子结点 C、有一个以上叶子结点的必定是非线性结构 D、有一个以上根结点的必定是非线性结构 参考答案AA506:：下列排序方法中，最坏情况下时间复杂度（比较次数）低于O（n2）的是_A、快速排序 B、冒泡排序 C、简单插入排序 D、堆排序参考答案DA507:：某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为_A、149 B、199 C、不可能有这样的二叉树 D、150参考答案CA508:：设栈的存储空间为S（1：50），初始状态为top=0.现经过一系列正常的入栈与退栈操作后，top=30，则栈中的元素个数为_A、20 B、19 C、31 D、30参考答案DA545:：循环队列的存储空间为Q（1：50），初始状态为front=rear=50.现经过一系列入队与退队操作后front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为_A、3 B、52 C、1 D、2参考答案DA546:：某棵树的度为4，且度为4、3、2、1的结点数分别为1、2、3、4，则该树种的叶子结点数为_A、9 B、10 C、8 D、11参考答案DA547:：设二叉树中共有15个结点，其中的结点值互不相同。如果该二叉树的前序序列与中序序列相同，则该二叉树的深度为_A、6 B、4 C、不存在这样的二叉树 D、15参考答案DA548:：下列叙述中正确的是_A、算法的有穷性是指算法的规模不能太大 B、算法的复杂度用于衡量算法的控制结构C、算法的效率与数据的存储结构无关