计算机二级公共基础部分

1、 第八章 公共基础本章内容在考试中占10分，主要包括数据结构与算法、程序设计基础、软件工程和数据库设计基础四部分内容，考试范围虽然比较广，但每部分并不需要考生掌握特别专业的知识，只需要了解基本知识即可，考生可通过历年真题的练习辅助本章内容的学习。8.1 数据结构与算法本节需要考生主要掌握以下内容：1、算法和算法复杂度的基本概念。2、数据结构的基本概念。3、线性表的逻辑结构和顺序存储结构。4、线性表的链式存储结构5、栈和队列的逻辑结构、存储结构和基本运算。6、二叉树的定义、存储结构和遍历操作。7、常用查找和排序算法。8.1.1算法1、算法基本概念算法是指解题方案的准确而完整的描述。程序依据算法编

2、制，但算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法的基本特征包括：（1）可行性；算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即算法的每一步都必须是可行的。（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；（4）拥有足够的情报。算法的基本要素有两个，一是对数据对象的运算和操作；二是算法的控制结构。其中基本运算和操作包括算术运算、逻辑运算、关系运算和

3、数据传输，算法的控制结构包括顺序、选择和循环3种结构。2、算法的时间复杂度和空间复杂度衡量算法优劣的标准是算法的复杂度。算法复杂度分为时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)。一般用算法的最坏情况复杂度作为算法的时间复杂度。最坏情况复杂性是指在规模为n时，算法所执行的基本运算的最大次数，用大写字母O表示。例：O（n2）。同等规模下，时间复杂度越低，算法效率越高。常见的时间复杂度，按数量级比较排列关系为：算法空间复杂度是指执行这个算法所需要的内存空间。

4、一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。8.1.2数据结构1、数据结构数据结构是研究数据逻辑结构、存储结构以及相关运算的一门学科，主要包括三个方面内容：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。数据结构中讨论以上问题的主要目的是为了提高数据的处理效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。数据结构是指相互有关联的数据元素的集合，是反映数据

5、元素之间关系的数据元素集合的表示，包括逻辑结构和存储结构。2、数据的逻辑结构数据的逻辑结构包含表示数据元素的信息以及各数据元素之间的前后件关系。根据各数据元素之间前后件关系的复杂程度，一般将数据逻辑结构分为：线性结构和非线性结构。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。不满足线性结构条件的数据结构均称为非线性结构。线性表、栈和队列都是常见的线性结构，而树和二叉树则属于非线性结构。3、数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。数据的存储结构有顺序、链接、索引等。一个数据结构中的各数据元素在计

6、算机存储空间中的位置关系与逻辑关系有可能不同。不管是线性结构，还是非线性结构数据，采用哪种存储结构比较好，要根据数据参与的运算具体情况具体分析。8.1.3线性表及其顺序存储结构线性表是具有n个数据元素的有限序列，由一组数据元素构成，其中数据元素的位置取决于其序号，元素之间的相对位置是线性的。如：一个N维向量、矩阵。1、线性表的结构特征一个非空线性表：a1，a2，an，具有以下特征：（1）有且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表

7、的基本运算包括查找、插入和删除元素等操作。2、线性表的顺序存储结构顺序存储结构通过元素的相对存储地址来表示元素之间的逻辑关系。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表中逻辑上相邻的元素的物理位置必定紧邻，所以根据线性表的第一个元素地址，就可以直接计算出任意一个元素的存储地址，ai的存储地址ADR(ai)计算公式为：ADR(ai)=ADR(a1)+(i-1)k其中ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。由于可以随机定位，所以线性表顺序存储是一种随机存取的存储结构

8、。3、线性表的顺序存储结构优缺点线性表的顺序存储结构的优点是可随机存取元素，适合频繁访问元素的情况。线性表的顺序存储结构的缺点：（1）在插入和删除时，需移动大量元素；在线性表中插入或删除一个元素时，需要平均移动表的一半元素，需要移动的元素个数与该元素的位置有关。在长度为n的顺序表中插入一个元素的时间复杂度为O(n)，删除一个元素的时间复杂度为O(n)。（2）元素个数不确定时，必须预先分配较大的空间；（3）一旦定义，表的容量难以扩充。所以，线性表的顺序存储结构不适合对线性表频繁执行插入和删除元素的情况。8.1.4线性表的链式存储结构线性链表1、线性链表如果需要对线性表元素频繁执行插入和删除操作，

9、此时应采用线性表的链式存储结构。线性表的链式存储结构称为线性链表，是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素，因此，链表中结点的逻辑次序和物理次序不一定相同，如下图8.1所示。head a b c d 图8.1上图中，head称为头指针，head=NULL（或0）时，该链表称为空表。2、链表结点在链式存储结构中，数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点，为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息，这个信息称为指针(pointer)或链(link)。这

10、两部分组成了链表中的结点结构，如下图8.2所示。data link图8.2可以看出，结点由两部分组成，其中数据域data用于存储数据元素值，指针域link一般用于存放结点直接后继的地址，用于指向后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系由指针域确定。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。3、链式存储结构特点链式存储结构的特点主要有：（1）数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）链式存储结构只能顺序存取元素。在对链表操作时，只能通过头指针进入链表，并通过每个

11、结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。（3）链表中插入和删除元素不需移动其他元素，只需改变有关结点的指针，可有效提高插入和删除操作的效率。（4）链式存储结构不需提前分配空间，可以方便地扩充。4、循环链表(circular linked list)：循环链表是特殊的链表，链表中最后一个结点的指针指向头结点，使链表构成环状，其中只有一个头结点的循环链表为空表，如下图8.3所示。hh空表图8.3和一般链表相比，循环链表从表中任一结点出发均可找到表中其他结点，可提高查找效率。8.1.5栈1、栈的基本概念栈是

12、一种特殊的线性表，是限定在一端进行插入与删除的线性表，其中允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈用top表示栈顶位置，用bottom表示栈底，按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，具有记忆作用。2、栈的基本运算栈的基本运算包括入栈、退栈和读栈顶元素。（1）入栈运算在栈顶插入元素称为入栈运算。入栈时，首先执行top=top+1，然后将新元素插入到栈顶指针指向的位置。如果栈满，执行入栈操作会出现溢出错误，称为“上溢”。（2）退栈运算删除元素称为退栈运算或出栈运算。退栈时，首先将栈顶指针指向的元素赋给指定的变量，然后执行top=top-1操作。如

13、果栈空，执行退栈操作会出现溢出错误，称为“下溢”。（3）读栈顶元素读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。3、栈的存储结构栈可以采用顺序存储结构，也可以采用链式存储结构。（1）栈的顺序存储栈的顺序存储用一维数组S(1:m)作为栈的顺序存储空间，m为栈的最大容量。S(bottom)表示栈底元素，S(top)为栈顶元素。当top=0时表示栈空，top=m时表示栈满。（2）栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链

14、表来说，在首端插入删除结点要比尾端相对地容易一些，所以，一般将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。8.1.6 队列1、队列队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头，允许插入的一端称为队尾。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素，显然退出队列的次序只能是a1,a2,an ，即先进入队列的成员总是先离开队列，所以队列称作“先进先出”（FIFO，First In First Out）或“后进后出”（LILO，Last In Last Out）

15、的线性表。队列的基本运算包括入队和退队运算。从队尾插入一个元素称为入队，从队头删除一个元素称为退队。在队列中，一般用头指针front指向队头元素的前一个位置，用尾指针rear指向队尾元素，队头指针front和队尾指针rear共同决定了队列中元素的个数和变化情况，如图8.4所示。退队a1a2a3a4an入队frontrear图8.42、队列的存储结构队列的存储结构可以采用顺序存储，也可以采用链式存储结构。（1）队列的链式存储结构队列的链式存储结构称为链队列，由头指针和尾指针分别指向链表的头结点和尾结点。（2）队列的顺序存储结构队列的顺序存储结构与栈类似，可用一维数组QM作为队列的顺序存储空间，元

16、素下标从0到M-1，最多存储M个元素。队列的顺序存储结构存在问题：当front= -1，rear=M-1时，此时队列满，若再有元素入队则发生溢出，这种情况称为“真溢出”，但当front>-1，rear=M-1时，此时队列有空闲空间，但队尾指针已指向空间的最后一个元素，若再有元素入队也会发生溢出，这种情况称为“假溢出”。解决队列顺序存储结构中的假溢出问题，可采用循环队列。3、循环队列在实际应用中，队列的顺序存储结构一般采用循环队列形式。循环队列是队列是一种顺序存储结构，在循环队列结构中，当存储空间的最后一个位置已被使用而要进行入队运算时，只要存储空间的第一个位置空闲，就可将元素加入到第一个

17、位置，即把队列设想成环形，让Q0接在QM-1之后，入队时，若rear=M-1，则令rear=0。循环队列入队情况如下图8.5所示。图8.5从Front指针指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。循环队列入队和出队操作中指针值的位置可利用“取模”运算实现：入队：rear=(rear+1)%M; Qrear=x;出队：front=(front+1)%M; x=Qfront;由图8.5可知，循环队列中队列空和队列满的条件均为front=rear，为区别队列空和队列满两种情况，一般采用两种解决方案：（1）少用一个元素空间当front=rear时表示队列空，当(re

18、ar+1)%M=front表示队列满。（2）另外设一个标志S以区别队空、队满当S=0表示队列空，S=1且front=rear表示队列满。队列满时，如果再执行入队操作，将发生溢出，称为“上溢”。队列空时，如果再执行出队操作，将发生溢出，称为“下溢”。真题解析1、数据的存储结构是指_。A）存储在外存中的数据 B）数据所占的存储空间量C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示【答案】D【解析】数据的存储结构是数据的逻辑结构在计算机中的表示，根据数据的逻辑关系和运算特点可以采取顺序存储或链式存储的方式，所以选项D正确。2、下列关于栈的描述中错误的是_。A）栈是先进后出的线性表

19、 B）栈只能顺序存储C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针【答案】B【解析】栈是先进后出线性表，在栈顶执行插入和删除操作，不需要改变栈底指针，具有记忆作用，选项A、C和D正确；栈既可以顺序存储，也可以用链式存储，所以选项B错误。3、下列对于线性链表的描述中正确的是_。A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的【答案】A【解析】线性链表是线性表的链式存储结构，链式存储结构中元素的存储顺序与逻辑顺序

20、不一致，且存储空间不一定连续，所以选项A正确。4、下列叙述中正确的是_。A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】D【解析】数据逻辑结构按元素的前后件关系，可以分为线性和非线性结构，一种逻辑结构可以有多种存储结构，同样的逻辑结构，存储结构不同，数据的处理效率也不同，如线性表可以顺序存储，也可以链式存储，当频繁向线性表中插入或删除数据时，采用链式存储的处理效率更高，所以选项D正确。5、按照“后进

21、先出”原则组织数据的数据结构是_。A）队列 B）栈 C）双向链表 D）二叉树【答案】B【解析】队列是“先进先出”的数据结构，选项A错误；双向链表是存储结构，二叉树是非线性结构，不是按后进先出原则组织数据，选项C和D错误；栈是按后进先出原则组织数据的数据结构，所以选项B正确。6、下列叙述中正确的是_。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定【答案】D【解析】队列是线性结构，循环队列是队列的链式存储

22、结构，选项A错误；循环队列中队头指针指向队头元素的前一个位置，队尾指针指向队尾元素，两者共同决定队列中元素的个数和动态变化情况，所以选项B和C错误，只有选项D正确。7、设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有 个元素。A）15 B）35 C）45 D）10【答案】A 尾减头再加容量【解析】可以用公式进行计算：|rear-front+MAX| Mod MAX|10-45+50| Mod（取余树） 5015。8.1.7 树与二叉树1、树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中

23、，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。图8.6所示是一棵有9个结点的树，树的度为3，深度为4，根节点为A，结点D、H、I、F和G是叶子结点。DABCEFGIH图 8.62、二叉树度为2的树称为二叉树，图8.7所示为一棵二叉树。 A B C D G E H F I图8.7二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点

24、的左子树与右子树。3、二叉树的基本性质（1）在二叉树的第k层上，最多有2k-1(k1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个，可以用公式n0=n2+1表示，其中n0表示叶子结点（度为0），n2表示度为2的结点数；（4）具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分；最多4、满二叉树满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。图8.8所示就是一个满二叉树。ABCDEGFHIKJMLNO图8.8满二叉树第k层上有2k-1个结点，深度为m的满二叉树有2m-1个结点。5、完

25、全二叉树完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。图8.9所示就是一个完全二叉树。AC BEDFGHIJ1243576图8.9由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，但完全二叉树一般不是满二叉树。完全二叉树的性质：（1）具有n个结点的完全二叉树的深度为log2n+1；（2）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号（k=1,2.n），有以下结论： 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为Int(k/2)； 若2kn，则编号为k

26、的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）； 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。6、二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。1）顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素，即按照完全二叉树的每个结点编号的顺序存放结点内容。下图8.10是图8.9所示的完全二叉树顺序存储结构结点存放的顺序。12345678910ABCDEFGHIJ图8.102）链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关

27、系，对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下图8.11所示，其中Lchild和Rchild分别指向结点的左孩子和右孩子。Lchilddata Rchild图8.117、二叉树的遍历所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为：前序遍历、中序遍历和后序遍历。用D表示根，R表示右子树，L表示左子树（1）前序遍历（DLR）：首先访问根结点，然后遍历左子树，最后遍历右子树。（2）

28、中序遍历（LDR）：首先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历（LRD）：首先遍历左子树，然后访问遍历右子树，最后访问根结点。例： 设有如下图8.12所示的二叉树： A B C D G E H F I图8.12前序遍历（DLR）的结果为： A B D E H I C F G中序遍历（LDR）的结果为：D B H E I A F C G后序遍历（LRD）的结果为：D H I E B F G C A8.1.8 查找算法查找是数据处理领域中的一个重要内容，是指在一个给定的数据结构中查找某个指定的元素。常见的查找算法有顺序查找和二分查找。1、顺序查找顺序查找是一种最简单的查找方法。

29、其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。顺序查找主要适用以下两种情况：（1）线性表为无序表；（2）采用链式存储结构。2、二分法查找二分法查找只适用于顺序存储的有序表。当有序线性表采用顺序存储时才能采用二分查找，二分查找的效率比顺序查找高得多。对于长度为n的有序线性表，在最坏情况下，二分查找只需比较log2n次，而顺序查找需要比较n次。8.1.9 排序算法排序是

30、指将一个无序序列整理成按值非递减顺序排列的有序序列。排序算法有很多种，常见的有以下几种：1、交换类排序所谓交换类排序法是指借助数据元素之间的互相交换进行的排序的一种方法。主要的交换排序算法有冒泡排序和快速排序。（1）冒泡排序冒泡排序是一种最简单的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变成有序。将n个元素排好序，冒泡排序需要比较的次数为n(n-1)/2。（2）快速排序快速排序也是一种互换类排序方法，由于它比冒泡排序法的速度快，因此称之为快速排序法。将n个元素排好序，快速排序在最坏情况下需要比较的次数为n(n-1)/2。，除堆和希2、插入排序插入排序是将无序序列中的各元素依次插入到

31、已经有序的线性表中使之有序的过程。插入排序算法主要有简单插入排序和希尔排序。（1）简单插入排序简单插入排序法效率与冒泡排序相同，将n个元素排好序，简单插入排序在最坏情况下需要n(n-1)/2次比较。（2）希尔排序希尔排序对简单插入排序做了较大改进，基本思想是将整个无序序列分割成若干个小的子序列分别进行插入排序。将n个元素排好序，希尔排序法在最坏情况下需要O(n1.5)次比较。3、选择类排序选择类排序法主要包括简单选择排序法和堆排序法。（1）简单选择排序将n个元素排好序，简单选择排序法在最坏情况下需要n(n-1)/2次比较。（2）堆排序堆排序法不适合规模较小的线性表，但对于规模较大的线性表很有效

32、。将n个元素排好序，堆排序法在最坏情况下需要O(nlog2n)次比较。真题解析1、在深度为7的满二叉树中，叶子结点的个数为_。A）32 B）31 C）64 D）63【答案】C【解析】按照二叉树的基本性质，在第k层上，最多有2k-1(k1)个结点。满二叉树每一层拥有最多的结点，深度为7的满二叉树的叶子数为27-164，选项C正确。2、对图8.13所示的二叉树进行中序遍历的结果是_。FCEADGB图8.13A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG【答案】A【解析】中序遍历二叉树的顺序是：先遍历左子树，再访问根结点，最后遍历右子树，在左子树和右子树的遍历中仍遵循

33、中序遍历规则。该二叉树中F是根结点，先遍历其左子树（包含结点CADB），其中C是根结点，左结点A最先被访问，然后访问根结点C，接着遍历其右子树，右子树中先访问左结点B再访问根结点D，所以F的左子树遍历结果是ACBD，然后访问根结点F，再遍历其右子树（包含结点EG），E是根结点，没有左子树，右结点是G，所以右子树的遍历结果是EG，最后的结果是：ACBDFEG，选项A正确。3、对下图8.14所示的二叉树进行前序遍历的结果为_。 ABCDEFYXZ图8.14A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ 【答案】C【解析】前序遍历二叉树的顺序是：先访问

34、根结点，再遍历左子树，最后遍历右子树，在左子树和右子树的遍历中仍遵循前序遍历规则。该二叉树中A是根结点，先访问结点A，再遍历其左子树（包含结点BDEY），在左子树中先访问根结点B，再遍历B的左子树和右子树，可以看出A的左子树遍历结果是BDYE；A的右子树包含结点CFXZ，右子树的前序遍历结果是CFXZ，最后遍历结果是ABDYECFXZ，选项C正确。4、某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为_。A）n+1 B）n-1 C）2n D）n/2 【答案】A【解析】根据二叉树的性质，叶子结点数总比度为2的结点数多1个，选项A正确。5、一棵二叉树中共有70个叶子结点与80个度为1的结点，

35、则该二叉树中的总结点数为_。 A）219 B）221 C）229 D）231【答案】A。【解析】根据二叉树的性质，叶子结点数总比度为2的结点数多1，即n0=n2+1，而总的结点数N= n0n1n27080（701）219，选项A正确。同步练习1、冒泡排序在最坏情况下的比较次数是_。A）(n1)/2 B）nlog2n C）n(n1)/2 D）/22、下列关于栈的描述正确的是_。A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素3、下列叙述中正确的是_。A）线性链表是线性

36、表的链式存储结构 B）栈与队列是非线性结构C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构4、下列对队列的叙述正确的是_。A）队列属于非线性表 B）队列按“先进后出”原则组织数据 C）队列在队尾删除数据 D）队列按“先进先出”原则组织数据5、下列叙述中正确的是_。A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 D）以上三种说法都不对6、下列关于栈的叙述正确的是_。A）栈按“先进先出”组织数据 B）栈按“先进后出”组织数据 C）只能在栈

37、底插入数据 D）不能删除数据7、一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序为_。A）12345ABCDE B）EDCBA54321C）ABCDE12345 D）54321EDCBA 8、下列叙述中正确的是_。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间9、下列叙述正确的是_。A）线性表的链式存储与顺序存储所需的存储空间是相同的B）线性表的链式存

38、储结构所需的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需的存储空间一般要少于顺序存储结构D）上述三种说法都不对10、下列叙述正确的是_。A）在栈中，栈中元素随栈底指针与栈顶指针的变化而变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而变化D）上述三种说法都不对11、下列关于栈的叙述正确的是_。A）栈顶元素最先能被删除 B）栈顶元素最后才能被删除C）栈底元素永远不能被删除 D）以上三种说法都不对12、下列叙述正确的是_。A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链

39、表是非线性结构D）双向链表是非线性结构13、下列关于线性链表的叙述中，正确的是_。A）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续B）进行插入与删除时，不需要移动表中的元素C）各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致14、一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为_。A）4 B）6 C）16 D）1015、下列叙述中正确的是_。A）循环队列是非线性结构 B）循环队列是队列的一种链式存储结构C）循环队列是一种逻辑结构 D）循环队列是队列的一种顺序存储结构16、下列叙述中正确的是_。A）数据的逻辑结构与存储结构是一一对应的B）算

40、法的时间复杂度与空间复杂度一定相关C）算法的时间复杂度是指执行算法所需要的计算工作量D）算法的效率只与问题的规模有关，而与数据的存储结构无关17、某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根节点在第1层）_。A）3 B）8 C）12 D）618、对长度为n的线性表做快速排序，在最坏情况下，比较次数为_。A）n (n - 1) B）n (n - 1)/2 C）n D）n - 119、下列叙述中正确的是_。A）线性表链式存储结构的存储空间一般要少于顺序存储结构B）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的C）线性表链式存储结构与顺序存储结构的存储空间都是连续

41、的20、下列叙述中正确的是_。A）队列是一种后进先出的线性表 B）栈与队列都是线性结构C）栈与队列都是非线性结构 D）栈是一种先进先出的线性表21、下列叙述中正确的是_。A）叶子结点总是比度为2的结点少一个 B）度为2的结点数是度为1的结点数的两倍C）叶子结点数是度为2的结点数的两倍 D）叶子结点总是比度为2的结点多一个22、支持子程序调用的数据结构是_。A）树 B）队列 C）二叉树 D）栈23、下列排序方法中，最坏情况下比较次数最少的是_。A）直接插入排序 B）冒泡排序C）简单选择排序 D）堆排序24、下列叙述中正确的是_。A）有序线性表既可以采用顺序储存结构，也可以采用链式存储结构B）循环

42、队列是非线性结构C）队列是“先进后出”的线性表D）栈是“先进先出”的线性表25、下列数据结构中，属于非线性结构的是_。A）二叉树 B）带链栈 C）带链队列 D）循环队列26、下列数据结构中，能够按照“先进后出”原则存取数据的是_。A）栈 B）二叉树 C）队列 D）循环队列27、下列叙述中正确的是_。A）循环列队中的元素个数随队头指针的变化而动态变化B）循环列队中的元素个数随队头指针队尾指针的变化而动态变化C）循环列队中的元素个数随队尾指针的变化而动态变化28、一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为_。 A）230 B）231 C）219 D）22929、下

43、列叙述中正确的是_。 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）算法的时间复杂度与空间复杂度没有直接关系 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）一个算法的空间复杂度大，则其时间复杂度必定小30、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_。A）45 B）90 C）10 D）931、算法的有穷性是指_。A）算法程序的长度是有限的 B）算法只能被有限的用户使用C）算法程序的运行时间是有限的 D）算法程序所处理的数据量是有限的32、设循环队列的存储空间为Q（1：35），初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15

44、,rear=15,则循环队列中的元素个数为_。A）0或35 B）20 C）16 D）1533、下列关于栈的叙述中，正确的是_。A）栈顶元素一定是最先入栈的元素 B）栈底元素一定是最后入栈的元素C）栈操作遵循先进后出的原则34、对于循环队列，下列叙述中正确的是_。A）队头指针可以大于队尾指针，也可以小于队尾指针 B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指针是固定不变的35、在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是_。A）O（n2） B）0(log2n) C）0(nlog2n) D）0(n)36、算法的空间复杂度是指_。A）算法在执行过程中所需要的计

45、算机存储空间 B）算法所处理的数据量C）算法在执行过程中所需要的临时工作单元数 D）算法程序中的语句或指令条数37、下列数据结构中，能够按照“先进先出”原则存取数据的是_。A）二叉树 B）队列 C）栈 D）循环队列38、下列与队列结构有关联的是_。A）数组元素的引用 B）函数的递归调用C）多重循环的执行 D）先到先服务的作业调度同步练习参考答案：12345678910CCADDBBABC11121314151617181920ABBCDCCBBB21222324252627282930DDDAAABDBA3132333435363738CACABABD8.2 程序设计基础本节需要考生掌握以下内

46、容：1、程序设计方法和风格。2、结构化程序设计方法。3、面向对象程序设计方法，掌握面向对象方法的基本概念。8.2.1程序设计方法和风格1、程序设计方法程序设计是指设计、编制、调试程序的方法和过程。程序设计方法是研究问题求解如何进行系统构造的软件方法学。常用的程序设计方法有结构化程序设计方法、软件工程方法和面向对象方法。2、程序设计风格程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。良好的程序设计风格应该是：源程序文档化；数据说明的次序要规范化；语句的结构应该简单直接，不要为提高效率而复杂化；输入数据前要有提示信息，输出信息符合规范。为提高程序的可读型和可理解性，应在程序适当位置添加注

47、释。注释分序言性注释和功能性注释，其中序言性注释通常位于程序的开头部分，给出程序的整体说明；功能性注释一般嵌入在程序体中，用于描述语句或程序的功能。当今主导的程序设计风格是“清晰第一，效率第二”。8.2.2结构化程序设计1、结构化程序设计的原则结构化程序设计方法的四条原则是：自顶向下；逐步求精；模块化；限制使用Goto语句。2、结构化程序设计的基本结构结构化程序设计有3种基本结构。即顺序结构、选择结构和循环结构。（1）顺序结构：一种简单的程序设计，是最基本、最常用的结构；（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；（3）重

48、复结构：又称循环结构，根据给定条件，判断是否需要重复执行某一相同程序段。结构化程序设计方法将程序和数据结构松散地耦合在一起，不适合大型应用程序的开发，解决此问题的方法就是采用面向对象的程序设计方法。8.2.3面向对象的程序设计1、面向对象方法面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。2、面向对象方法的优点（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。3、面向对象方法的基本概念（1）对象对象是面向对象方法中最基本的

49、概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性是对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。对象是属性和方法的封装体。对象的基本特点：标识惟一性；分类性；多态性；封装性；模块独立性好。（2）类类是具有共同属性、共同方法的对象的集合。类是对象的抽象，而对象是对应类的一个实例。（3）消息消息是一个实例与另一个实例之间传递的信息。消息是面向对象程序设计中对象与对象之间进行通信的一种机制。消息的组成包括：接收消息的对象的名

50、称；消息标识符，也称消息名；零个或多个参数。（4）继承继承是面向对象方法的一个主要特征，是使用已有的类定义作为基础建立新类的定义技术。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承是父类和子类之间共享属性和操作的机制。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。（5）多态性多态性是指同样的消息被不同的对象接收时可导致完全不同的行动的现象。多态性不仅增加面向对象软件系统的灵活性，还可有效提高软件的可重用性和可扩充性。利用多态性，用户能够发送一般形式消息，而将所有实现细节留给接受消息的对象。真题解析1、下列选项中不属于结构化程序设计方法的

51、是_。A）自顶向下 B）逐步求精 C）模块化 D）可封装【答案】D【解析】结构化程序设计方法的四条原则是：自顶向下；逐步求精；模块化；限制使用Goto语句，可封装是对象的基本特点，所以答案是D。2、下列选项中不符合良好程序设计风格的是_。A）源程序要文档化 B）数据说明的次序要规范化 C）避免滥用Goto语句 D）模块设计要保证高耦合、高内聚 【答案】D【解析】程序设计要的良好的风格：源程序文档化，数据要有说明，语句的结构简单易理解，输入数据要有提示，输出要符合要求；限制使用Goto语句；模块设计要低耦合、高内聚，所以答案是D。同步练习1、面向对象方法中，继承是指_。A）一个对象具有另一个对象的性质 B）一组对象所具有的