文档介绍：全国计算机二级公共基础知识要点
考试方式
1、 公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。公共基础部分占全卷的30分 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系
C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进
算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。
时间复杂度和空间复杂度
数据结构
数据结构的定义
数据的逻辑结构和存储结构
数据结构的图形表示
线性结构与非线性结构
数据结构研究的主要内容
(1)数据集中数据之间的逻辑关系
线性
树
图
(2)数据的存储结构
(3)各种数据结构的运算
能输入到计算机中
并能被计算机程序处理的
符号的集合。
整数(1,2)、实数(,)
字符串(Beijing)、
图形、声音。
基本概念和术语
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
计算机管理图书问题
在图书馆里有各种卡片：有按书名编排的、
有按作者编排的、有按分类编排
如何将查询图书的这些信息存入计算机中
既要考虑查询时间短，又要考虑节省空间
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
最简单的办法之一是建立一张表，
每一本书的信息在表中占一行，如
如何将0,1,2,3,4,5,6,7,8,9这10个数存放在
计算机中能最快地达到你所需要的目的？
目的不同，最佳的存储方方法就不同。
从大到小排列：9,8,7,6,5,4,3,2,1,0
输出偶数：0,2,4,6,8,1,3,5,7,9
数据元素在
计算机中的表示
数据结构是一门研究数据组织、存储和运算的一般方法的学科。
对数据结构中的节点进行
操作处理
(插入、删除、修改、查找、排序)
（1）数据元素(Data Element)
数据元素是数据的基本单位，即数据集合中的个体。
有时一个数据元数可由若干数据项(Data Item)组成。数据项是数据的最小单位。
数据元素亦称节点或记录。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B．非线性结构
A 顺序存储
B 链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面
数据结构可描述为 Group=（D，R）
（2）逻辑结构
有限个数据元素的集合
有限个数据元素间关系的集合
线性
树
图
常用数据结构:
(A , B , C , ······· ，X ,Y , Z)
例:学生成绩表
86
胡孝臣
9861103
95
刘忠赏
9861107
100
张卓
9861109
成绩
姓名
学号
①线性表
②栈——后进先出
③队列——先进先出
例:英文字母表
数据结构S=(D,R)
D={春,夏,秋,冬}
R={<春,夏>,<夏,秋>,<秋,冬>}
什么型的数据结构?
用图形工具
春
夏
秋
冬
线性结构
①树形结构
例:全校学生档案管理的组织方式
例:计算机文件管理系统也是典型的树形结构
B．非线性结构
1
4
2
3
例:数据结构B(D,R)
D={ 1 , 2 , 3 , 4}
R={(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) }
2
1
3
例:数据结构C(D,R)
D={ 1 , 2 , 3 }
R={ <1,2>, <2,3>, <3,2>, <1,3>}
②图形结构
元素n
……..
元素i
……..
元素2
元素1
Lo
Lo+m
Lo+(i-1)*m
Lo+（n-1)*m
存储地址
存储内容
Loc(ai)=Lo+（i-1)*m
1、顺序存储
每个元素所占用
的存储单元个数
（3）存储结构
例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang)
顺序存储结构：
存储地址
数据
7
8
9
10
11
12
13
14
zhao
qian
sun
li
zhou
wu
zheng
wang
7
基地址
顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有