程序设计语言是用于书写计算机程序的语言，用于表达和描述要加工的数据以及求解 问题的步骤和过程。它是根据预先定义的语法规则，由一个有限字母表上的字符构成的字符 串的总体。
程序是按照工作步骤事先编排好的、具有特殊功能的指令序列。。 程序设计语言是人类用于编排程序的工具，人类利用程序设计语言来编写程序，程序再根据 所用程序设计语言种类来翻译成计算机可以直接执行的指令序列。 1、标识符 标识符是由程序员定义的单词，用来给程序中的数据、函数和其他用户自定义对象命名。 2、数据类型及数据类型的三要素 (1)逻辑结构：定义了一系列的逻辑表达——值(通常对应人类世界的数据表达方式) (2)存储结构：存储空间大小(决定了属于该类型的数据能够取值的范围） (3)数据操作：能应用于这些值上的一系列操作。 3、变量及变量的三要素 (1)变量用来代表内存存储空间，该存储空间用来存放被加工的数据或处理的结果。源程序 中对变量的操作（读和赋值）实际上是对存储空间的读写操作。 变量定义将引起内存空间的分配，存储单元个数取决于变量的数据类型。 (2)变量的三要素：名称、值和数据类型。 4、三类常量：文字常量、命名常量、符号常量；命名常量和符号常量的区别。 文字常量：在程序中未被命名（非标识符）的值。 符号常量：仅含有符号名称的值，用于标识文字常量。 C 语言符号常量定义：#define 标识符 替换の文本(文字常量) 命名常量：和变量类似，命名常量也是内存存储空间的名字，代表一片内存存储空间，但一 旦赋值便不允许程序去改变该存储空间中的数据。 C 语言命名常量定义：const float pi = 3.14 问题：命名常量和符号常量的区别 (1)内存分配上，命名常量会在内存的程序运行数据区分配到内存（2 分），而符号常量不会 （1 分）。 (2)类型定义上，命名常量精确定义了数据类型，排除了程序的不安全性（1 分）；而符号常 量只是简单的替换，并采用系统默认类型，存在不安全性（1 分）。 5、表达式，表达式的递归形式定义 表达式是由运算符、操作数和括号经过有限次组合成的，它是计算求值的基本单位。 运算符的结合性：除单目运算符、赋值运算符和条件运算符是右结合性，其他都是左结合性。
指令的组成： Ⅰ操作码：用来表明本条指令要求计算机完成的操作； Ⅱ地址码： (1)操作数地址：CPU 根据该地址取得所需的操作数；可能直接给出操作数，可能是内存地 址，也可能是寄存器地址（即寄存器名）； (2)操作结果的存储地址：将对操作数的操作结果保存在该地址中，以便再次使用；可能是 内存地址，也可能是寄存器地址； (3)下一条指令的地址：一般的，如果程序是顺序执行，则下一条指令的地址由程序计数器 PC（存放下一条指令地址的寄存器）指出；仅当改变程序的运行顺序（转移、调用子程序） 时，下条指令的地址才由转移类指令给出。 三、程序语言及程序设计基础 问题：请简述程序设计语言的概念，程序的概念，以及两者之间的关系。
址，即能正确返回。 问题 2、为何不同的函数可以使用同名的参数和变量？
因为不同函数的活动记录占用不同的内存单元，程序运行时始终是从位于栈顶的活动 记录中取形参和变量的值。 3、子程序设计（函数设计） 高内聚：功能相对独立和完整。 低耦合：与外界（调用者）的关系尽量松散，不要太紧密，使其能方便地被重用。 参数设计、减少代码冗余 4、变量的作用域 变量的作用域即可以引用该变量的程序段。 C 语言中变量可以在三种位置进行定义： (1)函数内部的定义部分（即任何语句之前） (2)函数内部的某一个复合语句内部 (3)所有函数之外 变量定义的位置决定了变量的作用域。 以上三种位置的变量分别对应于： (1)函数作用域 (2)块作用域（只在复合语句范围内才能引用该变量） (3)文件作用域（从变量的定义位置开始，到本文件结束为止的区域） 问题：为什么不要使用全局变量？ (1)外部变量可以减少函数参数的使用，但会加强函数之间的数据联系，使这些函数依赖这 些外部变量，因而使得这些函数的独立性降低（重用函数时必须要记得“带着”外部变量）。 (2)由于无法限制各函数对外部变量的访问，可能会使外部变量被某些函数非法修改，当程 序出错时不好检查。 从模块化程序设计的观点来看这是不利的，因此不是非用不可时，不要使用外部变量。 六、递归 1、 递归的概念，递归函数定义 递归的定义： (1)从程序书写来看，在定义一个函数时，若在函数的功能实现部分又出现对它本身的调用， 则称该函数是递归的或递归定义的。 (2)从函数动态运行来看，当调用一个函数 A 时，在进入函数 A 且还没有退出（返回）之前， 又再一次由于调用 A 本身而进入函数 A，则称之为函数 A 的递归调用。
地址总线是控制器向存储器中的地址译码器传送地址编码的通路。 数据总线是在输入输出设备和存储器、存储器和 CPU 之间传送数据的通路。 控制总线用来传送控制部件向运算部件、存储器、输入输出设备发出的控制信号。
问题：假设某计算机有 4KB 存储器（存储单元是字节），地址总线至少需要多少根？说明理 由。 至少需要 12 根（2 分）。 计算机存储器按照存储单元进行地址编制，每个存储单元是一个字节（1 分），因此 4KB 容 量存储器的地址容量为 4KB/1B=212(1 分)，由于地址以“二进制”方式表示，因此 4K 大小 地址容量至少需要地址总线为 log2212=12（1 分）。 2、存储器与存储系统， a)存储系统 高速缓存(寄存器)：用于临时存放数据的少量高速专用存储器，存取速度比主存快。主要存 在于 CPU、输入输出设备中。 内存（主存）：由存储单元组成，其功能涉及存储地址寄存器（MAR）、存储数据寄存器（MDR）。 外存（辅存）：光盘、磁盘等。 b)存储空间，存储地址、存储单元，位(bit)与字节(byte) 存储单元：存储器的组成单元，存放 8 位二进制信息 存储单元地址：用于标识和识别每一个存储单元，也是二进制形式 1Byte＝8Bit 3、控制器及运算器 a)控制器的结构
6、三种基本语句：赋值、输入、输出 7、三种基本程序结构：顺序、分支、循环 四、算法设计方法 1、什么是算法？算法的五大特征 (1)（在计算机能力集范围内）； (2)确定性：算法中的每一个步骤，必须是明确定义的，不得有任何歧义性 ； (3)有穷性：算法必须在执行有穷步之后结束； (4)有输入信息的说明：对加工对象提要求； (5)有输出信息的步骤：至少要输出问题答案。 2、结构化编程：自顶向下、逐步细化、模块化设计（函数）、结构化编码（三种基本结构） 3、算法的描述方法（N-S 流程图） 4、迭代算法、穷举算法 5、算法思路：问题抽象（数学建模），求解问题的步骤 五、子函数 1、函数的定义、函数原型 函数定义包含两部分： (1)定义该函数的接口，即函数头，包括函数名、参数和返回值（面向调用者）。 (2)定义该函数的功能实现部分（面向被调用者）。 函数定义的格式： 返回值类型 函数名(参数列表)//接口定义部分 {
注：如果指令中的操作数是内存地址，则需要先由地址形成逻辑形成真正的物理地址，然后 传送到内存，这样后续才能实现内存的读取 b)指令的执行：取指令→分析指令→执行指令，指令计数器 PC (Program Counter) 取指令：控制器首先从程序计数器中取得当前要执行的指令的地址，根据这个地址从主存储 器中取出指令复制到指令寄存器中，并将下一条指令的地址置入程序计数器 PC 中； 分析指令：然后由指令译码器对指令寄存器中存放的指令的操作码部分进行译码 执行指令：根据译码结果由微操作控制部件产生各种最基本的不可再分的微操作的控制信 号，即微命令，以控制各计算机部件完成该指令的功能。 c)指令及指令系统，指令的组成(操作码+地址码) 指令：能够被计算机硬件直接识别的、命令计算机进行某种基本操作的二进制代码串 指令系统：计算机能直接识别和执行的全部指令的集合，称为该种计算机的指令系统。
堆区：用户可以在程序运行过程中根据需要动态地进行存储空间的分配，这样的分配在堆区 进行 函数的活动记录是一段在栈区分配的连续的内存存储区，用以存放函数一次执行所需的数 据。
问题 1、如何确保能够逐层返回到上一级调用？ 函数 A 调用函数 B，则在函数 B 的活动记录中记录了 A 的返回地址。返回前取出该地
不会，每一次函数调用会在栈顶分配新的活动记录。 问题 2：对递归函数的每一次调用结束返回时，为何能回到调用前的程序运行状态？如 f(1) 调用结束返回 f(2)时，n 的值为 2。
计算导论与程序设计复习重点 一、计算、计算机发展史、计算模型 1、计算与计算思维 (1)什么是计算？转换/变换； 广义：计算就是把一个符号串 f 变换成另一个符号串 g。 更广义：计算就是对信息的变换。 (2)什么是计算思维？抽象与自动化 2、图灵机的计算模型：组成，计算过程，状态及状态转移。 a.图灵机的组成： (1)一个无限长的纸带 (2)一个读写头（中间那个大盒子） (3)内部状态（盒子上的方块，比如 A,B,E,H）， (4)一个程序，用于对这个盒子进行控制。 b.计算过程：从读写头在纸带上读出一个方格的信息，并且根据它的内部状态开始对程序进 行查表，得到一个输出动作和下一时刻所转移到的内部状态。 c.状态：可以将事物区分开的一种标识。 d.状态转移：当在某一状态下读入一个字符时，便使状态发生改变，从当前状态转换到后继 状态。 3、结合图灵机，什么是程序？理解程序的含义 程序是一套控制规则，它可以根据当前机器所处的状态以及当前读写头所指的格子上的符号 来确定读写头下一步的动作，并改变内部状态，令机器进入一个新的状态。 4、什么是存储程序的概念？ 要求程序和数据一样，也必须存储在计算机的主存储器中，这样计算机就能够自动重复地执 行程序，而不必每个问题都重新编程，从而大大加快运算进程。 二、计算机组成与原理 1、冯诺依曼计算机的组成结构 由运算器、控制器、存储器、输入设备、输出设备五大部分组成。
2、 递归过程，基于函数调用过程能够自主分析递归过程，得出结果。 递归算法的执行过程分递推和回归两个阶段。 递推阶段：不断简化问题的阶段，把对较复杂问题（规模为 n）的求解转化为比原问题简单 一些的问题（规模小于 n）的求解，当递推到最简单的不用再简化的问题时，递推终止。 回归阶段：当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。 问题 1：发出 f(2)调用时，将 2 赋值给形参 n。然后发出 f(1)调用，将 1 赋值给形参 n。接 着发出 f(0)调用，将 0 赋值给形参 n。后来赋给形参 n 的值会不会覆盖原来赋给 n 的值（如 值 1 覆盖原来的值 2）？为什么？