2022年2022年计算机科学导论复习大纲 .pdf

《2022年2022年计算机科学导论复习大纲 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机科学导论复习大纲 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机科学导论复习大纲1.学科根本问题：什么能被（有效地）自动进行。他来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期2.学科知识体的三个层次：分支领域（Area）【分为】知识单元（Unit）【分为】知识点（Topic）3.计算学科三个学科形态（过程）：抽象、理论、设计4.哈密尔顿回路问题：访问除原点外每个结点一次，对于任一图无法判断是否存在哈密尔顿回路欧拉回路问题：访问每条边一次，对于任一图可以判断是否存在欧拉回路5.要完成 n个盘子的梵天塔的移动，最少需要：6.P类问题：所有在多项式时间内可以求解的问题，此问题采用确定性算法

2、NP类问题：所有在多项式时间内可以验证的问题，此问题采用非确定性算法7.NP完全性问题：NP类中某些问题的复杂性与整个类的复杂性有关，当这些问题中任何一个存在多项式时间算法时，则所有NP问题都是多项式时间可解，这些问题被称为NP完全性问题8.停机问题：针对任意给定的图灵机和输入，寻找一个一般的算法（或图灵机），用于判定给定图灵机在接收了初始输入后能否到达终止状态，即停机状态。若能找到，则停机问题可解；否则，不可解【简言之】我们能不能找到这样一个测试程序，它能判断出任意的程序在接收了某个输入并执行后能不能终止9.贪婪准则：1）每次都选择价值最大的物品装包2）每次都选择重量最小的物品装包3）每次都

3、选择价值密度（价值/重量）最大的物品装包10.程序的三种基本结构：PTFAA名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -PBAB 1）顺序结构 2）选择结构 3）循环结构11.Internet 软件的层次结构：OSI 的分层：物理 链路网络传输会话 表示 应用TCP/IP（现用）的分层：物理链路网络传输 应用12.超文本传送协议：HyperText Transfer Protocol（HTTP）13.图灵：电子计算机的理论和模型是由英国数学家图灵建立的14.图灵机：图灵机属于理论形态15.冯 诺依曼：冯 诺依曼为美籍匈牙利科学家16.冯 诺依曼计算机五大特点（又称存

4、储程序特点）：1）计算机由运算器、控制器、存储器、输入及输出设备五部分组成2）程序与数据置于同一存储器；指令和数据均可送至运算器运算3）数据以二进制表示4）顺序执行指令5）机器以运算器为中心17.EMIAC：EMIAC是第一台真正工作的计算机，他相当于CPU18.Brooks hear：Brooks hear在其著作计算机科学导论中给出一个基于冯 诺依曼计算机体系结构的程序执行实例19.执行程序的机器指令集：操作码操作数描述1RXY将内存 XY单元中的数据取出，存入寄存器R中2RXY将数XY存放到寄存器 R中名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -3RXY将寄存

5、器 R中的数据存入主存地址为XY 的单元中40RS将寄存器 R中的数存入寄存器S中5RST将寄存器 S与T中用二进制补码表示的数相加，结果存入寄存器R中6RST将寄存器 S与T中用浮点数表示的数相加，结果存入寄存器 R中7RST将寄存器 S与T中的数进行或运算，结果存入寄存器 R中8RST将寄存器 S与T中的数进行与运算，结果存入寄存器 R中9RST将寄存器 S与T中的数进行异或运算，结果存入寄存器 R中AR0X将寄存器 S中的数右移 X次，每次将最低位移出的数字放在最高位的空缺中BRXY若寄存器 R中的数与寄存器 0中的相同，就将内存XY 单元中的数据（跳转指令）存入程序计数器中；否则，按原

6、来的顺序继续执行C000停机，C000如：1A43【表示】将43单元中的数据取出，存入寄存器A中20.计算机语言：机器语言（机器指令）【高级】汇编语言【高级】高级语言21.机器指令：机器指令是计算机硬件能够直接识别和运行的语言，由操作码和操作数组成22.高级语言：高级程序设计语言是一种无需了解计算机内部即能运用的语言23.CISC：复杂指令系统计算机24.RISC：精简指令系统计算机25.程序设计 _语言翻译系统的三部分：1）汇编语言翻译系统2）高级程序设计语言编译系统3）高级语言翻译系统名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -26.算法的重要特性：1）有穷性（

7、又称有限性）2）确定性3）输入4）输出5）能行性（又称正确性）27.流程图：流程图是描述算法的常用工具，它采用美国国家标准化协会（American National Standard Institute,ANSI）规定的一组图形符号来表示算法28.算法分析考虑的三个问题：1）算法的时间杂度2）算法的空间杂度执行过程中所占存储空间的大小3）算法是否便于阅读、修改和测试29.线性表：1）后进先出（栈）2）先进先出（队列）30.图：图是由结点和连接这些结点的边所组成的集合31.程序：每个程序都具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法32.程序=算法+数据结构：此公式是1976年

8、由瑞士计算机科学家尼科莱 沃恩提出的33.软件 =程序 +文档：软件一般指计算机系统中的程序及其文档34.软件分类：系统软件（不做事）、支撑软件（工具）、应用软件35.单位转换：1K=1024（）位1M=1024K1G=1024M1T=1024G36.二进制代码：计算机中数值数据信息、字符、图像及汉字等信息用二进制代码形式表示；微机中主要使用的二进制编码为ASCII 码37.ASCII 码：目前采用的字符编码是由美国国家标准局（AmericanNational Standards）制定的国际标准信息交换码（AmericanStandard Code for Information Interc

9、hange,ASCII）38.浮点数：计算机中浮点数由阶码与尾码组成名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -39.布尔代数：由 0和1组成的集合以及定义在其上的“3 个运算”构成40.半加器真值表：输入输出00001110111041.理论：从数学的角度来说，理论是基本概念、基本原理或定律以及由这些概念与原理逻辑推理出来的结论组成的集合42.公理化方法：公理化方法是一种构造理论体系的演绎方法，它是从尽可能少的基本概念、公理出发，运用演绎推理规则，推出一系列的命题，从而建立整个理论体系的思想方法；公理化方法是构建理论体系的常用方法43.公理系统需满足的三条件：无矛

10、盾性、独立性、完备性44.形式验证：形式验证是基于已建立的形式规格，对规格系统的相关特性进行分析和验证，以评判系统是否满足期望的特征；形式验证的主要技术包括模型检验、定理证明以及模型检验与定理证明的结合45.系统科学：系统科学是探索系统的存在方式和运动变化规律的学问，是对系统本质的理性认识，是人们认识客观世界的一个知识体系46.几种常用的系统科学方法：1）系统分析法2）信息方法3）功能模拟方法4）黑箱方法5）整体优化方法47.结构化方法：结构化方法是计算学科的一种典型的系统开发方法。它采用了系统科学的思想方法，从层次的角度自顶向下地分析和设计系统；结构化方法起源于结构化程序设计语言，其核心问题

11、是模型问题名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -48.结构化程序设计概念：结构化程序设计概念是由Dijkstra提出的，其实质是控制程序设计的复杂性49.结构化程序设计方法的要点：1）无 go to语句2）一入口一出口3）自顶向下逐步求精其中1和2是解决程序结构规范的问题；3是解决将大化小、将难化简的求解方法的问题50.结构化方法遵循的基本原则：1）抽象原则2）分解原则3）模块化原则51.面向对象方法：面向对象（Object-Oriented,OO）方法是以面向对象思想为指导进行系统开发的一类方法的总称。这类方法以对象为中心，以类和继承为结构机制来抽象现实世界

12、，并构建相应的软件系统；与结构化方法一样，面向对象方法也起源于面向对象程序语言，且其核心问题也是模型问题；用于面向对象技术的软件开发项目主要采用转换模型52.面向对象模型遵循的基本原则：1）抽象原则2）封装原则3）模块化原则4）层次原则53.理查德 海明：发明纠错的数学家是理查德 海明54.乔布斯：今年 10月，计算机行业的伟人乔布斯病逝55.计算机根据用途及适用范围的分类：通用计算机和专用计算机（手机等）56.第五代计算机的特征：人工智能57.CPU 主要组成部分：运算器和控制器58.MHZ：计算机系统时钟的速度用MHZ（兆赫兹）表示59.指令的执行步骤：1）取指令2）分析指令3）执行指令4

13、）写回寄存器或内存60.RAM：用来存放正在执行的程序指令或所需数据的存储器为名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -RAM61.外存：1）磁带（工作在顺序存取方式）2）磁盘（工作在直接存取方式）62.ARPANET：Internet 起源于第一个计算机网络ARPANET，由美国高级国防研化署研制63.网络分类：局域网、城域网、广域网64.IP地址：IP地址共 32位（4个字节）二进制数，即4个0255的数字65.网格：下一代因特网（外网）主要指网格（分摊任务至其他电脑以加快网速）66.网站后缀：1）com：company商业网站2）gov：government

14、政府网站3）edu：education教育网站cn表示China67.yahoo:雅虎为搜索引擎68.PGP 软件：PGP 主要为 Email 提供安全服务69.链接：超文本中不同信息间通过链接进行连接70.exe：病毒最可能出现在exe文件中71.防火墙：能防止内部网络受外部攻击的是防火墙72.RSA：目前最成功的公钥密码（非对称密码）体制为RSA；密钥密码（对称密码）体制为DES73.数字签名（用电子方式确认姓名）的功能：1）发送方不能否认所发消息的内容2）接收方确认消息来源于指定发送者3）接收方不能伪造发送内容74.信息安全三要素：1）保密性：阻止未经授权的用户读取数据2）完整性：阻止未

15、经授权的用户修改或删除数据3）可用性：保证授权实体在需要时可以使用系统75.共享软件：在一实验性范围内，可免费得到软件的拷贝权76.自由软件：不受限制地自由使用、复制、研究、修改和分发的软件77.操作系统：用来管理计算机系统的硬件、软件资源，控制程序运行，改善人机界面和为应用软件提供支持的软件系统；操作名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -系统是最靠近硬件的一种软件，他把硬件改造成为功能更加完善的虚拟机器，使得对计算机系统的使用和管理更加方便78.操作系统的安装：安装操作系统时，有时需要从光盘启动，这时需改变启动时的顺序，在CMOS 中进行设置79.常用的操作

16、系统：Windows、MS-DOS、Unix、Linux80.操作系统分类：1）分时操作系统2）实时操作系统：计算机过程控制系统通常采用实时控制系统3）网络操作系统4）批处理操作系统81.ins：键盘上用于切换插入或改写两种状态的键是ins 82.数据库系统（DBS）的组成：1）数据库（DB）2）数据库管理系统（DBMS）：数据库系统的核心3）数据库管理员（DBA）4）数据库应用程序5）用户83.多媒体信息的最重要特性：继承性84.BMP：图像文件格式85.MPEG：运动图像压缩编码86.MIS：管理信息系统87.UML：统一建模语言88.创新的两大特点：新颖性、价格性89.信息系统设计的主要

17、步骤：1）概念设计2）逻辑设计3）物理设计例1.设有三件物品，价值；重量；背包容量，使用三种贪婪原则取得解，判断是否为最优解名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -2.将下列自然语言用 Brooks hear给出的机器指令描述1）将十六进制数 A0装入寄存器 02）将寄存器 1中的值右移 3位3）将地址为 E8内存单元的值装入寄存器A4）若寄存器 A与寄存器 B的值相等，则跳转到地址为00的内存单元所存储的指令执行5）将寄存器 6和寄存器 8中的内容相与6）将寄存器 1的内容存入地址为 D2的内存单元中3.在Brooks hear给出的机器中，假设内存单元地址从00开始，用机器语言写一个程序，用来计算内存单元B1、C1、D1中的值，将结果放入E14.进制转换：二进制?十进制、八进制?十进制、十六进制?十进制、二进制?八进制、二进制?十六进制5.补码：原码 反码补码（注意取值范围）名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -