搜索
第一章1、信息的概念（1）信息是对现实世界中存在的客观实体、现象、关系进行描述的数据；（2）信息是消息；（3）信息是知识；（4）信息是经过加工后并对实体的行为产生影响的数据。数据的概念：是现实世界客观存在的实体或事物的属性值，表现为人们感官听到的事实和看到的景象；2、数据和信息的关系信息是有一定含义的数据；信息是经过加工（处理）后的数据；信息是对决策有价值的数据；3、信息产品的三个层次：数据——数据采集，用于事物处理系统；信息——数据处理，用于管理信息系统；知识——信息融合，用于决策支持系统。4、信息技术（informationtechnology，IT）主要由计算机硬件技术、计算机软件技术和通信技术三大部分组成。5、硬件系统：由运算器、控制器、存储器、输入设备、输出设备组成；其中，运算器和控制器合为中央处理器，简称CPU；6、计算机系统定义为有硬件系统和软件系统两部分组成；7、软件和程序区别软件（software）：是指计算机程序、方法、规则的文档以及在计算机上运行它时必须数据的集合。程序（program）：为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合；是人们求解问题的逻辑思维活动的代码化描述；程序的要便于阅读、交流。软件按功能分为系统和应用软件8、系统软件控制与协调计算机及外设，支持应用软件的开发和运行的软件系统。包括操作系统、编译程序、诊断程序、系统服务程序、语言处理程序、数据库管理系统和网络管理程序等。一般是在计算机系统购买时随机携带的，也可以根据需要另行安装；系统软件的主要特征是：与硬件有很强的交互性；能对资源共享进行调度管理；能解决并发操作处理中存在的协调问题；其中的数据结构复杂，外部接口多样化，便于用户反复使用。9、应用软件应用软件是为满足用户不同领域、不同问题的应用需求而提供的那部分软件。是直接服务于用户的软件系统；可分为通用性工具软件和专用软件；它可以拓宽计算机系统的应用领域，放大硬件的功能；应用软件具有无限丰富和美好的开发前景。10、软件危机体现软件开发进度难以预测；软件开发成本难以控制；用户对软件功能难以满足；软件产品质量无法保证；软件产品难以维护；软件通常缺少适当的文档资料11、三种语言的区别机器语言是机器指令的集合，其代码由0、1组成的二进制串表示，不需翻译可直接为机器所接受。汇编语言符号化的机器语言。它用助记符和标识符代替机器指令的操作码和地址码高级语言是一种与具体的计算机指令系统无关、独立于计算机类型、且表达方式接近于自然语言或数学语言、容易被人们掌握和书写的语言。如C，Pascal，java等。12、翻译程序是把甲种语言程序翻译为等价的乙种语言程序的程序。其中，甲种语言称为源语言。乙种语言称为目标语言。汇编程序若源语言是汇编语言，目标语言是机器语言，则该翻译程序被称为汇编程序。编译程序若源语言是高级语言，目标语言是汇编语言或机器语言，则该翻译程序被称为编译程序。解释程序是翻译程序的另一种形式，它对源程序的语句边解释边执行，不产生目标程序第二章算法和数据结构是程序的两个重要方面1、算法中某一具体语句在算法的运行过程中执行的次数即为该语句的频度，记做F(n)；时间复杂度是以算法中频度最大的语句来度量的，可记做T(n)=O(F(n))。2、算法的空间复杂度分析，是指对该算法在执行过程中所需辅助空间大小的分析。3、算法特性算法是对特定问题的求解步骤的一种描述，是指令的有限序列。作为算法，有以下几个基本特性：1）有穷性，每条指令执行的次数与时间都是有限的，必须在若干步之后终止；2）确定性，每条指令的含义明确，不能存在二义，即在相同条件下的结果唯一；3）可行性，算法所描述的操作可以通过有限的基本操作实现；4）输入，算法应当有0个或多个输入；5）输出，算法也应当有1个或多个输出。算法描述算法描述即用某种描述语言或方法来表达算法，或选用某一种高级语言在计算机上实现。常用的算法描述语言有：1）自然语言描述，即用人们日常使用的语言来描述算法；2）程序流程图描述，即用一组几何图形表示各种类型的操作，在图形上用扼要的文字和符号表示具体的操作，并用带有箭头的流线表示操作的先后次序。4迭代法一般用于求方程的近似根的算法设计5、递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。6、在递归的定义中至少要有一条是非递归的，做为递归的终止条件，即边界条件。第三章1、数据结构（datastructure)：数据元素和数据元素关系的集合，是指同一数据对象中个数据元素间存在的关系。数据元素（dataelement）：是数据的基本单位，是数据集合中的一个个体；亦称节点（node）或记录（record）；数据（data)：是信息的载体，是可以用计算机表示并加工的各种“符号”的集合；数据项（dataitem）：有独立含义的数据最小单位，也称域(field)；数据对象（dataobject）：有相同性质的数据元素的集合；2、数据结构研究的主要问题1）数据的逻辑结构：是指数据元素及其关系的数学特性，反映数据之间的逻辑关系。三种基本结构:线性结构:数据元素存在着线性(一对一)的关系；树形结构:数据元素存在着层次(一对多)的关系；图形结构:数据元素存在着任意(多对多)的关系。2）数据的存储结构：数据在计算机内部的存储方式。3）数据的操作：数据的操作即是对数据进行的处理***3、数据结构的三个方面1.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等4、线性表的存储结构采用顺序存储结构，称之为顺序表，亦为向量；5、顺序表和链表的比较（1）线性表的长度顺序表的存储空间是静态分配的，故其上、下界是固定的，若执行过程中表长需要发生变化（插入、删除），就要留足空间，从而产生浪费，又可能因为不足而使表产生溢出。在表长经常发生变化时，采用链表很方便。（2）线性表的主要操作顺序表连续存放，可随机存取表中任何记录，适于频繁的查找操作的表，但是进行插入、删除、移动时，就很不方便。链表进行查找时，只能顺序从首指针起，比较浪费时间，但是插入、删除运算时，只需要较小的时间就可完成，但是其每一数据元素，多一指针域，浪费存储空间。（3）高级语言实现有些高级语言不支持指针，自然只能采用顺序表。6、堆栈定义：限定只能在表的一端进行插入和删除运算的特殊的线性表。其集合论的定义方法与线性表基本相同。7、队定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。为什么使用循环队列：为了解决假溢出问题8、循环队列：将头尾连接成一个环，形成的队列就是循环队列9、数组概念数组是线性表的推广，可以将之看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。10、稀疏定义：非零元较零元少，且分布没有一定规律的矩阵。11、为了便于通过三元组法访问稀疏矩阵中的元素，通常附设两个向量POS和NUM，称为行辅助向量伪地址表示法是通过本元素在矩阵中（含0元素）按行优先顺序的相对位置12、带行指针向量的单链表设置一个行指针向量，向量中每个元素为一个指针，指向本行矩阵的第一个非0元素节点，若本行无非0元素，则指针为空。矩阵中每一个非0元素由三个数据域，列、元素值以及指向本行下一个非0结点的指针，同一行的非0元素构成一个单链表。13、树的常用术语结点（Node）：树中的元素，含数据项及若干指向其子树的指针；结点的度（Degree）：结点拥有的子树数。树中最大结点的度数称为树的度数；结点的层次（Level）：从根结点开始算起，根为第一层；叶子（Leaf）：度为零的结点，也称端结点；孩子（Child）：结点子树的根称为该结点的孩子结点；兄弟（Sibling）：同一双亲的孩子；双亲（Parent）：孩子结点的上层结点；深度（Depth)：树中结点的最大层次数。森林（Forest）：M棵互不相交的树的集合。有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树，反之，称为无序树。14、结点同构型：每个结点的指针域数目均为树的度数。运算方便，浪费空间。15二叉树定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。16、二叉树的基本性质1）二叉树的第i层上至多有2i-1（i1）个结点；2）深度为h的二叉树中至多含有2h–1个结点；3）若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1。17、1）满二叉树特点：深度为h且含有2h-1个结点的二叉树，为满二叉树。图示满二叉树，结点编号为自上而下，自左而右。2）完全二叉树特点：指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，完全一致，则为完全二叉树。3）平衡二叉树特点：又称AVL树，它或为一棵空树，或具如下性质：其左子树和右子树都是平衡二叉树，且左、右子树的深度之差的绝对值不超过1。左、右子树的深度之差为平衡因子，平衡二叉树的平衡因子只能为0，-1，1。18、一般树转换为二叉树由于二叉树常常用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。为此，给定一棵树，可以找到唯一的一棵二叉树与之对应。1）普通树转换为二叉树的方法：对每个孩子进行自左至右的排序；在兄弟之间加一条连线；对每个结点，除了左孩子外，去除其与其余孩子之间的联系；以根结点为轴心，将整个树顺时针转45度19、遍历二叉树的应用1）.建立一棵二叉树在遍历过程生成结点，建立二叉树的存储结构，用链式存储结构2）统计二叉树中叶子结点的个数3）由遍历序列恢复二叉树20、哈夫曼树及其应用（WPL1、哈夫曼树（Huffman)最优树：是带权的路径长度最短的树，常用于信息检索；路径长度：从一个结点到另一结点之间经过的分支数目称为这对结点间的路径长度；树的路径长度：从树根到每一结点的路径长度之和，用PL表示；结点带权的路径长度：为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：为树中叶子结点带权路径长度之和。记作：其中：Wk为树中每个叶子结点的权；Lk为每个叶子结点到根的路径长度。WPL最小的二叉树就称作最优二叉树或哈夫曼树。2、哈夫曼树的构造过程例：给定权值{7，5，2，4}，构造哈夫曼树。1）根据给的n个权值{w1,w2,········，wn}构造n棵二叉树的集合F={T1,T2,········，Tn},每棵二叉树仅有一个带权为wi的根结点；2)在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。且规定左子树根结点的权值小于右子树根结点的权值；3）将新的二叉树加入到森林F中，去除原两棵权值最小的树；4）重复2、3步骤，直至F中只剩一棵树为止。4、哈夫曼编码哈夫曼编码---利用哈夫曼树构造通讯中的电文编码（前缀码）。例：要传输的电文是{CAS；CAT；SAT；AT}，要传输的字符集是:D={C，A，S，T，；}，字符出现的频率分别是W={2，4，2，3，3}21、图的基本概念图(Graph)：图G是由两个集合V(G)和E(G)组成的,记为G=(V,E），其中：V(G)是顶点的非空有限集；E(G)是边的有限集合，边是顶点的无序对或有序对；有向图：有向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头，（v,w)!=(w,v)。无向图：无向图G是由两个集合V(G)和E(G)组成的，其中：V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)。22、、图的相关术语权：与图的边或弧相关的数叫权(Weight），可以表示从一个顶点到另一个顶点的距离或耗费；带权的图叫网；子图：图G(V,E)和图G’(V’,E’),若V’V，E’E，则称G’为G的子图；顶点的度