公共基础知识要点.doc

公共基础知识要点
第一章数据结构与算法
一、算法
1、算法的基本特征
(1)可行性
(2)确定性
(3)有穷性有限的时间内做完,有限个步骤之后终止
(4)拥有足够的情报
2、算法的基本要素
(1)对数据对象的运算与操作
(2)算法的控制结构
通常,计算机可以执行的基本操作是以指令的形式描述的
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成
3、算法的复杂度
主要包括时间复杂度和空间复杂度
算数的时间复杂度
所谓算法的时间复杂度,是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法执行的基本运算次数还与问题的规模有关。
算数的空间复杂度
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
二、数据结构的基本概念
数据结构主要研究和探讨以下三个方面的的问题:
数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
对各种数据结构进行的运算。
数据的逻辑结构
所谓数据结构实际上就是指数据元素之间的前后件关系
一个数据结构应包含以下两方面的信息:
表示数据元素的信息
表示各数据元素之间的前后件关系
所谓数据的逻辑结构,是指反应数据元素之间逻辑关系的数据结构。
2、数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数据元素的信息,还要存放各数据元素之间的前后件关系的信息。
一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。
3、线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构于非线性结构。
如果一个非空的数据结构满足下列两个条件:
有且只有一个根结点;
每一个结点最多有一个前件,也最多有一个后件。
在一个线性结构中插入或删除任何一个结点后还应是线性结构
则称该数据结构为线性结构为线性结构,线性结构又称线性表。
如果一个数据结构不是线性结构,则称之为非线性结构。
三、线性表及其顺序存储结构
1、线性表的基本概念
线性表是由n(n>=0)个数据元素a1、a2……an组成的一个有序数列。
非空线性表有如下一些结构特征:
有且只有一个根结点a1,它无前件;
有且只有一个终端结点an,它无后件;
除根结点和终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
2、线性表的顺序存储结构
在计算机中存放线性表,一种最简单的方法是顺序存储,也称为顺序分配。
线性表的顺序存储结构具有以下两个基本特点:
线性表中所有元素所占的存储空间是连续的;
线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储空间。
3、