计算机二级选择

1、 执行算法时不使用任何存储空间B) 1.下列叙述中正确的是 A)所谓算法就是计算方法执行算法时所使用的额外空间随算法所处理的数据空间大C) B)程序可以作为算法的一种描述方法 小的变化而变化 算法设计只需考虑得到计算结果C)执行算法时所使用的额外空间固定（即不随算法所处理的D) 算法设计可以忽略算法的运算时间D) 数据空间大小的变化而变化）算法不算法是指对解题方案的准确而完整的描述，B【解析】【解析】对于算法的空间复杂度，如果额外空间量相对于D等于数学上的计算方法，也不等于程序。算法设计需要考虑问题规模（即输入数据所占的存储空间）来说是常数，即额可行性、确定性、有穷性与足够的情报，不能只考虑计

2、算结外空间量不随问题规模的变化而变化，则称该算法是原地工果。算法设计有穷性是指操作步骤有限且能在有限时间内完 作的。成，如果一个算法执行耗费的时间太长，即使最终得出了正 下列叙述中正确的是8.算法在实现时需要用具体的程序确结果，也是没有意义的，。 算法的复杂度与问题的规模无关A) 设计语言描述，所以程序可以作为算法的一种描述方法。 算法的优化主要通过程序的编制技巧来实现B) 下列关于算法的描述中错误的是2. C)对数据进行压缩存储会降低算法的空间复杂度 算法强调动态的执行过程，不同于静态的计算公式A) D)数值型算法只需考虑计算结果的可靠性 算法必须能在有限个步骤之后终止B)为了减少算法所占的

3、存储空间，【解析】在许多实际问题中，C C)算法设计必须考虑算法的复杂度 通产采用压缩存储技术，以便尽量减少不必要的额外空间。 D)算法的优劣取决于运行算法程序的环境 9.下列叙述中正确的是【解析】算法设计不仅要考虑计算结果的正确性，还要考D A)数据的存储结构会影响算法的效率 虑算法的时间复杂度和空间复杂度。 B)算法设计只需考虑结果的可靠性 3.下列叙述中正确的是 C)算法复杂度是指算法控制结构的复杂程度 算法的复杂度包括时间复杂度与空间复杂度A) D)算法复杂度是用算法中指令的条数来度量的 算法的复杂度是指算法控制结构的复杂程度B)其数据处理的效率是不同的。【解析】采用不同的存储结构，A

4、 C)算法的复杂度是指算法程序中指令的数量 因此，在进行数据处理时，选择合适的存储结构很重要。 D)算法的复杂度是指算法所处理的数据量 10.下列叙述中错误的是运行A【解析】算法复杂度是指算法在编写成可执行程序后， 数据结构中的数据元素可以是另一数据结构A)时所需要的资源，资源包括时间资源和内存资源。算法的复 数据结构中的数据元素不能是另一数据结构B)杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指 空数据结构可以是线性结构也可以是非线性结构C)执行算法所需要的计算工作量；算法的空间复杂度是指算法 非空数据结构可以没有根结点D) 在执行过程中所需要的内存空间。“基它是数据的【解析】数据元素

5、是一个含义很广泛的概念，B 下列叙述中正确的是4.在计算机中通常作为一个整体进行考虑和处理。数，本单位” 算法的时间复杂度与计算机的运行速度有关A)据元素可以是一个数据也可以是被抽象出的具有一定结构数 算法的时间复杂度与运行算法时特定的输入有关B)据集合，所以数据结构中的数据元素可以是另一数据结构。 算法的时间复杂度与算法程序中的语句条数成正比C)满足有且只有一个根结点并且每一个结点最多有一个前件， D)算法的时间复杂度与算法程序编制者的水平有关也最多有一个后件的非空的数据结构认为是线性结构，不满为了能够比较客观地反映出一个算法的效率，在度【解析】B足条件的结构为非线性结构。空数据结构可以是线

6、性结构也量一个算法的工作量时，不仅应该与所使用的计算机、程序可以是非线性结构。非空数据结构可以没有根结点，如非性设计语言以及程序编制者无关，而且还应该与算法实现过程 线结构“图”就没有根结点。中的许多细节无关。为此，可以用算法在执行过程中所需基 11.下列叙述中正确的是本运算的执行次数来度量算法的工作量。算法所执行的基本 A)非线性结构可以为空运算次数还与问题的规模有关；对应一个固定的规模，算法 B)只有一个根结点和一个叶子结点的必定是线性结构 所执行的基本运算次数还可能与特定的输入有关。 C)只有一个根结点的必定是线性结构或二叉树 5.下列叙述中正确的是 D)没有根结点的一定是非线性结构 A

7、)解决同一个问题的不同算法的时间复杂度一般是不同的有如果一个非空的数据结构满足下列两个条件：A【解析】 B)解决同一个问题的不同算法的时间复杂度必定是相同的且只有一个根结点；每一个结点最多有一个前件，也最多对同一批数据作同一种处理，如果数据存储结构不同，不C)有一个后件。则称该数据结构为线性结构。如果一个数据结 同算法的时间复杂度肯定相同构不是线性结构，则称之为非线性结构。线性结构和非线性对同一批数据作不同的处理，如果数据存储结构相同，不D)结构都可以是空的数据结构。树只有一个根结点，但不论有 同算法的时间复杂度肯定相同 几个叶子结点，树都是非线性结构。可能相A【解析】解决同一个问题的不同算法

8、的时间复杂度， 下列叙述中错误的是12.同也可能不相同。算法的时间复杂度与数据存储结构无关， 向量是线性结构A)对同一批数据作同一种处理或者不同处理，数据存储结构相 B)非空线性结构中只有一个结点没有前件 同或者不同，算法的时间复杂度都可能相同或者不同。 C)非空线性结构中只有一个结点没有后件 6.下列叙述中正确的是 D)具有两个以上指针域的链式结构一定属于非线性结构 算法的空间复杂度是指算法程序中指令的条数A)【解析】双向链表每个结点有两个指针，一个为左指针，D B)压缩数据存储空间不会降低算法的空间复杂度一个为右指针，用于指向其后件结点，用于指向其前件结点； 算法的空间复杂度与算法所处理的

9、数据存储空间有关C)再加上头指针，具有两个以上的指针，但双向链表属于线性 D)算法的空间复杂度是指算法程序控制结构的复杂程度结构。非空线性结构中第一个结点没有前件，最后一个结点算法的空间复杂度是指算法在执行过程中所需要的【解析】C无后件，其余结点最多有一个前件，也最多有一个后件。向个部分：输3内存空间。算法执行期间所需的存储空间包括 量也满足这个条件，属于线性结构。入数据所占的存储空间；程序本身所占的存储空间；算法执 设数据结构13.B=(D, R)，其中 行过程中所需要的额外空间。 D= a, b, c, d, e, f 为了降低算法的空间复杂度，要求算法尽量采用原地工作7. R= (f,

10、a), (d, b), (e, d), (c, e), (a, c) (in place)。所谓原地工作是指 该数据结构为 执行算法时不使用额外空间A) 也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。A)线性结构 现经过top=0。S(1:m)B)循环队列 ，初始状态为19.设栈的顺序存储空间为，则栈中的元素一系列正常的入栈与退栈操作后， top=m+1C)循环链表 D)非线性结构 个数为 A) 0 A【解析】数据的逻辑结构有两个要素：一是数据元素的集合， 中各数据元素之B)m 二是通常记为D；D上的关系，它反映了D 间的前后件关系，通常记为R。即一个数据结构可以表示成C)不可能 DB

11、表示数据结构。为了反映中各数据元D)m+1B=（D,R）。其中经过入栈和退栈运算，top=0，素之间的前后件关系，一般用二元组来表示。例如，假设a【解析】栈为空时，栈顶指针C，当栈满时b是的前件，top=m初始状态为top=0，指针始终指向栈顶元素。与b是D中的两个数据，则二元组（a,b）表示a m+1。无法继续入栈，top值不可能为f，元素顺序为fab是a的后件。本题中R中的根结点为。现经过一，初始状态为top=-120.设栈的存储空间为S(1:50)cedb，满足线性结构的条件。 ，则栈中的元素个数系列正常的入栈与退栈操作后，。下列数据结构 B=(D, R)top=30D= 1, 2, 3

12、, 4, 5 14.设数据集合为 为中为非线性结构的是 A)20A)R= (2,5), (5,4), (3,1), (4,3) B)R= (1,2), (2,3), (3,4), (4,5) B)19 C)31C)R= (1,2), (2,3), (4,3), (3,5) D)30D)R= (5,4), (4,3), (3,2), (2,1) 表示栈为空（没有规定栈top=-1R=(2,5),(5,4),(3,1),(4,3)，2为根结点，元D【解析】栈的初始状态为AC【解析】项中，经过一系列正常的入栈与退栈操作后）中栈底必须是，31属于线性结构；同理B项1为根结0素顺序为254 个。元素顺序

13、1:30）中插入了元素，共30top=30，则空间（51点，元素顺序为234，D项5为跟结点，则为top=m+1设栈的顺序存储空间为3项中，元素有两个前S(1:m)，初始状态为21.15432，均为线性结构。C 件，属于非线性结构。 栈中的数据元素个数为 A)top-m+115.下列叙述中正确的是 A)矩阵是非线性结构 B)m-top+1 数组是长度固定的线性表 C)m-topB) C)对线性表只能作插入与删除运算 D)top-mm（，说明栈空时top=m+1B【解析】栈的初始状态top=m+1D)线性表中各元素的数据类型可以不同 针是减操作，入栈时栈顶指是开口向上的）【解析】矩阵也是线性表，

14、只不过是比较复杂的线性表。线B在栈底，1。本题），退栈时栈顶指针是加操作（性表中各元素的数据类型必须相同。在线性表中，不仅可以top=top+1（top=top-1）也就是栈中没有元素，时，当x=0可以假设栈中有做插入与删除运算，还可以进行查找或对线性表进行排序等x个元素，由此可以时，也就是栈满，则top=1；当则top=m+1 操作。x=m m-top+1。16.在线性表的顺序存储结构中，其存储空间连续，各个元素得出top=m+1-x，继而得出。现 所占的字节数 ，初始状态为top=m+122.设栈的顺序存储空间为S(1:m)，则栈中的元素经过一系列正常的入栈与退栈操作后， A不同，但元素的

15、存储顺序与逻辑顺序一致top=0 个数为B)不同，且其元素的存储顺序可以与逻辑顺序不一致 相同，元素的存储顺序与逻辑顺序一致A)1C) D)B)m相同，但其元素的存储顺序可以与逻辑顺序不一致 C)m+1C【解析】在线性表的顺序存储结构中，其存储空间连续，各 个元素所占的字节数相同，在存储空间中是按逻辑顺序依次D)不可能，存放的。top=m+1【解析】栈的初始状态为D top=m+1，说明栈空时退栈时栈顶指针是加下列叙述中正确的是17. ，（top=top-1 ）入栈时栈顶指针是减操作，说明栈中不能再进行入栈top=1能采用顺序存储的必定是线性结构A) top=top+1）。栈满时操作（ B)所

16、有的线性结构都可以采用顺序存储结构的情况不会出现。操作，top=0。经过一top=m+1S(1:m)，初始状态为具有两个以上指针的链表必定是非线性结构C) 23.设栈的存储空间为。现又要将一个元素进栈，栈top=1系列入栈与退栈操作后， 循环队列是队列的链式存储结构D) top顶指针【解析】B所有的线性结构都可以用数组保存，即都可以采用值变为 A)0 顺序存储结构。而反过来不可以，完全二叉树也能用数组保 但完全二叉树不属于非，存（按层次依次存放到数据元素中）B)发生栈满的错误 线性结构。双向链表具有两个以上的指针，但属于线性结构。C)m D)2 循环队列是队列的顺序存储结构。，说明栈空时top

17、=m+1下列叙述中正确的是18. B【解析】栈的初始状态为top=m+1退栈时栈顶指针是加 在栈中，栈顶指针的动态变化决定栈中元素的个数A)，（top=top-1）入栈时栈顶指针是减操作，说明栈中不能再进行入栈 在循环队列中，队尾指针的动态变化决定队列的长度B)top=1）。栈满时操作（top=top+1 “上溢”错误）操作（C)在循环链表中，头指针和链尾指针的动态变化决定链表的。经过一 长度，初始状态为top=m+124.设栈的存储空间为S(1:m)现又在栈中退出一个元素后，D)在线性链表中，头指针和链尾指针的动态变化决定链表的。系列入栈与退栈操作后，top=m 值为 长度栈顶指针top A

18、)0来指示栈顶的位置，用指topA【解析】在栈中，通常用指针 B)m-1动态反应了栈中元素的变top指向栈底。栈顶指针bottom针 C)m+1化情况。在循环队列中，队头指针和队尾指针的动态变化决 产生栈空错误D)定队列的长度。链式存储结构中，各数据结点的存储序号是，top=m+1，初始状态S(1: m)【解析】栈的顺序存储空间为C不连续的，并且各结点在存储空间中的位置关系与逻辑关系 各结点在存储空间中的位置关系与逻辑关系也不一致，故头1是开口向上的。经过一系列入栈所以这个栈是m在栈底， 指针和尾指针或栈顶指针无法决定链表长度。，则栈中有1个元素，若现在又退出一与退栈操作后top=m ，初始状

19、态为循环队列的存储空间为m+1的位置。 Q(1:50)30.个元素，那么栈顶指针下移一位，回到。经过一系列正常的入队与退队操作后，front=rear=5025.设栈的存储空间为S(1:50)，初始状态为top=51。现经过一则循环队列中的元素个此后又插入一个元素，front=rear=25top=20，则栈中的元素个数，系列正常的入栈与退栈操作后， 数为为 且产生上溢错误A)1 ，或50A)31 B)30 B)51 C)21 C)26 D)20 D)2front=rear=50，由初始状态为A【解析】循环队列长度为50A【解析】栈的初始状态top=51，故本栈是51在栈底，入栈1进首先队尾指

20、针rear可知此时循环队列为空。时栈顶指针是减操作（top=top-1），退栈时栈顶指针是加操入队运算时，指向的位置插入新元素。rear），然后在队尾指针时，元素存储在作（top=top+1）。当top=20(20:50)空间中，（即rear+1。退队运算时，排头指针rear=1rear=50+1时，50-20+1=31个元素。 置当队尾指针因此共有指针指向的位置上的frontfront+1下列处理中与队列有关的是 ），然后删除front进1（即26.front=rear=25当front=1A)二叉树的遍历 。元素，当排头指针front=50+1时，置时可知队列空或者队列满，此后又插入了一个

21、元素，如果之操作系统中的作业调度 B)前队列为空，插入操作之后队列里只有一个元素；如果插入 C)执行程序中的过程调用 ，执行插入则会产生溢出错误。个元素)D)执行程序中的循环控制 之前队列已满(50 ，初始状态为 B【解析】队列是指允许在一端进行插入，而在另一端进行删Q(1:40)31.循环队列的存储空间为。经过一系列正常的入队与退队操作后，除的线性表。由于最先进入队列的元素将最先出队，所以队front=rear=40则循环队列中的元素个此后又退出一个元素，列具有“先进先出”的特性，体现了“先来先服务”的原则。front=rear=15， 数为操作系统中的作业调度是指根据一定信息，按照一定的算

22、法， A) 14从外存的后备队列中选取某些作业调入内存分配资源并将新 创建的进程插入就绪队列的过程。执行程序中的过程调用一B)15 般指函数调用，需要调用时候转入被调用函数地址执行程序，C)40 0且产生下溢错误与队列无关。执行程序中的循环控制是指算法的基本控制结D)39，或时可知队列空或者队列满，此后构，包括对循环条件的判定与执行循环体，与队列无关。二【解析】当front=rear=15D如果之前队列为空，退出操作会产生错误，叉树是一个有限的结点集合，二叉树的遍历是指不重复地访又退出一个元素，执行)，如果退出之前队列已满问二叉树中的所有结点，与队列无关。 (40个元素队列里有0个元素； Q2

23、7.设有栈S和队列，初始状态均为空。首先依次将39个元素。退出后，队列里还有，初始状态为入栈，然后从栈中退出三个元素依次入队，再将设循环队列的存储空间为Q(1:50)32.A,B,C,D,E,F。现经过一系列入队与退队操作后，front=rear=50将栈中所有元素退出并依次入队，最后将队列X,Y,Z入栈后，此后又正常地插入了两个元素。最后该队列中中所有元素退出，则退队元素的顺序为 front=rear=1 的元素个数为A)DEFXYZABC A)3B)FEDZYXCBA C)FEDXYZCBA B)1 C)2D)DEFZYXABC 栈是一种特殊的线性表，它所有的插入与删除都限B【解析】D)5

24、2此后又可以,front=rear=1定在表的同一端进行。队列是指允许在一端进行插入，而在可知队列空或者队列满【解析】C由正常地插入了两个元素说明插入前队列为空，则插入后队列入栈后，栈中元素A,B,C,D,E,F另一端进行删除的线性表。将 为。元素个数为2将FED退出三个元素入队，ABCDEF，队列元素为，X,Y,Z，初始状态为空。现经过Q(1:m)，退栈全部入队后，队列元素为入栈后栈中元素为ABCXYZ33.设循环队列的存储空间为，此后。FEDZYXCBA ，rear=m-1front=m一系列正常的入队与退队操作后， 28.下列叙述中正确的是 从该循环队列中删除一个元素，则队列中的元素个数

25、为 循环队列是顺序存储结构A)m-1A) B) B)m-2循环队列是链式存储结构 C)0 C)循环队列空的条件是队头指针与队尾指针相同 循环队列的插入运算不会发生溢出现象D)D)1指向的后一个位置直到队尾指针循环队列是队列的一种顺序存储结构。A【解析】在循环队列【解析】从排头指针frontB指向的位置之间所有的元素均为队列中的元素。如果rear中，在队列满和队列为空时，队头指针与队尾指针均相同；个；如果rear-frontrear-front0当需要插入的数据大于循环队列的存储长度，入队运算会覆，则队列中的元素个数为。该题中盖前面的数据，发生溢出现象。rear-front+mrear-fron

26、t0 ，则队列中的元素个数为）（m-1，即rear-front0 29.下列叙述中正确的是则该循环队列中的元素个数为m-10【解析】该题中m-1rear，则D【解析】 二维数组D)个元素，在作顺序查找时，最坏情况下（最后10-30+m=m-20（采用链式存储结构）是链表【解析】双向链表也叫双链表，A一个元素才是要找的元素或没有要查找的元素）比较次数为的一种，它的每个数据结点中都有两个指针，分别指向直接 次。m-20后继和直接前驱。循环队列是队列的一种顺序存储结构。二，初始状态36.设循环队列的存储空间为Q(1:m) 叉链表和二维数组属于非线性结构。 front=rear=m。经过一系列正常的操

27、作后，front=1，rear=m为其存储空间一般是不连续的，41.在线性表的链式存储结构中，为了在该队列中寻找值最大的元素，在最坏情况下需要的比 并且 较次数为 A)前件结点的存储序号小于后件结点的存储序号 A)0 B)前件结点的存储序号大于后件结点的存储序号 B)1前件结点的存储序号可以小于也可以大于后件结点的存储C) C)m-2 序号 D)m-1 D)以上三种说法均不正确，则该循环队列中的，即【解析】该题中10C各数据结点的存储序【解析】在线性表的链式存储结构中，C。此在该队列中寻找值最大的元素，在最坏m-1元素个数为号是不连续的，并且各结点在存储空间中的位置关系与逻辑 情况下需要的比较

28、次数为m-1-1=m-2。关系也不一致，因此前件结点的存储序号与后件结点的存储，初始状态为Q(1:50)37.设循环队列的存储空间为 序号之间不存在大小关系。为了front-1=rear。经过一系列正常的操作后，front=rear=50。 下列叙述中正确的是 42.在该队列中寻找值最大的元素，在最坏情况下需要的比较次 结点中具有两个指针域的链表一定是二叉链表A) 数为结点中具有两个指针域的链表可以是线性结构，也可以是B) A)48 非线性结构 B)49 循环链表是循环队列的链式存储结构C) C)1 循环链表是非线性结构D) D)0结点中具有两个指针域的链表既可以是双向链表也【解析】B，则该循

29、环队列【解析】该题中Arear-front=front-1- front0A)带链栈的栈底指针是随栈的操作而动态变化的 1=1rear-1rear-front=rear-中的元素个数为（）。因队列中只有B)若带链队列的队头指针与队尾指针相同，则队列为空 个元素，故寻找值最大的元素不需要进行比较，即比较次数C)若带链队列的队头指针与队尾指针相同，则队列中至少有 0为。一个元素 线性表的链式存储结构与顺序存储结构相比，链式存储结39.D)不管是顺序栈还是带链的栈，在操作过程中其栈底指针均 构的优点有 是固定不变的 A)节省存储空间A【解析】由于带链栈利用的是计算机存储空间中的所有空闲 B)插入与删

30、除运算效率高存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的 便于查找C)队列中若只有一个元素，则头指针与尾指针相同。 D)排序时减少元素的比较次数45.带链栈空的条件是 线性表的顺序存储结构称为顺序表，线性表的链式【解析】BA)top=bottom=NULL 存储结构称为链表，两者的优缺点如下表所示。B)top=-1 且 bottom=NULL 优点类型 缺点 C)top=NULL 且 bottom=-1 ）插入和删除运算 顺序表（可以随机存取表中）1（1D)top=bottom=-1 效率低的任意结点 A【解析】在带链的栈中，只会出现栈空和非空两种状态。当）存储空间不便于2（无需为表示

31、结点间）2（栈为空时，有top=bottom=NULL；当栈非空时，top指向链 的逻辑关系额外增加存扩充 。表的第一个结点（栈顶）不便于对存储空（ 储空间3 间的动态分配 D)不确定如果top=bottom，46.在带链栈中，经过一系列正常的操作后，【解析】带链的队列使用了链表来表示队列，而链表中的 D则栈中的元素个数为 时，不A)0 或 1 元素存储在不连续的地址中，因此当front=10,rear=5 B)0 能确定队列中元素的个数。 C)1 53.下列叙述中错误的是 循环链表中有一个表头结点A)D)栈满 A【解析】带链栈就是没有附加头结点、运算受限的单链表。循环链表是循环队列的存储结构

32、B)循环链表的表头指针与循环链表中最后一个结点的指针均栈顶指针就是链表的头指针。如果栈底指针指向的存储单元C) 指向表头结点则当中存有一个元素，top=bottom时，栈中的元素个数为1； D)如果栈底指针指向的存储单元中没有元素，则当top=bottom循环链表实现了空表与非空表运算的统一循环链表是指在单链表的第一个结点前增加一个表B时，栈中的元素个数为0。 【解析】头结点，队头指针指向表头结点，最后一个结点的指针域的经过一系列正某带链栈的初始状态为top=bottom=NULL，47.改为指向表头结点。循环链表是线性表的一种链。该栈中的元素个数值由NULL常的入栈与退栈操作后，top=bo

33、ttom=20 为 式存储结构，循环队列是队列的一种顺序存储结构。从表中任何一个结点位置出发就可以不重复地访问到表中A)0 54. B)1 其他所有结点的链表是 循环链表C)20 A) 双向链表D)不确定 B) 带链的栈就是用一个单链表来表示的栈，栈中的每单向链表C)B【解析】 一个元素对应链表中的一个结点。栈为空时，头指针和尾指二叉链表D)所有结点的指针构成了一个环状链，在循环链表中，A针都为NULL；栈中只有一个元素时，头指针和尾指针都指【解析】只要指出表中任何一个结点的位置，就可以从它出发不重复向这个元素。 地访问到表中其他所有结点。48.某带链栈的初始状态为top=bottom=NUL

34、L，经过一系列正 。该栈中的元素55.非空循环链表所表示的数据结构，常的入栈与退栈操作后，top=10bottom=20 个数为 有根结点也有叶子结点A) 没有根结点但有叶子结点B)A)0 有根结点但没有叶子结点C)B)1 C)10 没有根结点也没有叶子结点D)链表的最后一个结点循环链表表头结点为根结点，D)不确定 A【解析】为叶子节点，虽然它含有一个指向表头结点的指针，但是表D【解析】带链的栈使用了链表来表示栈，而链表中的元素 存储在不连续的地址中，因此当top=10，bottom=20时，不头结点并不是它的一个后件。 下列结构中为非线性结构的是56.能确定栈中元素的个数。 树A)49.带链

35、队列空的条件是 向量A)front=rear=NULL B) rear=NULLB)front=-1 且 二维表C) 矩阵 rear=-1C)front=NULL 且 D)【解析】由定义可以知道，树为一种简单的非线性结构。在 AD)front=rear=-1数这种数据结构中，所有数据元素之间的关系具有明显的层队列A【解析】带链的队列就是用一个单链表来表示的队列， 次特性。中的每一个元素对应链表中的一个结点。队列空时，头指针的结点和叶子结点，且只有度为3 。2557.某棵树中共有个结点，和尾指针都为NULL 50.在带链队列中，经过一系列正常的操作后，3的结点数为其中叶子结点有front=rea

36、r，7个，则该树中度为如果 则队列中的元素个数为 A)6 B)7A)0 B)1 C)8 1C)0 或 D)不存在这样的树73的结点和叶子结点（D D)队列满【解析】根据题意，树中只有度为=25-7=18个；又根据树中的结点数，则度为3的结点有；队列C【解析】带链队列空时，头指针和尾指针都为NULL个）3n+1=25,则3的结点数为n,树中所有结点的度之和 中只有一个元素时，头指针和尾指针都指向这个元素。+1，设度为的结点数不同，故不存在这3得。经过一系列某带链的队列初始状态为51.front=rear=NULLn=8。两种方式得到的度为 该队列中的元素个。样的树。front=rear=10正常

37、的入队与退队操作后，、11的结点个数分别为、3、2 数为 、58.某棵树的度为4，且度为4 4，则该树中的叶子结点数为3 2、A)0 A)11 B)1 B)90C)1或 D)不确定C)10 【解析】带链队列空时，头指针和尾指针都为Bnull；队列中D)8树中所有=，根据树中的结点数A 只有一个元素时，头指针和尾指针都指向这个元素。【解析】设叶子结点数为n则0+1=21,。经过一系列front=rear=NULL某带链的队列初始状态为52.4+n2+23+11+3+1结点的度之和，得4 。front=10, rear=5正常的入队与退队操作后，n=21-1-2-3-4=11该队列中的元素。的02

38、，共有 个数为59.设一棵树的度为327个结点，其中度为3 的结点数为 110 A)4 14结点数分别为，。该树中度为 A) 11 B)5 B) 12 C)6 A) 1C) 13 B)351D)不可能有这样的树 C) 350，根据树中的结点数=树中B【解析】设度为1的结点数为n 不存在这样的二叉树4+21+1n+010+1=27，则D)所有结点的度之和+1，得3的结点0n。 ，根据在二叉树中度为D【解析】设叶子结点数为n=12的结点数的结点多一个，则度为60.设一棵度为3的树，其中度为2，1，0的结点数分别为3，2（叶子结点）总比度为2。由于结点数只能为整数，得n=350.5为n-1,n+n-

39、1+30=7301，6。该树中度为3的结点数为 所以不存在这样的二叉树。A)1 个为叶子结点，则个结点，其中 20067.某二叉树中共有350B)2 C)3的结点数为 该二叉树中度为 2 A)不可能有这样的二叉树D)不可能有这样的树 B)1503的结点数为A【解析】设树的结点数为n，则度为 ，=树中所有结点的度之和+1C)199n-3-1-6=n-10，根据树中的结点数 3D)1496+1=n，解得n=11，则度为）+23+11+0（得3n-10的结点，根据在二叉树中度为0A【解析】叶子结点数为的结点数为n-10=11-10=1。 200的结点数的结点多一个，则度为的结点，且叶子结点2（叶子结

40、点）总比度为261.设一棵树的度为3，其中没有度为2 数为5。该树中度为3的结点数为 199+200350，故不存在这样的二叉树。为199，个叶子结点，则该二叉树 A) 3，其中有6468.某二叉树的深度为7 的结点数为B)1 中度为1 A)0C) 2 B)1D)不可能有这样的树 C)23的结点数为n，则度为C【解析】设树的结点数为m，度为 树中所有结点的度D)631的结点数为m-n-5, 根据树中的结点数=的结点）+50【解析】叶子结点有64个，根据在二叉树中度为A0+1=m，则n=2。 ，得之和+13n+1（m-n-5的结点数2的结点个数（叶子结点）总比度为2的结点多一个，则度为362.度

41、为的一棵树共有30个结点，其中度为3,1m个结点，则该二的二叉树最多有2-1为。则该树中的叶子结点数为分别为3,4 63个；又深度为m7因此该树不存在度，A) 14 -1=127个结点。叉树最多有264+63=127 B) 15 的结点。为1个结点，则下列说法中错误的1277C) 16 的二叉树共有69.深度为 D)不可能有这样的树 是 的结点数为2该二叉树是满二叉树A)B【解析】设叶子结点数为n，则度为 30-3-4-n=23-n，根据树中的结点数=的结点该二叉树有一个度为树中所有结点的度之和1B) 该二叉树是完全二叉树C)。）+1，得33+2（23-n+14+0n+1=30，则n=15 个

42、叶子结点该二叉树有64363.设某棵树的度为，其中度为2,1,0的结点个数分别为D)m个结2-13,4,15。则该树中总结点数为 B【解析】满二叉树满足深度为m的二叉树最多有7，-1=127且有127个结点，满足不可能有这样的树A) 2点，本题中二叉树深度为7达到最大值，故此二叉树为满二叉树，也是完全二叉树。满B)30 k-1结点，则该二叉树的叶子结点数为2二叉树第kC)22 层上有7-1 1的结点。D)35 =64个。满二叉树不存在度为2 nA【解析】设树的总结点数为，则度为的完全二叉树的结点数不可能是 70.深度为3的结点数为5 树中所有结点的度之和A)15=n-3-4-15=n-22，根

43、据树中的结点数 15+1=n，则B)16n=27.5，求4+03+1+2n-223+1，得（） C)17出的结点数不为整数，故不可能有这样的树存在。 则度为4584564.某二叉树共有个结点，其中叶子结点有个，D)18的二叉k 的结点数为1 【解析】设完全二叉树的结点数为n，根据深度为Ak-1k-1n再根据完全二叉树的定义可知，2 A)400树至多有2-1个结点，55-1k15n-1-1n2，2-1。 B)754本题中完全二叉树的深度为5，则2 15。 C)75631。因此，结点数不能为 25671.某完全二叉树共有个结点，则该完全二叉树的深度为不确定D) 45【解析】叶子结点有C个，根据在二

44、叉树中度为A)70的结点 的结点多一个，则度为（叶子结点）总比度为2的结点数2B)8 个。845-45-44=7561个，因此度为44为的结点数为C)9 个度为16的结点，个度为15某二叉树中有65.12则的结点，D)10个结点的完全二叉具有nC 该二叉树中总的结点数为 【解析】根据完全二叉树的性质：则个结点，。本题中完全二叉树共有 A)32256n+1树的深度为log2 log B)46256+1=8+1=9。深度为2个结点，则该完全二叉125 C)4872.深度为的完全二叉树中共有 D)49树中的叶子结点数为 CA)62的结点（叶子结点）总比度0【解析】根据在二叉树中度为 的结点多一个，得

45、度为2为个，故总16+1=17的结点数为0B)63 =17+15+16=48的结点数 个。C)64 个结点，其中度为730某二叉树共有66.个，则30的结点有1D)65 叶子结点个数为k-1点；在遍历左、右子树时，仍然先遍历左子树，然后遍历右个结点、且深度为层上有2mB【解析】在满二叉树的第km DGEBHFCA的满二叉树共有。的满二叉树有2子树，最后访问根结点。故本题的后序序列是-1个结点，则深度为66-16，中序序列为=32个结点。本题是深度为7设二叉树的前序序列为2ABDEGHCFIJ-1=63个结点，第6层上有277. 。则后序序列为 的完全二叉树，则前6层共有63个结点，第7层的结点

46、数为DBGEHACIFJ A)JIHGFEDCBA层上有32个结点，125-63=62个且全为叶子结点。由于第6 B)DGHEBIJFCA 层上有个结点，则第61个结点无左右子树（该第7层上有62 结点为叶子结点）。因此，该完全二叉树中共有叶子结点C)GHIJDEFBCA 个。 D)ABCDEFGHIJ62+1=63，由于前序遍【解析】二叉树的前序序列为73.在具有2n个结点的完全二叉树中，叶子结点个数为 ABDEGHCFIJB。再由历首先访问根结点，可以确定该二叉树的根结点是AA)n HE、G B)n+1、中序序列为DBGEHACIFJ，可以得到结点D、B位于根结点的右子J、F、C)n-1

47、位于根结点的左子树上，结点C、I树上。由于中序遍历和后序遍历都是先遍历左子树，故本题D)n/2 再由后序遍历是最后访问根结点，结点；的结点后序遍历首先访问D树中必定存在度为A【解析】由二叉树的定义可知，0。采用排除法可和度为2的结点，设度为0结点有A0的结点故本题后序遍历最后访问的结点是根结点a个，根据度为 的结点多一个，得度为2。知，后续序列为的结点DGHEBIJFCA（即叶子结点）总比度为2，后序遍历序列为0有a-1个。再根据完全二叉树的定义，度为1的结点有个或CBADE78.某二叉树的中序遍历序列为 ，由于CBEDA，则前序遍历序列为a+0+a-1=2n11个，假设度结点为0个，得2a=

48、2n-1 结点个数必须为整数，假设不成立；当度为1的结点为1A)CBADE个 a=n，得，即叶子结点个数为n。B)CBEDA时，a+1+a-1=2n C)ABCDE74.下列数据结构中为非线性结构的是 A)二叉链表 D)EDCBA，由于后序遍历CBEDAB)循环队列 C【解析】二叉树的后序遍历序列为。再由中A循环链表C) 最后访问根结点，可以确定该二叉树的根结点是）一定在左子CB D)双向链表CBADE，可以得到子序列（序遍历序列为在中序序二叉树是A【解析】二叉树的链式存储结构也称为二叉链表，BC、树中，子序列（DE）一定在右子树中。结点的父结点；CB树的一种，属于非线性结构。 是结点列和后序

49、序列中顺序未变，说明结点DE在中序序列和后序序列中顺序相反，说明结点D结点、下列叙述中正确的是75. 的父结点。因此该二叉树的前序遍历序列为是结点 A)非完全二叉树可以采用顺序存储结构E ABCDE。有两个指针域的链表就是二叉链表B) ，中序序列为某二叉树的前序序列为 C)有的二叉树也能用顺序存储结构表示ABCDEFG79. 1顺序存储结构一定是线性结构D) 层）为DCBAEFG，则该二叉树的深度（根结点在第 C【解析】在计算机中，二叉树通常采用链式存储结构，但对A)2 B)3于满二叉树和完全二叉树来说，可以按层进行顺序存储。因 C)4CA此项错误，项正确。虽然满二叉树和完全二叉树可以采 D项

50、错误。D)5用顺序存储结构，但仍是一种非线性结构，因此为根结点；双向链表也有两个指针域，因此，则A 项错误。C【解析】二叉树的前序序列为ABCDEFGB位于根结点的左B、C、中序序列为DCBAEFG 有二叉树如下图所示：76.，可知结点D 位于根结点的右子树上。另外，结点G、F、子树上，结点E在前序序列和中序序列中顺序相反，则说明这三个DC、B、顺序未GF、结点依次位于前一个结点的左子树上；结点E、变，则说明这三个结点依次位于前一个结点的右子树上。故 4。二叉树深度为，则该设二叉树的前序序列与中序序列均为ABCDEFGH80. 二叉树的后序序列为 A)ABCDHGFE B)DCBAHGFE C

51、)EFGHABCD D)HGFEDCBA，ABCDEFGHD【解析】二叉树的前序序列与中序序列均为 只有右子树，没有左子A可知二叉树根结点为A，且根结点 则前序序列为依此类推，只有右子树无左子树。同理，可以推出结点B树。 A)ABDEGCFH该二叉树除叶子结点外，每个结点只有右子树无左子树。因 B)DBGEAFHC HGFEDCBA。此该二叉树的后序序列为 C)DGEBHFCA某二叉树的后序遍历序列与中序遍历序列相同，均为81. D)ABCDEFGH ，则按层次输出（同一层从左到右）的序列为ABCDEF【解析】前序遍历首先访问根结点，然后遍历左子树，最后A A)CBAFED遍历右子树；在遍历左

52、、右子树时，仍然先访问根结点，然 B)FEDCBA 后遍历左子树，最后遍历右子树。故本题前序序列是 C)DEFCBA ABDEGCFH。 D)ABCDEF中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子【解析】该二叉树的后序遍历序列与中序遍历序列均为B树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟只有左子树，右子树为；根结点FF，则根结点为ABCDEF 结点，最后遍历右子树。故本题的中序序列是。DBGEAFHC的右子树集合。这样问题就转化F是根结点ABCDE空。即后序遍历首先遍历左子树，然后遍历右子树，最后访问根结 A)的子树，同前序序列为就后序遍历序列与中序遍历序列均为ABCDE

53、理可得左子树集合的根结点为E，且根结点只有左子树右子B)中序序列 后序序列C)树。依次类推，该二叉树除叶子结点外，每个结点只有左子 前序序列或后序序列 D)树无右子树，结构如下： 【解析】中序遍历的次序是先遍历左子树，再遍历根结点，B根结点最后遍历右子树。而在排序二叉树中，左子树结点值值右子树结点值，要使对排序二叉树的遍历结果为有序序 列，只能采用中序遍历。如果其中的结点值互不相同。设二叉树中共有15个结点，85. 该二叉树的前序序列与中序序列相同，则该二叉树的深度为 A)4 B)6 C)15 不存在这样的二叉树D) 如果各结点值互不相个结点的二叉树中，在具有nC【解析】 FEDCBA。按层次

54、输出（同一层从左到右）的序列为同，若该二叉树的前序序列与中序序列相同，则说明该二叉，中序序列为某二叉树的前序序列为82.ABDFHCEG若该二叉树；二叉树的深度为n树只有右子树，左子树为空，。该二叉树按层次输出（同一层从左到右）的序HFDBACEG的后序序列与中序序列相同，则说明该二叉树只有左子树， 列为。故本题中二叉树的深度为n右子树为空，二叉树的深度为 A)HGFEDCBA 。15 B)HFDBGECA的顺序表中查找一个元素，假设需要查找的元n86.在长度为 C)ABCDEFGH 素一定在表中，并且元素出现在表中每个位置上的可能性是 D)ACEGBDFH 相同的，则在平均情况下需要比较的次

55、数为，可以确定这个ABDFHCEGC【解析】二叉树的前序序列为 A)n/4可以得到；再由中序序列，HFDBACEG二叉树的根结点是A B)n同为根结点HFDBAA的右子树。为根结点的左子树，CEG C)3n/4进行同样的推理，得CEGHFDB和右子树理依次对左子树 D)(n+1)/2 到该二叉树的结构如下：【解析】在顺序表中查找，最好情况下第一个元素就是要D 最后一个元素；在最坏情况下，查找的元素，则比较次数为11+2+则平均比较次数：（才是要找的元素，则比较次数为n。 /n=(n(n+1)/2)/n=(n+1)/2。+n）的顺序表中查找一个元素，假设需要查找的元在长度为n87.则出现在表中素有一半的机会在表中，并且如果元素在表中,每个位置上的可能性是相同的。则在平均情况下需要比较的 次数大约为 A)n B)3n/4 C)n/2该二叉树按层次输出（同一层从左到右）的序列为 D)n/