二级选择题练习一(数据结构与算法)答案版.docx

第一章数据结构与算法1.算法复杂度相关试题:算法的空间复杂度是指（）A)算法在执行过程中所需要的计算机存储空间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元数【解析】算法的空间复杂度是指算法在执行过程中所需要的内存空间。所以选择A。2.数据结构相关试题:下列数据结构中，属于非线性结构的是（）A)循环队列B)带链队列C)二叉树D)带链栈【解析】树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。3.栈和队列相关试题:下列关于栈的叙述正确的是（）A)栈按“先进先出”组织数据B)栈按“先进后出”组织数据C)只能在栈底插入数据D)不能删除数据【解析】栈是按“先进后出”的原则组织数据的，数据的插入和删除都在栈顶进行操作。故选B。下列关于栈的叙述中，正确的A)栈底元素一定是最后入栈的元素B)栈顶元素一定是最先入栈的元素C)栈操作遵循先进后出的原则D)以上说法均错误【解析】栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表，或“后进先出”表，所以选择C。下列关于栈叙述正确的是（）A)栈顶元素最先能被删除B)栈顶元素最后才能被删除C)栈底元素永远不能被删除D)栈底元素最先被删除【解析】栈是先进后出的数据结构，所以栈顶元素最后入栈却最先被删除。栈底元素最先入栈却最后被删除。所以选择A。 //总结:栈顶元素最先被删除，栈底元素最后被删除—原因：栈的数据处理原则支持子程序调用的数据结构是（）A)栈B)树C)队列D)二叉树【解析】栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为A。b.队列:相关试题:对于循环队列，下列叙述中正确的是（）A)队头指针是固定不变的B)队头指针一定大于队尾指针C)队头指针一定小于队尾指针D)队头指针可以大于队尾指针，也可以小于队尾指针【解析】循环队列的队头指针与队尾指针都不是固定的，随着入队与出队操作要进行变化。因为是循环利用的队列结构，所以对头指针有时可能大于队尾指针有时也可能小于队尾指针。故选D。设循环队列的存储空间为Q（1:35），初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数A)15 B)16 C)20 D)0或35【解析】在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界时，其加1操作的结果是指向向量的下界0。由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时，头尾指针均相等。答案为D选项。相关综合习题：下列叙述中正确的是（）A)栈是一种先进先出的线性表B)队列是一种后进先出的线性表C)栈与队列都是非线性结构D)以上三种说法都不对【解析】栈是一种先进后出的线性表，队列是一种先进先出的线性表，栈与队列都是线性结构。故选D。4. 树与二叉树相关试题:某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）A)3 B)6 C)8 D)12【解析】二叉树中，度为0的节点数等于度为2的节点数加1，即n2=n0-1，叶子节点即度为0，n0=1，则n2=0，总节点数为12=n0+n1+n2=1+n1+0，则度为1的节点数n1=11，故深度为12，选D。某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（）A)10B)8C)6D)4【解析】根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子节点总是比度为2的节点多一个，所以本题中是5＋1＝6个。故选C。某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（）A)32 B)46 C)48 D)49【解析】在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。由16个度为2的结点可知叶子结点个数为17，则结点总数为16+17+15=48，C选项正确。对下列二叉树进行前序遍历的结果为（）A)DYBEAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ【解析】前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后