二级公共基础知识考前押题 .docx

二级公共基础知识考前押题一、数据结构与算法1 .下列叙述中正确的是A）所谓匏法就是计算方法B）程序可以作为算法的一种描述方法Q算法设计只需考虑得到计算结果D）笄法设计可以忽略算法的运算时间B【解析】克法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为期法的一种描述方法。2 .下列关于算法的描述中错误的是A）算法强调动态的执行过程，不同于静态的计算公式B）算法必须能在有限个步骤之后终止C）算法设计必须考虑算法的豆杂度D）算法的优劣取决于运行算法程序的环境1）【解析】算法设计不仅要考虑计算结果的正确性，还要考虑算法的时间豆杂度和空间复杂度。3 .下列叙述中正确的是A）匏法的豆杂度包括时间星杂度与空间豆杂度B）算法的品杂度是指算法控制结构的复杂程度C）算法的曳杂度是指算法程序中指令的数量D）算法的豆杂度是指算法所处理的数据量M解析】第法完杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源.算法的复杂度包括时间夏杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间竟杂度是指算法在执行过程中所需要的内存空间。4 .下列叙述中正确的是A）算法的时间且杂度与计算机的运行速度有关B）算法的时间夏杂度与运行算法时特定的输入有关Q算法的时间豆杂度与算法程序中的语句条数成正比D）算法的时间夏杂度与算法程序编制者的水平有关B【解析】为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计匏机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运郭的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。5 .下列叙述中正确的是A）解决同一个问题的不同算法的时间豆杂度一般是不同的B）解决同一个问胭的不同算法的时间夏杂度必定是相同的。对同一批数据作同一种处理，如果数据存储结构不同，不同算法的时间划杂度肯定相同D）对同一批数据作不同的处理，如果数据存储结构相同，不同算法的时间受杂度肯定相同AL解析】解决同一个问网的不同算法的时间复杂度，可能相同也可能不相同。算法的时间豆杂度与数据存储结构无关，对I可一批数据作同一种处理或者不同处理，数据存储结构相同或者不同，算法的时间包杂度都可能相同或者不同。6 .下列叙述中正确的是A）算法的空间更杂度是指算法程序中指令的条数B）压缩数据存储空间不会降低算法的空间夏杂度C）算法的空间复杂度与算法所处理的数据存储空间有关D）算法的空间复杂度是指兑法程序控制结构的更杂程度C【解析】算法的空间豆杂度是指算法在执行过程中所需要的内存空间。第法执行期间所需的存储空间包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。7 .为了降低算法的空间复杂度，要求算法尽量采用原地工作（inplace）.所谓原地工作是指A）执行算法时不使用额外空间B）执行算法时不使用任何存储空间。执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变化D）执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小的变化而变化）DL解析】对于算法的空间豆杂度，如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即领外空间量不随问题规模的变化而变化，则称该算法是原地工作的。8 .下列叙述中正确的是A)莫法的笑杂度与问题的规模无关B)算法的优化主要通过程序的编制技巧来实现Q对数据进行压缩存储会降低算法的空间曳杂度D)数值型算法只需考虑计算结果的可靠性C【解析】在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。9 .下列叙述中正确的是A)数据的存储结构会影响党法的效率B)算法设计只需考虑结果的可靠性Q算法复杂度是指算法控制结构的更杂程度D)算法史杂度是用算法中指令的条数来度量的A【解析】采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构很重要.10 .下列叙述中错误的是A)数据结构中的数据元素可以是另一数据结构B)数据结构中的数据元素不能是另一数据结构C)空数据结构可以是线性结构也可以是非线性结构D)非空数据结构可以没有根结点B【解析】数据元素是一个含义很广泛的概念，它是数据的“基本单位”，在计匏机中通常作为一个整体进行考虑和处理。数据元素可以是一个数据也可以是被抽象出的具有一定结构数据集合，所以数据结构中的数据元素可以是另一数据结构。满足有且只有一个根结点并且每一个结点最多有一个前件，也故多有一个后件的非空的数据结构认为是线性结构，不满足条件的结构为非线性结构。空数据结构可以是线性结构也可以是非线性结构,非空数据结构可以没有根结点，如非性线结构“图”就没有根结点。IL下列叙述中正确的是A)非线性结构可以为空B)只有一个根结点和一个叶子结点的必定是线性结构C)只有一个根结点的必定是线性结构或二叉树D)没有根结点的一定是非线性结构A【解析】如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点威多有一个前件，也龄多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构,树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。12 .下列叙述中错误的是A)向量是线性结构B)非空线性结构中只有一个结点没有前件C)非空线性结构中只有一个结点没有后件D)具有两个以上指针域的链式结构一定属于非线性结构D【解析】双向链表每个结点有两个指针，一个为左指针，用于指向其前件结点；一个为右指针，用于指向其后件结点，再加上头指针，具有两个以上的指针，但双向链表属于线性结构.非空线性结构中第一个结点没有前件，最后一个结点无后件，其余结点最多有一个前件，也最多有一个后件。向量也满足这个条件，属于线性结构.13 .设数据结构B=(D,R),其中D=a,b,c,d,e,fR=(f,a),(d,b),(e,d),(c,e),(a,c)该数据结构为A)线性结构B)循环队列C)循环链表D)非线性结构R【解析】数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D：二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成B=(D,R).其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设H与b是D中的两个数据，则二元组(a,b)表示U是b的前件，b是a的后件。本网中R中的根结点为f.元素顺序为f-ac-e-db,满足线性结构的条件。14 .设数据集合为31,2,3,4,5)下列数据结构B=(D,R)中为非线性结构的是A)R=(2,5),(5,4),(3,1),(4,3)B)R=(1,2),(2,3),(3,4),(4,5)C)R=(1,2),(2,3),(4,3),(3,5)D)R=(S,4),(4,3),(3,2),(2,1)C【解析】A项中，R=(2,5),(5,4),(3,1),(4,3),2为根结点，元素顺序为2-5-43-1,属于线性结构；同理B项I为根结点，元素顺序为1-2-3-4-5,D项5为跟结点，元素顺序为5-4-3-2-1,均为线性结构。C项中，元素3有两个前件，属于非线性结构。15 .下列叙述中正确的是A）矩阵是非线性结构B）数组是长度固定的线性表C）对线性表只能作插入与删除运算D）线性表中各元素的数据类型可以不I可B【解析】矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行杳找或对线性表进行排序等操作。16 .在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数A不同，但元素的存储顺序与逻辑顺序一致B）不同，且其元素的存储顺序可以与逻辑顺序不一致C）相1可，元紊的存储顺序与逻辑顺序一致D）相同，但其元素的存储顺序可以与逻辑顺序不一致C【解析】在线性表的顺序存储结构中，共存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。17 .下列叙述中正确的是A）能采用顺序存储的必定是线性结构B）所有的线性结构都可以采用顺序存储结构C）具有两个以上指针的链表必定是非线性结构D）循环队列是队列的链式存储结构B【解析】所有的线性结构都可以用数组保存，即都可以采用顺序存储结构,而反过来不可以，完全二叉树也能用数组保存（按层次依次存放到数据元素中），但完全二叉树不属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。18 .下列叙述中正确的是A）在栈中，栈顶指针的动态变化决定栈中元素的个数B）在循环队列中，队尾指针的动态变化决定队列的长度Q在循环链表中，头指针和链尾指针的动态变化决定链表的长度D）在线性链表中，头指针和链尾指针的动态变化决定链表的长度【解析】在栈中，通常用指针Iop来指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。19 .设栈的顺序存储空间为S（Lm）,初始状态为SP=O.现经过一系列正常的入栈与退栈操作后，top=m+l,则栈中的元素个数为A）0B）mC）不可能D）m+1C【解析】栈为空时，栈顶指针Iop=O,经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为Iop=O,当栈满时top=m,无法继续入栈，top值不可能为m+1°20 .设栈的存储空间为S（l:50）,初始状态为lop=T,现经过一系列正常的入栈与退栈操作后，top=30,则栈中的元素个数为A）20B）19C）31D）30D【解析】栈的初始状态为top=T表示栈为空（没有规定栈中栈底必须是0），经过一系列正常的入栈与退栈操作后lop=30,则空间（1:30）中插入了元素，共30个。21 .设栈的顺序存储空间为S（l:m）,初始状态为top=m+l,则栈中的数据元素个数为A）top-m+lB）m-top+lC）m-topD）top-mB【解析】栈的初始状态IOP=In+1,说明栈空时toj>=m+l（m在栈底，1是开口向上的），入栈时栈顶指针是减操作（Iop=Iop-D.退栈时栈顶指针是加操作（I。P=U>p+D。本胭可以假设栈中有X个元素，当x=0时，也就是栈中没有元素，则IoP=In+1；当x=m时，也就是栈满，则IOP=L由此可以得出top=m+l-,继而得出x=m-top+l,22 .设栈的顺序存储空间为SU：m）,初始状态为IOP=m+1。现经过一系列正常的入栈与退栈操作后，Iop=O,则栈中的元索个数为A）lB）mC）m+1D）不可能D【解析】栈的初始状态为top=m+l,说明栈空时top=m+l,人找时栈顶指针是减操作Cop=BpT）,退栈时栈顶指针是加操作（IOP=Iop+D。栈满时IOP=L说明栈中不能再进行入栈操作，Iop=O的情况不会出现。23 .设栈的存储空间为S（Lm）,初始状态为lop=m+l.经过一系列入栈与退栈操作后，Iop=L现又要将一个元素进栈，栈顶指针I。P值变为A）0B）发生栈满的错误CmD）2B【解析】栈的初始状态为top=m+l,说明栈空时top=m+l.入栈时栈顶指针是减操作(top=top-l),退栈时栈顶指针是加操作(I。P=IoP+1)。栈满时Iop=I,说明栈中不能再进行入校操作("上溢"错误)24 .设栈的存储空间为S(Lm),初始状态为IOP=m+1。经过一系列入栈与退栈操作后，IoP=m。现又在栈中退出一个元素后，栈顶指针I。P值为A)0B)m-1Qm+1D)产生栈空错误C【解析】栈的顺序存储空间为SU:m),初始状态top=m+l,所以这个栈是m在栈底，1是开口向上的。经过一系列入栈与退栈操作后I。所喻则栈中有1个元素，若现在又退出一个元素，那么枝顶指针下移一位，回到m+1的位置.25 .设栈的存储空间为S(l:50),初始状态为IOP=51。现经过一系列正常的入栈与退栈操作后，top=20,则栈中的元素个数为A|31B)30C)21D)20【解析】栈的初始状态IOP=51,故本栈是51在栈底，入栈时栈顶指针是减操作(top=top-D,退栈时枝顶指针是加操作(I。P=lop+D.当IOP=20时，元素存储在(20:50)空间中，因此共有50-20+1=31个元素。26 .下列处理中与队列有关的是A)二叉树的遍历B)操作系统中的作业调度C)执行程序中的过程调用D)执行程序中的循环控制B【解析】队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的匏法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。执行程序中的过程调用一般指函数调用，需要调用时候转入被调用函数地址执行程序，与队列无关.执行程序中的循环控制是指第法的基本控制结构,包括对循环条件的判定与执行循环体，与队列无关。二叉树是一个有限的结点集合，二叉树的遍历是指不重豆地访问二叉树中的所有结点，与队列无关.27 .设有栈S和队列Q,初始状态均为空。首先依次将,B,C,D,E,F入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为A)DEFXYZABCB)FEDZYXCBAOfedxyzcbaD)DEFZYXABCB【解析】栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将八通工川工工入栈后，栈中元素为ABCDEF,退出三个元素入队，队列元素为FED,将X,Y,Z入栈后栈中元素为ABCXYZ,退栈全部入队后，队列元素为FEDZYXCBA。28 .下列叙述中正确的是A)循环队列是顺序存储结构B)循环队列是链式存储结构C)循环队列空的条件是队头指针与队尾指针相同D)循环队列的插入运算不会发生溢出现象A【解析】循环队列是队列的一种顺序存储结构。在循环队列中，在队列满和队列为空时，队头指针与队尾指针均相同；当需要插入的数据大于循环队列的存储长度，入队运算会覆盖前面的数据，发生溢出现象。29 .下列叙述中正确的是A)在循环队列中，队尾指针的动态变化决定队列的长度B)在循环队列中，队头指针和队尾指针的动态变化决定队列的长度C)在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D)在带链的栈中，栈顶指针的动态变化决定栈中元素的个数B【解析】在循环队列中，队头指针和队尾指针的动态变化决定队列的长度°带链的栈和带链的队列均采用链式存储结构，而在这种结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。30 .循环队列的存储空间为Q(l:50),初始状态为fronl=rear=50经过一系列正常的入队与退队操作后，ronl=rear=25,此后又插入一个元素，则循环队列中的元素个数为A)l,或50且产生上溢错误B)51Q26D)2A【解析】在循环队列运转起来后，当front=rear=25时可知队列空或者队列满，此后又插入了一个元素，如果之前队列为空，插入操作之后队列里只有一个元索：如果插入之前队列己满(50个元素)，执行插入则会产生溢出错误.31 .循环队列的存储空间为QU:40),初始状态为front=rear=40,经过一系列正常的入队与退队操作后，front=rear=15,此后又退出一个元素，则循环队列中的元素个数为A)14B)15C)40D)39,或。且产生下溢错误I)【解析】在循环队列运转起来后，当fronl=rear=I5时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有0个元素:如果退出之前队列已满(40个元素)，执行退出后，队列里还有39个元素。32 .设循环队列的存储空间为Q(l:50),初始状态为front=rear=50o现经过一系列入队与退队操作后，fronl=rear=l,此后又正常地插入了两个元素。最后该队列中的元素个数为A)3B)lC)2D)52C【解析】在循环队列运转起来后，由front=rear=I可知队列空或者队列满,此后又可以正常地插入了两个元素说明插入前队列为空，则插入后队列元素个数为2。33 .设循环队列的存储空间为Q(Lm),初始状态为空。现经过一系列正常的入队与退队操作后，front，rear=m-L此后从该循环队列中删除一个元素，则队列中的元素个数为A)m-1B)m-2C)0D)lB【解析】在循环队列运转起来后，如果rear-ronl>0,则队列中的元素个数为rear-fronl个；如果reur-fronl<0,则队列中的元素个数为rear-front+限该题中rl<m,即rear-front<0,则该循环队列中的元素个数为(IJrI)-m+m=m-le此后从该循环队列中删除一个元素，则队列中的元素个数为rlT=m-2°34 .设循环队列的存储空间为Q(Lm),初始状态为空。现经过一系列正常的入队与退队操作后，fronl=m-l,rear=m,此后再向该循环队列中插入一个元素，则队列中的元素个数为A)mB)m-1QlD)2D【解析】该题中m-l<m,即rear-front>0,则该循环队列中的元素个数为nr5T)=1。此后从该循环队列中插入一个元素，则队列中的元素个数为1+1=2.35 .设循环队列为Q(Lm),其初始状态为front=rear=三o经过一系列入队与退队运算后，front=30,rear=10,现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为A)19B)20C)m-19D)m-20D【解析】front=30»rear-10,front>rear,则队列中有10-30+m=r20个元素，在作顺序查找时，最坏情况下(最后一个元素才是要找的元素或没有要杳找的元素)比较次数为m-20次。36 .设循环队列的存储空间为Q(Lm),初始状态为fronl=rear=m,经过一系列正常的操作后，Cronl=I,rear=m1,为了在该队列中寻找值最大的元素，在般坏情况下需要的比较次数为A)0B)IC)m-2D)m-1C【解析】该题中l<m,即rear-front>0,则该循环队列中的元素个数为m-l.此在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为m-lT=r2°37 .设循环队列的存储空间为Q(l:50),初始状态为ronl=rear=50o经过一系列正常的操作后，fronl-l=rearo为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A)48B)49C)lD)0A【解析】该胭中rear-fronl=frontT-frOntx0,则该循环队列中的元素个数为rear-fronl+50=front-l-fronl+50=49,在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为49-1=48。38 .设循环队列的存储空间为Q(l:50),初始状态为fronl=rear=50,经过一系列正常的操作后，fronl=rear-U为了在该队列中寻找值最大的元素，在球坏情况下需要的比较次数为A)lB)OC)49D)50B【解析】该题中rear-front=rear-(rearT)>0.则该循环队列中的元素个数为rear-front=rear-(rearT)=l.因队列中只有1个元素，故寻找值城大的元素不需要进行比较，即比较次数为0。39 .线性表的链式存储结构与顺序存储结构相比.链式存储结构的优点有A）节省存储空间B）插入与甜除运算效率高Q便于查找D）排序时减少元素的比较次数B【解析】线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。类型优点缺点顺序表（I）可以随机存取表中的任意结点（2）无需为表示结点间的逻辑关系额外增加存储空问（1）插入和删除运算效率低（2）存储空间不便于扩充（3）不便于对存储空间的动态分配涟表（1）在进行插入和删除运算时，只需要改变指针即可，不需要移动元素（2）存储空间易于扩充并且方便空间的动态分配需要额外的空间（指针域）来表示数据元素之间的逻辑关系，存储密度比顺序表低40 .卜列结构中属于线性结构链式存储的是A）双向链表B）循环队列C）二叉链表D）二维数组八【解析】双向链表也叫双链表，是链表（采用链式存储结构）的一种，它的每个数据结点中都有两个才旨针，分别指向直接后继和直接前驱。循环队列是队列的一种顺序存储结构。二叉链表和二维数组属于非线性结构。41 .在我性表的链式存储结构中，其存储空间一般是不连续的，并且A）前件结点的存储序号小于后件结点的存储序号B）前件结点的存储序号大于后件结点的存储序号Q前件结点的存储序号可以小于也可以大于后件结点的存储序号D）以上三种说法均不正确C【解析】在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系o42 .卜列叙述中正确的是A）结点中具有两个指针域的链表一定是二叉链表B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C）循环链表是循环队列的链式存储结构D）循环链表是非线性结构B【解析】结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。43 .带链的栈与顺序存储的栈相比，其优点是A）入栈与退栈操作方便B）可以省略栈底指针Q入栈操作时不会受栈存储空间的限制而发生溢出D）所占存储空间相同C【解析】带链的栈就是用一个线性锥表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出（不需考虑栈满的问限）。44 .下列叙述中正确的是A）带链栈的栈底指针是随栈的操作而动态变化的B）若带链队列的队头指针与队尾指针相同，则队列为空C）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D）不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的A【解析】由于带链栈利用的是计算机存储空间中的所有空闹存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与足指针相同。45 .带链栈空的条件是A）top=bottom=NULLB）top=-1且bottom=NULLC）top=NULL且bottom=-lD）top=bottom=-1A【解析】在带链的栈中，只会出现栈空和非空两种状态。当栈为空时，有lop=botlwB=NULL；当栈非空时，IOP指向链表的第一个结点（栈顶）。46 .在带链栈中，经过一系列正常的操作后，如果lop=bott0<n,则栈中的元素个数为A）O或1B）0QlD）栈满A【解析】带链栈就是没有附加头结点、运算受限的单链表.栈顶指针就是链表的头指针,如果枝底指针指向的存储单元中存有一个元素，则当lop=boito<n时，栈中的元素个数为1：如果栈底指针指向的存储单元中没有元素，则当to=bOttom时，栈中的元素个数为Oe47 .某带链栈的初始状态为IOP=bollom=NULL,经过一系列正常的入栈与退栈操作后，top=bOlIom=20。该栈中的元素个数为A）0）lC）20D）不确定B【解析】带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素48 .某带链栈的初始状态为lop=bollom=NULL,经过一系列正常的入栈与退栈操作后，top=10,bottom=20e该栈中的元素个数为A）0B）l010D）不确定1）【解析】带链的栈使用/链表来表示栈，而链表中的元素存储在不连续的地址中，因此当IOp=I0,b<Hiom=20时，不能确定栈中元素的个数.49 .带链队列空的条件是A）front=rear=NULLB）front=-1且rear=NULLOfront=NULL且rear=-lD）front=rear=-1A【解析】带链的队列就是用一个单链表来表示的队列，队列中的每一个元素对应链表中的一个结点。队列空时，头指针和尾指针都为WLL50 .在带链队列中，经过一系列正常的操作后，如果fronl=rear,则队列中的元素个数为A）0B）IC）。或1D）队列满C【解析】带链队列空时，头指针和尾指针都为NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。51 .某带链的队列初始状态为front=rear=NULL<经过一系列正常的入队与退队操作后，fronl=rear=10o该队列中的元素个数为A）0B）lC）I或0D）不确定B【解析】带链队列空时，头指针和尾指针都为null；队列中只有一个元素时，头指针和尾指针都指向这个元素。52 .某带链的队列初始状态为front=rear=NULL.经过一系列正常的入队与退队操作后，ront=10,rear=5,该队列中的元素个数为A）4）5C）6D）不确定D【解析】带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当ronl=10,rear=5时，不能确定队列中元素的个数。53 .下列叙述中错误的是A）循环链表中有一个表头结点B）循环曾表是循环队列的存储结构Q循环链表的表头指针与循环链表中质后一个结点的指针均指向表头结点D）循环链表实现了空表与非空表运算的统一B【解析】循环链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，龄后一个结点的指针域的值由NiJLL改为指向表头结点。循环链表是线性表的一种链式存储结构.循环队列是队列的一种顺序存储结构.54 .从表中任何一个结点位置出发就可以不重豆地访问到表中其他所有结点的链表是A）循环链表B）双向链表C）单向链表D）二叉锥表A【解析】在循环链表中，所有结点的指针构成了一个环状链，只要指出表中任何一个结点的位.置，就可以从它出发不至匏地访问到表中其他所有结点。55 .非空循环链表所表示的数据结构A）有根结点也有叶子结点B）没有根结点但有叶子结点C）有根结点但没有叶子结点D）没有根结点也没有叶子结点RL解析】循环链表表头结点为根结点，链表的殷后一个结点为叶子节点，虽然它含有一个指向表头结点的指针，但是表头结点并不是它的一个后件。56 .下列结构中为非线性结构的是A）树B）向量C）二维表D）矩阵M解析】由定义可以知道，树为一种简单的非线性结构,在数这种数据结构中，所有数据元素之间的关系具有明显的层次特性。57 .某棵树中共有25个结点，且只有度为3的结点和叶子结点，其中叶子结点有7个，则该树中度为3的结点数为A)6B)7C)8D)不存在这样的树D【解析】根据题意，树中只有度为3的结点和叶子结点(7个)，则度为3的结点有25-7=18个；又根据树中的结点数=树中所有结点的度之和+1,设度为3的结点数为n,则3n+l=25,得n=8°两种方式得到的度为3的结点数不同，故不存在这样的树.58 .某棵树的度为4,且度为4、3、2、1的结点个数分别为1、2、3、4,则该树中的叶子结点数为A)ll8)9QlOD)8A【解析】设叶子结点数为n,根据树中的结点数-树中所有结点的度之和+1,得4Xl+3X2+2X3+lX4+nX0+l=21,则n=21-l-2-3-4=ll,59 .设一棵树的度为3,共有27个结点，其中度为3,2,。的结点数分别为4,1,IOe该树中度为1的结点数为A)11B)12C)13D)不可能有这样的树B【解析】设度为1的结点数为n,根据树中的结点数=树中所有结点的度之和+1,得3X4+2Xl+lXn+0XlQH=27,则n=12e60 .设一棵度为3的树，其中度为2,1,O的结点数分别为3,1,6。该树中度为3的结点数为A)lB)2C)3D)不可能有这样的树A【解析】设树的结点数为n,则度为3的结点数为n-37-6=n-10,根据树中的结点数=树中所有结点的度之和+1,得3X(nTO)+2X3+lXl+0X6+l=n,解得n=ll,则度为3的结点数为nTO=UTO=L61 .设一棵树的度为3,其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为A)3B)lC)2D)不可能有这样的树C【解析】设树的结点数为m,度为3的结点数为n,则度为1的结点数为rn-5,根据树中的结点数=树中所有结点的度之和+1,得3Xn+lX(m-n-5)+5X0+l=m,则n=2062 .度为3的一棵树共有30个结点，其中度为3,1的结点个数分别为3,4.则该树中的叶子结点数为A) 14B) 15C) 16D)不可能有这样的树B【解析】设叶子结点数为n,则度为2的结点数为30-3-4-n=23-n,根据树中的结点数-树中所有结点的度之和+1,得3X3+2X(23-n)+lX4+0Xn+l=30,则n=1563 .设某棵树的度为3,其中度为2,1,0的结点个数分别为3,4,15。则该树中总结点数为A)不可能有这样的树B|30C)22D)3SA【解析】设树的总结点数为n,则度为3的结点数为n-3-4-15=n-22,根据树中的结点数=树中所有结点的度之和+1,得3X(n-22)+2X3+lX4+OX15+l=n,则n=27.5,求出的结点数不为整数，故不可能有这样的树存在.64 .某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为A)400B)754C)756D)不确定CL解析】叶子结点有45个，根据在二叉树中度为O的结点(叶子结点)总比度为2的结点多一个，则度为2的结点数为44个，因此度为1的结点数为845-45-44=756个。65 .某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为A)32)46C48D49C【解析】根据在：叉树中度为O的结点(叶子结点)总比度为2的结点多一个，得度为O的结点数为16+1=17个，故总的结点数=17+15+16=48个。66 .某二叉树共有730个结点，其中度为1的结点有30个，则叶子结点个数为A)lB)3S1C)350D)不存在这样的二叉树1)【解析】设叶子结点数为n,根据在二叉树中度为0的结点(叶子结点)总比度为2的结点多一个，则度为2的结点数为n-l,n+nT+30=730,得n=350.5.由于结点数只能为整数，所以不存在这样的二叉树.67 .某二叉树中共有350个结点，其中200个为叶子结点，则该二叉树中度为2的结点数为A)不可能有这样的二叉树B)1500199D)149八【解析】叶子结点数为200,根据在二叉树中度为。的结点(叶子结点)总比度为2的结点多一个，则度为2的结点数为199,I99+2OO>35O,故不存在这样的二叉树.68 .某二叉树的深度为7,其中有64个叶子结点，则该二叉树中度为1的结点数为A)0B)lC)2D)63八【解析】叶子结点有64个，根据在二叉树中度为。的结点(叶子结点)总比度为2的结点多一个，则度为2的结点数为63个；又深度为m的二叉树最多有2"-1个结点，则该二叉树场多有2'T=127个结点。64+63=127,因此该树不存在度为1的结点。69 .深度为7的二叉树共有127个结点，则下列说法中错误的是A)该二叉树是满二叉树B)该二叉树有一个度为1的结点Q该二叉树是完全二叉树D)该二叉树有64个叶子结点B【解析】满二叉树满足深度为m的二叉树最多有2、1个结点，本题中二叉树深度为7且有127个结点，满足2=1=127,达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第k层上有2处,结点，则该二叉树的叶子结点数为27'=64个。满二叉树不存在度为1的结点。70 .深度为5的完全二叉树的结点数不可能是A)15B)16Q17D)18A【解析】设完全二叉树的结点数为n,根据深度为k的二叉树至多有2卜-1个结点，再根据完全二叉树的定义可知，2l,-l<n2k-l.,本题中完全二叉树的深度为5,则2"T<n2b-1,15<n3k因此，结点数不能为15。71 .某完全二叉树共有256个结点，则该完全二叉树的深度为A)7B)8C)9D)10C【解析】根据完全二叉树的性质：具有n个结点的完全二叉树的深度为“ogm+l0本甥中完全二叉树共有256个结点，则深度为口og?256+1=8+1=9°72 .深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为A)62B)63064D)6SB【解析】在满二叉树的第k层上有2"个结点、且深度为m的满二叉树有2-l个结点，则深度为6的满二叉树共有2忆1=63个结点，第6层上有2=32个结点。本题是深度为7的完全二叉树，则前6层共有63个结点，第7层的结点数为125-63=62个且全为叶子结点.由于第6层上有32个结点，第7层上有62个结点，则第6层上有1个结点无左右子树(该结点为叶子结点)。因此，该完全二叉树中共有叶子结点62+1=63个。73 .在具有2n个结点的完全二叉树中，叶子结点个数为A)nB)n+1C)n-1D)n2八【解析】由二叉树的定义可知，树中必定存在度为0的结点和度为2的结点，设度为0结点有a个，根据度为0的结点(即叶子结点)总比度为2的结点多一个，得度为2的结点有