当前位置：文档之家 › 计算机二级公共基础知识 PPT

计算机二级公共基础知识 PPT

  • 格式：ppt
  • 大小：579.00 KB
  • 文档页数：119

下载文档原格式

  / 119

合集下载

全国计算机等级考试之二级公共基础知识PPT课件( 124页)

全国计算机等级考试之二级公共基础知识PPT课件( 124页)

元素2 153 6
元素3 134 6
存储地址 存储内容
指针
1345
元素1
1400
1346
元素4
∧
…….
…….. …….
1400
元素2
1536
…….
…….. …….
1536
元素3
1346
元素4 ∧
h
链式存储
1345
元素1 140
元素2 153 元素3 134
0
6
6
链接存储结构特点：
元素4 ∧
1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针愈组成)。
图形结构
的
三 个
2、数据的存储结构 A 顺序存储
方 面
(亦称物理结构) B 链式存储
3、数据的运算：检索、排序、插入、删除、修改等。
图形结构——节点间的连结是任意的
1 2
4 3
D={ 1 , 2 , 3 , 4} R={(1,2) , (1,3) , (1,4) , (2,3)
(3,4) , (2,4) }
△ 人与计算机交流的语言非平常人与人之间 交流的语言，是专门的语言——程序设计 语言。
△ 程序设计语言是计算机系统软件的重要组成 部分。
△ 执行程序设计的语言有很多，可分高级语言 和低级语言，区别在于接近自然语言的程度
△ 高级语言一般与具体的计算机硬件无关，比 较接近人类自然语言的语法习惯及数学表达 形式。
1
2
3
D={ 1 , 2 , 3 } R={ (1,2) , (2,3) , (3,2) , (1,3) }
线性表
A．线性结构 栈
队 1．数据的逻辑结构

全国计算机等级考试二级公共基础知识(应试版) ppt课件

全国计算机等级考试二级公共基础知识(应试版) ppt课件
点； 性质3：在任意一棵二叉树中，度为0的结
点（即叶子结点）总是比度为2的结点多一个。 性质4：具有n个结点的二叉树，其深度至
少为［log2n］+1。
考点 二叉树及其基本性质 19
3、满二Байду номын сангаас树与完全二叉树 满二叉树: 除最后一层外，每一层上的
所有结点都有两个子结点。 一棵深度为k 且有2k -1个结点的二叉树。
（特点：每层都“充满”了结点）
A
B
C
D
E
F
G
H IJK
L MN O
深度为4的满二叉树
20
完全二叉树: 除最后一层外，每一层上的结点 数均达到最大值；在最后一层上只缺少右边的 若干结点。
深度为k 的，有n个结点的二叉树，当且仅当其
每一个结点都与深度为k 的满二叉树中编号从1
至n的结点一一对应。
完全二叉树的特点就是，只有最后一层叶子不
是否会认为老师的教学方法需要改进？ • 你所经历的课堂，是讲座式还是讨论式？ • 教师的教鞭 • “不怕太阳晒，也不怕那风雨狂，只怕先生骂我
笨，没有学问无颜见爹娘 ……” • “太阳当空照，花儿对我笑，小鸟说早早早……”
2．算法复杂度 算法复杂度包括时间复杂度和空间复杂度。
考点 算法的复杂度
5
1.2 数据结构
考点 线性结构和非线性结构
8
在一个线性结构中插入或删除任何一个 结点后还应是线性结构。
栈、队列、字符串等都是线性结构。
数组、广义表、树和图等数据结构都是 非线性结构。
P153
9
1.3 栈
栈限定只在一端进行插入与删除的线性 结构（表）。在栈中，一端是封闭的，既不 允许进行插入元素，也不允许删除元素；另 一端是开口的，允许插入和删除元素。通常 称插入、删除的这一端为栈顶，另一端为栈 底。当表中没有元素时称为空栈。

全国计算机等级考试二级_公共基础知识精品PPT课件

全国计算机等级考试二级_公共基础知识精品PPT课件
4.数据的运算：检索、排序、插入、删除、修改等。
14
三、线性表 线性表是最简单的、最常用的一种线性结构。 1.线性表的定义:线性表是n个元素的有限序列，它们
之间的关系可以排成一个线性序列：a1，a2，…… ，ai，…… ，an ，其中n称作表的长度，当n=0 时，称作空表。 线性表（非空线性表）必须同时满足以下3个条件： （1）有且只有一个根结点a1，它无前件。 （2）有且只有一个终端结点an，它无后件。 （3）除根结点与终端结点外，其他所有结点有且只 有一个前件，也有且只有一个后件。
线性表的定义、线性表的顺序存储结构及其插入与删除运算。
栈和队列的定义、栈和队列的顺序存储结构及其基本运算。
线性单链表、双向链表与循环链表的结构及其基本运算。
树的基本概念，二叉树的定义及其存储结构，二叉树的前序、 中序和后序遍历。
顺序查找与二分法查找算法、基本排序算法（交换类排序、选 择类排序与插入类）。
8
A.二元关系表示方法：一个数据结构可以表示为B=（ D、R），其中R用二元组来表示(a、b)。 a表示前 件， b表示后件。 例如，一年四季的数据结构可以表示成: B=（D、R） D={春，夏，秋，冬} R={（春，夏），（夏，秋），（秋，冬）}
B.在图形表示方法中，用中间标有元素值的方框来表示 数据元素，称为数据结点，简称为结点；用一条有 向线段从前件结点指向后件结点（注意：有时可以 省略箭头）来表示元素之间的前后关系。
16
例：正确表示线性表(A1，A2，A3，A4)的顺序结 构是( )
二级公共基础知识
二级公共基础知识
第一章 算法与数据结构 第二章 程序设计基础 第三章 软件工程基础 第四章 数据库设计基础
2
本章要求

最新二级公共基础知识ppt课件

最新二级公共基础知识ppt课件

➢ 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某 个学生的信息，按条件检索某个学生的信息等。
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
二级公共基础知识
第一章 算法与数据结构
返回

全国计算机等级考试二级公共基础知识精品PPT课件

全国计算机等级考试二级公共基础知识精品PPT课件

二级公共基础知识
11
一、算法
全国计算机等级考试
National Computer Rank Examination
5、在计算机中，算法是指（ B ）
A) 加工方法
B) 解题方案的准确而完整的描述
C) 排序方法
D) 查询方法
6、下列叙述中正确的是（ B ）
A) 算法的效率只与问题的规模有关，而与数据的存储结构无关。
全国计算机等级考试
二级公共基础知识
8
一、算法
全国计算机等级考试
National Computer Rank Examination
算法的基本要素： （1）对数据对象的运算和操作： A .算术运算 B .逻辑运算 C .关系运算 D .数据传输 （2）算法的控制结构： A .顺序结构 B .选择结构 C .循环结构
全国计算机等级考试
National Computer Rank Examination
算法
算法的定义 算法的特征 算法的基本要素 算法复杂度
数据结构的定义
数据结构
逻辑结构 和 物理结构
线性结构 和 非线性结构
顺序表、链表、堆栈 队列、循环队列、树
全国计算机等级考试
二级公共基础知识
7
一、算法
全国计算机等级考试
数据 结构
数据本身
数据之间的 前后件关系
数据结构表示为：DS={D，S} 例：D={春，夏，秋，冬}
S={(春,夏)，(夏,秋)，(秋,冬)，(冬,春)}
全国计算机等级考试
二级公共基础知识
13
二、数据结构
全国计算机等级考试
National Computer Rank Examination

全国计算机等级考试二级公共基础知识课件版

全国计算机等级考试二级公共基础知识课件版
需求分析
通过与用户交流，了解其需求 和业务规则，为设计提供依据 。
逻辑设计
将概念设计转化为逻辑模型， 确定表、字段及约束。
数据库设计概述
根据用户需求，规划、创建和 管理数据库的过程。
概念设计
使用概念模型进行设计，确定 实体、属性及关系。
物理设计
确定数据的物理存储结构，如 文件类型、存储路径等。
2023-2026
查找
查找定义
查找是从数据结构中找出特定元素的过程。
查找算法
常见的查找算法包括顺序查找、二分查找等。
查找效率
查找效率取决于数据结构的类型和数据的分布情况。
排序
排序算法
常见的排序算法包括冒泡排序、插入排序、 快速排序等。
排序定义
排序是将一组数据按照某种规则排列的过程 。
排序效率
排序效率取决于排序算法的时间复杂度和数 据量的大小。
PART 04
数据库设计基础
数据库基本概念
数据库
是长期存储在计算机内的、有组织的、可共享的数 据集合。
数据模型
是抽象表示现实世界数据和数据间关系的数据结构 。
数据库管理系统
是管理数据库的系统软件，用于建立、使用和维护 数据库。
数据模型
概念模型
用图形方式（如实体-联系图）表示数据概念及数 据间关系。
二叉树定义
二叉树是一种特殊的树，每个节点最多有两个子 节点。
二叉树性质
二叉树的性质包括二叉树的遍历、二叉树的平衡 等。
图
01
图定义
图是由节点和边组成的集合，表 示对象之间的关系。
图遍历
02
03
Байду номын сангаас
图的应用

全国计算机等级考试二级共公基础知识(NCRE-2-P)教案(ppt文档)


1.1 算法
1.1.1 算法的基本概念
算法：对解题方案准确而完整的描述 1、算法的特征
可行性 确定性 有穷性（可能完成、合理时间） 拥有足够的情报
2、算法的基本要素
（1）对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输 （2）算法的控制结构：控制结构（顺序、选择、循环），描述工具（传统流程图、N-S流
1.3.2 线性表的顺序存储结构
线性表顺序存储的特点：
存储空间是连续的 元素在存储空间按逻辑顺序存放
采用顺序存储的线性表的主要运算有：
插入、删除、查找、排序、分解、合并、复制、逆转
1.3.3 顺序表的插入运算
在第i个元素之前插入新元素时，需要移动n-i+1个元素 在存储空间满的情况下插入新元素，将发生上溢错误 效率：平均移动一半的元素（第1位置全移动，最后位置不用动）
退栈：删除元素，使top-1。Top=0(栈空)时将发生下溢错误
读栈顶元素：
7
入栈 退栈 6 ↓ ↑5
top→ D
4
CHale Waihona Puke 3B2bottom → A
1
1.4.2 队列及其基本运算
队列：
允许在一端进行插入、另一端进行
删除的线性表
退队←
特征：FIFO
循环队列及其运算：
标志：
s=0 队列空 s=1 队列非空
2、算法的空间复杂度（指执行这个算法所需的内存空间）
1.2 数据结构的基本概念
数据结构涉及三方面问题：
数据的逻辑结构：数据元素间固有逻辑关系
35
16
数据的存储结构：数据元素在计算机中的存储关系 对各种数据结构进行的运算
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。
1.2 数据结构的基本基本概念
数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有
为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为
[log2n]+1,其中[log2n]表示取log2n的整数部分； （5）具有n个结点的完全二叉树的深度为
[log2n]+1；
二叉树的基本性质：
（6）设完全二叉树共有n个结点。如果从根结点开始， 按层序（每一层从左到右）用自然数1，2，….n给结 点进行编号（k=1,2….n），有以下结论：
计算机二级公共基础知识
公共基础知识
数据结构与算法 数据库设计基础 程序设计基础 软件工程基础
第一章 数据结构与算法
1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法
的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则
对于长度为n的有序线性表，最坏情况只
需比较log2n次。
1．8 排序技术
排序是指将一个无序序列整理成按值非递减顺
序排列的有序序列。
交换类排序法：（1）冒泡排序法，需要比较 的次数为n(n-1)/2；（2）快速排序法需要比较 的次数为n(n-1)/2 。
插入类排序法：（1）简单插入排序法，最坏 情况需要n(n-1)/2次比较；（2）希尔排序法， 最坏情况需要O(n^1.5)次比较。
二叉树的5种形态：
ø
(a)
(b)
(c)
(d)
(e)
图 5-7
完全二叉树与满二叉树
完全二叉树是指除最后一层外，每一层上的 结点数均达到最大值，在最后一层上只缺少 右边的若干结点。
在最后一层上与满二叉树相应层次编号为一 一对应，则称这棵二叉树为完全二叉树。
树的形态
A
(a)
(b)
A BB
A BC DE
栈与队列
栈与队列
相同点：都是线性结构
不同点：先进先出，后进先出
栈
队列
循环队列
为什么需要循环队列？ 计算循环队列长度
用一个固定大小为m的数组来实现， 那么队列中元素个数=(rear-front + m)%m
栈
典型应用
逆序输出 10进制转换2进制
用户名:jsj 密码:无
A
B (c)
A B C (g)
Figure 7-6 A collection of binary trees
A
B (d)
A B C
(h)
二叉树的基本性质：
（1）在二叉树的第k层上，最多有2k-1(k≥1) 个结点；
（2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度
情况 ； （5）输出：一个算法有一个或多个输出，以反映对输入数据加工
后的结果。
1.1 算法
算法的基本要素：一是对数据对象的运算和操作；二 是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运
算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、
树的遍历
1
1
1
2
32
3
Left subtree Right subtree
(a)先序遍历
(b)中序遍历
2
3
(c)后序遍历
二叉树的遍历：
（1）前序遍历（DLR），首先访问根结点，然 后前序遍历左子树，最后前序遍历右子树；
（2）中序遍历（LDR），首先中序遍历左子树， 然后访问根结点，最后中序遍历右子树；
根结点，叶子结点 度、深度、结点数 满二叉树，完全二叉树
树
在树结构中，一个结点所拥有的后件的 个数称为该结点的度
所有结点中最大的度称为树的度。 树的最大层次称为树的深度。
非线性结构
树
二叉树
二叉树
定义：二叉树是另一种树形结构。它与树形结 构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。
都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱
两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限
个步骤后终止，包括合理的执行时间的含义； （4）输入：一个算法有0个或多个输入 ，以刻画运算对象的初始
①若k=1，则该结点为根结点，它没有父结点；若 k>1，则该结点的父结点编号为INT(k/2)；
②若2k≤n，则编号为k的结点的左子结点编号为2k； 否则该结点无左子结点（也无右子结点）；
③若2k+1≤n，则编号为k的结点的右子结点编号为 2k+1；否则该结点无右子结点。
满二叉树是指除最后一层外，每一层上的所有结点有 两个子结点，则k层上有2k-1个结点深度为m的满二 叉树有2m-1个结点。
（3）后序遍历（LRD）首先后序遍历左子树， 然后后序遍历右子树，最后访问根结点。
B D
G
A C
先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA
E
F
H
1．7 查找技术
顺序查找的使用情况： （1）线性表为无序表； （2）表采用链式存储结构。 二分法查找只适用于顺序存储的有序表，
减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念
数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻
辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计
一个后件。 非线性结构：不满足线性结构条件的数据结构。
两种最基本的存储结构
顺序存储（数组）
两种最基本的存储结构
链表
不是顺序存储，用指针联系
单向链表，双向链表
效率高
单向链表
双向链表
大家应该也有点累了，稍作休息
大家有疑问的，可以询问和交流
大家有疑问的，可以询问和交流
可以互相讨论下，但要小声点