职业规划 公共营养师 计算机二级公共基础知识要点

计算机二级公共基础知识要点

为了方便计算机等级试,特意整理出来的。第一章数据结构与算法1算法是解题方案的准确而完整的描述,它不等于程序,也不等于计算方法。基本特征:可行性、确定性、有穷性、拥有足够的情报。2算法复杂度主要包括时间复杂度和空间复杂度。时间复杂度:用来衡量算法执行过程中所需要的基本运算次数。空间复杂度:用来衡量算法执行过程中所需要的存储空间。3数据结构研究的主要内容:(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算4研究数据结构的主要目的:提高数据处理的效率。5数据结构的定义:指相互关联的数据元素的集合。6数据的逻辑结构反映数据元素之间的逻辑关系,数据的存储结构是数据的逻辑结构在计算机存储空间的存放形式。同一种逻辑结构可以采用不同存储结构,但影响数据处理效率。7数据结构分为两大类型:线性结构与非线性结构常见线性结构:线性表、栈、队列、线性链表常用非线性结构:树、二叉树、图8线性表示由n(n>=0)个相同类型的数据元素构成的有限序列。结构特征:(1)数据元素在表中的位置由序号决定,数据元素之间的相对位置是线性的(2)对于一个非空线性表,有且只有一个根节点a1,它无前件,有且只有一个终端结点an,它无后件,除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。基本存储结构:(1)顺序存储(2)链式存储9顺序表的插入运算时需要移动元素,在等概率情况下,平均需要移动n/2个元素。10进行顺序表的删除运算时也需要移动元素,在等概率情况下,平均移动(n-1)/2个元素。11栈只能在栈顶插入或删除元素,是一种先进后出FILO(或称为后入先出LIFO)的线性表。12队列是只能从队尾插入元素,在队头删除元素,是一种先进先出FIFO(或后入后出LILO)的线性表。13线性链表不能随机存取。14在线性链表中插入元素时,不需要移动数据元素,只需要修改相关结点指针即可,也不会出现“上溢”现象。15在线性链表中删除元素时,也不需要移动数据元素,只需要修改相关结点指针即可。16循环链表实单链表基础上增加了一个表头结点,其插入和删除运算与单链表相同,可以从任意结点出发来访问表中其他所有结点,并实现空表与非空表的运算。17一般二叉树通常采用链式存储结构,对于满二叉树与完全二叉树来说,可以按层序进行顺序存储。18二分查找知识用于顺序存储的线性表,对于无序线性表和线性表的链式存储结构只能用顺序查找。19冒泡排序是每一趟都会把较小的元素先前移动,最坏比较次数是n(n-1)/2。20简单插入排序法是将无序序列中的各元素依次插入到已经有序的线性表中,最坏比较次数为n(n-1)/2。21希尔排序法的基本思想:将无序序列划分成若干个子序列(又相隔某个增量h的元素组成)分别进行直接插入排序,待整个序列中的元素基本有序(增量足够小)时,在对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的。22选择排序每一趟都是找出无序序列中的最小一个元素,最坏比较次数为n(n-1)/2。23排序技术:(1)交换排序法:冒泡排序、快速排序(2)插入排序法:简单插入排序法、希尔排序(3)选择排序法:简单选择排序法、堆排序法

本文来自网络,不代表职业规划立场,转载请注明出处:http://www.vocationoops.com/zyl/ggyys/25338.html
返回顶部