二级公共基础知识1-PPT课件

1、二 级 公 共 基 础 知 识 授课时间： 2019年4月1 一、涉及面广，但难度小你应该知道 公共基础知识考题特点 计算机等级二级理论考试中有关公共知识部分的题目共有15道，涉及算法及数据结构、程序设计基础、软件工程基础和数据库设计基础等四门学科，但是从整体上分析，考试中的考核内容的难度不大，考点也相对集中些。2二、考核重点为基本概念、基本方法 和基本运算你应该知道 计算机等级二级理论考试中涉及的题目都是基本概念、基本方法和基本运算，考核以概念和认识性内容为主，理解性、应用性内容极少。 3三、考核重点是数据结构和算法你应该知道 以下是对以往二级理论考试的大概统计： 算法及数据结构： 50%

2、程序设计基础：12.5% 软件工程基础：18.75% 数据库设计基础：18.75%4你应该知道 共讲授 12个学时，具体安排如下：数据结构与算法（4学时 ）程序设计基础、软件工程基础（4学时） 数据库系统、真题讲解（ 4学时） 本 课 程 授 课 安 排51、了解算法的基本概念和一些常用的算法，学会计算算法的时间复杂度；2、掌握数据结构的基本概念，并了解数据的逻辑结构和存储结构，学会利 用图形的方式表示数据结构 ；学习目标与要求 算法与数据结构：3、了解线性表的基本概念，并掌握线性表的顺序存储结构以及顺序存储的 线性表的基本运算； 4、了解栈和队列的基本概念，并掌握它们的基本运算； 5、了解线

3、性链表的基本概念，并掌握线性链表的基本运算，同时，了解循 环链表的基本概念和基本操作； 6、理解树的概念，尤其是二叉树的基本概念和相关性质，掌握二叉树的存 储结构和遍历技术； 7、掌握查找技术，学会利用顺序查找和二分查找在数列中查找指定的数据； 8、学会利用相关的排序技术实现无序数列的排序操作。 6数据结构与算法一、算法（ algorithm）1、算法的基本概念 算法是指解题方案的准确而完整的描述。它是指令的有限序列，其中每一条指令表示一个或多个操作。它是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法具有有穷性、确定性、可行性、输入和输出（

4、拥有足够的情报）等个重要特性。72、算法的基本要素 对数据对象的运算和操作： 算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序； 描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描述语言等； 一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。 算法的控制结构： 数据结构与算法83、算法设计的基本方法 列举法 归纳法 递推 递归（以简洁的形式设计和描述算法） 减半递推技术 回溯法数据结构与算法9二、算法的复杂度1、时间复杂度 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。 一个算法是由控制结构（顺序、分支和循环）和原

5、操 作构成的，算法时间取决于两者的综合效果。 算法中基本操作重复执行次数n和算法执行时间同步 增长，称作算法的时间复杂度。数据结构与算法10二、算法的复杂度1、时间复杂度 在同一问题规模下，如果算法执行所需要的基本运算次数取决于某一特定输入时，可以用以下方法分析工作量：平均性态和最坏情况复杂性。数据结构与算法11算法与数据结构2、空间复杂度 一般是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、 输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。 一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据

6、进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。12算法与数据结构3、例题讲解 算法的时间复杂度是指( C ) A、执行算法程序所需要的时间 B、算法程序的长度 C、算法执行过程中所需要的基本运算次数 D、算法程序中的指令条数 算法的基本特征是可行性、确定性、 【1】和拥有足够 的情报。 【答案】:有穷性 算法的空间复杂度是指( D ) A) 算法程序的长度 B) 算法程序中的指令条数 C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间 13算法与数据结构 在计算机中，算法是指（ B ） A) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法

7、 算法分析的目的是( D ) A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的 【 1 】 。【答案】:时间复杂度和空间复杂度 14算法与数据结构三、数据结构（ Data Structure）1、数据结构研究的主要内容当今计算机应用的特点： 1、所处理的数据量大且具有一定的关系； 2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。 对数据的讨论不单单是数据本身，还要包括数据与数据之间的关系。15特点： 每个学生的信息占据一行，所有

8、学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 应用举例1学籍档案管理假设一个学籍档案管理系统应包含如下表所示的学生信息。16 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。图 1-1 家庭血缘关系图特点： 在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构； 对它的操作有：建立树形结构，输出结点内容等等。17 应用举例3制定教学计划 在制定教学计划时，需要考虑

9、各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：18这种数据可以用下面的图来表示：18 课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图 1-2 计算机专业必修课程开设先后关系1919 1、数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构B非线性结构A顺序存储 B链式存储 线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)数据结构的主要研究问题：20202、基本概念和术语 数据结构是一门研究数据组织、存储和运算的一般

10、方法的学科。例：整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。计算机管理图书问题 ： 在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如：2121数据元素在计算机中的表示 数据结构是一门研究数据组织、存储和运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶

11、数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理（插入、删除、修改、查找、排序）2222 数据元素(Data Element) 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元素可由若干数据项(Data Item)组成。数据项是数据的最小单位。数据元素亦称节点或记录。数据结构可描述为 Group=（D，R）有限个数据元素的集合有限个节点间关系的集合2323数据结构可描述为 Group=（D，R） 例1：一年四季的数据结构可表示成B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬） 例2：家庭成员数据结构可表示成B=（D，R）D=父亲

12、，儿子，女儿 R=（父亲，儿子），（父亲，女儿）冬春夏秋父亲儿子女儿24数据结构也可用图形表示一年四季的数据结构可表示成家庭成员数据结构可表示成冬春夏秋父亲儿子女儿（ 概念：结点、前件、后件、根结点、叶子 ）25 树形结构全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构。26HGFECDBA树形结构 结点间具有分层次的连接关系HBCDEFGA271423 D=1 , 2 , 3 , 4R=(1,2),(1,3), (1,4),(2,3), (3,4),(2,4) 213 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) 图形结构节点间的连结是任意的28

13、3、例题讲解数据处理的最小单位是( C ) A)数据 B)数据元素 C) 数据项 D) 数据结构数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及( A ) A) 数据的存储结构 B) 计算方法 C) 数据映象 D) 逻辑存储数据结构包括数据的逻辑结构、数据的 【4】 以及对数据的操作运算。 【答案】物理结构（或存储结构）29 线性结构与非线性结构： 线性结构：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。 如：一年四季，26个英文字母非线性结构：线性以外的数据结构。 如：反映家庭成员间辈分关系的数据结构 算法与数据结构304、线性表（Lin

14、ear List）学 生 成 绩 表 (按成绩排列)86胡孝臣986110395刘忠赏9861107100张卓9861109成 绩姓 名学 号 线性表结点间是以线性关系联结： 线性表：具有线性结构的有限序列。 数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。31线性表的定义: 线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2， ，ai， ，an 其中n称作表的长度，当n=0时，称作空表。线性表的特点： 1、线性表中所有元素的性质相同。 2、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，

15、最 后一个数据元素无后继。 3、数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有： 初始化、求长度、取元素、修改、前插、删除、检索、排序3232 线性表的 顺序存储结构 及其 插入 与 删除 操作特点： 1、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。 2、所有元素所占的存储空间是连续的。 3、各数据元素在存储空间中是按逻辑顺序依次存放的 （a）做插入、删除时需移动大量元素。 （b）空间估计不明时，按最大空间分配。算法与数据结构33顺序存储存储地址存储内容元素n.元素i.元素2元素1LoLo + mLo+(i-1)mLo+（n-1)mLoc(元素i)=Lo+（i-

16、1)m每个元素所占用的存储单元个数 线性表的 顺序存储结构：首地址起始地址基地址34元素a1元素a2.元素ai+1. 0 1i 线性表的顺序存储结构可用C语言中的一维数组来描述.第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)* mVVViVm-1 int VM; 其中：V是数组的名字，M是数组大小， 假设数组中的元素是整型类型算法与数据结构35插入运算.a2a1an.ai+1ai01i-1in-1ai-1.a2a1alength ai+1ai x ai-1. a2 a1 X aiai+1.alength插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定

17、在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：3636在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。删除算法的分析3737 线性表的例题讲解 顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1】 的存储单元中。 【答案】相邻 长度为n的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数 为【2】 。 【答案】 n/2 线性表L=(a1,a

18、2,a3,ai，an)，下列说法正确的是（D） A) 每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件 3838数据结构中，与所使用的计算机无关的是数据的( C ) A) 存储结构B) 物理结构 C) 逻辑结构D) 物理和存储结构 下列叙述中，错误的是（ B ） A) 数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种

19、存储结构 数据的存储结构是指（ B ） A）数据所占的存储空间 B）数据的逻辑结构在计算机中的表示 C）数据在计算机中的顺序存储方式 D）存储在外存中的数据39 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成( C ) A) 动态结构和静态结构 B) 紧凑结构和非紧凑结构 C) 线性结构和非线性结构 D) 内部结构和外部结构 数据的逻辑结构有线性结构和 【2】两大类。非线性结构 当线性表采用顺序存储结构实现存储时，其主要特点是【1】。 【答案】逻辑结构中相邻的结点在存储结构中仍相邻。40405、堆栈和队列 堆栈和队列的定义 栈和队列是两种特殊的线性表，它们是运算时要受到某

20、些限制的线性表，故也称为限定性的数据结构。 堆栈的定义堆栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种 结构称为后进先出。设栈s=（a1，a2，ai， ，an）,其中a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。 a1 a2 . an进栈出栈栈顶栈底4141 队列的定义队列：一种特殊的线性结构，限定只能在表的一端进行插入， 在表的另一端进行删除的线性表 。此种结构称为先进 先出（FIFO）表。 a1 , a2 , a3 , a4 , an-1 , an队 列 示 意 图队

21、头队尾 队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；4242 堆栈和队列的例题讲解栈和队列的共同特点是（ C ） A)都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（ B ） A) e3,e1,e4,e2 B) e4,e3,e2,e1 C) e3,e4,e1,e2 D) 任意顺序一些重要的程序语言(如C语言和Pascal语言) 允许过程的递归调用。而实现递归调用中的存储分配通常用（ A ） A) 栈 B) 堆 C) 数组

22、 D) 链表 4343 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E 入栈前，栈中元素可以出栈，则出栈序列可能是（ B ） A) ABCED B) DCBEA C) DBCEA D) CDABE 栈通常采用的两种存储结构是（ A ） A) 顺序存储结构和链表存储结构 B) 散列方式和索引方式 C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构 栈和队列通常采用的存储结构是 【1】。 【答案】链式存储和顺序存储 下列数据结构中，按先进后出原则组织数据的是（ B ） A) 线性链表 B) 栈 C) 循环链表 D) 顺序表 4444当循环队列非空且队尾指针等于队头指针时，说明循环队

23、列已满，不能进行入队运算。这种情况称为【2】。答案：上溢 由两个栈共享一个存储空间的好处是（ B ） A) 减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率 C) 减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率下列关于栈的叙述中正确的是（ D ）)在栈中只能插入数据 B）在栈中只能删除数据C）栈是先进先出的线性表 D）栈是后进先出的线性表下列关于队列的叙述中正确的是（ C ）在队列中只能插入数据 B）在队列中只能删除数据C）队列是先进先出的线性表 D）队列是后进先出的线性表 4545 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在

24、物理上相邻的存储单元里。 顺序存储结构的三个缺点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。存储内容元素n.元素i.元素2元素146466、线性链表线性链表的基本概念： 线性表的链式存储结构称为线性链表。 为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。算法与数据结构47将存储空间中的每一个存储结点分为两部：一部分称为数据域，用于存储数据元素的值；另一部分称为指针域，用于存放下一个数据元素的存储序号（即存储结点的地址），也就是指向后件结点. 线性链表中存储结点的结构如

25、图2.20所示48481、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。2、逻辑上相邻的节点物理上不必相邻。3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。4、查找结点时链式存储要比顺序存储慢。 链接存储结构特点：算法与数据结构49 指向线性表中第一个结点的指针HEAD称为头指针。 当HEAD=NULL（或0）时称为空表。 对于线性链表，可以从头指针开始，沿着各个结点的指针扫描到链表中的所有结点。线性链表的逻辑结构图所示505151 线性链表的基本运算：线性链表的运算主要有以下几个： 在线性链表中包含指定元素的结点之

26、前 插入一个新元素。 在线性链表中删除包含指定元素的结点。 将两个线性链表按要求合并成一个线性 链表。52 线性链表的 插入 运算： 线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。 为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，然后将存放新元素值的结点链接到线性链表中指定的位置。算法与数据结构535454 线性链表的删除指在链式存储结构下的线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。 线性链表的 删除 运算：算法与数据结构555656 循环链表的结构与前面所讨论的线性链

27、表相比，具有以下两个特点： 循环链表的头指针指向表头结点。 在循环链表中，所有结点的指针构成了一个环状链。 循环链表：5757 在实际应用中，循环链表与线性单链表相比主要有以下两个方面的优点： 在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所 有的结点。 由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链表中至少有一个 结点存在，从而使空表与非空表的运算统一。算法与数据结构58链表不具有的特点是（ B ） A) 不必事先估计存储空间 B) 可随机访问任一元素 C) 插入删除不需要移动元素 D) 所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构

28、，线性链表属于 【1】 。 【答案】存储结构线性表的顺序存储结构和线性表的链式存储结构分别是( B )A) 顺序存取的存储结构、顺序存取的存储结构B) 随机存取的存储结构、顺序存取的存储结构C) 随机存取的存储结构、随机存取的存储结构D) 任意存取的存储结构、任意存取的存储结构 线性链表的例题讲解59591.6、树与二叉树： 树的基本概念： 前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。 60算法与数据结构现实世

29、界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。6162626363 有关树的几个概念根结点、叶子结点、结点的孩子与父结点、结点的度、树的度、结点的层次、树的深度、子树、森林等。6464 二叉树(binary tree)是一种很有用的非线性结构。 二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别 称为该结点的左子树与右子树。 二叉树（Binary Tree）：因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论65656666性质1：二叉树的第k层上至多有2 k-1（i 1）个结点二叉树

30、的性质：423167891011121314155第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。67二叉树的性质：性质2：深度为h的二叉树中至多含有2h-1个结点423167891011121314155此树的深度h=4，共有24-1=15个节点。68性质3：在任意一棵二叉树中，度为0的结点 （即叶子结点）总是比度为2的结点多一个。例1：某二叉树中度为2的结点有18个，则 该二叉树中有 19 个叶子结点。二叉树的性质：6969满二叉树与完全二叉树 满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树是指这样的二叉树：除最后一层外，每一层

31、上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 注意：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。算法与数据结构70 满二叉树的特点：每一层上都含有最大结点数。7171完全二叉树的特点：除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置7272 对于完全二叉树而言如果它的结点个数为偶数，则该二叉树中：叶子结点的个数=非叶子结点的个数如果它的结点个数为奇数，则该二叉树中：叶子结点的个数=非叶子结点的个数+1（即叶子结点数比非叶子结点数多一个）规律总结：算法与数据结构73 例题讲解1、设一棵完全二叉树共有700个结点，则在该二叉树中有 350 个叶子结

32、点。2、在深度为5的满二叉树中，叶子结点的 个数为（ C ） A) 32 B) 31 C) 16 D) 15算法与数据结构 74二叉树的存储 二叉树通常采用链式存储结构。存储结点由两部分组成：数据域、指针域。其中指针域有两个：左指针域、右指针域 因此二叉树的链式存储结构也称为二叉链表7575二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点。 二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。 设访问根结点记作V；遍历根的左子树记作L；遍历根的右子树记作R； 前序： VLR（即根左右） 中序： LVR（即左根右） 后序： LRV（即左右根）767677771、设一棵二叉树的中序遍历结果为DBEAFC, 前序遍历结果为ABDECF，则后序遍历结 果为： DEBFCA 例题讲解2、已知一棵二叉树前序遍历和中序遍历分别 为ABDEGCFH和DBGEACHF，则该二叉树 的后序遍历为（ B ） A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 783、具有3个结点的二叉树有（ D ） A) 2种形态 B) 4种形态 C) 7种形态 D) 5种形态 4、 设有下列二叉树：