计算机二级公共基础知识.pptVIP

计算机二级公共基础知识

二级ACCESS—数据库基础知识本章的重要性经统计本章在理论考试中占10%左右即4个左右的选择题。本章在考试中只涉及笔试题目，上机不考。

二级ACCESS—数据访问页关键考点顺序存储与链式存储的基本概念栈、队列的基本概念与基本操作循环队列元素个数的计算算法时间、空间复杂度的概念几种查找与排序的比较次数二叉树的遍历二叉树结点个数的计算

基本数据结构与算法1.1算法算法的基本概念算法：解题方案的准确而完整的描述。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。基本特性(P1)可行性：根据实际问题设计的算法，执行得到满意结果确定性：每一步骤必须有明确定义，不允许有多义性。有穷性：算法必须能在有限的时间内做完。拥有足够的情报：输入和输出，方可执行。

基本数据结构与算法1.1算法算法的复杂度：时间复杂度、空间复杂度算法的时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)算法空间复杂度算法空间复杂度是指执行这个算法所需要的内存空间。存储空间包括：①算法程序所占的空间、②输入数据所占的空间、③算法执行过程中所需要的额外空间。。

基本数据结构与算法数据结构主要研究以下三个方面的问题数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系）数据的存储结构：各数据元素在计算机中的存储关系对各种数据结构进行的运算主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。数据结构研究的主要内容

基本数据结构与算法数据元素(DataElement)数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项(DataItem)组成。数据项是数据的最小单位。数据元素亦称节点或记录。1.2数据结构的基本概念

基本数据结构与算法1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构类型

基本数据结构与算法线性结构和非线性结构线性结构条件（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。（3）首节点无前件，尾节点无后件。非线性结构：不满足线性结构条件的数据结构注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号

基本数据结构与算法线性结构和非线性结构全校学生档案管理的树形结构的组织方式非线性结构树形结构

基本数据结构与算法Lo+（n-1)*m元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m每个元素所占用的存储单元个数顺序存储与链式存储顺序存储常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点插入或删除操作时，需移动大量元数。长度变化较大时，需按最大空间分配。表的容量难以扩充

基本数据结构与算法每个节点都由两部分组成：数据域和指针域。数据域：存放元素本身的数据，指针域：存放指针，体现数据元素之间的逻辑联系顺序存储与链式存储1536元素21400元素11346元素3∧元素4head1345链接存储结构特点比顺序存储结构的存储密度小(每个节点都由数据域和指针愈组成)。逻辑上相邻的节点物理上不必相邻。插入、删除灵活(不必移动节点，仅改变节点中的指针)。链接存储结构

基本数据结构与算法1346元素31536…….……..…….1536元素21400…….……..…….∧元素413461400元素11345指针存储内容存储地址1536元素21400元素11346元素3∧元素4head1345顺序存储与链式存储链式存储的地址映射表

基本数据结构与算法1.3线性表线性表的基本概念线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。非空线性表的结构特征有且只有一个