计算机科学导论3到5章501.pdf

《计算机科学导论3到5章501.pdf》由会员分享，可在线阅读，更多相关《计算机科学导论3到5章501.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第三章 1.程序就是可以实现特定功能的一组指令序列的集合。2.计算机程序设计语言有：机器语言、汇编语言、高级语言。3.低级语言的特点：都与特定的计算机硬件系统严密相关。它们具有许多一样的特征。对程序员专业知识要求高，要求对计算机硬件的 构造和工作原理非常熟悉。每条指令的功能比较单一，程序员编写源程序时指令非常繁琐。由于直接针对特定硬件编程，所以最终的可执行代码非常精炼，并且执行效率高。4.高级语言的常见类型：BASIC 语言、FORTRAN 语言、COBOL 语言、PASCAL 语言、C语言、C+语言以及一些其它的高级语言。5.高级语言的优点是语句的功能强，程序员编写的源程序比较短，容易学习

2、，使用方便，可移植性较好，便于推广和交流。其缺点是编译程序比汇编程序复杂，而且编译出来的目的程序往往效率不高，目的程序的长度比有经历的程序员所编写的同样功能的汇编语言程序要长一半以上，运行时间也要长一些。6.高级语言的语法成分都是由根本符号组成的，根本符号可以分为单子符合多字符两种。单字符根本符号由单个字符组成，在高级语言中通常包括字母、数字、特殊字符这几种根本符号。7.多字符是由两个或两个以上的字符组成。8.根本元素由根本符号组成，可分为数、逻辑值、名字、标号和字符串等 5 大类。9.根本的数据类型，通常包括整数类型、实数类型和字符类型等。10.构造数据类型是在根本数据类型的根底上构造出来的

3、数据类型，数组和构造体是大多数高级语言都支持的两种最根本的机构造数据类型。11.高级语言的表达式由根本符号、根本元素和各种数据通过运算符连接而成，运算符大致包括1逻辑运算：与、或、非、异或等。2算术运算：加、减、乘、除、取模等。3 数据比较：大于、小于、等于、不等于等。4数据传送：输入、输出、赋值等。12.通过各种运算符连接而得到的表达式有算术表达式、关系运算表达式、字符串表达式。13.语句是构成高级语言源程序的根本单位，由根本元素、运算符、表达式等组成。14.使用高级语言编写程序的一般过程可以归纳为1使用文本编辑工具，逐条编写源程序的语句。保存源程序的文件时，文件的后缀名与所使用的高级语言有

4、关。2编译源程序文件，生成目的文件，文件后缀名通常为 obj。3链接目的文件，生成可执行文件，文件后缀名通常为 exe。4在计算机上运行可执行程序，并进展调试和维护。15.高级语言的数据表示手段：常量、变量。16.常见的数据类型包括原始类型如整数、浮点数或字符、数组、构造、代数数据类型、抽象数据类型、引用类型、类以及函数类型。17.表达式是操作符、操作数和标点符号组成的序列，其目的是用来说明一个计算过程。18.声明用于说明每个标识符预留存储空间。预留存储空间的声明称为定义。19.类型检查是利用一组逻辑规那么来推理一个程序在运行时刻的行为。20.类型系统用于定义如何将程序语言中的数值和表达式归类

5、为许多不同的类型、如何操作这些类型、这些类型如何互相作用。21.类型系统提供的主要功能有：平安性、最正确化、可读性、抽象化。22.解释程序在处理源程序时，执行方式类似于日常生活中的“同声翻译。按照高级语言源程序的语句顺序，由相应语言的 解释器逐句解释成目的代码机器语言，解释一句、执行一句，立即产生运行结果。23.编译程序是把用高级语言程序编写的用户程序源程序作为一个整体来处理，首先将程序源代码“翻译成目的代码机器语言，编译后与系统提供的代码库链接，形成一个完好的、可执行的机器语言程序目的程序代码。24.词法分析作为翻译过程的第一个阶段，其任务是从左到右逐个字符地对源程序进展扫描，读入源程序，对

6、构成源程序的字符流进展进展扫描和分解。通过词法分析识别出每个单词。25.语法分析是编译过程的第二个阶段，其任务是在词法分析的根底上将单词序列分解成各类语法短语。26.编译过程中的语义处理能实现以下两个功能。1审查每个语法构造的静态语义，即验证语法构造法的程序是否真正有意义，有时把这个工作称为静态语义分析或静态审查。2假设静态语义正确，那么语义处理要执行真正的翻译，要么生成程序的一种中间表示形式 中间代码，要么生成实际的目的代码。27.中间代码试编译程序构造在逻辑上更为简单、明确。28.常用的中间代码形式有妮波兰形式、三元式和四元式。29.中间代码优化的任务是对中间代码进展转换或进展改造，目的是

7、使生成的目的代码更为高效，即节省时间和空间。30.目的代码生成的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。31.新的编译程序自动化方向包括并行编译技术、穿插编译技术、硬件描绘语言及其编译技术等。32.程序设计语言的设计是一门技术，需要相应的理论、技术、方法和工具来支持。程序设计语言的设计就是根据问题的需求，设计数据构造和算法、编制程序和调制程序，使计算机程序能完成所需要的任务。33.程序设计语言的设计是设计和编制程序的过程。第四章 1.程序设计步骤如下（1）确定要解决的问题。（2）分析问题。（3）选择计算方法。（4）确定数据构造和算法。（5）绘制流程图。

8、（6）编写程序。（7）整理资料，交付使用。2.研究问题的思路有自上而下和自下而上两种。3.自上而下：先研究总体，然后研究每一个局部的细节。4.自下而上：先研究每一个局部的细节，然后研究总体。5.构造化方法有助于在正式编写程序之前充分理解问题的本质和实现方法，并且可以在详细编码过程中提供指导。6.构造化方法通常遵循以下原那么：1用户参与的原那么2先分析、再设计、后实现的原那么。3自上而下的原那么。4阶段成果文档化。7.构造化程序设计方法采用自上而下的方法解决实际，应该遵循以下几个根本原那么。1使用顺序、选择、循环 3 种根本控制构造表示程序的逻辑步骤。2程序语句组织成容易识别的模块，每个模块符合

9、单入口、单出口的要求。3严格要求控制 GOTO 语句的使用。8.模块化方法是一种传统的软件开发方法，该方法通常是将待开发软件划分为一些功能相对独立的模块，模块与模块之间定义相应的接口，各个模块是可以分别单独开发、调试、运行和测试，然后，再将多个模块组合起来，进展软件的整体测试，从而完成整个软件的开发。9.函数程序以其明晰、简洁和易读等特点使得大型程序的开发更高效，维护更容易，因此函数程序语言受到学术界的亲眯和业界的欢迎。10.程序设计风格指一个人编制程序时所表现出来的特点、习惯、逻辑思路等。11.为了使数据定义更易于理解和维护，有以下原那么1数据说明顺序应标准，使数据的属性更易于查找，从而有利

10、于测试、纠错与维护。2一个语句说明多个变量是，各变量名按字典顺序排列。3对于复杂的数据构造，要加注释，说明在程序实现时的特点。12.语句构造的原那么是简单、直接。13.在编写输入和输出语句时应考虑的原那么：1输入操作步骤和输出格式尽量简单。2应检查输入数据的合法性、有效性，报告必要的输入状态信息及错误信息。3输入一批数据时，使用数据或文件完毕标志，而不要用记数来控制。4交互式输入时，提供可用的选择和边界值。5当程序设计语言有严格的格式要求时，应保持输入格式的一致性。6输出数据表格化、图形化。14.数据时对客观事物的符号表示。在计算机系统内，数据通常是指可以输入到计算机中并被计算机进展处理的符号

11、的集合。15.数据类型是指具有一样取值范围和可以施行同种操作的数据的集合。16.数据构造是指数据元素之间的互相关系的集合，包括数据的逻辑构造、物理构造及数据运算。17.典型的数据构造有：线性表、栈、队列、树、图。18.线性表示由有限个同类的数据元素构成的序列，元素之间是一对一的线性关系，除了第一个元素只有直接后继、最后一个元素只有直接前驱外，其余数据元素都有一个直接前驱和一个直接后继。19.线性表是最简单、最常用的一种数据构造。20.对于 n 各数据元素构成的一个线性序列，假设只允许在其指定的一端插入或删除一个数据元素，那么这种逻辑构造称为栈或堆栈。允许插入或删除的这一端称为栈项，另一个固定端

12、称为栈底。没有 元素的堆栈称为空栈。21.对于由 n 个数据元素构成的一个线性序列，假设在其固定的一端只允许插入数据元素，且在另一端只允许删除数据元素，这种逻辑构造称为队列。只允许插入的一端称为队尾，只允许删除的一端称为队首。22.在树型构造中，每个数据元素称为一个结点，除了唯一的根结点外，其他结点都有且仅有一个父结点，每个元素可以有多个子结点。23.图构造是一种比树型构造更复杂的非线性构造。在图构造中，每个数据元素称为一个顶点，任意两个顶点之间都可能相关，这种相关性用一条边来表示，顶点之间的领接关系可以是任意的。24.查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的纪录或数据

13、元素。25.查找分为：顺序查找、二分查找、分块查找。26.排序分为：直接插入排序、冒泡排序、快速排序。第五章 1.算法是一组明确的、可以执行步骤的有序集合，在有限的时间内终止并产生结果。算法就是被准确定义的一组规那么，明确规定先做什么，再做什么，并能判断在某种情况下完成怎样的操作，最终在有限的时间内执行有限的步骤后获得结果。2.算法的特性：有穷性、确定性、有效性。3.常用算法有：递归算法、迭代算法、穷举算法、贪心算法。4.算法的描绘工具有：自然语言、流程图、伪代码。5.自然语言是人们日常使用的语言，可以是中文、英文等。6.流程图是用规定的一组图形符号、流程线和文字说明来描绘算法的一种表示方法。

14、7.伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描绘算法。8.对于一个算法的评价，通常要从正确性、可理解性、强健性、时间复杂度及空间复杂度等多个方面加以衡量。9.分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法的各局部并发和独立地运行，每一局部只承载有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构件出了故障，这些算法仍然能工作正常。10.NP 问题是非确定性多项式问题，是指算法无法直接计算出结果，只能通过进展一些有选项的“猜算来得到结果。11.数据加密的根本过程就是对原来为明文的文件或数据按某种算法进展处理，使其成为不可读的一段代码，通常成为“密文，使其只能在输入相应的密匙之后才能显示出本来内容，通过这样的途径来到达保护数据不被非法窃取、阅读的目的。12.并行算法是在给定并行形式下的一种详细、明确的计算方法和步骤，其有不同的分类方法。