计算机科学导论整理

1、计算机科学导论整理第1章 ：1. 二进制转换：1. 十进制整数转换为二进制整数 十进制整数转换为二进制整数采用"除2取余，逆序排列"法。具体做法是：用2去除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为零时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。 2十进制小数转换为二进制小数 要点：乘二取整，正序排列解释：对被转换的小数乘以2，取其整数部分(0或1)作为二进制小数部分，取其小数部分，再乘以2，又取其整数部分作为二进制小数部分，然后取小数部分，再乘以2，直到小数部分为0或者

2、已经去到了足够位数。每次取的整数部分，按先后次序排列，就构成了二进制小数的序列。0.2乘以2，取整后小数部分再乘以2，运算4次后得到的整数部分依次为0、0、1、1，结果又变成了0.2，若果0.2再乘以2后会循环刚开始的4次运算，所以0.2转换二进制后将是0011的循环，即：(0.2)10=(0.0011 0011 0011 .)2循环的书写方法为在循环序列的第一位和最后一位分别加一个点标注。2.八进制： 二进制转换为八进制 方法：取三合一法，即从二进制的小数点为分界点，向左（向右）每三位取成一位，接着将这三位二进制按权相加，得到的数就是一位八位二进制数，然后，按顺序进行排列，小数点的位置不变，

3、得到的数字就是我们所求的八进制数。如果向左（向右）取三位后，取到最高（最低）位时候，如果无法凑足三位，可以在小数点最左边（最右边），即整数的最高位（最低位）添0，凑足三位。例 将二进制数101110.101转换为八进制 得到结果：将101110.101转换为八进制为56.5 3.十六进制：二进制转换为十六进制 方法：取四合一法，即从二进制的小数点为分界点，向左（向右）每四位取成一位，接着将这四位二进制按权相加，得到的数就是一位十六位二进制数，然后，按顺序进行排列，小数点的位置不变，得到的数字就是我们所求的十六进制数。如果向左（向右）取四位后，取到最高（最低）位时候，如果无法凑足四位，可以在小数

4、点最左边（最右边），即整数的最高位（最低位）添0，凑足四位。 例：将二进制11101001.1011转换为十六进制 得到结果：将二进制11101001.1011转换为十六进制为E9.B 数值的原码表示是指，将最高位用作符号位（0表示正数，1表示负数），其余各位代表数值本身的绝对值（以二进制形式表示）的表示形式。例如，+9的原码是00001001 符号位上的0表示正数 -9的原码是10001001。 符号位上的1表示负数 所谓原码就是前面所介绍的二进制定点表示法，即最高位为符号位，“0”表示正，“1”表示负，其余位表示数值的大小。 反码表示法规定：正数的反码与其原码相同；负数的反码是对其原码逐位

5、取反，但符号位除外。 补码表示法规定：正数的补码与其原码相同；负数的补码是在其反码的末位加1。循环移位：逻辑移位：将所有的单位向后移一位并将多出来的末尾数填充至第一位。算术移位：不将多出来的一位填充，以0代替。逻辑运算：And有0则为0，or有1则为1，xor相同则为0不同则为1.CPU中央处理器，计算机中控制数据操控的电路。有三部分构成：算术逻辑单元：包含在数据上执行运算（加法或减法）的电路。控制单元：包含协调及其活动的电路。寄存器单元：包含称为寄存器的数据存储单元（与主存单元相似）用作CPU内部的信息临时存储。储存器为了存储数据计算及包含大量的电路，每一个电路能够存储单独的一个位。一个存储

6、单元容量是一个字节=一个八位的串。只读存储器（英语：Read-Only Memory，简称：ROM）。ROM所存数据，一般是装入整机前事先写好的，整机工作过程中只能读出，而不像随机存储器那样能快速地、方便地加以改写。ROM所存数据稳定 ，断电后所存数据也不会改变；其结构较简单，读出较方便，因而常用于存储各种固定程序和数据。随机存取存储器（英文：random access memory，RAM）又称作“随机存储器”，是与CPU直接交换数据的内部存储器，也叫主存(内存)。它可以随时读写，而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。存储单元的内容可按需随意取出或存入，且存

7、取的速度与存储单元的位置无关的存储器。这种存储器在断电时将丢失其存储内容，故主要用于存储短时间使用的程序。 按照存储单元的工作原理，随机存储器又分为静态随机存储器（英文：Static RAM，SRAM)和动态随机存储器（英文Dynamic RAM，DRAM)。第2章 ：第3章 ： 多任务处理：，多任务是指一个用户同时执行多项任务分时处理：是指多个用户同时访问一台机器。假脱机技术含义：即外围设备联机并行操作，它除了是一种速度匹配技术外、也是一种虚拟设备技术。用一种物理设备模拟另一类物理设备，使各作业在执行期间只使用虚拟的设备，而不直接使用物理的独占设备。这种技术可使独占的设备变成可共享的设备，使

8、得设备的利用率和系统效率都能得到提高。将一台独享打印机改造为可供多个用户共享的打印机，是应用SPOOLing技术的典型实例。具体做法是：系统对于用户的打印输出，但并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中；然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。Ram：随机存取存储器（英文：random access memory，RAM）又称作“随机存储器”，是与CPU直接交换数据的内部存储器，也叫主存(内存)。它可以随时读写，

9、而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。Rom：ROM是只读存储器（Read-Only Memory）的简称，是一种只能读出事先所存数据的固态半导体存储器。其特性是一旦储存资料就无法再将之改变或删除。通常用在不需经常变更资料的电子或电脑系统中，并且资料不会因为电源关闭而消失。Blos： 英文"Basic Input Output System"的缩略词，直译过来后中文名称就是"基本输入输出系统"。其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序

10、和系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。虚拟存储：据程序执行的互斥性和局部性两个特点，我们允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好像计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。进程状态：反映进程执行过程的变化。这些状态随着进程的执行和外界条件的变化而转换。进程状态分为五个基本状态，即初始状态，就绪状态，执行状态，等待

11、状态与终止状态。操作系统分成四大部分：驱动程序：最底层的、直接控制和监视各类硬件的部分，它们的职责是隐藏硬件的具体细节，并向其他部分提供一个抽象的、通用的接口。内核：操作系统内核部分，通常运行在最高特权级，负责提供基础性、结构性的功能。接口库：是一系列特殊的程序库，它们职责在于把系统所提供的基本服务包装成应用程序所能够使用的编程接口（API），是最靠近应用程序的部分。外围：是指操作系统中除以上三类以外的所有其他部分，通常是用于提供特定高级服务的部件。例如，在微内核结构中，大部分系统服务，以及UNIX/Linux中各种守护进程都通常被划归此列。操作系统组件：外壳（shell）：与机器环境进行通信

12、。 文件管理程序：协调机器的海量存储器的使用。 设备驱动程序：处理与机器的外围设备的通信。 内存管理程序：协调机器主存的使用。 调度程序：协调系统中的进程。 分派程序：控制进程的CPU时间的分配操作系统如何防止进程间相互访问：如果一个进程需要资源，需要对操作系统提出请求，要求访问资源。这时，操作系统必须根据资源是否被其他的进程占用来决定是否批准这个请求。如果被占用，那么这个操作系统应该批准这个请求，并允许该进程执行；否则，操作系统应当拒绝这个请求，也许吧这个进程归为等待进程，直到资源可用为止。如果有两个进程同时获得资源的访问权，那么这两个程序都是不可取的。进程：在操作系统的控制下执行某个程序的

13、活动程序：程序，是指为了得到某种结果而可以由计算机等具有信息处理能力的装置执行的代码化指令序列，或者可以被自动转换成代码化指令序列的符号化指令序列或者符号化语句序列。 程序是指令的集合，而进程是遵循这些指令的操作。 第4章 ：1.网络面临的威胁：恶意软件（病毒，蠕虫，特洛伊木马和间谍软件），Dos（拒绝服务），垃圾邮件2.2.网址的格式：主机名+域名+目录+文件名称3.3.邮箱的格式：用户名域名4.4.IP地址的格式：IP地址由四个用小数点隔开的十进制整数(0-255)组成的。实际上一个IP地址是一个32位的二进制数。每8个位可以用一个十进制整数数字来表示5.5.TCP/IP协议的含义及功能：

14、TCP/IP是一组专业化协议，包括IP、TCP、UDP、ARP、ICMP以及其它的一些被称为子协议的协议。6.功能：TCP/IP协议是一个协议族，主要功能是为网络传输提供服务。TCP/IP协议分为4层，链路层、传输层、网络层和应用层。每一层完成不同的功能，共同作用完成网络传输服务。其中，下面的3层：链路层、传输层、网络层主要是完成网络传输的，只有应用层对用户来说可见 7.6.公钥加密体系的含义：公钥加密，加密、解密用的是不同的密钥，一个密钥“公开”，即公钥，另一个自己秘密持有，即私钥，加密方用公钥加密，只有用私钥才能解密史称公钥加密体系：PKI。：第5章 ： 算法是定义一个可终止过程的一组有序

15、的、无歧义的、可执行的步骤的集合。 素数的含义 只能被1和这个数本身整除的整数，如2、3、5、7、11。 会画流程图 一个流程图包括：1.表示相应操作的框；2.带箭头的流程线；3.框内外必要的文字说明。1.顺与结构 2.选择结构3.循环结构三种基本结构的共同特点：1.只有一个入口；2.只有一个出口；3.结构内的每一部分都有机会被执行到；4.结构内不存在闭环。算法分析包含哪些情况1.逐步求精 这种方法本质上不是试图立即解决整个问题，而是首先把一个手头的问题看作多个问题。我们可以按照步骤通过解决各个子问题来最后解决整个问题，其中每一步都比解决完整的问题要更容易。2.自底向上法 与逐步求精法相反。参

16、数之间的传递在C+中实现的传递是值传递。顺序查找与平均查找 1.顺序查找：在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。 2.平均查找：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。第6章 ：1.语法和语义的区别一种语言是合法句子的集合。什么样的

17、句子是合法的呢？可以从两方面来判断：语法和语义。语法是和文法结构有关，然而语义是和按照这个结构所组合的单词符号的意义有关。合理的语法结构并不表明语义是合法的。例如我们常说：我上大学，这个句子是符合语法规则的，也符合语义规则。但是大学上我，虽然符合语法规则，但没有什么意义，所以说是不符合语义的。2.递归的过程及意义并能计算结果栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程，称做递归过程。递归是程序设计中一个强有力的工具。概述编辑一个直接调用自己或通过一系列的过程调用语句间接调用自己的过程，称作递归过程。当一个过程的运行期间调用另一个过

18、程时，在执行被调用过程之前，系统需先完成如下三件事：1、将所有的实在参数，返回地址等信息传递给被调用的过程保存。2、为被调用过程的局部变量分配存储空间。3、将控制转移到被调用入口。从被调过程返回调用过程1、保存被调用过程的计算结果。2、释放被调用过程的数据区。3、依照被调过程保存的返回地址将控制转移到调用过程。服从后调用先返回的原则。基本原理是重复的把原问题转换为相似的新问题，直到把问题解决为止。关键点：1、用较简单的问题来表示较复杂的问题。2、不能产生自己调用自己的无穷序列。即必须要有一个是递归出去的出口。递归的调用时通过栈来实现的。“递归”过程是指调用自身的过程。通常，这不是编写Visua

19、lBasic代码的最有效方法。其一，有很多数学函数是递归定义的，如大家熟悉的阶乘函数Fact（n）=1若n=1Fact（n）=n·Fact（n-1）若n>12阶Fibonacci数列Fib（n）=0若n=0Fib（n）=1若n=1Fib（n）=Fib（n-1）+Fib（n-2）其它情形和ackerman函数Ack（m，n）=n+1m=0Ack（m，n）=Ack（m-1，1）n=0Ack（m，n）=Ack（m-1，Ack（m,n-1）其它情形等；其二，有的数据结构，如二叉树，广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述；其三，还有一类问题，虽则问题本身没有明显的

20、递归结构，用递归求解比迭代求解更简单，如八皇后问题，Hanio塔问题等。限制条件。您在设计一个递归过程时，必须至少测试一个可以终止此递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理。如果没有一个在正常情况下可以满足的条件，则过程将陷入执行无限循环的高度危险之中。内存使用。应用程序的局部变量所使用的空间有限。过程在每次调用它自身时，都会占用更多的内存空间以保存其局部变量的附加副本。如果这个进程无限持续下去，最终会导致StackOverflowException错误。效率。几乎在任何情况下都可以用循环替代递归。循环不会产生传递变量、初始化附加存储空间和返回值所需的开销，因

21、此使用循环相对于使用递归调用可以大幅提高性能。相互递归。如果两个过程相互调用，可能会使性能变差，甚至产生无限循环。此类设计所产生的问题与单个递归过程所产生的问题相同，但更难检测和调试。调用时使用括号。当Function过程以递归方式调用它自身时，您必须在过程名称后加上括号（即使不存在参数列表）。否则，函数名就会被视为表示函数的返回值。测试。在编写递归过程时，应非常细心地进行测试，以确保它总是能满足某些限制条件。您还应该确保不会因为过多的递归调用而耗尽内存。第7章 ：软件危机(Software Crisis) 是计算机软件在它的开发和维护过程中所遇到的一系列严重问题。概括地说，主要包含两方面的问

22、题：如何开发软件，怎样满足对软件日益增长的需求；如何维护数量不断膨胀的已有软件。软件生命周期的四个阶段：四个阶段需求分析、设计、实施、运行和审计需求分析：主要目标：确定预期系统要提供的服务，这些服务的运行条件（如时间限制，安全性），以及定义外界与系统的交互方式。需求分析包括来自于其系统的利益相关者，（将来的使用者，还有其他有关连的人比如法律上和财务上的人）提供的重要数据。需求分析过程：编写和分析软件用户的要求；和项目的最终利益相关者协商，在一般需求、核心需求、费用和可行性之间权衡；最终确定的需求要明确最终的软件系统必须具有的特性和服务。设计：主要目标：制定问题的方案。实现：涉及程序的具体编写、

23、数据文件的穿件和数据库的开发。测试：本质上等同于调试程序和确认最终的软件产品是否与软件需求规格说明文档一致的过程。绘制借书还书的数据流图：图书馆文件借书流程在数据流图中，箭头表示数据路径，椭圆表示数据操控发生的地点，矩形表示数据源和数据存储。 读者记录 读者 图书id 借书记录 借书 还书读者读者 更新藏书记录第8章 ：1.栈的含义：栈是这样的一种列表，该表的项只能在表头进行添加和删除。用通俗的术语来表示，栈的头称为栈顶，栈的尾称为栈底。2.进栈，出栈的含义：在栈顶增加一个新的项称为入栈，在栈顶删除一个项称为出栈。注意，最后入栈的数据最先出栈，这样就可以得到：栈是LIFO（Last-in,fi

24、rst-out,后进先出，读作“LIE-foe”）的结构。3.队列的含义：队列是这样的一种列表，起表项只能从表头删除，新表项只能从表尾插入。4.进队，出队的过程：与栈不同，先进队列的项会先从队列中删除，就是说队列是FIFO（先进后出，读作“FIE-foe”）的结构，这意味着表项以它们存储的顺序从队列中删除第9章 :1.数据库的含义数据库是指一种多维的数据集合。之所以说是多维的，是因为在这种集合中，通过数据项间的内部链接，信息可以从不同的角度来获取。这与传统的文件系统不同，传统的文件系统，有时也称为平面文件，是一种一维的存储系统，因为它只从一个角度来展示信息；比如，一个包含作曲家及其作品信息的平

25、面文件，也许只能提供一个按作曲家分类的作品清单；而对于一个数据库来说，它可以呈现某一作曲家的所有作品，也可以是某一类音乐作品的所有作曲家，还可以是改写了其他作曲家作品的那些作曲家。数据库管理系统(Database Management System)是一种操纵和管理数据库的大型软件，用于建立、使用和维护数据库，简称DBMS。它对数据库进行统一的管理和控制，以保证数据库的安全性和完整性。用户通过DBMS访问数据库中的数据，数据库管理员也通过dbms进行数据库的维护工作。它可使多个应用程序和用户用不同的方法在同时或不同时刻去建立，修改和询问数据库。大部分DBMS提供数据定义语言DDL（Data D

26、efinition Language）和数据操作语言DML（Data Manipulation Language），供用户定义数据库的模式结构与权限约束，实现对数据的追加、删除等操作。数据库管理系统是数据库系统的核心，是管理数据库的软件。数据库管理系统就是实现把用户意义下抽象的逻辑数据处理，转换成为计算机中具体的物理数据处理的软件。有了数据库管理系统，用户就可以在抽象意义下处理数据，而不必顾及这些数据在计算机中的布局和物理位置。2.数据库管理的含义数据库管理系统(Database Management System)是一种操纵和管理数据库的大型软件，用于建立、使用和维护数据库，简称DBMS。它

27、对数据库进行统一的管理和控制，以保证数据库的安全性和完整性。用户通过DBMS访问数据库中的数据，数据库管理员也通过dbms进行数据库的维护工作。它可使多个应用程序和用户用不同的方法在同时或不同时刻去建立，修改和询问数据库。大部分DBMS提供数据定义语言DDL（Data Definition Language）和数据操作语言DML（Data Manipulation Language），供用户定义数据库的模式结构与权限约束，实现对数据的追加、删除等操作。数据库管理系统是数据库系统的核心，是管理数据库的软件。数据库管理系统就是实现把用户意义下抽象的逻辑数据处理，转换成为计算机中具体的物理数据处理的

28、软件。有了数据库管理系统，用户就可以在抽象意义下处理数据，而不必顾及这些数据在计算机中的布局和物理位置。3.数据库管理系统的含义数据库管理系统(Database Management System)是一种操纵和管理数据库的大型软件，用于建立、使用和维护数据库，简称DBMS。它对数据库进行统一的管理和控制，以保证数据库的安全性和完整性。用户通过DBMS访问数据库中的数据，数据库管理员也通过dbms进行数据库的维护工作。它可使多个应用程序和用户用不同的方法在同时或不同时刻去建立，修改和询问数据库。大部分DBMS提供数据定义语言DDL（Data Definition Language）和数据操作语言

29、DML（Data Manipulation Language），供用户定义数据库的模式结构与权限约束，实现对数据的追加、删除等操作。数据库管理系统是数据库系统的核心，是管理数据库的软件。数据库管理系统就是实现把用户意义下抽象的逻辑数据处理，转换成为计算机中具体的物理数据处理的软件。有了数据库管理系统，用户就可以在抽象意义下处理数据，而不必顾及这些数据在计算机中的布局和物理位置。根据处理对象的不同，数据库管理系统的层次结构由高级到低级依次为应用层、语言翻译处理层、数据存取层、数据存储层、操作系统。*应用层是DBMS与终端用户和应用程序的界面层，处理的对象是各种各样的数据库应用。*语言翻译处理层是对数据