软件基础知识整理

《软件基础知识整理》由会员分享，可在线阅读，更多相关《软件基础知识整理（12页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 1、信息的概念、信息的概念 （1）信息是对现实世界中存在的客观实体、现象、关系进行描述的数据； （2）信息是消息； （3）信息是知识；（4）信息是经过加工后并对实体的行为产生影响的数据。 数据的概念：数据的概念： 是现实世界客观存在的实体或事物的属性值，表现为人们感官听到的事实和看到的景 象；2、数据和信息的关系、数据和信息的关系信息是有一定含义的数据；信息是经过加工（处理）后的数据； 信息是对决策有价值的数据； 3、信息产品的三个层次：信息产品的三个层次：数据 数据采集，用于事物处理系统；信息 数据处理，用于管理信息系统；知识 信息融合，用于决策支持系统。 4、信息技术（信息技

2、术（information technology，IT）主要由计算机硬件技术、计算机软件技术和通信技术三大部分组成。 5、硬件系统：硬件系统：由运算器、控制器、存储器、输入设备、 输出设备组成； 其中，运算器和控制器合为中央处理器，简称 CPU； 6、计算机系统定义为有硬件系统和软件系、计算机系统定义为有硬件系统和软件系统两部分组成；统两部分组成； 7、 软件和程序区别软件和程序区别 软件（software）：是指计算机程序、方法、规则的文档以及在计算机上运行它时必须 数据的集合。 程序（program）： 为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合； 是人们求解问题的逻辑

3、思维活动的代码化描述； 程序的要便于阅读、交流。 软件按功能分为系统和应用软件软件按功能分为系统和应用软件 8、系统软件、系统软件 控制与协调计算机及外设，支持应用软件的开发和运行的软件系统。包括操作系统、编译程序、诊断程序、系统服务程序、语言处理程序、数据库管理系 统和网络管理程序等。一般是在计算机系统购买时随机携带的，也可以根据需要另行安装；系统软件的主要特征是：与硬件有很强的交互性；能对资源共享进行调度管理；能解决并发操作处理中存在的协调问题；其中的数据结构复杂，外部接口多样化，便于用户反复使用。9、 应用软件应用软件 应用软件是为满足用户不同领域、不同问题的应用需求而提供的那部分软件。

4、是直接 服务于用户的软件系统；可分为通用性工具软件和专用软件；它可以拓宽计算机系统的应用领域，放大硬件的功能；应用软件具有无限丰富和美好的开发前景。 10、软件危机体现、软件危机体现 软件开发进度难以预测； 软件开发成本难以控制； 用户对软件功能难以满足； 软件产品质量无法保证； 软件产品难以维护； 软件通常缺少适当的文档资料 11、三种语言的区别、三种语言的区别 机器语言机器语言是机器指令的集合，其代码由 0、1 组成的二进制串表示，不需翻译可直接为机器 所接受。 汇编语言汇编语言符号化的机器语言。它用助记符和标识符代替机器指令的操作码和地址码 高级语言高级语言是一种与具体的计算机指令系统无

5、关、独立于计算机类型、且表达方式接近于自 然语言或数学语言、容易被人们掌握和书写的语言。如 C，Pascal，java 等。 12、翻译程序、翻译程序是把甲种语言程序翻译为等价的乙种语言程序的程序。其中，甲种语言称为 源语言。乙种语言称为目标语言。 汇编程序汇编程序若源语言是汇编语言，目标语言是机器语言，则该翻译程序被称为汇编程序。编译程序编译程序若源语言是高级语言，目标语言是汇编语言或机器语言，则该翻译程序被称 为编译程序。 解释程序解释程序是翻译程序的另一种形式，它对源程序的语句边解释边执行，不产生目标程 序第二章第二章算法和数据结构是程序的两个重要方面是程序的两个重要方面1、算法中某一具

6、体语句在算法的运行过程中执行的次数即为该语句的频度，记做频度，记做 F(n)；时间复杂度是时间复杂度是以算法中频度最大的语句来度量的，可记做 T(n) = O(F(n)。 2、算法的空间复杂度分析，是指算法的空间复杂度分析，是指对该算法在执行过程中所需辅助空间大小的分析。 3、算法特性算法特性 算法是对特定问题的求解步骤的一种描述，是指令的有限序列。作为算法，有以下几个基本特性：1）有穷性，）有穷性，每条指令执行的次数与时间都是有限的，必须在若干步之后终止；2）确定性，）确定性，每条指令的含义明确，不能存在二义，即在相同条件下的结果唯一；3）可行性）可行性，算法所描述的操作可以通过有限的基本操

7、作实现；4）输）输 入入，算法应当有 0 个或多个输入；5）输）输 出出，算法也应当有 1 个或多个输出。 算法描述算法描述 算法描述即用某种描述语言或方法来表达算法，或选用某一种高级语言在计算机上 实现。常用的算法描述语言有：常用的算法描述语言有：1）自然语言描述，）自然语言描述，即用人们日常使用的语言来描述算法；2）程序流程图描述，）程序流程图描述，即用一组几何图形表示各种类型的操作，在图形上用扼要的文 字和符号表示具体的操作，并用带有箭头的流线表示操作的先后次序。4 迭代法一般用于求方程的近似根的算法设计求方程的近似根的算法设计 5、递推法是利用问题本身所具有的一种递推关系求问题解的一种

8、方法。递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。 6、在递归的定义中至少要有一条是非递归的，做为递归的终止条件，即边界条件。在递归的定义中至少要有一条是非递归的，做为递归的终止条件，即边界条件。第三章第三章 1、数据结构（、数据结构（data structure)：数据元素和数据元素关系的集合，是指同一数据对象中个数据元素间存在的关系。数据元素（数据元素（data element）：）：是数据的基本单位，是数据集合中的一个个体；亦称节点（node）或记录 （record） ； 数据（数据（data)： 是信息的载体，是可以用计算机表示并加工的各种“符号”的集合； 数据项（数据

9、项（data item）：）：有独立含义的数据最小单位，也称域(field)；数据对象（数据对象（data object）：）：有相同性质的数据元素的集合；2、数据结构研究的主要问题数据结构研究的主要问题 1）数据的逻辑结构：是指数据元素及其关系的数学特性，反映数据之间的逻辑关 系。三种基本结构:线性结构: 数据元素存在着线性(一对一)的关系；树形结构: 数据元素存在着层次(一对多)的关系；图形结构: 数据元素存在着任意(多对多)的关系。2）数据的存储结构：数据在计算机内部的存储方式。3）数据的操作：数据的操作即是对数据进行的处理 *3、数据结构的三个方面、数据结构的三个方面 1.数据的逻辑结

10、构 2.数据的存储结构 3.数据的运算：检索、排序、插入、删除、修改等4、线性表的存储结构线性表的存储结构采用顺序存储结构，称之为顺序表，亦为向量亦为向量； 5、顺序表和链表的比较顺序表和链表的比较 （1）线性表的长度线性表的长度 顺序表的存储空间是静态分配的，故其上、下界是固定的，若执行过程中表长需要发 生变化（插入、删除） ，就要留足空间，从而产生浪费，又可能因为不足而使表产生溢 出。在表长经常发生变化时，采用链表很方便。 （2）线性表的主要操作线性表的主要操作 顺序表连续存放，可随机存取表中任何记录，适于频繁的查找操作的表，但是进行插 入、删除、移动时，就很不方便。链表进行查找时，只能顺

11、序从首指针起，比较浪费时间，但是插入、删除运算时， 只需要较小的时间就可完成，但是其每一数据元素，多一指针域，浪费存储空间。 （3）高级语言实现高级语言实现 有些高级语言不支持指针，自然只能采用顺序表。 6、堆栈定义：、堆栈定义：限定只能在表的一端进行插入和删除运算的特殊的线性表。其集合论的 定义方法与线性表基本相同。 7、队定义：、队定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行 删除的线性表。 为什么使用循环队列：为什么使用循环队列： 为了解决假溢出问题 8、循环队列：、循环队列：将头尾连接成一个环，形成的队列就是循环队列 9、数组概念、数组概念 数组是线性表的推广

12、，可以将之看成是一种特殊的线性表，即线性表中数据元素本身 也是一个线性表。 10、稀疏定义：、稀疏定义：非零元较零元少，且分布没有一定规律的矩阵。 11、为了便于通过三元组法访问稀疏矩阵中的元素，通常附设两个向量 POS 和 NUM，称为行辅助向量行辅助向量 伪地址表示法是伪地址表示法是通过本元素在矩阵中（含 0 元素）按行优先顺序的相对位置12、带行指针向量的单链表带行指针向量的单链表 设置一个行指针向量，向量中每个元素为一个指针，指向本行矩阵的第一个非 0 元素 节点，若本行无非 0 元素，则指针为空。矩阵中每一个非 0 元素由三个数据域，列、 元素值以及指向本行下一个非 0 结点的指针，

13、同一行的非 0 元素构成一个单链表。13、树的常用术语树的常用术语 结点（结点（Node）：）：树中的元素，含数据项及若干指向其子树的指针； 结点的度（结点的度（Degree）：）：结点拥有的子树数。树中最大结点的度数称为树的度数；结点的层次（结点的层次（Level）：）：从根结点开始算起，根为第一层； 叶子（叶子（Leaf）：）：度为零的结点，也称端结点； 孩子（孩子（Child）：）：结点子树的根称为该结点的孩子结点； 兄弟（兄弟（Sibling）：）：同一双亲的孩子； 双亲（双亲（Parent）：）：孩子结点的上层结点； 深度（深度（Depth)： 树中结点的最大层次数。 森林（森林（F

14、orest）：）：M 棵互不相交的树的集合。 有序树：有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树，反之，称 为无序树。14、结点同构型结点同构型：每个结点的指针域数目均为树的度数。运算方便，浪费空间。 15 二叉树定义：二叉树定义：二叉树是 n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两 棵分别称为左子树和右子树的互不相交的二叉树构成。 16、二叉树的基本性质二叉树的基本性质 1）二叉树的第 i 层上至多有 2i-1（i 1）个结点； 2）深度为 h 的二叉树中至多含有 2h 1 个结点； 3）若在任意一棵二叉树中，有 n0 个叶子结点，有 n2 个度

15、为 2 的结点，则：n0 = n2 + 1。 17、1）满二叉树）满二叉树 特点：深度为 h 且含有 2h-1 个结点的二叉树，为满二叉树。图示满二叉树，结点编号为自 上而下，自左而右。 2）完全二叉树）完全二叉树 特点：指深度为 k 的，有 n 个结点的，且每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应，完全一致，则为完全二叉树。 3）平衡二叉树）平衡二叉树 特点：又称 AVL 树，它或为一棵空树，或具如下性质：其左子树和右子树都是平衡二叉 树，且左、右子树的深度之差的绝对值不超过 1。左、右子树的深度之差为平衡因子，平 衡二叉树的平衡因子只能为 0，-1，1。 1

16、8、一般树转换为二叉树一般树转换为二叉树 由于二叉树常常用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉 树之间的关系。为此，给定一棵树，可以找到唯一的一棵二叉树与之对应。 1）普通树转换为二叉树的方法： 对每个孩子进行自左至右的排序； 在兄弟之间加一条连线； 对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 以根结点为轴心，将整个树顺时针转 45 度19、遍历二叉树的应用遍历二叉树的应用 1）.建立一棵二叉树建立一棵二叉树 在遍历过程生成结点，建立二叉树 的存储结构，用链式存储结构 2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数 3）由遍历序列恢复二叉树）由遍历序列恢复二叉树 20、哈夫曼树及其应用（哈夫曼树及其应用（WPL1、哈夫曼树 （Huffman) 最优树最优树：是带权的路径长度最短的树，常用于信息检索； 路径长度路径长度：从一个结点到另一结点之间经过的分支数目称为这对结点间的路径长度； 树的路径长度树的路径长度：从树根