计算机2级公共基础知识2

计算机等级考试

公共基础知识

第2页计算机二级考试公共基础知识大纲

数据结构与算法程序设计基础软件工程基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30％，是一个不小的比例。

第3页计算机二级考试公共基础知识试卷分析

章节考试时间数据结构与算法程序设计基础软件工程基础数据库设计基础2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年9月10分2分8分10分2010年3月10分0分10分10分第4页算法⒈算法的基本概念

2.算法复杂度的概念和意义

一、基本数据结构与算法

数据结构⒈数据结构的概念⒉线性表⒊栈和队列⒋树与二叉树⒌查找技术⒍排序技术

对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第5页算法的定义对解题方案准确而完整的描述称为算法。算法是程序设计的核心⒈算法的基本概念

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。例：n个数从大到小进行排序。

有多种排序方法，常用的有冒泡排序、选择排序等。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。第6页

2.

算法的基本特征一个算法应该具有以下五个重要的特征：

有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成拥有足够的情报第7页算法与计算机程序算法——是一组逻辑步骤程序——用计算机语言描述的算法3.算法的表示INPUTrS=3.14*r*rPTINTS开始输入RS=3.14*

R*R输出S结束问题：输入园的半径，计算园的面积

一个算法的表示需要使用一些语言形式。传统的算法-------图形法，如“流程图”和N-S图目前常用的方法-------使用伪码描述算法。第8页冒泡排序的方法：1.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；3.重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。

算法举例：n个数排序第9页4.算法的两个基本要素：基本运算和操作算术运算关系运算逻辑运算数据传输控制结构

顺序选择循环一是对数据对象的运算和操作；二是算法的控制结构。算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法

第10页5.

算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间

算法在执行过程中临时占用的存储空间

时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有：O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平方阶。第11页(1)在计算机中，算法是指______。

A.查询方法B.加工方法

C.解题方案的准确而完整的描述D.排序方法(2)下列叙述中正确的是______。A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指______。A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(c)(B)算法习题:(A)第12页(4)算法的时间复杂度是指______。

A)算法的执行时间

B)算法所处理的数据量

C)算法程序中的语句或指令条数

D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指

______。A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是______。

A）一个算法的空间复杂度大，则其时间复杂度也必定大

B）一个算法的空间复杂度大，则其时间复杂度必定小

C）一个算法的时间复杂度大，则其空间复杂度必定小

D）上述三种说法都不对(D)计算工作量(A)(D)算法的时间复杂度是指A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数算法的基本特征是可行性、确定性、

【1】和拥有足够的情报。算法的空间复杂度是指

A)算法程序的长度 B)算法程序中的指令条数

C)算法程序所占的存储空间D)执行过程中所需要的存储空间在计算机中，算法是指

A)加工方法 B)解题方案的准确而完整的描述

C)排序方法 D)查询方法例题讲解有穷性算法分析的目的是

A)找出数据结构的合理性B)找出算法中输入和输出之间的关系

C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】。时间复杂度和空间复杂度第15页

计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。二、数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。

一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。超市的物品如何存放才好找且节省空间呢？第16页二.数据结构数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算（操作）。第17页1.逻辑结构

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。例：1.一年四季的数据结构

B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成员的数据结构

B=(D,R)D={父亲，儿子，女儿}R={(父亲，儿子),(父亲，女儿)}春夏秋冬数据结构的图形表示父亲儿子女儿第18页常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构①线性结构结构中的每个元素之间存在一个对一个的关系；②树形结构结构中的每个元素之间存在一个对多个的关系；③图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。第19页2.存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：一年四季

家庭成员计算机存储空间怎样存放？

存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：顺序存储结构链式存储结构索引存储结构只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。一种数据结构可以根据需要表示成一种或多种存储结构。第20页3.数据的运算检索插入删除更新排序

通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：数据的逻辑结构数据的存储结构数据的运算父亲儿子女儿第21|92页常见的数据结构

数据结构分类

线性结构与非线性结构两大类型线性结构：一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。①有且仅有一个根结点；②除第一个结点外，每一个结点最多有一个前件；除最后一个结点外，每一个结点最多有一个后件。常见的线性结构有：线性表、栈、队列、线性链表等第22|92页a1a2a5a3a4HEAD319510线性链表的逻辑状态常见的非线性结构有树、二叉树、图等非线性结构：一个数据结构不是线性结构。第23页１．线性表（LinearList）

线性表是由n（n≥0）个数据元素

a1，a2，…，ai，…，an组成的一个有限序列。简单的线性表春夏秋冬复杂的线性表记录102011001

张三男…

记录202011003李四女…记录3记录4第24页线性表的顺序存储结构特点：

顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。…a1a2…ai…an…存储地址200020042000+4*(i-1)2000+4*(n-1)……占4个字节Loa（ai）=Loa（a1）+L*（i-1）第i个数的地址第一个数的地址L为该类型数所占的字节线性表的存储结构线性表的存储结构有两种：

顺序存储结构

链式存储结构第25页

顺序表的插入运算顺序表的删除运算顺序表的插入和删除运算

在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。第26页插入运算ai-1…..a2a1alength…ai+1aixai-1…..a2a1alength…ai+1aiX

插入算法的分析:

假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：第27页

删除运算ai-1…..a2a1alength…ai+1aiai-1…..a2a1alength…ai+1删除算法的分析:

在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：总结:

顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。第28页线性表的链式存储结构

线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：链式存储结构分为单链表、双向链表、循环链表线性链表不能随机存取数据域指针域第29页设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的物理状态1a12a23a34a45a567线性表的顺序存储结构注意:123此类编号不代表所在的地址单元的地址编码线性表的链式存储结构

及其插入与删除操作第30页zhaoqiansunlizhouwuzhengwang/H存储地址数据17131925313743liqiansunwangwuzhaozhengzhou指针43131null377192531头指针单链表第31页单链表的插入运算在P所指向的结点之后插入新的结点单链表删除运算PbaxSbaPLa…aian^…ai-1ai+1要求:删除结点ai。第32页循环链表:

首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。a1a2an∧a3L…..带头结点的单链表a1a2ana3L…..循环单链表特点:

可以从任何一个结点开始访问链表的所有结点.第33页双向链表的存储结构

在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。HEAD31510a2a3a4a1提问：单向链表的缺点是什么？提示：如何寻找结点的直接前趋。

双向链表可以克服单链表的单向性的缺点。

在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。双向循环链表

第34页线性表的应用：应用最广的数据结构。.高级语言中的数组；·计算机的文件系统；·计算机的目录系统；·电话号码查询系统（可采用顺序表或单链表结构）；·各种事务处理（可采用顺序表或单链表结构）;第35页2.栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。

栈（Stack）及其基本运算

队列（Queue）及其基本运算

循环队列及其基本运算第36页1.栈栈——是一种只允许在表的一端进行插入或删除操作的线性表。栈顶top——允许插入或删除一端。栈底bottom——不允许插入或删除一端。空栈——不含元素的空表。…a1a2an栈底栈顶进栈出栈栈s=(a1,a2,…,an)后进先出或先进后出（LIFO）第37页栈的物理存储结构可以用顺序结构，也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算栈的基本运算有三种：入栈、退栈和读栈顶元素

在顺序栈中插入和删除运算不需要移动表中其他数据元素。第38页2.栈的顺序存储结构及其基本运算a2a1a1a2top

用顺序存储结构表示的栈:

顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为针栈顶指，它始终指向待插入元素的位置。基本运算：压（进）栈：PUSH出栈：POP读栈顶元素：gettop第39页例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：top＝base非空桟：top始终在桟顶元素的后一个位置桟的元素个数：top-base上溢下溢第40页2、队列定义：一种特殊的线性结构，限定只能在表的一端（队尾rear）进行插入，在表的另一端（队头front）进行删除的线性表。此种结构称为先进先出（FIFO）表。a1,

a2,

a3,

a4,…………

an-1,

an

队列示意图队头队尾先进先出后进后出（LIFO）第41页e3e4(c)e1,e2出队，e4入队

队满rear=3fronte1e2e3

(b)rearfront(b)e1,e2,e3入队队列的顺序存储结构及其基本运算

3210(a)rear=front=-1(队空）rearfront空队列:非空队列:队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而rear始终指向队尾元素的位置rear-front第42页

队列的物理存储结构可以用顺序结构，也可以用链式结构。顺序队列的运算栈有三种操作：入栈＼出栈＼读栈顶元素队列有三种操作：入队＼出队＼读队首元素例：有入栈元素序列：ABCD，求可能的出栈序列．如是队列又是什么情况呢？第43页

循环队列把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置于始端。循环队列的运算队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。

第44页……frontrearMaxsize-101e3e4

rear=3front第45页0012345frontABCDEFrear上溢0012345frontrear下溢front=rear队满front=rear队空第46页数据存储结构方面的考题

1：数据的存储结构是指（）

A)存储在外存中的数据B)数据所占的存储空间量

C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示2.下列叙述中正确的是（

）

A）栈是“先进先出”的线性表

B）队列是“先进后出”的线性表

C）循环队列是非线性结构

D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构3.数据结构分为线性结构和非线性结构，带链的队列属于（

）。4.下列数据结构中，属于非线性结构的是（

）A）循环队列B)带链队列C)二叉树D）带链栈答案：D。答案：D。答案：线性结构。答案：c第47页5。下列叙述中正确的是（）。

A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C）顺序存储结构能存储有序表，链式存储结构不能存储有序表

D）链式存储结构比顺序存储结构节省存储空间答案：A。6。下列关于栈的叙述正确的是（

）

A）栈按“先进先出”组织数据B)栈按“先进后出”组织数据

C）只能在栈底插入数据D）不能删除数据

答案：B。7.一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为（

）

。答案：A，B，C，D，E，F，5，4，3，2，1第48页9.设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有【2】个元素。

（2010年3月）

8。假设用一个长度为50的数组（数组元索的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有【】个元素。答案：19答案：1546－50－1－10链表不具有的特点是A)不必事先估计存储空间B)可随机访问任一元素C)插入删除不需要移动元素 D)所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构，线性链表属于【1】

。数据结构中，与所使用的计算机无关的是数据的

A)存储结构 B)物理结构

C)逻辑结构 D)物理和存储结构数据的逻辑结构有线性结构和【1】

两大类。数据的存储结构是指A）数据所占的存储空间B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据例题讲解存储结构非线性结构顺序存储方法是把逻辑上相邻的结点存储在物理位置

【2】的存储单元中。

数据处理的最小单位是

A)数据 B)数据元素C)数据项 D)数据结构数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及

A)数据的存储结构 B)计算方法C)数据映象D)逻辑存储线性表的顺序存储结构和线性表的链式存储结构分别是

A)顺序存取的存储结构、顺序存取的存储结构

B)随机存取的存储结构、顺序存取的存储结构

C)随机存取的存储结构、随机存取的存储结构

D)任意存取的存储结构、任意存取的存储结构

相邻根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成

A)动态结构和静态结构 B)紧凑结构和非紧凑结构

C)线性结构和非线性结构D)内部结构和外部结构数据结构包括数据的逻辑结构、数据的

【2】以及对数据的操作运算。数据的基本单位是

【5】。下列叙述中，错误的是

A)数据的存储结构与数据处理的效率密切相关

B)数据的存储结构与数据处理的效率无关

C)数据的存储结构在计算机中所占的空间不一定是连续的

D)一种数据的逻辑结构可以有多种存储结构存储结构数据元素链表不具有的特点是A)不必事先估计存储空间B)可随机访问任一元素C)插入删除不需要移动元素 D)所需空间与线性表长度成正比顺序存储方法是把逻辑上相邻的结点存储在物理位置

【2】的存储单元中。长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【1】

。线性表若采用顺序存储结构时，要求内存中可用存储单元的地址

A)必须是连续的 B)部分地址必须是连续的

C)一定是不连续的D)连续不连续都可以例题讲解相邻线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是

A)每个元素都有一个直接前件和直接后件

B)线性表中至少要有一个元素

C)表中诸元素的排列顺序必须是由小到大或由大到小

D)除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件线性表的顺序存储结构和线性表的链式存储结构分别是

A)顺序存取的存储结构、顺序存取的存储结构

B)随机存取的存储结构、顺序存取的存储结构

C)随机存取的存储结构、随机存取的存储结构

D)任意存取的存储结构、任意存取的存储结构下列叙述中，错误的是

A)数据的存储结构与数据处理的效率密切相关

B)数据的存储结构与数据处理的效率无关

C)数据的存储结构在计算机中所占的空间不一定是连续的

D)一种数据的逻辑结构可以有多种存储结构

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成

A)动态结构和静态结构 B)紧凑结构和非紧凑结构

C)线性结构和非线性结构D)内部结构和外部结构当线性表采用顺序存储结构实现存储时，其主要特点是【1】

。随机存取链表不具有的特点是A)不必事先估计存储空间B)可随机访问任一元素C)插入删除不需要移动元素D)所需空间与线性表长度成正比用链表表示线性表的优点是A)便于随机存取B)花费的存储空间较顺序存储少C)便于插入和删除操作D)数据元素的物理顺序与逻辑顺序相同长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为【1】

。在单链表中，增加头结点的目的是

A)方便运算的实现B)使单链表至少有一个结点

C)标识表结点中首结点的位置

D)说明单链表是线性表的链式存储实现例题讲解非空的循环单链表head的尾结点(由p所指向)，满足

A)p->next==NULL B)p==NULLC)p->next=head D)p=head循环链表的主要优点是

A)不再需要头指针了

B)从表中任一结点出发都能访问到整个链表

C)在进行插入、删除运算时，能更好的保证链表不断开

D)已知某个结点的位置后，能够容易的找到它的直接前件当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【2】。用链表表示线性表的突出优点是【1】。上溢插入、删除灵活栈和队列的共同特点是

A)都是先进先出B)都是先进后出

C)只允许在端点处插入和删除元素D)没有共同点如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是

A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意顺序一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用

A)栈 B)堆C)数组 D)链表例题讲解栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是

A)ABCED B)DCBEAC)DBCEA D)CDABE栈通常采用的两种存储结构是

A)线性存储结构和链表存储结构 B)散列方式和索引方式

C)链表存储结构和数组D)线性存储结构和非线性存储结构栈和队列通常采用的存储结构是【1】

。下列数据结构中，按先进后出原则组织数据的是

A)线性链表B)栈C)循环链表 D)顺序表▽当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为

【2】。链表存储结构和数组上溢由两个栈共享一个存储空间的好处是A)减少存取时间，降低下溢发生的机率B)节省存储空间，降低上溢发生的机率C)减少存取时间，降低上溢发生的机率D)节省存储空间，降低下溢发生的机率下列关于栈的叙述中正确的是Ａ）在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是后进先出的线性表下列关于队列的叙述中正确的是Ａ）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是后进先出的线性表第60页树型结构是一种重要的非线性结构。

树的概念

二叉树的概念

二叉树的存储

二叉树的遍历3.树与二叉树第61页树的概念

树的定义：是一种简单的非线性结构。n个结点的有限集。（n>=0）

ABDFECGHIJKM结点：根结点：没有前件的结点只有一个称为根结点。简称树的根。空树：无结点则称为空树；

父结点：结点的前件称该结点的父结点。A只有一个结点的树第62页树型结构的常用术语ABDFECGHIJKM子结点：结点的后件，称为该结点的子结点。可以有多个。叶子结点没有后件的结点；

Q：图中叶子结点有几个？7结点的度一个结点的子树的个数；(有几个分叉)Q：结点A、G的度数？3，2.Q：度数为0、1、2、3的结点分别有几个？

树的度树中所有结点度的最大值；Q：右图中树的度？3第63页树型结构的常用术语ABDFECGHIJKM

结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；

Q：图中结点F的层次？

树的深度

树中所有结点层次的最大值；

Q：图中树的深度？

有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。①②③④第64页二叉树的概念

定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。称左子树和右子树

二叉树的5种基本形态第65页★树与二叉树的区别A．树和二叉树的结点个数最少都可为0。B．树中结点的最大度数没有限制，二叉树结点最大度数为2。C．树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。3个结点的树3个结点的二叉树第66页二叉树的性质【性质1】

在二叉树的第k层上最多有2k-1个结点（k≥1）ABCDFEHG121314158910114567123第67页【性质2】深度为m的二叉树最多有2m-1个结点（m≥1）ABCDFEHG121314158910114567123第68页【性质3】二叉树上叶子结点数比度为2的结点数多1ABCDFEHG度为2的结点叶子结点第69页【性质4】具有n个结点的二叉树的深度最少为

log2n

+1),其中，log2n

的结果是不大于log2n的最大整数121314158910114567123深度为4的满二叉树深度为4的完全二叉树84567123深度为3的完全二叉树具有4～7个结点深度为4的完全二叉树具有8～15深度为5的完全二叉树具有15～31log2(8+1)=ln9/In2=4log2(15+1)=In16/In2=4深度为6的完全二叉树具有32～63深度为7的完全二叉树具有64～127深度为8的完全二叉树具有128～255深度为9的完全二叉树具有256～511深度为10的完全二叉树具有512～1023深度为11的完全二叉树具有1024～2047第70页满二叉树和完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。最后一层的结点均为0度。完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。则称这棵二叉树为完全二叉树。完全二叉树中度数为1的结点的个数为0或1。第71页121314158910114567123满二叉树完全二叉树12138910114567123

完全二叉树是满二叉树满二叉树也是完全二叉树第72页1213891011456123非完全二叉树深度为4的完全二叉树84567123第73页性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1=<i=<n)有：

(1)如果i=1,则结点i是二叉树的根,无双亲;

如果i>1,则双亲Parent(i)是结点|i/2|。

(2)如果2i<=n,则编号i的左子结点为2i，否则无左子结点，显然也就没有右子结点。

(3)如果2i+1<=n,则编号i的右子结点2i+1，否则该结点无右子结点。

总之：如

i>1它的双亲是i/2取整，左子结点是2*i，右子结点是2*i+1.当然如果算下来超过总数民N，则为没有。第74页例：112345678910121i=6其双亲为|i/2|=3；其左子结点为2*i=12;i=1是树的根,无双亲;其左子结点为2*i=2,右子结点为2*i+1=3.∵2*i=18>122*i+1=19>12∴其无左、右子结点。∵2*i+1=13>12∴其无右子结点。i=9其双亲为|i/2|=

4

；第75页1：在深度为7的满二叉树中,叶子结点的个数为

A)32

B)31

C)64

D)632：在深度为7的满二叉树中，度为2的结点个数为【】

。3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为

A）219B）221C）229D）2314：某二叉树中度为2的结点有18个，则该二叉树中有【】个叶子结点。5：一棵二叉树第六层（根结点为第一层）的结点数最多为【】个。（树型结构方面的考题

1答案：C。3答案：A。5答案：32。2答案：63。4答案：19。第76页二叉树的存储

在计算机中，二叉树通常采用链式存储结构。对于满二叉树和完全二叉树可以按层进行顺序存储。LlinkinfoRlink二叉树的存储结点的结构ABDCFGEA∧G∧∧E∧∧F∧B∧C∧

Dt第77页2、二叉树的存储结构

(2)链式存储结构T[16]若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。11ABcFED

●●●●●●●●●124

8

910563712131415(1)顺序存储结构(1)顺序存储结构2h-1=24-1=15用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。第78页(2)链式存储结构链式存储结构二叉链表三叉链表二叉链表：二叉链表的结点包含三个域：数据域、左、右指针域。例：ABCDEFGA^B^C^D^E^F^^G^第79页三叉链表：三叉链表的结点包含四个域：数据域、左、右、双亲指针域。例：ABCDEFGA^^B^C^D^E^F^^G^链式存储结构的特点：（1）操作便于实现（2）结构复杂第80页二叉树的遍历

遍历指不重复地访问二叉树中的所有结点。二叉树的遍历的次序与树型结构上的大多数运算有联系。遍历的方式有三种（1）前序遍历（DLR）（2）中序遍历（LDR）（3）后序遍历（LRD）ABCDFEHG第81页二叉树的遍历

遍历指不重复地访问二叉树中的所有结点。（1）先（前）序遍历（DLR）根左右若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。ABCDFEHG先序遍历的结果：

ABECFGHD第82页（2）中序遍历（LDR）左根右若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。中序遍历的结果：EBAFHGCD（3）后序遍历（LRD）右根左若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。后序遍历的结果：E

BHGFDCAABCDFEHG第83页先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？练习：根据先序遍历序列，建立二叉树第84页1:设二叉树如下：

对该二叉树进行后序遍历的结果为【3】

树型结构方面的考题22:对如下二叉树进行后序遍历的结果为A)ABCDEF

B)DBEAFCC)ABDECF

D)DEBFCA

EDBGHFCA

DABCFHDGE已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是

A)acbedB)decabC)deabc D)cedba

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为

A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG树是结点的集合，它的根结点数目是

A)有且只有1 B)1或多于1C)0或1 D)至少2下列叙述中正确的是

A)线性表是线性结构 B)栈与队列是非线性结构

C)线性链表是非线性结构 D)二叉树是线性结构例题讲解在深度为5的满二叉树中，叶子结点的个数为

A)32 B)31C)16 D)15若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是

A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca在树结构中，树根结点没有【1】。具有3个结点的二叉树有

A)2种形态B)4种形态C)7种形态D)5种形态设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为

A)12 B)13C)14 D)15双亲结点设有下列二叉树：

对此二叉树前序遍历的结果为A)ZBTTCPXAB)ATBZXCTPC)ZBTACTXPD)ATBZXCPT设有下列二叉树：对此二叉树的中序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中的叶子结点数为A）8B）7C）6D）5设一棵完全二叉树共有700个结点，则该二叉树中有（）个叶子结点。

在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有（）个元素。设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（）。3503DEBFCA第89页⒌查找技术

查找是数据处理的重要内容。查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。若找到了满足条件的结点，称查找成功；否则称查找失败。衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。通常根据不同的数据结构，采用不同的查找方法：

顺序查找

二分查找第90页1.7.1.1顺序查找（线性查找）◆查找过程：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。◆可以采用从前向后查，也可采用从后向前查的方法。◆在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。最好情况：1最坏情况：n◆在下面两种情况下只能采取顺序查找：

a.线性表为无序表（元素排列是无序的）；

b.即使是有序线性表，但采用的是链式存储结构。第91页1.7.1.2折半查找（二分法查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。分三种情况：

1）若中间项的值等于x,则说明已查到。

2）若x小于中间项的值,则在线性表的前半部分查找；

3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。第92|92页折半查找算法举例对给定数列（有序）{3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

第1次：{3，5，11，17，21，23，28，30，32，50}

K=30mid1=（1+10）/2=5

k>a(mid1)=a(5)=21

第2次：{23，28，30，32，50}mid2=（6+10）/2=8K=a(mid2)=a(8)=30lowhighmidlowhighmid第93|92页练习

假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找关键字值为27的数据元素.对于长度为n的有序线性表，最坏情况只需比较log2n次。

第94页1.7.2排序1.7.2.1概述

1、排序的功能：

将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。

2、排序过程的组成步骤：首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。第95页排序方法插入排序选择排序交换排序归并排序简单插入排序希尔排序简单选择排序堆排序起泡排序快速排序第96页1.7.2.2插入排序

简单插入、希尔排序1、简单插入排序:

基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。第97页该算法适合于n较小的情况，时间复杂度为O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1趟最坏情况下：需要n(n-1)/2次比较最好：

n-1次比较第98页希尔排序：希尔排序的基本思想:

先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序.最坏情况下：需要O(n1.5)次比较第99页

1、简单选择排序思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。1.7.2.3选择排序

简单选择排序、堆排序简单选择排序法,

最坏情况需要n(n-1)/2次比较；

时间复杂度为O(n2)，适用于待排序元素较少的情况。第100|92页初态：[15，14，22，30，37，15，11]第一趟：[11][14，22，30，37，15，15]第二趟：[11，14][22，30，37，15，15]第三趟：[11，14，15][30，37，22，15]第四趟：[11，14，15，15][37，22，30]第五趟：[11，14，15，15，22][37，30]第六趟：[11，14，15，15，22，30][37]

有序序列例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：第101页

2、堆排序（也是一种选择排序）堆是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。897624331510112536497856(a):堆顶元素取最大值(b):堆顶元素取最小值堆排序需要比较的次数为O(nlog2n)

(1)堆的示例

第102页1.7.2.4交换排序交换排序的特点在于交换。有冒泡和快速排序两种。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，……关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；依次类推，则完成排序。第103页冒泡排序

冒泡排序的方法：扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大(或最小)的元素排到表的最后(或最前)

；除最后(或最前)一个元素，对剩余的元素重复上述过程，将次大(或次小)的数排到表的倒数(或正数)第二个位置；重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。

第104页冒泡排序的方法设待排数据元素的关键字为（18，20，15，32，4，25），第一趟冒泡排序后的序列状态如图所示：

182015324251820153242518152032425181520324251815204322518152042532最大数第二趟冒泡排序第105页Q：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？

冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序终止条件:

本趟排序未发生交换，终止排序算法第106页初始第一趟第二趟第三趟第四趟第五趟序列排序后排序后排序后排序后排序后 26 18 18

18

189 18 26 26

26 915 32 32

329 15 18 54 47 915 26 47 9 1532

9 15 47

15 54

设待排数据元素的关键字为（26,18,32,54,47,9,15)冒泡排序法，需要比较的次数为n(n-1)/2；

第107页2、快速排序(对冒泡排序的改进）思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。时间复杂度：O(log2n)当待排序列逆序时，蜕变成冒泡排序，时间复杂度:O(n(n-1)/2)第108页1.7.2.5内部排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。若待排序的记录个数n较小时，可采用简单排序方法。若n较大时，应采用快速排序或堆排序。若待排序的记录已基本有序，可采用简单插入和起泡排序。第109页方法归并排序简单插入希尔排序简单选择堆排序起泡排序快速排序插入选择交换比较次数使用建议查找:方法顺序折半比较次数log2n最好:1最坏:n平均:(n+1)/2使用条件顺序存储结构的有序表任何表排序:n-1n(n-1)/2n1.5n(n-1)/2nlog2nn-1n(n-1)/2log2nn(n-1)/2正序的表、n小的表与表的初始数据无关、n小的表正序的表、n小的表n大的表,但逆序的表会蜕变为起泡排序借助辅助空间最多的方法n大的表第110|92页排序法小结：简单选择排序法,

最坏情况需要n(n-1)/2次比较；冒泡排序法,

最坏情况需要n(n-1)/2次比较；希尔排序法,

最坏情况需要O(n1.5)次比较；堆排序法,最坏情况需要O(nlog2n)次比较；

第111|92页排序查找方面的考题：(1)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）

A)冒泡排序为n/2B)冒泡排序为n

C)快速排序为nD)快速排序为n(n-1)/2

(2)在长为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。A）63B）

64C）

6D）

7(3)下列数据结构中，能用二分法进行查找的是（

）

A）顺序存储的有序线性表 B）线性链表

C）二叉链表 D）有序线性链表(4)下列排序方法中，最坏情况下比较次数最少的是（

）

A）冒泡排序

B）简单选择排序

C）直接插入排序

D）堆排序DBAD第112页在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为

【2】。长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【1】

。假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为

A)log2n B)n2C)O(n1..5) D)n(n-1)/2已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是

A)堆排序B)直接插入排序C)快速排序D)直接选择排序例题讲解log2nn/2第113页

冒泡排序算法在最好的情况下的元素交换次数为【1】

。在最坏情况下，堆排序需要比较的次数为

【2】。最简单的交换排序方法是

A)快速排序 B)选择排序C)堆排序 D)冒泡排序排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、【1】

和选择排序等。0nlog2n交换排序第114页在下列几种排序方法中，要求内存量最大的是

A)插入排序B)选择排序C)快速排序 D)归并排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A)冒泡排序B)选择排序C)快速排序D)归并排序

希尔排序属于

A)交换排序B)归并排序C)选择排序 D)插入排序对长度为n的线性表进行顺序查找，在最坏的情况下所需要的比较次数为Ａ)n+1B)nC)(n+1)/2D)n/2第115页2.程序设计基础第116页第二章程序设计基础内容：

1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。第117页1.源程序的文档化符号的命名:见名知意注释（序言性和功能性注释）程序的视觉组织:空格、空行、缩进。。。。2.数据说明数据说明的次序应该规范化变量安排有序化对复杂数据结构应注释说明3.语句的结构每条语句简单明了尽量不用或少用GOTO语句尽量只采用3种基本控制结构编程4.输入和输出对所有输入数据进行校验和合理性检查输入输出格式保持一致设计良好的输出报表清晰第一，效率第二2.1.2程序设计风格程序设计结构化程序设计（面向过程的程序设计）面向对象的程序设计第118页第119页2.2结构化程序设计2.2.1基本概念★基本思想

对大型的程序设计，使用一些基本的结构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口、一个出口。由这些基本结构组成