大学计算机—基于计算思维知识点.docx

大学计算机基础知识点第一章 计算思维与计算机1、三大科学思维理论思维（以数学为基础的理论思维）、实验思维以物理为基础的实验思维、计算思维2、计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动. 3、计算思维的本质：抽象+自动化4、计算机是一种能存储程序和数据，自动执行程序、快速而精确地完成对各种数字化信息处理的电子设备5、1946年(美)宾夕法尼亚大学第一台数字电子计算机 ENIAC诞生。6、按照计算机所使用的逻辑部件将计算机的发展分为四代： 第一代：(1946-1957) 电子管时代 第二代：(1958-1964) 晶体管时代第三代：(1965-1970) 中小规模集成电路 第四代：(1971至今) 大规模、超大规模集成电路(出现网络，使用面日益广泛)7、存储程序的工作原理是：在计算机中设置存储器，将程序和数据存放到存储器中，计算机按照程序指定的逻辑顺序依次取出存储器中的内容进行处理，直到得出结果。 计算机有两个基本能力：一是能够存储程序和数据 二是能够自动地执行程序程序(Program) ：是指可以连续执行的一条条指令的集合指令(Instruction) ：是指计算机完成某一种操作的命令指令是一组二进制代码操作码：指出进行什么操作地址码：是规定操作数的值或地址、操作结果的地址及下一条指令的地址等l第二章n 数制（Numbering System）即表示数值的方法，有进位计数制和非进位计数制两种 n 进位计数制的基本特点如下: 使用固定个数的数码表示数值的大小 逢R进一 采用位权表示法 数制的转换二进制、八进制、十六进制和十进制之间的转换信息的存储单位（位、字节）除字节外，还有千字节(KB)、兆字节(MB)、吉字节(GB)、太字节(TB)，拍字节(PB)。它们的换算关系原码、反码、补码之间的转换ASCII（American Standard Code for Information Interchange）码，即美国标准信息交换代码。在这种编码方案中，用八位二进制（一个字节）来存放一个字符，常用字符有128个，编码从0到127ASCII码无需记忆，只要了解0-9依次升高，a-z依次升高就可以 汉字的编码：区位码、国标码、机内码的转换字形码所占字节的计算第三章u 微处理器也叫中央处理单元(CPU)，主要由运算器和控制器组成，是任何微型计算机系统中必备的核心部件。u 内存储器 u 内存储器按其工作方式的不同，可以分为随机存取存储器(RAM)、只读存储器(ROM) 。u ROM是只能读出信息而不能由用户写入信息的存储器，断电后，其中的信息也不会丢失。 u RAM是指在CPU运行期间既可读出信息也可写入信息的存储器，但断电后，写入的信息会丢失。u 注意：CPU只能直接对内存进行读写，而不能直接读写外存 为了解决主存RAM与CPU工作速度不匹配的问题，在CPU和主存之间设置了一级高速度、小容量的存储器，称之为高速缓冲存储器l 外存储器即外存，其主要作用是长期存放计算机工作所需要的系统文件、应用程序、用户程序、文档和数据等。外存中存储的程序和数据必须先送入内存，才能被计算机执行。l 总线(BUS)是连接微机中各个部件的一组物理信号线，用于各部件之间的信息传输。l 一次传输信息的位数称为总线宽度。 按照总线上传送信息类型的不同，可将总线分为数据总线、地址总线和控制总线。控制总线(CB)：用控制总线来传送控制信号地址总线(AB)：通常地址总线是单向的。地址总线的宽度与所寻址的范围有关，即地址总线的位数决定了CPU可直接寻址的内存空间大小，一般来说，若地址总线为n根，则可寻址空间为2n字节比如8位微机的地址总线为16根，则其最大可寻址空间为21664KB数据总线(DB)：是CPU同各部件交换信息的通路。数据总线都是双向的。 BIOS:实际上就是微机的基本输入输出系统（Basic InputOutput System），其内容集成在微机主板上的一个ROM芯片上，主要保存着有关微机系统最重要的基本输入输出程序，系统信息设置、开机上电自检程序和系统启动自举程序等。 计算机软件是指为了充分发挥计算机硬件的效能和方便用户使用计算机而设计的各种程序和数据的总和。软件分为：系统软件、应用软件系统软件是指控制计算机的运行，管理计算机的各种资源，并为应用软件提供支持和服务的一类软件操作系统(operating system)，它管理和控制计算机系统中的硬件及软件资源，为用户提供一个功能强大、使用方便且可扩展的工作环境，它是配置在计算机硬件上的第一层软件，是对硬件功能的扩充 应用软件是指用户为了解决各种实际问题而开发和研制的软件，它在系统软件的支持下运行 第四章算法的特性：确定性、可行性、有穷性、有零个或多个输入、有一个或多个输出 算法的描述 图形符号 符号名称 说 明 起始、终止框 表示算法的开始或结束 输入、输出框 框中标明输入、输出的内容 处理框 框中标明进行什么处理 判断框 框中标明判定条件并在框外标明判定后的两种结果的流向 流程线 表示从某一框到另一框的流向 连接点 表示算法流向出口或入口连接点 用自然语言表示：就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来 用流程图表示：就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法 用程序设计语言表示 常量与变量 常量：在程序执行过程中，其值不发生改变的量称为常量 变量：在程序运行过程中，其值可以改变的量称为变量。 一个变量有一个名字 ，变量通过其名字来访问 变量的访问主要有“读”和“写”两种操作 运算符 ：用于告知计算机对数据进行操作的类型、方式和功能 表达式 :用运算符将运算对象（操作数或另一个表达式）连接起来的、符合语法规则的式子称为表达式。控制语句对应的三种结构：顺序结构、选择结构、循环结构常用算法：极值算法、求和算法、枚举算法、迭代算法第五章数据结构包括以下三方面内容： 逻辑结构、存储结构、和对数据的操作 v 逻辑结构：数据元素之间逻辑上的关系，数据的组织形式。简称为数据结构.v 数据的逻辑结构具体可分为四类： 集合 线性结构 树型结构 图状结构存储结构：数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。一般地，一个存储结构包括以下两个主要部分存储结点(简称结点),每个结点存放一个数据元素 数据元素之间关系的表示，也就是逻辑结构的计算机内部表示线性表: 是n(nO)个同类型数据元素(结点)的有穷序列。其中数据元素的个数n称为线性表的长度(简称表长)。表长为O的线性表称为空表。表示成：(a1，a2 ，an) 线性表逻辑结构的基本特征: 存在唯一的一个被称为“第一个”的数据元素和唯一的一个被称为“最后一个”的数据元素； 除第一个数据元素外，其他数据元素有且仅有一个直接前趋元素； 除最后一个数据元素外，其他数据元素有且仅有一个直接后继元素线性表的顺序存储结构顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素特点：逻辑结构中相邻的结点在存储结构中仍相邻在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化(1) 插入：在表的第i(1in+1)个位置上，插入一个新结点x，使线性表的长度加1 。基本步骤为： 将结点aian各后移一个位置,以便空出第i个位置； 将新结点x置入第i个位置； 表长加l删除：将表的第i(1in)个结点删去，使线性表的长度减1。基本步骤为： 结点ai+1an依次前移一个位置(覆盖被删结点ai)； 表长减1单链表是用一组任意的存储单元来存放线性表的结点。 单链表的结点(每个存储单元)由数据域(data)和指针域(next)两部分组成；数据域用于存储线性表一个数据元素；指针域用于存放一个指针，该指针指向其直接后继结点。这样，所有结点通过指针链接起来,因此链表中结点的逻辑次序和物理次序不一定相同 特点：指针为数据元素之间的逻辑关系的映像栈的逻辑结构和线性表相同，但是，栈(Stack)是仅限在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底,表中无元素时为空栈栈的运算原则是“先进后出” 插入运算称为进栈(或入栈) 删除运算称为退栈(或出栈)基本运算为： 入栈、出栈、取栈顶元素队列(Queue)，两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队头(front)，允许插入的一端称为队尾 (real)队列(Queue)，两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队头(front)，允许插入的一端称为队尾 (real)树是n(n0)个结点的有限集合。在任意一棵非空树中: 有且仅有一个特定的称为根的结点： 当nl时，其余结点分为m(m0)个互不相交的非空集合T1，T2，Tm，其中每一个集合本身又是一棵树，并称为根的子树。 树是一种“分支层次”结构。“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”； “层次”是指树上所有结点可以按它们的层数划分成不同的“层次度:树上任一结点所拥有的子树的数目称为该结点的度。 叶子或终端结点:度为0的结点称为叶子或终端结点。 非终端结点或分支结点:度大于O的结点称为非终端结点或分支结点。 树的度:一棵树中所有结点的度的最大值称为该树的度。 若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子或子结点。 父结点相同的结点互称为兄弟。 一棵树上的任何结点(不包括根本身)称为根的子孙。反之，若B是A的子孙，则称A是B的祖先 (3)结点的层数(或深度)从根开始算起：根的层数为l，其余结点的层数为其双亲的层数加l。一棵树中所有结点层数的最大值称为该树的高度或深度二叉树：是结点的有穷集合，它或者是空集，或者同时满足下述两个条件： 有且仅有一个称为根的结点； 其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且Tl与T2有顺序关系(T1在T2之前)，它们分别称为根的左子树和右子树。二叉树的每个结点至多只有两棵子树，并且这两棵子树之间有次序关系。二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子二叉树的基本性质 二叉树第i(i1)层上至多有2i-1个结点。 深度为k(k1)的二叉树至多有2k-1个结点。 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2+1。q 满二叉树 一棵深度为k(k1)且有2k -1个结点的二叉树称为满二叉树，这种树的特点是每一层上的结点数都是最大结点数。q 完全二叉树 深度为k(k1)有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1in)的结点x有： 若i=l，则结点x是根，无双亲；若i1，则x的双亲结点P的编号为i/2。 若2*in，则结点x无左孩子(且无右孩子)；否则，x的左孩子的编号为2*i。 若2*i+1n，则结点x无右孩子；否则，x的右孩子的编号为2*i+1二叉树的顺序存储 将一棵树中的所有n个结点按层编号，将编号为i的结点存入一维数组的第i个单元。 若二叉树不是完全二叉树，则通过在非完全二又树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。 用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适二叉树的链式存储 结点结构中设两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针唯一确定的二叉树的遍历：就是按某种次序“访问”二叉树上的所有结点，使得每个结点被访问一次，而且仅被访问一次。 二叉树是由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。限定先左后右，则遍历有先根(序)、中根(序)和后根(序)遍历二分查找(折半查找) 对于任何一个顺序表，若其中的所有结点按键值的某种次序排列，则称为有序表。二分查找法的基本思想是：每次将处于查找区间中间位置上的数据元素的键值x与给定值K比较，若不等则缩小查找区间(若K比中间值大则舍弃下半部分，若K比中间值小则舍弃上半部分)并在新的区间内重复上述过程，直到查找成功或查找区间长度为0(即查找不成功)为止。直接插入法排序：依次将每个记录插入到一个有序的子序列中去冒泡法排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。完成第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟冒泡排序，直至排序结束直接选择排序：的记录中再选出键值最小的记录与第二个记录交换；依次类推，直至所有记录排序完成。在第i趟中，通过n-1次键值比较选出所需记录第六章 数据库：数据库(Database,简称DB)是长期储存在计算机内、有组织的、可共享的大量数据集合 数据库管理系统：数据库管理系统(DataBase Management System，DBMS)位于应用程序和操作系统之间，是为建立、使用和维护数据库而配置的一层数据管理软件，负责对数据库中的数据进行统一的管理和控制 数据库系统： (Data Base System，DBS)是指带有数据库的计算机系统。包括数据库、数据库管理系统、应用程序、数据库管理员以及用户等部分 数据的整体结构化 目前数据库以二维表的形式存在 数据的共享性高，冗余度低 数据的独立性高 数据的统一管理和控制 数据模型的组成要素 数据结构：所研究的对象类型的集合。 数据操作：对相应数据结构允许执行的操作的集合 数据的完整性约束：完整性规则是给定的数据模型中数据及其联系所具有的制约和依存规则，以保证数据的正确、有效和相容 概念模型（实体-联系数据模型） 实体：客观存在并可相互区别的事物称为实体(Entity)。实体可以是具体的人、事、物，也可以是抽象的概念或联系。 属性：实体的特性称为实体的属性(Attribute)。一个实体可以由若干个属性来刻画 联系：在现实世界中，事物内部以及事物之间是有联系的，这些联系在信息世界中反映为实体集内部的联系和实体集之间的联系。 一对一联系(1：1)如果对于实体集A中的每一个实体，实体集B中至多有一个实体与之联系，反之亦然，则称实体集A与B具有一对一联系，记为1：1 一对多联系(1：n)如果对于实体集A中的每一个实体，实体集B中有n个实体(n0)与之联系，反之，对于实体B中的每一个实体，实体集A中至多只有一个实体与之联系，则称实体集A与B具有一对多联系，记为1：n。 多对多联系(m：n) 如果对于实体集A中的每一个实体，实体集B中有n个实体(n0)与之联系，反之，对于实体集B中的每一个实体，实体集A中也有m个实体(m0)与之联系，则称实体集A与B具有多对多联系，记为m：n。 E-R图的表示： 实体型：用矩形表示，矩形框内写明实体名。 属性：用椭圆形表示，椭圆形内写明属性名，并用无向边将其与相应的实体连接起来。 联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体或联系连接起来，同时在无向边旁标上联系的类型 关系数据结构 基本术语如下： 关系(Relation)：一个关系对应一张二维表。 元组(Tuple)：表中的一行即为一个元组。 属性(Atturibute)：表中的一列即为一个属性，每一列的第一行是属性名，其余行是属性值。 候选码：表中的某个属性或属性组合，它可以唯一的标识一个元组 主码：在多个候选码中选择一个作为主码关系应满足如下性质：关系必须是规范化的，即要求关系必须满足一定的规范条件，其中最基本的一条就是，关系的每一列不可再分。关系中必须有主码，使得元组唯一。如学生关系中，学号属性是主码，课程关系中，编号是主码，选修关系中，学号和编号一起是主码 元组的个数是有限的且元组的顺序可以任意交换 属性名是唯一的且属性列的顺序可以任意交换 关系完整性规则 实体完整性规则 主码的属性值不能为空值。因为如果出现空值，那么主码就无法保证元组的唯一性。 参照完整性规则 关系之间的联系是靠公共属性实现的如果这个公共属性是一个关系R1的主码，那么在另一个与它有联系的关系R2中就称为外码参照完整性规则：外码的取值只有两种可能，要么是空值，要么等于R1中某个元组的主码值 逻辑结构设计 转换原则： 一个实体型转换为一个关系模式。 关系的属性：实体型的属性关系的码：实体型的码 一个m:n联系转换为一个关系模式。 关系的属性：与该联系相连的各实体的码以及联系本身的属性 关系的码：各实体码的组合 一个1:n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并。 1) 转换为一个独立的关系模式 关系的属性：与该联系相连的各实体的码以及联系本身的属性 关系的码：n端实体的码 ) 与n端对应的关系模式合并 合并后关系的性属：在n端关系中加入1端关系的码和联系本身的属性 合并后关系的码：不变 一个1:1联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并。 1) 转换为一个独立的关系模式 关系的属性：与该联系相连的各实体的码以及联系本身的属性 关系的候选码：每个实体的码均是该关系的候选码 与某一端对应的关系模式合并 合并后关系的属性：加入对应关系的码和联系本身的属性 合并后关系的码：不变第七章计算机网络是指利用通信线路和设备将分布在不同物理位置的许多自治计算机互连起来、并在网络软件系统的支持下实现资源共享和信息传递的系统。 网络的拓扑结构是指网络中通信线路和站点(终端结点或转发结点)的几何排列形式总线型：只有单一的通信线路(称为总线)，所有站点直接连接到这条总线上。环型：各个站点通过通信线路连接成一个闭合的环。在单条环路的环型网络中信息流向是单方向的 星型：有一个惟一的转接结点，各站点通过点到点的链路直接连接到转接结点上。树型：结点按层次进行连接。信息交换主要在上下层结点之间。树型网络中除了叶子结点之外的所有非终端结点都是转接结点 按照覆盖范围与规模分类 ：局域网（LAN）城域网(MAN)、广域网（WAN） 计算机网络的功能：数据通信、资源共享 根据计算机在网络中的作用可将计算机分为服务器和工作站 服务器是一种功能强大的高档计算机，构成与普通计算机基本相似，是计算机网络系统的核心设备，主要负责网络资源管理和用户服务 工作站是具有独立处理能力的计算机，即可以单独使用，也可以联网工作 网卡（NIC，Network Interface Card）：网络接口卡（简称网卡）又称为网络适配器（NIA，Network Interface Adapter），是计算机局域网中最重要的连接设备之一。网卡的作用是将计算机与通信设施相连接，将计算机的数字信号与通信线路能够传送的电子信号互相转换 网络协议(Protocol)是指在网络中的结点在进行数据交换时应满足的一些规则、约定与标准。一个网络协议由以下三要素组成： 语法：用户数据与控制信息的结构和格式； 语义：需要发出何种控制信息，以及完成的动作与做出的响应； 时序：对事件实现顺序的详细说明网络和网络可以通过路由器互