计算机科学导论3到5章

第三章 1. 程序就是能够实现特定功能的一组指令序列的集合。2. 计算机程序设计语言有：机器语言、汇编语言、高级语言。3. 低级语言的特点：都与特定的计算机硬件系统紧密相关。它们具有许多相同的特征。对程序员专业知识要求高，要求对计算机硬件的 结构和工作原理非常熟悉。每条指令的功能比较单一，程序员编写源程序时指令非常繁琐。由于直接针对特定硬件编程，所以最终的可执行代码非常精炼，并且执行效率高。4. 高级语言的常见类型：BASIC语言、FORTRAN语言、COBOL语言、PASCAL语言、C语言、C+语言以及一些其它的高级语言。5. 高级语言的优点是语句的功能强，程序员编写的源程序比较短，容易学习，使用方便，可移植性较好，便于推广和交流。其缺点是编译程序比汇编程序复杂，而且编译出来的目标程序往往效率不高，目标程序的长度比有经验的程序员所编写的同样功能的汇编语言程序要长一半以上，运行时间也要长一些。6. 高级语言的语法成分都是由基本符号组成的，基本符号可以分为单子符合多字符两种。单字符基本符号由单个字符组成，在高级语言中通常包括字母、数字、特殊字符这几种基本符号。7. 多字符是由两个或两个以上的字符组成。8. 基本元素由基本符号组成，可分为数、逻辑值、名字、标号和字符串等5大类。9. 基本的数据类型，通常包括整数类型、实数类型和字符类型等。10. 结构数据类型是在基本数据类型的基础上构造出来的数据类型，数组和结构体是大多数高级语言都支持的两种最基本的机结构数据类型。11. 高级语言的表达式由基本符号、基本元素和各种数据通过运算符连接而成，运算符大致包括（1）逻辑运算：与、或、非、异或等。（2）算术运算：加、减、乘、除、取模等。（3）数据比较：大于、小于、等于、不等于等。（4）数据传送：输入、输出、赋值等。12. 通过各种运算符连接而得到的表达式有算术表达式、关系运算表达式、字符串表达式。13. 语句是构成高级语言源程序的基本单位，由基本元素、运算符、表达式等组成。14. 使用高级语言编写程序的一般过程可以归纳为（1）使用文本编辑工具，逐条编写源程序的语句。保存源程序的文件时，文件的后缀名与所使用的高级语言有关。（2）编译源程序文件，生成目标文件，文件后缀名通常为obj。（3）链接目标文件，生成可执行文件，文件后缀名通常为exe。（4）在计算机上运行可执行程序，并进行调试和维护。15. 高级语言的数据表示手段：常量、变量。16. 常见的数据类型包括原始类型（如整数、浮点数或字符）、数组、结构、代数数据类型、抽象数据类型、引用类型、类以及函数类型。17. 表达式是操作符、操作数和标点符号组成的序列，其目的是用来说明一个计算过程。18. 声明用于说明每个标识符预留存储空间。预留存储空间的声明称为定义。19. 类型检查是利用一组逻辑规则来推理一个程序在运行时刻的行为。20. 类型系统用于定义如何将程序语言中的数值和表达式归类为许多不同的类型、如何操作这些类型、这些类型如何互相作用。21. 类型系统提供的主要功能有：安全性、最佳化、可读性、抽象化。22. 解释程序在处理源程序时，执行方式类似于日常生活中的“同声翻译”。按照高级语言源程序的语句顺序，由相应语言的 解释器逐句解释成目标代码（机器语言），解释一句、执行一句，立即产生运行结果。23. 编译程序是把用高级语言程序编写的用户程序（源程序）作为一个整体来处理，首先将程序源代码“翻译”成目标代码（机器语言），编译后与系统提供的代码库链接，形成一个完整的、可执行的机器语言程序（目标程序代码）。24. 词法分析作为翻译过程的第一个阶段，其任务是从左到右逐个字符地对源程序进行扫描，读入源程序，对构成源程序的字符流进行进行扫描和分解。通过词法分析识别出每个单词。25. 语法分析是编译过程的第二个阶段，其任务是在词法分析的基础上将单词序列分解成各类语法短语。26. 编译过程中的语义处理能实现以下两个功能。（1）审查每个语法结构的静态语义，即验证语法结构法的程序是否真正有意义，有时把这个工作称为静态语义分析或静态审查。（2）如果静态语义正确，则语义处理要执行真正的翻译，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。27. 中间代码试编译程序结构在逻辑上更为简单、明确。28. 常用的中间代码形式有妮波兰形式、三元式和四元式。29. 中间代码优化的任务是对中间代码进行转换或进行改造，目的是使生成的目标代码更为高效，即节省时间和空间。30. 目标代码生成的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。31. 新的编译程序自动化方向包括并行编译技术、交叉编译技术、硬件描述语言及其编译技术等。32. 程序设计语言的设计是一门技术，需要相应的理论、技术、方法和工具来支持。程序设计语言的设计就是根据问题的需求，设计数据结构和算法、编制程序和调制程序，使计算机程序能完成所需要的任务。33. 程序设计语言的设计是设计和编制程序的过程。 第四章1. 程序设计步骤如下（1） 确定要解决的问题。（2） 分析问题。（3） 选择计算方法。（4） 确定数据结构和算法。（5） 绘制流程图。（6） 编写程序。（7） 整理资料，交付使用。2. 研究问题的思路有自上而下和自下而上两种。3. 自上而下：先研究总体，然后研究每一个局部的细节。4. 自下而上：先研究每一个局部的细节，然后研究总体。5. 结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法，并且可以在具体编码过程中提供指导。6. 结构化方法通常遵循以下原则：（1）用户参与的原则（2）先分析、再设计、后实现的原则。（3）自上而下的原则。（4）阶段成果文档化。7. 结构化程序设计方法采用自上而下的方法解决实际，应该遵循以下几个基本原则。（1）使用顺序、选择、循环3种基本控制结构表示程序的逻辑步骤。（2）程序语句组织成容易识别的模块，每个模块符合单入口、单出口的要求。（3）严格要求控制GOTO语句的使用。8. 模块化方法是一种传统的软件开发方法，该方法通常是将待开发软件划分为一些功能相对独立的模块，模块与模块之间定义相应的接口，各个模块是可以分别单独开发、调试、运行和测试，然后 ，再将多个模块组合起来，进行软件的整体测试，从而完成整个软件的开发。9. 函数程序以其清晰、简洁和易读等特点使得大型程序的开发更高效，维护更容易，因此函数程序语言受到学术界的亲眯和业界的欢迎。10. 程序设计风格指一个人编制程序时所表现出来的特点、习惯、逻辑思路等。11. 为了使数据定义更易于理解和维护，有以下原则（1）数据说明顺序应规范，使数据的属性更易于查找，从而有利于测试、纠错与维护。（2）一个语句说明多个变量是，各变量名按字典顺序排列。（3）对于复杂的数据结构，要加注释，说明在程序实现时的特点。12. 语句构造的原则是简单、直接。13. 在编写输入和输出语句时应考虑的原则：（1）输入操作步骤和输出格式尽量简单。（2）应检查输入数据的合法性、有效性，报告必要的输入状态信息及错误信息。（3）输入一批数据时，使用数据或文件结束标志，而不要用记数来控制。（4）交互式输入时，提供可用的选择和边界值。（5）当程序设计语言有严格的格式要求时，应保持输入格式的一致性。（6）输出数据表格化、图形化。14. 数据时对客观事物的符号表示。在计算机系统内，数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合。15. 数据类型是指具有相同取值范围和可以实施同种操作的数据的集合。16. 数据结构是指数据元素之间的相互关系的集合，包括数据的逻辑结构、物理结构及数据运算。17. 典型的数据结构有：线性表、栈、队列、树、图。18. 线性表示由有限个同类的数据元素构成的序列，元素之间是一对一的线性关系，除了第一个元素只有直接后继、最后一个元素只有直接前驱外，其余数据元素都有一个直接前驱和一个直接后继。19. 线性表是最简单、最常用的一种数据结构。20. 对于n各数据元素构成的一个线性序列，如果只允许在其指定的一端插入或删除一个数据元素，那么这种逻辑结构称为栈或堆栈。允许插入或删除的这一端称为栈项，另一个固定端称为栈底。没有 元素的堆栈称为空栈。21. 对于由n个数据元素构成的一个线性序列，如果在其固定的一端只允许插入数据元素，且在另一端只允许删除数据元素，这种逻辑结构称为队列。只允许插入的一端称为队尾，只允许删除的一端称为队首。22. 在树型结构中，每个数据元素称为一个结点，除了唯一的根结点外，其他结点都有且仅有一个父结点，每个元素可以有多个子结点。23. 图结构是一种比树型结构更复杂的非线性结构。在图结构中，每个数据元素称为一个顶点，任意两个顶点之间都可能相关，这种相关性用一条边来表示，顶点之间的领接关系可以是任意的。24. 查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的纪录或数据元素。25. 查找分为：顺序查找、二分查找、分块查找。26. 排序分为：直接插入排序、冒泡排序、快速排序。 第五章1. 算法是一组明确的、可以执行步骤的有序集合，在有限的时间内终止并产生结果。算法就是被精确定义的一组规则，明确规定先做什么，再做什么，并能判断在某种情况下完成怎样的操作，最终在有限的时间内执行有限的步骤后获得结果。2. 算法的特性：有穷性、确定性、有效性。3. 常用算法有：递归算法、迭代算法、穷举算法、贪婪算法。4. 算法的描述工具有：自然语言、流程图、伪代码。5. 自然语言是人们日常使用的语言，可以是中文、英文等。6. 流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。7. 伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描述算法。8. 对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度及空间复杂度等多个方面加以衡量。9. 分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法的各部分并发和独立地运行，每一部分只承载有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构件出了故障，这些算法仍然能工作正常。10. NP问题是非确定性多项式问题，是指算法无法直接计算出结果，只能通过进行一些有选项的“猜算”来得到结果。11. 数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常成为“密文”，使其只能在输入相应的密匙之后才能显示出本来内容，通过这样的途径来达到保护数据不被非法窃取、阅读的目的。12. 并行算法是在给定并行模式下的一种具体、明确的计算方法和步骤，其有不同的分类方法。