SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! ⑤值和名⑥名和地址 B:①可传回结果的值②可传回存放结果的地址 ③可传回结果的值和存放结果的地址④不可传回任何结果(值或地址) D:①直接②间接③变址④引用或赋值 E:①传值调用②引用调用③传名调用④宏扩展 【解析】 传值调用是指把实在参数的值传递给相应的形式参数,子程序不能通过这种方式传回任何结 果。引用调用是指把实在参数的地址传递给相应的形式参数,此时子程序对形式参数的一次 引用或赋值都是对形式参数的间接访问 C语言规定,实参变量对形式参数的数据传递是"值传递",即单向传递,只能由实参传给形 参,而不能由形参传给实参。所以说,C语言中函数是传值调用的。 【答案】A:③B:④C:①D:②E:① 试题5(1997年试题1) 从供选择的答案中,选出应填入下面叙述中内的最确切的答案,把相应编号写在答卷的对 应栏内 一种最早用于科学计算的程序设计语言是A:一种提供指针和指针操作且不存在布尔类型 的、应用广泛的系统程序设计语言是B:一种适合在互联网上编写程序可供不同平台上运行 的面向对象程序设计语言是C:一种在解决人工智能问题上使用最多的、有较强的表处理功 能的函数程序设计语言是D;一种以谓词逻辑为基础的、核心是事实、规则和推理机制的实 用逻辑程序设计语言E 供选择的答案 A~E:① Pascal②Ada③ Smalltalk④ Snobol⑤C ⑥ Alogo68⑦Java⑧Lisp⑨ Prologo (fOrtran 【解析】 程序设计语言从机器语言、汇编语言到今的高级语言,其发展越来越快,功能越来越强,同 时,其可理解性也越来越接爱人类的思维方式。 Fortran是第一种被用于进行科学计算的高级语言,它出现于50年代中期,其设计目的主要 暖和于科学计算,它在程序设计语言的发展史上起着突出的作用 Alogo68是另一种早期研制出来的高级语言,虽然没有被广泛使用,但对后来的程序设计语 言的发展有着重大影响 C语言是目前应用最广泛的系统程序设计语言,它提供了指针与指针操作,且不存在布尔类 型,对数据的访问灵活广泛,C语言还可提供很多底层系统调用,与硬件结合紧密,易用性 Java是适应 Internet发展的需要而产生的通用网络程序设计语言,它提供了更好的网络安全 性和平台无关性,并且采用了面向对象的原理,便于扩展,适合在互联网上编写可供不同平 台上运行的面向对象程序设计语言。 Prolog语言在人工智能领域应用较广泛,是一种以谓词逻辑为基础,借助于推理规则从已有 事实推出新的事实的实用的逻辑程序设计语言 Ada和 smalltalk两种语言引入了一定的封装机制,实现了信息隐臧。Ada的主要封装机制为 程序包: Smalltalk是一种纯面向对象程序设计语言,它侧重于动态链接,不进行任何类型 检查,并且类和对象之间没有明显区别 Snobol于1962年由贝尔实验室开发,它主要的操作为字符串操作。该语言一般不作为通用 语言使用,而是作为一种研究工具,用于对文艺作品、音乐等进行分析 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn931j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 31 页 ⑤值和名 ⑥名和地址 B：①可传回结果的值 ②可传回存放结果的地址 ③可传回结果的值和存放结果的地址 ④不可传回任何结果(值或地址) D：①直接 ②间接 ③变址 ④引用或赋值 E：①传值调用 ②引用调用 ③传名调用 ④宏扩展 【解析】 传值调用是指把实在参数的值传递给相应的形式参数，子程序不能通过这种方式传回任何结 果。引用调用是指把实在参数的地址传递给相应的形式参数，此时子程序对形式参数的一次 引用或赋值都是对形式参数的间接访问。 C 语言规定，实参变量对形式参数的数据传递是"值传递"，即单向传递，只能由实参传给形 参，而不能由形参传给实参。所以说，C 语言中函数是传值调用的。 【答案】A：③ B：④ C：① D：② E：① 试题 5 (1997 年试题 1) 从供选择的答案中，选出应填入下面叙述中 内的最确切的答案，把相应编号写在答卷的对 应栏内。 一种最早用于科学计算的程序设计语言是 A；一种提供指针和指针操作且不存在布尔类型 的、应用广泛的系统程序设计语言是 B；一种适合在互联网上编写程序可供不同平台上运行 的面向对象程序设计语言是 C；一种在解决人工智能问题上使用最多的、有较强的表处理功 能的函数程序设计语言是 D；一种以谓词逻辑为基础的、核心是事实、规则和推理机制的实 用逻辑程序设计语言 E。 供选择的答案 A～E：① ② ③ ④ ⑤ Pascal Ada Smalltalk Snobol C ⑥ ⑦⑧⑨ ⑩ Alogo 68 Java Lisp Prologo Fortran 【解析】 程序设计语言从机器语言、汇编语言到今的高级语言，其发展越来越快，功能越来越强，同 时，其可理解性也越来越接爱人类的思维方式。 Fortran 是第一种被用于进行科学计算的高级语言，它出现于 50 年代中期，其设计目的主要 暖和于科学计算，它在程序设计语言的发展史上起着突出的作用。 Alogo 68 是另一种早期研制出来的高级语言，虽然没有被广泛使用，但对后来的程序设计语 言的发展有着重大影响。 C 语言是目前应用最广泛的系统程序设计语言，它提供了指针与指针操作，且不存在布尔类 型，对数据的访问灵活广泛，C 语言还可提供很多底层系统调用，与硬件结合紧密，易用性 强。 Java 是适应 Internet 发展的需要而产生的通用网络程序设计语言，它提供了更好的网络安全 性和平台无关性，并且采用了面向对象的原理，便于扩展，适合在互联网上编写可供不同平 台上运行的面向对象程序设计语言。 Prolog 语言在人工智能领域应用较广泛，是一种以谓词逻辑为基础，借助于推理规则从已有 事实推出新的事实的实用的逻辑程序设计语言。 Ada 和 smalltalk 两种语言引入了一定的封装机制，实现了信息隐藏。Ada 的主要封装机制为 程序包；Smalltalk 是一种纯面向对象程序设计语言，它侧重于动态链接，不进行任何类型 检查，并且类和对象之间没有明显区别。 Snobol 于 1962 年由贝尔实验室开发，它主要的操作为字符串操作。该语言一般不作为通用 语言使用，而是作为一种研究工具，用于对文艺作品、音乐等进行分析
SMI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军)培训资料,请勿散发! Lip是一种在解决人工智能问题上使用最多的、有强的表处理功能的函数程序设计语言。 【答案】A:⑩:B:⑤C:⑦D:⑧E:⑨ 试题6(1997)年试题7 从供选择的答案中,选出应填入下面叙述中{}内的最确切的答案,把相应编号写在答卷的 对应栏内。 用高级语言编写程序时,子程序调用语句中的实在参数必须与子程序说明中的形式参数在A 上保持一致。在允许子程序递归调用的高级语言环境中,需用动态存储管理方法,它通常使 用一个B存放子程序的调用记录,调用记录可包括(1)全局量存储区域的C:(2)调用点所在 子程序的D;(3)调用点的E;(4)形式参数和实在参数的通信区域:(5)返回值:(6)本子程序 的局部量和临时变量存储区域等 供选择的答案 A:①个数、类型②个数、顺序 ③个数、格式、顺序④个数、类型、顺序 B:①线性表②队列③堆④下推栈 C~E:①子程序首地址②调用记录首地址 ③参数地址④寄存器地址 ⑤返回地址⑥开始地址 【解析】 除少数程序语言之外,形式参数和实在参数之间的对应关系通常按位置来确定。子程序定义 中有形式参数表,而子程序调用是用实在参数法表。进入子程序时,第一个形式参数就和第 个实在参数所表示的数据或其他信息相关联,依奖对应。这样,子程序调用语句中的实在 参数必须与子程序说明中的形式参数在个数、类型和顺序上保持一致,否则就不能在主程序 和子程序之间正确地传递信息 对于允许子程序递归调用的程序语言,一般采用动态存储管理方法,用下堆栈来实现。由于 某一子程序可能被调用了若干次,但只有最近一次调用正处于执行状态,而其余各次调用正 等待下次调用的返回。这样,前几次该子程序调用的属于该子程序的局部变量存储区中的内 容必须保存起来,以便下次调用返回时再继续使用。子程序执行需要一个用来存放有关信息 的区域,这个区域为过程的调用记录,一般包含以下几部分: 全局变量存储区域的开始地址 调用点所在子程序的调用记录的地址; 调用点机器状态,如返回地址和寄存器当时值 形式参数和实在参数的通信区域 回值 本子程序的局部量和临时变量存储区 【答案】:A:④B:④C:⑥D:②E:⑤ 试题7(1996年试题5 从供选择的答案中,选出应填入下面叙述中内的最确切的解答,把相应编号写在答卷的对 应栏内 有限状态自动机可用五元组(VT,Q,δ,q0,Qf)来描述,它可对应于A。设有一有限状态 自动机M的定义如下: VT={0,1}Q={q04q1q2} 6定义为: 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn932j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 32 页 Lisp 是一种在解决人工智能问题上使用最多的、有强的表处理功能的函数程序设计语言。 【答案】A：⑩： B：⑤ C：⑦ D：⑧ E：⑨ 试题 6 (1997)年试题 7 从供选择的答案中，选出应填入下面叙述中{ }内的最确切的答案，把相应编号写在答卷的 对应栏内。 用高级语言编写程序时，子程序调用语句中的实在参数必须与子程序说明中的形式参数在 A 上保持一致。在允许子程序递归调用的高级语言环境中，需用动态存储管理方法，它通常使 用一个 B 存放子程序的调用记录，调用记录可包括(1)全局量存储区域的 C；(2)调用点所在 子程序的 D；(3)调用点的 E；(4)形式参数和实在参数的通信区域；(5)返回值；(6)本子程序 的局部量和临时变量存储区域等。 供选择的答案 A：①个数、类型 ②个数、顺序 ③个数、格式、顺序 ④个数、类型、顺序 B：①线性表 ②队列 ③堆 ④下推栈 C～E：①子程序首地址 ②调用记录首地址 ③参数地址 ④寄存器地址 ⑤返回地址 ⑥开始地址 【解析】 除少数程序语言之外，形式参数和实在参数之间的对应关系通常按位置来确定。子程序定义 中有形式参数表，而子程序调用是用实在参数法表。进入子程序时，第一个形式参数就和第 一个实在参数所表示的数据或其他信息相关联，依奖对应。这样，子程序调用语句中的实在 参数必须与子程序说明中的形式参数在个数、类型和顺序上保持一致，否则就不能在主程序 和子程序之间正确地传递信息。 对于允许子程序递归调用的程序语言，一般采用动态存储管理方法，用下堆栈来实现。由于 某一子程序可能被调用了若干次，但只有最近一次调用正处于执行状态，而其余各次调用正 等待下次调用的返回。这样，前几次该子程序调用的属于该子程序的局部变量存储区中的内 容必须保存起来，以便下次调用返回时再继续使用。子程序执行需要一个用来存放有关信息 的区域，这个区域为过程的调用记录，一般包含以下几部分： ·全局变量存储区域的开始地址； ·调用点所在子程序的调用记录的地址； ·调用点机器状态，如返回地址和寄存器当时值； ·形式参数和实在参数的通信区域； ·返回值； ·本子程序的局部量和临时变量存储区。 【答案】：A：④ B：④ C：⑥ D：② E：⑤ 试题 7 (1996 年试题 5) 从供选择的答案中，选出应填入下面叙述中 内的最确切的解答，把相应编号写在答卷的对 应栏内。 有限状态自动机可用五元组(VT，Q，δ，q0，Qf)来描述，它可对应于 A。设有一有限状态 自动机 M 的定义如下： VT={0，1} Q={q0,q1,q2} δ 定义为：
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 6(q00)=q1,6q10=q2 6(q2,1)=q2,6(q20)=q M是一个B有限状态自动机,它所对应的状态转换图为C,它所能接受的语言可以用正则 表达式表示为D,其含义为E 供选择的答案 A:①0型文法②1型文法③2型文法④3型文法 B:①歧义的②非歧义的③确定的④非确定的 50.1 0.1 0 0 D:①(01)*②000)③(01)+00④001)*0 E:①由0和1所组成的符号串的集合。 ②以0为头符号和尾符号、由0和1所组成的符号串的集合。 ③以两个0为结束的、由0和1所组成的符号串的集合 ④以两个0为开始的、由0和1所组成的符号串的集合。 【解析】 先来看一下地分类表2-3 Chomsky文法分类表 定奖型 文法名称 对后的自动机 递可枝举语 图灵机(T 后文相关交法 前后文有关语言 线性限界自动 后文无关语言 非确定下自 正规文法 有限状态语言 个有限状态自动机M用5元组(VT,Q,δ,q0,Q来表示,其中ⅤT={0,1}是一个有穷 字母表,它的每个元素称为一个输入字符:Q(q0,q14q2)是一个有限集,它的每个元素称为 个状态:6定义为8q0,0)=q1,6(q10)=q2,6(q2,1)=q2.6(q2,0=q2是一个从VTxQ到Q上的(单 值)部分映射;q为初态;Qe={q2}为终态集 有限自动机分为确定的有限自动机和非确定的有限自动机。确定的有限自动机的确定性表现 在映射δ:VT×Q→Q是一个单值函数,即对任何状态qQ和输入字符aVT,映射8q,a) 唯一确定下一个状态。由分析可知本题给出的是一个确定的有限自动机,它的状态转换如图 2-7所示 它所能接受的语言可以用正则表达式表示为000)*,其含义为由两个0开始的后跟任意个 包含0个或多个0或1组成的符号串的集号 【答案】:A:④B:③C:/D:/E:/ (注:原题中C的供选择答案有印刷错误,故C、D、E的任何解答均作正确处理。) 试题8(1995年试题15 从供选择的答案中,选出应填入下面叙述中{}内的正确答案,把编号写在答卷的对应栏内。 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn933j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 33 页 δ(q0,0)=q1,δ(q1,0)=q2 δ(q2,1)=q2,δ(q2,0)=q2 Qf={q2} M 是一个 B 有限状态自动机，它所对应的状态转换图为 C，它所能接受的语言可以用正则 表达式表示为 D，其含义为 E。 供选择的答案 A：①0 型文法 1 ② 型文法 2 ③ 型文法 3 ④ 型文法 B：①歧义的 ②非歧义的 ③确定的 ④非确定的 D：①② ③ ④ (0|1)* 00(0|1) (0|1)*00 0(0|1)*0 E：①由 0 和 1 所组成的符号串的集合。 ②以 0 为头符号和尾符号、由 0 和 1 所组成的符号串的集合。 ③以两个 0 为结束的、由 0 和 1 所组成的符号串的集合。 ④以两个 0 为开始的、由 0 和 1 所组成的符号串的集合。 【解析】 先来看一下地分类表 2-3 一个有限状态自动机 M 用 5 元组(VT，Q，δ，q0，Qf)来表示，其中 VT={0，1}是一个有穷 字母表，它的每个元素称为一个输入字符：Q=(q0,q1,q2)是一个有限集，它的每个元素称为 一个状态；δ 定义为 δ(q0,0)=q1,δ(q1,0)=q2,δ(q2,1)=q2,δ(q2,0)=q2 是一个从 VT×Q 到 Q 上的(单 值)部分映射；q0 为初态；Qf={q2}为终态集。 有限自动机分为确定的有限自动机和非确定的有限自动机。确定的有限自动机的确定性表现 在映射 δ：VT×Q→Q 是一个单值函数，即对任何状态 q Q 和输入字符 a VT，映射 δ(q,a) 唯一确定下一个状态。由分析可知本题给出的是一个确定的有限自动机，它的状态转换如图 2-7 所示。 它所能接受的语言可以用正则表达式表示为 00(0|1)*，其含义为由两个 0 开始的后跟任意个 (包含 0 个或多个)0 或 1 组成的符号串的集号。 【答案】：A：④ B：③ C：/ D：/ E：/ (注：原题中 C 的供选择答案有印刷错误，故 C、D、E 的任何解答均作正确处理。) 试题 8 (1995 年试题 15) 从供选择的答案中，选出应填入下面叙述中{ }内的正确答案，把编号写在答卷的对应栏内
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 编译技术涉及语言和自动机理论,形式语言可由短语结构文法G生成(记为L(G),G可分 成0型、1型、2型、3型和4种类型,与之相对应的自动机分别为图灵机、A、B、C。 个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法G,只有当 G为D时,命题"(G)是空集,有限集或无限集才是可判定的,当给出二个不同文法G1和 G2,只有当G1、G2都是E时命题"(G1)=L(G2)"才是可判定的 供选择的答案 ~C:①自动机②下推自动机③双向自动机 ④线性界限自动机⑤有限状态自动机⑥非线性自动机 D~E:①1型②2型③3型④0型 ⑤2型或3型⑥1型或2型或3型⑦0型或1型或2型或3型 【解析】 用计算机对自然语言进行完全自动处理是一件十分困难的事情。这是因为自然语言歧义性 哟,用形式化的语法描述起来很困难。为了便于计算机的自动处理,语言的形式化描述便显 得十分重要。现有算法语言在形式上都是形式语言 形式语言可由短语结构文法来生成。一个短语结构文法G是一个4元组:G=(VTVN,PS)。 其中VT是终止符的非空有限集,VN是非终止符的变量的非空有限集,S为起始符,P是 产生式集。P中的每个产生式又称重写规则,其一般形式是α→β,其中α、β均为字符串 由起始符开始,不断使用P中产生式,可能得到终止符组成的字符串。这种终止符串的全 体就是文法G生成的语言,记为LG) 按照对产生式中α和β的不同限制,文法G可分成0型、1型、2型、3型4类,又分别称 图灵文法、上下文有关文法、上下文无关文法、正则文法。由文法所生成的语言也相应分成 这4类。自动机是能由文法G产生出G所生成的语言L(G)的一种装置,它可用一个5元组 表示。自动机也可分好多种,其中有限状态自动机是能由正则文法产生正则语言的自动机, 即它对应于3型语言:下推自动机则对应于上下文无关语言(2型):线性界限自动机则对应 于上下文有关语言(1)型:图灵机则对应于0型语言。 文法G是任意给出的,有可能出现这样的情况:给定某个文法G,对T中的终止符所组成 的任何字符串都无法识别出它能由G生成,即L(G)是个空集。也可能有某个给定的文法G 其L(G)是无限制。由于VT的终止符可重复出现,字符串长度无限制,因此不可能用列举 终止字符串进行句法分析,以判断给定的G,其L(G)是无限集还是有限集,或是空集。 我们期望能有一种算法,可直接从G出发,通过有限步运算给出L(G)是空集、有限集或无 限集的结论。若存在这样的算法,就是可判定的,否则就不是可判定的。研究中发现可否判 定L(G)是空集、有限集或无限集与文法G有关的,可以证明,当文法G是2型或3型时, 是可判定的。类似的,对二个文法G1与G2是否等价即是否有LG1)=L(G2),只有当Gl 和G2都是3型文法时,才是可判定的 【答案】A:④B:②C:⑤D:⑤E:③ 试题9(1994年试题2) 从供选择的答案中,选出应填入{}内的正确答案,把编号写在答卷的对应栏内。 在下列程序中 Program test(input, output); Var 1, ]: integer Procedure calc(pl, p2: integer) Begin p2: -p2*p2; pl: =pl-p2: =p2-pl; end(calc) Begin( main; 1:=2 3:=3 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn98341
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 34 页 编译技术涉及语言和自动机理论，形式语言可由短语结构文法 G 生成(记为 L(G))，G 可分 成 0 型、1 型、2 型、3 型和 4 种类型，与之相对应的自动机分别为图灵机、A、B、C。一 个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定文法 G，只有当 G 为 D 时，命题"L(G)是空集，有限集或无限集"才是可判定的，当给出二个不同文法 G1 和 G2，只有当 G1、G2 都是 E 时命题"L(G1)=L(G2)"才是可判定的。 供选择的答案 A～C：①自动机 ②下推自动机 ③双向自动机 ④线性界限自动机 ⑤有限状态自动机 ⑥非线性自动机 D～E：①1 型 2 ② 型 3 ③ 型 0 ④ 型 ⑤2 型或 3 型 1 ⑥ 型或 2 型或 3 型 0 ⑦ 型或 1 型或 2 型或 3 型 【解析】 用计算机对自然语言进行完全自动处理是一件十分困难的事情。这是因为自然语言歧义性 哟，用形式化的语法描述起来很困难。为了便于计算机的自动处理，语言的形式化描述便显 得十分重要。现有算法语言在形式上都是形式语言。 形式语言可由短语结构文法来生成。一个短语结构文法 G 是一个 4 元组：G=(VT,VN,P,S)。 其中 VT 是终止符的非空有限集，VN 是非终止符的变量的非空有限集，S 为起始符，P 是 产生式集。P 中的每个产生式又称重写规则，其一般形式是 α→β，其中 α、β 均为字符串。 由起始符开始，不断使用 P 中产生式，可能得到终止符组成的字符串。这种终止符串的全 体就是文法 G 生成的语言，记为 L(G)。 按照对产生式中 α 和 β 的不同限制，文法 G 可分成 0 型、1 型、2 型、3 型 4 类，又分别称 图灵文法、上下文有关文法、上下文无关文法、正则文法。由文法所生成的语言也相应分成 这 4 类。自动机是能由文法 G 产生出 G 所生成的语言 L(G)的一种装置，它可用一个 5 元组 表示。自动机也可分好多种，其中有限状态自动机是能由正则文法产生正则语言的自动机， 即它对应于 3 型语言；下推自动机则对应于上下文无关语言(2 型)；线性界限自动机则对应 于上下文有关语言(1)型；图灵机则对应于 0 型语言。 文法 G 是任意给出的，有可能出现这样的情况：给定某个文法 G，对 VT 中的终止符所组成 的任何字符串都无法识别出它能由 G 生成，即 L(G)是个空集。也可能有某个给定的文法 G， 其 L(G)是无限制。由于 VT 的终止符可重复出现，字符串长度无限制，因此不可能用列举 终止字符串进行句法分析，以判断给定的 G，其 L(G)是无限集还是有限集，或是空集。 我们期望能有一种算法，可直接从 G 出发，通过有限步运算给出 L(G)是空集、有限集或无 限集的结论。若存在这样的算法，就是可判定的，否则就不是可判定的。研究中发现可否判 定 L(G)是空集、有限集或无限集与文法 G 有关的，可以证明，当文法 G 是 2 型或 3 型时， 是可判定的。类似的，对二个文法 G1 与 G2 是否等价即是否有 L(G1)=L(G2)，只有当 G1 和 G2 都是 3 型文法时，才是可判定的。 【答案】A：④ B：② C：⑤ D：⑤ E：③ 试题 9 (1994 年试题 2) 从供选择的答案中，选出应填入{ }内的正确答案，把编号写在答卷的对应栏内。 在下列程序中： Program test (input, output)； Var i, j: integer； Procedure calc (pl, p2: integer)； Begin p2:=p2*p2; pl:=p1-p2:=p2-p1;end{calc} Begin{main}i:=2,j:=3
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! Calc(ij); write(): End main i 当参数传递采用引用方式( Call by reference)时,所得结果j=A 当参数传递采用换名方式( Call by name)时,所得结果j=B; 当参数传递采用赋值方式( Call by value)时,所得结果j=C 递归是程序设计中很重要的一种控制结构,通常实现递归时,采用的数据结构是D。 对那些既可以用递归方式,也可以用循环方式求解的问题,就执行效率而言E 供选择的答案 A~C:①0②3③5④6 ⑤10⑥16⑦20⑧28 D:①数组②栈③队列④循环链表 E:①数组②两者相同③循环优于递归④递归优于循环 【解析】 个过程的过程体若包含对其自身的调用,则称此过程是直接递归的。若一个过程的过程体 调用某过程,而该过程又调用原过程或经一系列调用后又回到对原过程的调用,则称此原过 程是间接递归的。通常实现递归时采用的数据结构是栈,这是因为栈有先进后出的特性,可 以保存调用时的"现场",并在调用结束时恢复"现场",栈是实现递归的简单途径。对于既可 用递归方式求解,也可用循环方式求解的问题,就执行效率和资源而言,显然是循环优于递 归,因为递归的开销大。 当用户在调用点调用一个过程时,会通过参数传送信息,一个过程的形式参数用来向过程传 送信息的标识符,实在参数用来在调用点向被调用过程传送信息。形式参数和实在参数之间 的关系通常按位置来标定,不同程序语言所规定的参数信息传送方式不同。 当采用引用方式( Call by reference减或换名方式 Call by name时,在过程中对形式参数的调用 本质上是对实在参数单元的引用。先是给形式参数赋初值,而后,在过程中对该形式参数的 赋值最终引起调用程序中实在参数值的改变。在本题中形式参数为pl和p2。实在参数初值 为i=2和j=3,通过引用方式调用这两个参数,将执行以下计算过程 pl=2p2=3p2=p2°p2=9pl:=pl-p2=2-3=7p2:=p2-pl=9(-7)=16 所得结果为j=16。 参数传送采用赋值方式时,从调用点向被调用过程传送的是实在参数的值。这一值成为过程 中相应位置上形式参数的初值,此后该形式参数在过程中实际是局部变量,其结果无需返回 给实在参数。本题中实在参数j=3,在过程中仅起向形式参数p2赋初值的作用。过程中关 于p2的运算对j不再起作用,因而过程调用结束后j的值仍为3。 【答案】A:⑥B:⑥C:②D:②E:③ 试题10(1994年试题16 从供选择的答案中,选出应填入下面有关形式语言叙述中{}内的正确答案,把编号写在答 卷的对应栏内。 文法G=( VTVNPS)的类型由G中的A决定。若G0=({ab},S,X,Y,PS),P中的产生式及其 序号如下 l:S→XaY 则G0为型文法,对应于C,由G0推导出句子aa和 baabbb时,所用产生式序号组成的序 列分别为D和E 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn33 页
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 35 页 Calc(i,j);write(j); End{main} 当参数传递采用引用方式(Call by reference)时，所得结果 j=A； 当参数传递采用换名方式(Call by name)时，所得结果 j=B； 当参数传递采用赋值方式(Call by value)时，所得结果 j=C； 递归是程序设计中很重要的一种控制结构，通常实现递归时，采用的数据结构是 D。 对那些既可以用递归方式，也可以用循环方式求解的问题，就执行效率而言 E。 供选择的答案 A～C：① ② ③ ④ 0 3 5 6 ⑤10 16 20 28 ⑥ ⑦ ⑧ D：①数组 ②栈 ③队列 ④循环链表 E：①数组 ②两者相同 ③循环优于递归 ④递归优于循环 【解析】 一个过程的过程体若包含对其自身的调用，则称此过程是直接递归的。若一个过程的过程体 调用某过程，而该过程又调用原过程或经一系列调用后又回到对原过程的调用，则称此原过 程是间接递归的。通常实现递归时采用的数据结构是栈，这是因为栈有先进后出的特性，可 以保存调用时的"现场"，并在调用结束时恢复"现场"，栈是实现递归的简单途径。对于既可 用递归方式求解，也可用循环方式求解的问题，就执行效率和资源而言，显然是循环优于递 归，因为递归的开销大。 当用户在调用点调用一个过程时，会通过参数传送信息，一个过程的形式参数用来向过程传 送信息的标识符，实在参数用来在调用点向被调用过程传送信息。形式参数和实在参数之间 的关系通常按位置来标定，不同程序语言所规定的参数信息传送方式不同。 当采用引用方式(Call by reference)或换名方式(Call by name)时，在过程中对形式参数的调用 本质上是对实在参数单元的引用。先是给形式参数赋初值，而后，在过程中对该形式参数的 赋值最终引起调用程序中实在参数值的改变。在本题中形式参数为 p1 和 p2。实在参数初值 为 i=2 和 j=3，通过引用方式调用这两个参数，将执行以下计算过程： p1=2,p2=3 p2:=p2*p2=9 p1:=p1 -p2=2-3=-7 p2:=p2-p1=9-(-7)=16 所得结果为 j=16。 参数传送采用赋值方式时，从调用点向被调用过程传送的是实在参数的值。这一值成为过程 中相应位置上形式参数的初值，此后该形式参数在过程中实际是局部变量，其结果无需返回 给实在参数。本题中实在参数 j=3，在过程中仅起向形式参数 p2 赋初值的作用。过程中关 于 p2 的运算对 j 不再起作用，因而过程调用结束后 j 的值仍为 3。 【答案】A：⑥ B：⑥ C： D ② ： E ② ：③ 试题 10 (1994 年试题 16) 从供选择的答案中，选出应填入下面有关形式语言叙述中{ }内的正确答案，把编号写在答 卷的对应栏内。 文法 G=(VT,VN,P,S)的类型由 G 中的 A 决定。若 G0=({a,b},{S,X,Y},P,S)，P 中的产生式及其 序号如下： 1：S→XaaY 2：X→YY|b 3：Y→XbX|a 则 G0 为型文法，对应于 C，由 G0 推导出句子 aaaa 和 baabbb 时，所用产生式序号组成的序 列分别为 D 和 E