国二公共基础知识研究报告.pptx

公共基础知识 算法与数据结构 程序设计基础 软件工程 数据库基础 1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义 3．栈的定义及其运算、线性链表的存储方式 4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5．查找 6．排序 第一章算法与数据结构 一、算法的基本概念 1、算法：解题方案的准确而完整的描述，包括解决问题的方法和步骤 。 算法≠程序≠计算方法 2、算法的基本特征： ⑴可行性：算法中描述的操作都是可以通过已经实现的基本运算的有限次数来实现 ⑵确定性：算法的每个步骤必须明确定义，不允许有多义性。 ⑶有穷性：指算法必须能在有限的时间内做完(即算法的运行时间有限)。 ⑷拥有足够的情报：指运算对象的初始输入要完备且正确 1.1 算法 二、算法复杂度 1、时间复杂度：执行算法所需要的计算工作量 2、空间复杂度：执行算法所需要的内存空间（存储空间）。 注意：1）时间复杂度通过算法所执行的基本运算次数来度量 2）空间复杂度的内存空间主要用于： 内存空间 算法程序 初始数据 运行过程中所需的额外空间 执行过程的工作单元 附加空间 3）时间复杂度和空间复杂度不相关 4）算法的效率与问题的规模和数据的存储结构都是息息相关的。 算法习题 (1)算法是指（ ） A.查询方法 B.交工方法 C.解题方案的准确而完整的描述 D.排序方法 (2)算法的有穷性是指： A.算法程序的运行时间是有限的 B.算法程序所处理的数据量是有限的 C.算法程序的长度是有限的 D.算法程序只能被有限的用户使用 (3)算法的时间复杂度是指（ ） A.算法的执行时间 B.算法所处理的数据量 C.算法程序中的语句或指令数 D.算法在执行过程中所需要的基本运算次数 (4)下列叙述中正确的是（ ） A.一个算法的空间复杂度大，则其时间复杂度也必定大 B.一个算法的空间复杂度大，则其时间复杂度也必定小 C.一个算法的时间复杂度大，则其空间复杂度也必定大 D.上述三种说法都不对 1.2 数据结构 一、数据结构的基本概念 1、数据结构：是抽象地研究数据的组织形式及其相互关系的一门学科。 数据的结构分为： （1）物理结构：也被称为“存储结构”，是指数据在计算机存储介质中真正存储的结构。 （2）逻辑结构：反映数据元素之间逻辑关系的数据结构 2、数据结构研究的主要内容：逻辑结构、物理结构（即 存储结构）和算法。 注意：逻辑结构和物理结构没有必然的联系，也不一定是一一对应的。 二、数据的逻辑结构： 反映数据元素之间逻辑关系的数据结构。 1、线性结构： ⑴有且仅有一个根结点 ⑵每个结点最多只有一个前件，也最多只有一个后件。例如： 主要有线性表、栈、队列、串等。 前后件关系 2、非线性结构： 该结构中一个结点可能有多个前件或后件。主要有树和图等。 三、数据的存储结构 指数据的逻辑结构在计算机存储空间中的存放形式（逻辑结构在计算机中的表示） 1、顺序存储：逻辑上相邻的数据元素，在物理存储位置上也相邻。 2、链式存储：逻辑上相邻的元素其物理位置不一定相邻，元素间的逻辑关系由附加的指针字段表示。 注意：1）一种逻辑结构可以表示成多种存储结构 2）存储结构影响数据处理的效率 例题：下列叙述中正确的是： A、程序执行效率与数据的存储结构密切相关 B、程序执行效率只取决于程序的控制结构 C、程序执行效率只取决于所处理的数据量 D、以上三种说法都不对 1.3、线性表 1、线性表的定义 线性表是n（n≥0）个数据元素a1，a2，……，an 的有序集合。线性表是一种线性结构，每个元素在表中的位置仅取决于元素本身的序号。n为线性表的长度，n为0的表称为空表。 学号 姓名 语文 数学 计算机 980001 张三 70 80 69 980002 吴军 89 76 98 980003 王平 87 87 76 980004 李帆 76 86 89 无后件 无前件 特点： ⑴线性表中所有元素所占的存储空间是连续的 ⑵线性表中各数据元素在存储空间中是按照逻辑顺序依次存放的 ⑶可以随机访问 缺点：插入和删除运算不方便；由于要求占用连续的存储空间，存储分配只能预先进行 2、线性表的存储结构 （1）线性表的顺序存储结构：当线性