计算机科学导论整理

计算机科学导论整理第一章：1.二进制转换：1.十进制整数转换为二进制整数十进制整数转换为二进制整数采用除2取余，逆序排列法。具体做法是：用2去除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为零时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。2．十进制小数转换为二进制小数要点：乘二取整，正序排列解释：对被转换的小数乘以2，取其整数部分(0或1)作为二进制小数部分，取其小数部分，再乘以2，又取其整数部分作为二进制小数部分，然后取小数部分，再乘以2，直到小数部分为0或者已经去到了足够位数。每次取的整数部分，按先后次序排列，就构成了二进制小数的序列。0.2乘以2，取整后小数部分再乘以2，运算4次后得到的整数部分依次为0、0、1、1，结果又变成了0.2，若果0.2再乘以2后会循环刚开始的4次运算，所以0.2转换二进制后将是0011的循环，即：(0.2)10=(0.001100110011.....)2循环的书写方法为在循环序列的第一位和最后一位分别加一个点标注。2.八进制：二进制转换为八进制方法：取三合一法，即从二进制的小数点为分界点，向左（向右）每三位取成一位，接着将这三位二进制按权相加，得到的数就是一位八位二进制数，然后，按顺序进行排列，小数点的位置不变，得到的数字就是我们所求的八进制数。如果向左（向右）取三位后，取到最高（最低）位时候，如果无法凑足三位，可以在小数点最左边（最右边），即整数的最高位（最低位）添0，凑足三位。例①将二进制数101110.101转换为八进制得到结果：将101110.101转换为八进制为56.53.十六进制：二进制转换为十六进制方法：取四合一法，即从二进制的小数点为分界点，向左（向右）每四位取成一位，接着将这四位二进制按权相加，得到的数就是一位十六位二进制数，然后，按顺序进行排列，小数点的位置不变，得到的数字就是我们所求的十六进制数。如果向左（向右）取四位后，取到最高（最低）位时候，如果无法凑足四位，可以在小数点最左边（最右边），即整数的最高位（最低位）添0，凑足四位。①例：将二进制11101001.1011转换为十六进制得到结果：将二进制11101001.1011转换为十六进制为E9.B数值的原码表示是指，将最高位用作符号位（0表示正数，1表示负数），其余各位代表数值本身的绝对值（以二进制形式表示）的表示形式。例如，+9的原码是00001001└→符号位上的0表示正数-9的原码是10001001。└→符号位上的1表示负数所谓原码就是前面所介绍的二进制定点表示法，即最高位为符号位，“0”表示正，“1”表示负，其余位表示数值的大小。反码表示法规定：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。补码表示法规定：正数的补码与其原码相同；负数的补码是在其反码的末位加1。循环移位：逻辑移位：将所有的单位向后移一位并将多出来的末尾数填充至第一位。算术移位：不将多出来的一位填充，以0代替。逻辑运算：And有0则为0，or有1则为1，xor相同则为0不同则为1.CPU中央处理器，计算机中控制数据操控的电路。有三部分构成：算术逻辑单元：包含在数据上执行运算（加法或减法）的电路。控制单元：包含协调及其活动的电路。寄存器单元：包含称为寄存器的数据存储单元（与主存单元相似）用作CPU内部的信息临时存储。储存器为了存储数据计算及包含大量的电路，每一个电路能够存储单独的一个位。一个存储单元容量是一个字节=一个八位的串。只读存储器（英语：Read-OnlyMemory，简称：ROM）。ROM所存数据，一般是装入整机前事先写好的，整机工作过程中只能读出，而不像随机存储器那样能快速地、方便地加以改写。ROM所存数据稳定，断电后所存数据也不会改变；其结构较简单，读出较方便，因而常用于存储各种固定程序和数据。随机存取存储器（英文：randomaccessmemory，RAM）又称作“随机存储器”，是与CPU直接交换数据的内部存储器，也叫主存(内存)。它可以随时读写，而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。存储单元的内容可按需随意取出或存入，且存取的速度与存储单元的位置无关的存储器。这种存储器在断电时将丢失其存储内容，故主要用于存储短时间使用的程序。按照存储单元的工作原理，随机存储器又分为静态随机存储器（英文：StaticRAM，SRAM)和动态随机存储器（英文DynamicRAM，DRAM)。第二章：第三章：多任务处理：，多任务是指一个用户同时执行多项任务分时处理：是指多个用户同时访问一台机器。假脱机技术含义：即外围设备联机并行操作，它除了是一种速度匹配技术外、也是一种虚拟设备技术。用一种物理设备模拟另一类物理设备，使各作业在执行期间只使用虚拟的设备，而不直接使用物理的独占设备。这种技术可使独占的设备变成可共享的设备，使得设备的利用率和系统效率都能得到提高。将一台独享打印机改造为可供多个用户共享的打印机，是应用SPOOLing技术的典型实例。具体做法是：系统对于用户的打印输出，但并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中；然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。Ram：随机存取存储器（英文：randomaccessmemory，RAM）又称作“随机存储器”，是与CPU直接交换数据的内部存储器，也叫主存(内存)。它可以随时读写，而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。Rom：ROM是只读存储器（Read-OnlyMemory）的简称，是一种只能读出事先所存数据的固态半导体存储器。其特性是一旦储存资料就无法再将之改变或删除。通常用在不需经常变更资料的电子或电脑系统中，并且资料不会因为电源关闭而消失。Blos：英文BasicInputOutputSystem的缩略词，直译过来后中文名称就是基本输入输出系统。其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。虚拟存储：据程序执行的互斥性和局部性两个特点，我们允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好像计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。进程状态：反映进程执行过程的变化。这些状态随着进程的执行和外界条件的变化而转换。进程状态分为五个基本状态，即初始状态，就绪状态，执行状态，等待状态与终止状态。操作系统分成四大部分：驱动程序：最底层的、直接控制和监视各类硬件的部分，它们的职责是隐藏硬件的具体细节，并向其他部分提供一个抽象的、通用的接口。内核：操作系统内核部分，通常运行在最高特权级，负责提供基础性、结构性的功能。接口库：是一系列特殊的程序库，它们职责在于把系统所提供的基本服务包装成应用程序所能够使用的编程接口（API），是最靠近应用程序的部分。外围：是指操作系统中除以上三类以外的所有其他部分，通常是用于提供特定高级服务的部件。例如，在微内核结构中，大部分系统服务，以及UNIX/Linux中各种守护进程都通常被划归此列。操作系统组件：外壳（shell）：与机器环境进行通信。文件管理程序：协调机器的海量存储器的使用。设备驱动程序：处理与机器的外围设备的通信。内存管理程序：协调机器主存的使用。调度程序：协调系统中的进程。分派程序：控制进程的CPU时间的分配操作系统如何防止进程间相互访问：如果一个进程需要资源，需要对操作系统提出请求，要求访问资源。这时，操作系统必须根据资源是否被其他的进程占用来决定是否批准这个请求。如果被占用，那么这个操作系统应该批准这个请求，并允许该进程执行；否则，操作系统应当拒绝这个请求，也许吧这个进程归为等待进程，直到资源可用为止。如果有两个进程同时获得资源的访问权，那么这两个程序都是不可取的。进程：在操作系统的控制下执行某个程序的活动程序：程序，是指为了得到某种结果而可以由计算机等具有信息处理能力的装置执行的代码化指令序列，或者可以被自动转换成代码化指令序列的符号化指令序列或者符号化语句序列。程序是指令的集合，而进程是遵循这些指令的操作。第四章：1.网络面临的威胁：恶意软件（病毒，蠕虫，特洛伊木马和间谍软件），Dos（拒绝服务），垃圾邮件2.2.网址的格式：主机名+域名+目录+文件名称3.3.邮箱的格式：用户名@域名4.4.IP地址的格式：IP地址由四个用小数点隔开的十进制整数(0--255)组成的。实际上一个IP地址是一个32位的二进制数。每8个位可以用一个十进制整数数字来表示5.5.TCP/IP协议的含义及功能：TCP/IP是一组专业化协议，包括IP、TCP、UDP、ARP、ICMP以及其它的一些被称为子协议的协议。6.功能：TCP/IP协议是一个协议族，主要功能是为网络传输提供服务。TCP/IP协议分为4层，链路层、传输层、网络层和应用层。每一层完成不同的功能，共同作用完成网络传输服务。其中，下面的3层：链路层、传输层、网络层主要是完成网络传输的，只有应用层对用户来说可见7.6.公钥加密体系的含义：公钥加密，加密、解密用的是不同的密钥，一个密钥“公开”，即公钥，另一个自己秘密持有，即私钥，加密方用公钥加密，只有用私钥才能解密——史称公钥加密体系：PKI。：第五章：算法是定义一个可终止过程的一组有序的、无歧义的、可执行的步骤的集合。②素数的含义只能被1和这个数本身整除的整数，如2、3、5、7、11。③会画流程图一个流程图包括：1.表示相应操作的框；2.带箭头的流程线；3.框内外必要的文字说明。1.顺与结构2.选择结构3.循环结构三种基本结构的共同特点：1.只有一个入口；2.只有一个出口；3.结构内的每一部分都有机会被执行到；4.结构内不存在闭环。④算法分析包含哪些情况1.逐步求精这种方法本质上不是试图立即解决整个问题，而是首先把一个手头的问题看作多个问题。我们可以按照步骤通过解决各个子问题来最后解决整个问题，其中每一步都比解决完整的问题要更容易。2.自底向上法与逐步求精法相反。⑤参数之间的传递在C++中实现的传递是值传递。⑥顺序查找与平均查找1.顺序查找：在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。2.平均查找：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。第六章：1.语法和语义的区别一种语言是合法句子的集合。什么样的句子是合法的呢？可以从两方面来判断：语法和语义。语法是和文法结构有关，然而语义是和按照这个结构所组合的单词符号的意义有关。合理的语法结构并不表明语义是合法的。例如我们常说：我上大学，这个句子是符合语法规则的，也符合语义规则。但是大学上我，虽然符合语法规则，但没有什么意义，所以说是不符合语义的。2.递归的过程及意义并能计算结果栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程，称做递归过程。递归是程序设计中一个强有力的工具。概述编辑一个直接调用自己或通过一系列的过程调用语句间接调用自己的过程，称