计算导论与程序设计复习提纲

1、第一部分：计算、计算机发展史、计算模型知识点：1、 什么是计算？转换/变换； 什么是计算思维？抽象与自动化2、 图灵机的计算模型： 组成，计算过程，状态及状态转移。3、 结合图灵机，什么是程序？ 理解程序的含义4、 什么是存储程序的概念？“存储程序”原理，是将根据特定问题编写的程序存放在计算机存储器中，然后按存储器中的存储程序的首地址执行程序的第一条指令，以后就按照该程序的规定顺序执行其他指令，直至程序结束执行。第二部分：计算机组成与原理知识点：1、 冯诺依曼计算机的组成结构 输入、输出设备，控制器，存储器，运算器2、 存储器与存储系统，a) 存储系统 高速缓存(寄存器)、内存、外存b) 存储

2、空间，存储地址、存储单元，位与字节3、 控制器及运算器a) 控制器的结构程序计数器，地址形成逻辑，指令寄存器，指令操作码译码器b) 指令的执行，取指令->分析指令à执行指令，指令计数器PCc) 指令及指令系统，指令的组成 指令:是能够被计算机硬件直接识别的、命令计算机进行某种基本操作的二进制代码串。计算机能直接识别和执行的全部指令的集合，称为该种计算机的指令系统。4、 系统软件（操作系统）a) 什么是操作系统？强调对计算机资源的管理，作业和进程的调度计算机最基本、最重要的软件，直接运行在裸机上b) 操作系统的组成进程管理，存储管理，设备管理，文件管理，用户界面，程序接口c) 了

3、解进程的概念，进程和程序的区别>进程是动态的，强调执行过程。程序是静态的。>进程具有并发性，程序没有。>不同的进程可以对应同一个程序，只是该程序对应的数据集不同。第三部分 程序语言及程序设计基础知识点1、 标识符由下划线，大小写字母和数字组成，并且必须由下划线或字母开头2、 数据类型及数据类型的三要素（逻辑表示、存储结构、数据操作）类型：整形，字符型，浮点型，布尔型。3、 变量及变量的三要素变量名，变量类型，变量值4、 表达式，表达式的递归形式定义由运算符，操作数和括号组成的，运算求值的基本单位。5、 三种基本语句：赋值、输入、输出6、 三种基本程序结构：顺序、分支、循环第四

4、部分 算法设计方法知识点1、 什么是算法？算法的五大特征由基本运算和规定的运算顺序组成的完整的解题步骤特征：有穷性，明确性，可执行性，有输入信息的说明，有输出信息的步骤2、 结构化编程，自顶向下、逐步求精的方法自顶向下，逐步细化，模块化设计，结构化编码3、 算法的描述方法（N-S流程图）4、 迭代算法、穷举算法5、 算法思路：问题抽象（数学建模），求解问题的步骤第五部分 子程序（函数）知识点1、 函数的定义、函数原型定义：封装并命名的一段程序代码，这段代码可以完成子程序定义的功能，可供调用2、 函数的调用a) 函数的参数原理，形参与实参b) 函数的调用过程：堆栈、函数活动记录3、 子程序设计（

5、函数设计）高内聚/低耦合，参数设计减少代码冗余4、变量的作用域第六部分 递归（函数递归）知识点1、 递归的概念，递归函数定义2、 递归过程，基于函数调用过程能够自主分析递归过程，得出结果。3、 递归程序设计，化简为同类问题，分解直至能求解4、 递归函数的参数设计，不建议使用全局变量。第七部分 数组知识点：1、 数组的概念：存储结构2、 数组的定义、下标运算符3、 数组的逐元素访问4、 数组作为函数参数：1. 数组元素作为参数（值传递）；2.数组名作为参数（相当于引用传递）5、 字符数组： 存储特征 -结束符；整体的输入与输出操作；字符串操作函数：拷贝、比较等6、 二维数组： 特别是数组名作为函

6、数参数的用法第八部分 指针与数组知识点：1、 指针的概念，指针的定义（语法）2、 指针运算符： 间接访问* 取地址 &3、 指针作为函数参数：相当于引用传递的效果4、 指针变量指向数组，指针的算术运算、关系运算注意：ptr+=i 与 ptr+i 的区别5、 指针与数组： a) 数组元素的4种访问方式（下标、偏移量）b) 指针与数组： 动态数组，堆区分配存储c) 指针数组，指向指针的指针，双重间接访问(*p)d) 动态分配多个字符串的处理（分配顺序：先分配指向字符串的指针空间，再分配字符串空间；释放顺序：先释放字符串空间，再释放指向字符串的指针空间）。以及在此基础上对多个字符串的操作，如排序、子串等。e) 通过指针访问和处理二维数组。（）第九部分 自定义数据类型结构体知识点：1、 再论数据类型（三要素），用户自定义（构造）数据类型2、 结构的定义，结构成员的访问，结构变量的操作（结构体的整体赋值）3、 结构作为函数参数 结构传值、传地址第十部分： 数据结构+算法=程序知识点：1、 基于数