➢ 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某 个学生的信息，按条件检索某个学生的信息等。
25
❖ 应用举例2——家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。
1
12
21
312
132
123
321
231
213
图 1-1 特点：
家庭血缘关系图
➢ 在求解过程中，所处理的数据之间具有层次关系，这是我们
18
算法 与数 据结构
3、算法设计的基本方法
❖ 列举法 ❖ 归纳法 ❖ 递推 ❖ 递归（以简洁的形式设计和描述算法） ❖ 减半递推技术 ❖ 回溯法
19
算法 与数 据结构
二、算法的复杂度
1、时间复杂度
❖ 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。
❖ 一个算法是由控制结构（顺序、分支和循环）和原操 作构成的，算法时间取决于两者的综合效果。
对数据的讨论不单是数据本身，还要包括数据与数 据之间的关系。
24
❖ 应用举例1——学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学生信息。
学号 99070101 99070102 99070103 99070104
......
学 生 基 本 情 况
姓名 性别 出 生 年 月
李军 男 80． 12
进行了解，并掌握关系模型的数据结构、关系的操作和数据约束等知识； 3、了解关系模型的基本操作，掌握关系模型的基本运算及扩充运算； 4、了解数据库的设计与管理，掌握数据库设计的几个阶段的方法和特点。 9
二级公共基础知识
第一章 算法与数据结构
返回
16
算法 与数 据结构
一、算法
1、算法的基本概念
算法是对特定问题求解步骤的一种描述，它是指令的有 限序列，其中每一条指令表示一个或多个操作。它是一组严 谨地定义运算顺序的规则，并且每一个规则都是有效的，且 是明确的，此顺序将在有限的次数下终止。
√D) 分析算法的效率以求改进
❖ 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的 【 1 】 。【答案】:时间复杂度和空间复杂度
23
算法 与数 据结构
三、数据结构（ Data Structure）
1、数据结构研究的主要内容
❖ 当今计算机应用的特点： 1、所处理的数据量大且具有一定的关系； 2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。
21
算法 与数 据结构
3、例题讲解
❖ 算法的时间复杂度是指( C )
A、执行算法程序所需要的时间
B、算法程序的长度
√C、算法执行过程中所需要的基本运算次数
D、算法程序中的指令条数
❖ 算法的基本特征是可行性、确定性、 【1】和拥有足够
的情报。 【答案】:有穷性
❖ 算法的空间复杂度是指( D )
A) 算法程序的长度
二级公共基础知识ppt课件
公共基础知识考题特点及复习建议
一、涉及面广，但难度小
计算机等级二级理论考试中有关公共知识部分的题 目共有15道，涉及算法及数据结构、程序设计基础、软 件工程基础和数据库设计基础等四门学科，但是从整体 上分析，考试中的考核内容的难度不大，考点也相对集 中些。
2
学习 目标 与要求
所说的树形结构；
➢ 对它的操作有：建立树形结构，输出终结点内容等。
26
❖ 应用举例3——制定教学计划
在制定教学计划时，需要考虑各门课程的开设顺序。有些课 程需要先导课程，有些课程则不需要，而有些课程又是其他课程 的先导课程。比如，计算机专业课程的开设情况如下表所示：
计 算 机 专 业 学 生 的 必 修 课 程
王 颜 霞 女
81． 2
孙涛 男
80． 9
单 晓 宏 男
81． 3
......
......
......
...... ...... ....... ...... ...... ......
特点：
➢ 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一 张表格；
➢ 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们 所说的线性结构；
课 程 编 号
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
课 程 名 称
程 序 设 计 基 础 离 散 数 学 数 据 结 构 汇 编 语 言
算 法 分 析 与 设 计 计 算 机 组 成 原 理
编 译 原 理 操 作 系 统 高 等 数 学 线 性 代 数 普 通 物 理 数 值 分 析
B) 算法程序中的指令条数
C) 算法程序所占的存储空间
√D) 执行过程中所需要的存储空间
22
算法 与数 据结构
❖ 在计算机中，算法是指（ B ）
√ A) 加工方法 B) 解题方案的准确而完整的描述
C) 排序方法 D) 查询方法 ❖ 算法分析的目的是( D )
A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性
算法具有有穷性、确定性、可行性、输入和输出（拥有 足够的情报）等５个重要特性。
17
学习 目标 与要求
2、算法的基本要素
❖ 对数据对象的运算和操作： 算术运算、逻辑运算、关系运算、数据传输
❖ 算法的控制结构： ➢ 算法中各操作之间的执行顺序； ➢ 描述算法的工具通常有传统流程图、N-S结构化流程 图、算法描述语言等； ➢ 一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。
➢ 程序设计基础：
1、了解程序设计的方法，以及程序设计风格确立的一些因素，掌握程序 设计的基本规则；
2、了解结构化程序设计的基本原则，掌握结构化程序设计的基本结构与特点; 3、了解面向对象的程序设计方法，并理解面向对象方法的一些基本概念。
➢ 数据库系统：
1、了解数据库系统的基本概念，以及数据库系统的发展； 2、了解数据模型的基本概念，并对E-R模型、层次模型、网状模型和关系模型
❖ 算法中基本操作重复执行次数n和算法执行时间同步 增长，称作算法的时间复杂度。
20
算法 与数 据构
2、空间复杂度
❖ 一般是指执行这个算法所需要的内存空间。 ❖ 一个算法所占用的存储空间包括算法程序所占的空间、
输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。 ❖ 一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。