计算机等级考试二级指导教程公共基础知识.docx

《计算机等级考试二级指导教程公共基础知识.docx》由会员分享，可在线阅读，更多相关《计算机等级考试二级指导教程公共基础知识.docx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国计算机等级考试指导教程二级公共根底学问编著 黄海军2021年9月目 录前言4二级考试中的公共根底学问的备考4历年公共根底学问考点统计及分析6第一章数据构造及算法7算法7数据构造的根本概念8线性表及其依次存储构造10栈和队列11线性链表13树及二叉树15查找技术19排序技术20第二章 程序设计根底22程序设计设计方法和风格22构造化程序设计面对过程的程序设计方法23面对对象的程序设计24第三章 软件工程根底273.1 软件工程根本概念273.2 构造化分析方法313.3 构造化设计方法323.4 软件测试363.5 程序的调试39第四章 数据库设计根底414.1 数据库系统的根本概念414.

2、2 数据模型45关系代数474.4 数据库设计及管理50计算机等级考试二级指导教程公共根底学问前言二级考试中的公共根底学问的备考从2005年初开场，教化部对全国计算机等级考试进展了较大调整。二级考试的笔试包括根底学问和程序设计两局部，其中根底学问占30分。这次改革的思想就是将根底学问的内容由计算机常识一级难度调整为程序开发根底三级难度，假如这局部学问内容没有驾驭好，难以在等级考试中取得好成果。因此，必需引起我们足够的重视，这局部因涉及四门课程学问，要求面广。事实上只要驾驭了确定的备考技巧过关也不难的。大纲的二级根底学问分为数据构造及算法, 程序设计根底, 软件工根底, 数据库设计根底四局部，下

3、面分别说一下学习重点和方法：1 数据构造及算法本章的学问用于提高程序的效率以及对较困难的问题进展求解。本章内容在计算机专业根底课中也属于比拟难的一门，学习本章的内容必需进展理解，死记硬背是无效的。对于等级考试，本章重点的考核点主要在二叉树，同时这也是本章的难点，考核形式主要为二叉树的遍历问题如给图求遍历序列, 给前序, 中序遍历求后序遍历等, 二叉树的结点问题如给出一些条件然后求叶子结点个数；还有排序和查找考试中也常常会涉及到，排序主要以计算时间困难度的形式考核，查找主要以计算最正确/最坏比拟次数的方式考核。其余的学问点主要以概念的形式考察，考生须要细致看书并理解。2 程序设计根底及软件工程根

4、底这两章以概述的形式简介了标准化开发软件的方法。及数据构造不同，这两章内容主要是记忆性的学问点。程序设计根底的内容及大纲改革前添加了面对对象程序设计的内容，考生可以对本章进展几次细读后了解即可；软件工程根底这章主要考核内容为构造化分析及构造化设计方法即SA及SD，约占50%，信息量较大，其次是软件测试约占20%，考生须要将相关的概念及规那么背诵，在以后有时机进展程序开发时这些学问可以得到深刻理解。3 数据库设计根底数据库是当前软件处理的信息核心，目前大局部软件都是基于数据库的，因此学习一下数据库学问对程序开发也是很有扶植的。本章主要的考核点是关系模型, 关系代数及数据库系统的根本概念，其余的学

5、问点了解即可，其中数据库的设计和管理可以结合着软件工程来看，考生会发觉这两者有许多相像之处。除了关系代数会考一些简洁的计算问题外，其余的都是以概念题的形式考核，考生须要细致的阅读。以上为复习二级公共根底的方法，顺便提及一点考生在选购教材的时候应当特殊留意，应当购置最近版的二级公共根底学问教程指定教材由高等教化出版社出版，还有考生在备考时，除了应完成教材中的习题外还应当做一下近几年的真题，并且用其估计一下自己的学问欠缺以便更好的进展查漏补缺。 历年公共根底学问考点统计及分析章节学问点2021下2021上2021下2021上2021下2021上2021下2021上2021下2021上2007下20

6、07上2006下2006上2005下2005上数据构造及算法算法220020420+22+2数据构造的根本概念0200040002+22线性表及依次存储0002+20000000栈和队列4442+20200+4242线性链表00000000202树及二叉树20+2220+22+24+2204+20+2查找技术20020002002排序技术002022000+220程序设计根底程序设计方法及风格00000004000构造化程序设计020+202000200面对对象程序设计0002020+200+200+2软件工程根底软件工程根本概念4+22+222+2602404+22构造化分析方法20+202

7、00+400000构造化设计方法02202022022软件测试00+22+20+20+20+22+200+202程序调试20000200+2220+2数据库设计根底数据库的根本概念22+20+220+422+24+22+22+22数据模型2+222+22+222+2204+202+2关系代数22202022020数据库设计及管理2020+20+2002020第一章数据构造及算法1, 算法：是指解题方案的精确而完整的描述。v 算法不等于程序，也不等于计算机方法，程序的编制不行能优于算法的设计。2, 算法的根本特征1可行性；针对实际问题而设计的算法，执行后能够得到满足的结果。2确定性，算法中每一步

8、骤都必需有明确定义，不允许有模棱两可的说明，不允许有多义性；3有穷性，算法必需能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；4拥有足够的情报。v 综上所述，所谓算法就是一组严谨地定义运算依次的规那么，每一个规那么都是有效的，是明确的，此依次将在有限的次数下终止。3, 算法困难度主要包括算法时间困难度和算法空间困难度。1算法时间困难度是指执行算法所须要的计算工作量。可以用执行算法的过程中所需根本运算的执行次数来度量。2算法空间困难度是指执行这个算法所须要的内存空间。【真题练习】2021年9月以下表达中正确的选项是( )。2021年3月算法的时间困难度是指( )。A算

9、法的执行时间 B算法所处理的数据量C算法程序中的语句或指令条数 D算法在执行过程中所须要的根本运算次数2021年9月算法的空间困难度是指( )。A算法在执行过程中所须要的计算机存储空间 B算法所处理的数据量C算法程序中的语句或指令条数 D算法在执行过程中所须要的临时工作单元数2007年4月以下表达中正确的选项是 。A算法的效率只及问题的规模有关，而及数据的存储构造无关B算法的时间困难度是指执行算法所须要的计算工作量C数据的逻辑构造及存储构造是一一对应的D算法的时间困难度及空间困难度确定相关2021年3月算法的有穷性是指( )。 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C

10、算法程序的长度是有限的 D算法只能被有限的用户运用2007年4月在算法中，对须要执行的每一步操作，必需给出清晰, 严格的规定。这属于算法的 。A正值性 B可行性 C确定性 D有穷性2006年9月以下表达中正确的选项是 。A一个算法的空间困难度大，那么其时间困难度也必定大B一个算法的空间困难度大，那么其时间困难度必定小C一个算法的时间困难度大，那么其空间困难度必定小D上述三种说法都不对2005年9月算法困难度主要包括时间困难度和【2】困难度。2005年4月算法具有5 个特性，以下选项中不属于算法特性的是 。A有穷性 B简洁性 C可行性 D确定性2005年4月问题处理方案正确而完整的描述称为【5】

11、。1, 数据构造是指相互有关联的数据元素的集合。2, 数据构造探讨的三个方面：数据的逻辑构造, 存储构造, 运算。1数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑构造；数据的逻辑构造包含：1表示数据元素的信息；2表示各数据元素之间的前后件关系。2在对数据进展处理时，各数据元素在计算机中的存储关系，即数据的存储构造；数据的存储构造有依次, 链接, 索引等。1依次存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来表达。由此得到的存储表示称为依次存储构造。2链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表

12、示的。由此得到的存储表示称为链式存储构造。3索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。3对各种数据构造进展的运算。v 数据的逻辑构造反映数据元素之间的逻辑关系，数据的存储构造也称数据的物理构造是数据的逻辑构造在计算机存储空间中的存放形式。同一种逻辑构造的数据可以采纳不同的存储构造，但影响数据处理效率。3, 数据构造的图形表示一个数据构造除了用二元关系表示外，还可以直观地用图形表示。在数据构造的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用

13、一条有向线段从前件结点指向后件结点。4, 数据构造分为两大类型：线性构造和非线性构造。1线性构造非空的数据构造条件：1有且只有一个根结点；2每一个结点最多有一个前件，也最多有一个后件。 v 常见的线性构造有线性表, 栈, 队列和线性链表等。2非线性构造：不满足线性构造条件的数据构造。v 常见的非线性构造有树, 二叉树和图等。【真题练习】(2021年9月)数据构造分为线性构造及非线性构造，带链的栈属于 【1】 (2021年9月)以下数据构造中，属于非线性构造的是 。A循环队列 B) 带链队列 C) 二叉树 D带链栈(2007年9月)以下表达中正确的选项是 。A程序执行的效率及数据的存储构造亲密相

14、关B程序执行的效率只取决于程序的限制构造C程序执行的效率只取决于所处理的数据量D以上三种说法都不对(2007年9月)以下表达中正确的选项是 。A数据的逻辑构造及存储构造必定是一一对应的B由于计算机存储空间是向量式的存储构造，因此，数据的存储构造确定是线性构造C程序设计语言中的数组一般是依次存储构造，因此，利用数组只能处理线线构造D以上三种说法都不对2005年9月以下表达中正确的选项是 。A一个逻辑数据构造只能有一种存储构造B数据的逻辑构造属于线性构造，存储构造属于非线性构造C一个逻辑数据构造可以有多种存储构造，且各种存储构造不影响数据处理的效率D一个逻辑数据构造可以有多种存储构造，且各种存储构

15、造影响数据处理的效率2005年9月数据构造分为逻辑构造和存储构造，循环队列属于【5】构造。2005年4月数据的存储构造是指 。A存储在外存中的数据 B数据所占的存储空间量C数据在计算机中的依次存储方式 D数据的逻辑构造在计算机中的表示1, 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n0)个数据元素组成的一个有限序列。在困难线性表中，由假设干数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的构造特征：1且只有一个根结点a ，它无前件；2有且只有一个终端点a ，它无后件；3除根结点及终端结点外，其他全部结点有

16、且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。2, 线性表的依次储构造具有以下两个根本特点：1线性表中全部元素的所占的存储空间是连续的；2线性表中各数元素在存储空间中是按逻辑依次依次存放的。a 的存储地址为：ADRa =ADR(a )+i-1k，ADRa 为第一个元素的地址，k代表每个元素占的字节数。v 由此可以看出，在线性表的依次存储构造中，其前后件两个元素在存储空间中是紧邻的，且前件元素确定存储在后件元素的前面，可以通过计算机干脆确定第i个结点的存储地址。3, 依次表的运算：插入, 删除。1依次表的插入运算：在一般状况下，要在第i1in个元素之前插入

17、一个新元素时，首先要从最终一个即第n个元素开场，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动完毕后，第i个位置就被空出，然后将新元素插入到第i项。插入完毕后，线性表的长度就增加了1。v 顺性表的插入运算时须要移动元素，在等概率状况下，平均须要移动n/2个元素。2依次表的删除运算：在一般状况下，要删除第i1in个元素时，那么要从第i+1个元素开场，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除完毕后，线性表的长度就减小了1。v 进展顺性表的删除运算时也须要移动元素，在等概率状况下，平均须要移动n-1/2个元素。插入, 删除运算不便利。【真题练习】2021年3月将长度

18、为n的依次存储在线性表中删除一个元素，最坏状况下须要移动表中的元素个数为 。2021年9月在长度为n的依次存储的线性表中插入一个元素，最坏状况下须要移动表中 【2】 .2021年9月以下表达中正确的选项是 。A依次存储构造的存储确定是连续的，链式存储构造的存储空间不确定是连续的B依次存储构造只针对线性构造，链式存储构造只针对非线性构造C依次存储构造能存储有序表，链式存储构造不能存储有序表D链式存储构造比依次存储构造节约存储空间2021年9月线性表的存储构造主要分为依次存储构造和链式存储构造.队列是一种特殊的线性表,循环队列是队列的3存储构造1, 栈及其根本运算1栈是限定在一端进展插入及删除的线

19、性表，允许插入及删除的一端称为栈顶，不允许插入及删除的另一端称为栈底。栈依据“先进后出FILO或“后进先出LIFO组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。2栈的根本运算：1插入元素称为入栈运算；2删除元素称为退栈运算；3读栈顶元素是将栈顶元素给一个指定的变量，此时指针无变更。栈的存储方式和线性表类似，也有两种，即依次栈和链式栈。2, 队列及其根本运算(1)队列是指允许在一端队尾进入插入，而在另一端队头进展删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出FIFO或“后进后出LILO的线性表。(2)队列运算包括1入队运算：从队尾插入一个元

20、素；2退队运算：从队头删除一个元素。(3) 循环队列及其运算：所谓循环队列，就是将队列存储空间的最终一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环运用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间，全部的元素均为队列中的元素。v 循环队列是队列的链式存储构造，循环队列中元素的个数=rear-front。【真题练习】2021年3月以下表达中正确的选项是：A, 循环队列是队列的一种依次存储构造 B, 循环队列是队列的一种链式存储构造C, 循环队列是非线性构造

21、D, 循环队列是始终逻辑构造2021年3月以下表达中正确的选项是A, 栈是一种先进先出的线性表 B, 队列是一种后进先出的线性表C, 栈和队列都是非线性构造 D, 以上三种说法都不对2021年3月设循环队列的存储空间为Q(1:3),初始状态为front=rear=30。现经过一系列入队及退队运算后，front=16，rear=15，那么循环队列中有 个元素。2021年3月一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，那么元素退队的依次为【】。2021年3月设某循环队列的容量为50，假如头指针front45指向队头元素的前一位置，尾指针rea

22、r10指向队尾元素，那么该循环队列中共有【】个元素。2021年9月以下数据结果中，能够依据“先进后出原那么存取数据的是 。A) 循环队列 B) 栈 C)队列 D)二叉树2021年9月对于循环队列，以下表达中正确的选项是 。A队头指针是固定不变的 B队头指针确定大于队尾指针C队头指针确定小于队尾指针 D队头指针可以大于队尾指针，也可以小于队尾指针2021年3月以下表达中正确的选项是 。A栈是“先进先出的线性表 B队列是“先进先出的线性表C循环队列是非线性构造D有序性表既可以采纳依次存储构造，也可以采纳链式存储构造2021年3月支持子程序调用的数据构造是 。A栈 B树 C队列 D二叉树2021年3

23、月假设一个长度为50的数组数组元素的下标从0到49作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，假如bottom=49，top=30数组下标，那么栈中具有【1】个元素。2021年9月一个栈的初始状态为空。现将元素1, 2, 3, 4, 5, A, B, C, D, E 依次入栈，然后再依次出栈，那么元素出栈的依次是 。A12345ABCDE BEDCBA54321 CABCDE12345 D54321EDCBA2021年9月以下表达中正确的选项是 。A循环队列有队头和队尾两个指针，因此，循环队列是非线性构造B在循环队列中，只须要队头指针就能反映队列中元素的动态

24、变更状况C在循环队列中，只须要队尾指针就能反映队列中元素的动态变更状况D循环队列中元素的个数是由队头指针和队尾指针共同确定2021年3月以下关于栈的表达正确的选项是 。 A栈按“先进先出组织数据 B)栈按“先进后出组织数据 C只能在栈底插入数据 D不能删除数据2021年3月设某循环队列的容量为50，头指针front=5指向队头元素的前一位置，尾指针rear=29指向队尾元素，那么该循环队列中共有【3】个元素。2007年4月以下对队列的表达正确的选项是 。A队列属于非线性表 B队列按“先进后出原那么组织数据C队列在队尾删除数据 D队列按“先进先出原那么组织数据2006年9月按“后进后出原那么组织

25、数据的数据构造是 4。2006年9月数据构造分为线性构造和非线性构造，带链的队列属于 5 。2006年4月依据“后进先出原那么组织数据的数据构造是 。A队列 B栈 C双向链表 D二叉树2005年9月以下数据构造中，能用二分法进展查找的是 。A依次存储的有序线性表 B线性链表 C二叉链表 D有序线性链表2005年9月以下关于栈的描述正确的选项是 。A在栈中只能插入元素而不能删除元素 B在栈中只能删除元素而不能插入元素C栈是特殊的线性表，只能在一端插入或删除元素D栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2005年4月以下关于栈的描述中错误的选项是 。A栈是先进后出的线性表 B栈只能

26、依次存储 C栈具有记忆作用D对栈的插入及删除操作中，不须要变更栈底指针1, 线性表依次存储的缺点：1插入或删除的运算效率很低。在依次存储的线性表中，插入或删除数据元素时须要移动大量的数据元素；2线性表的依次存储构造下，线性表的存储空间不便于扩大；3线性表的依次存储构造不便于对存储空间的动态安排。2, 线性链表：线性表的链式存储构造称为线性链表，是一种物理存储单元上非连续, 非依次的存储构造，数据元素的逻辑依次是通过链表中的指针链接来实现的。数据构造中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两局部组成：1用于存储据元素值，称为数据域；2用于存放指针，称为指针域，

27、用于指向前一个或后一个结点。在链式存储构造中，存储数据构造的存储空间可以不连续，各数据结点的存储依次及数据元素之间的逻辑关系可以不一样，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性构造，也可用于表示非线性构造。线性链表分为单链表, 双向链表和循环链表三种类型。在单链表中，每一个结点只有一个指针域，由这个指针只能找到其后件结点，而不能找到其前件结点。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针，指向其前件结点；另一个称为右指针，指向其后件结点，这种链表称为双向链表。线性链表，HEAD称为头指针，HEAD=NULL或0称为空表，假如是两指针：

28、左指针Llink指向前件结点，右指针Rlink指向后件结点。3, 线性链表的根本运算：查找, 插入, 删除。1在线性链表中包含指定元素的结点之前插入一个新元素。v 在线性链表中插入元素时，不须要移动数据元素，只须要修改相关结点指针即可，也不会出现“上溢现象。2在线性链表中删除包含指定元素的结点。v 在线性链表中删除元素时，也不须要移动数据元素，只须要修改相关结点指针即可。3将两个线性链表按要求合并成一个线性链表。4将一个线性链表按要求进展分解。5逆转线性链表。6复制线性链表。7线性链表的排序。8线性链表的查找。v 线性链表不能随机存取。4, 循环链表及其根本运算：在线性链表中，其插入及删除的运

29、算虽然比拟便利，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必需单独考虑，使空表及非空表的运算不统一。为了克制线性链表的这个缺点，可以采纳另一种链接方式，即循环链表。及前面所探讨的线性链表相比，循环链表具有以下两个特点：1在链表中增加了一个表头结点，其数据域为随意或者依据须要来设置，指针域指向线性表的第一个元素的结点，而循环链表的头指针指向表头结点；2循环链表中最终一个结点的指针域不是空，而是指向表头结点。即在循环链表中，全部结点的指针构成了一个环状链。循环链表的优点主要表达在两个方面：一是在循环链表中，只要指出表中任何一个结点的位置，就可以从它动身访问到表中其他全部的结点，而线

30、性单链表做不到这一点；二是由于在循环链表中设置了一个表头结点，在任何状况下，循环链表中至少有一个结点存在，从而使空表及非空表的运算统一。v 循环链表是在单链表的根底上增加了一个表头结点，其插入和删除运算及单链表一样。但它可以从任一结点动身来访问表中其他全部结点，并实现空表及非空表的运算的统一。【真题练习】2021年9月以下关于线性链表的表达中，正确的选项是 。A各数据结点的存储空间可以不连续，但它们的存储依次及逻辑依次必需一样B各数据结点的存储依次及逻辑依次可以不一样，但它们的存储空间必需连续C进展插入及删除时，不须要移动表中的元素D以上三种说法都不对2006年4月以下表达中正确的选项是 。A

31、线性链表是线性表的链式存储构造 B栈及队列是非线性构造C双向链表是非线性构造 D只有根结点的二叉树是线性构造2005年4月以下对于线性链表的描述中正确的选项是 。A存储空间不确定是连续，且各元素的存储依次是随意的B存储空间不确定是连续，且前件元素确定存储在后件元素的前面C存储空间必需连续，且前件元素确定存储在后件元素的前面D存储空间必需连续，且各元素的存储依次是随意的1, 树的根本概念树是一种简洁的非线性构造，全部元素之间具有明显的层次特性。在树构造中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件

32、的结点称为叶子结点。在树构造中，一个结点所拥有的后件的个数称为该结点的度，全部结点中最大的度称为树的度。树的最大层次称为树的深度。(二叉树的层数)2, 二叉树及其根本性质1什么是二叉树二叉树是一种很有用的非线性构造，它具有以下两个特点：1非空二叉树只有一个根结点；2每一个结点最多有两棵子树，且分别称为该结点的左子树及右子树。v 依据二叉树的概念可知，二叉树的度可以为0叶结点, 1只有一棵子树或2有2棵子树。2二叉树的根本性质：性质1 在二叉树的第k层上，最多有2k-1个结点；性质2 深度为m的二叉树最多有2 m-1个结点；性质3 度为0的结点即叶子结点总是比度为2的结点多一个；性质4 具有n个

33、结点的二叉树，其深度至少为log2 n+1，其中log2 n表示取log2 n的整数局部；3, 满二叉树及完全二叉树满二叉树是指除最终一层外，每一层上的全部结点有两个子结点，那么k层上有2k-1 个结点，深度为m的满二叉树有2m -1个结点。v 依据完全二叉树的定义可得出：度为1的结点的个数为0或1。完全二叉树是指除最终一层外，每一层上的结点数均到达最大值，在最终一层上只缺少右边的假设干结点。性质5 具有n个结点的完全二叉树的深度为log2 n+1；性质6 设完全二叉树共有n个结点。假如从根结点开场，按层序每一层从左到右用自然数1，2，n给结点进展编号k=1,2n，有以下结论：假设k=1,那么

34、结点为根结点，它没有父结点；假设k1,那么该结点的父结点编号为INTk/2；假设2k n,那么编号为k的结点左子编号为2k；否那么该结点无左子结点也无右子结点；假设2k+1 n,那么编号为k的结点的右子结点编号为2k+1；否那么该结点无右子结点。4, 二叉树的存储构造在计算机中，二叉树通常采纳链式存储构造。及线性链表类似，用于存储二叉树中各元素的存储结点也由两局部组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件即两个子结点，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。

35、v 二叉树存储构造采纳链式存储构造，对于满二叉树及完全二叉树可以按层序进展依次存储。5, 二叉树的遍历：指不重复地访问二叉树中的全部结点。1前序遍历DLR，首先访问根结点，然后遍历左子树，最终遍历右子树；2中序遍历LDR，首先遍历左子树，然后访问根结点，最终遍历右子树；3后序遍历LRD，首先遍历左子树，然后访问遍历右子树，最终访问根结点。【真题练习】2021年3月一棵二叉树共有25个节点，其中5个时子节点，那么度为1的节点数为 。A, 4 B, 6 C, 10 D, 162021年9月以下关于二叉树的表达中，正确的选项是 。 2021年9月某系统总体构造图如以下图所示：该系统总体构造图的深度是

36、 2021年9月在深度为7 的满二叉树中，度为2 的结点个数为【1】。2021年3月设二叉树如下：AB C D F E G H 对该二叉树进展后序遍历的结果为【】。2021年3月某二叉树有5个度为2的结点，那么该二叉树中的叶子结点数是 。A10 B8 C6 D42021年9月对以下二叉树进展中序遍历的结果 【1】 。ABCDEFXYZY2021年4月深度为5的满二叉树有【2】个叶子结点。2007年9月一棵二叉树中共有70个叶子结点及80个度为1的结点，那么该二叉树中的总结点数为 。A219 B221 C229 D2312007年9月对以下二叉树进展中序遍历的结果为4。FCEADBGHP2007

37、年4月以下二叉树进展前序遍历的结果为 。ABCDEFYXZADYBEAFCZX BYDEBFZXCA CABDYECFXZ DABCDEFXYZ2007年4月某二叉树中有n 个度为2 的结点，那么该二叉树中的叶子结点数为 。An+1 Bn-1 C2n Dn/22007年4月在深度为7 的满二叉树中，度为2 的结点个数为【1】。2006年9月对以下二叉树：ABDECF, G 进展中序遍历的结果是_。AACBDFEG BACBDFGE CABDCGEF DFCADBEG2005年9月对如下二叉树FEDBCA进展后序遍历的结果为 。AABCDEF BDBEAFC CABDECF DDEBFCA200

38、5年9月在深度为7 的满二叉树中，叶子结点的个数为 。A32 B31 C64 D632005年9月一棵二叉树第六层根结点为第一层的结点数最多为【4】个。2005年4月某二叉树中度为2 的结点有18 个，那么该二叉树中有【1】个叶子结点。查找：依据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：查找胜利：找到；查找不胜利：没找到。平均查找长度：查找过程中关键字和给定值比拟的平均次数。1, 依次查找根本思想：从表中的第一个元素开场，将给定的值及表中逐个元素的关键字进展比拟，直到两者相符，查到所要找的元素为止。否那么就是表中没有要找的元素，查找不胜利。在平均状况下，利用依次查

39、找法在线性表中查找一个元素，大约要及线性表中一半的元素进展比拟，最坏状况下须要比拟n次。依次查找一个具有n个元素的线性表，其平均困难度为On。以下两种状况下只能采纳依次查找：1假如线性表是无序表即表中的元素是无序的，那么不管是依次存储构造还是链式存储构造，都只能用依次查找。2即使是有序线性表，假如采纳链式存储构造，也只能用依次查找。2, 二分法查找思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必需在具有依次存储构造的有序表中进展。查找过程：1假设中间项的值等于x，那么说明已查到；2假设x小于中间项的值，那么在线性表的前半局部查找；3假设x大于中间项的

40、值，那么在线性表的后半局部查找。特点：比依次查找方法效率高。最坏的状况下，须要比拟log2n次。v 二分法查找只适用于依次存储的线性表，且表中元素必需按关键字有序升序，但允许相邻元素值相等排列。对于无序线性表和线性表的链式存储构造只能用依次查找。在长度为n的有序线性表中进展二分法查找，其时间困难度为Olog2n。【真题练习】2021年3月以下表达中正确的选项是_。A对长度为的有序链表进展查找，最坏状况下须要的比拟次数为B对长度为的有序链表进展对分查找，最坏状况下须要的比拟次数为n/2C对长度为的有序链表进展对分查找，最坏状况下须要的比拟次数为log2nD对长度为的有序链表进展对分查找，最坏状况下须要的比拟次数为log2n2021年9月在长度为n 的有序线性表中进展二分查找，最坏状况下须要比拟的次数是 。AO(n) BO(n2) CO(log2n) DO(nlog2n) 2006年9月在长为64 的有序线性表中进展依次查找，最坏状况下须要比拟的次数为_。A63 B64 C6 D72005年4月对于长度为n 的线性表进展依次查找，在最坏状况下所须要的比拟次数为 。Alog2n Bn/2 Cn Dn+1排序是指将一个无序序列整理成按值的有序表，对于长度为n的有序线性表，最坏状况只需比拟n次。交换类排序法：1冒泡排序法，须要比拟的次数为n(n-1)/2；2快速排序