SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 不是路径上边数的总和。关键路径是指两个结点间具有的最大长度的路径。通过计算可知, (Ⅵ1,Ⅵ2,Vs,V7,V8)是最短路径,(V,Ⅴ6,V5,Ⅴ3,V8)是关键路径 【答案】A:⑦B:③C:②D:④E:② 试题11(1992年试题6) 从供选择的答案中选出应填入{}内的正确答案,把编号写在答卷的对应栏内 在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会 产生不同的排序中间结果。设要将序列<Q,H,C,Y,P,A,M,S,R,F,X>中的关 键码按字母的升序重新排列,则A是冒泡排序一趟扫描的结果,B是初始步长为4的希尔 (She)排序一趟扫描的结果,C是两路归并(合并)排序一趟扫描的结果,D是以第一个元素 为分界元素的快速排序一趟扫描的结果,E是堆排序初始建堆的结果。 供选择的答案 A-E: F, H, C,D, P,A,M,Q,R,S,Y,X ②P,A,C,S,Q, ③A,D,C,R,F,Q,M,S,Y,P,H,Ⅹ OH, C,Q, P,A,M,S,R,D, F,X,Y ⑤H,Q,C,Y,A,P,M,S,D,R,F,Ⅹ 【解析】 冒泡排序将待排序的记录顺次两两比较,如为逆序则进行交换,将待排序序列依此法从头至 尾处理一遍称作一趟冒泡,一趟冒泡的效果是将关键码值最大的元素交换到了最后位置。对 于试题给定的序列,经一趟冒泡后变成序列<H,C,Q,P,A,M,S,R,D,F,X,Y 希尔排序也是一种插入排序,其特点是把待排序序列每隔某个”步长"的元素组成一个子序 列,分别对每个子序列进行直接插入排序,排序后的结果称为一趟扫视。每趟减少相隔步长 ,直至步长为1,对整个序列作一次扫视。对于试题给定的序列,取初始步为4,希尔排序 一趟扫视后,将序列变成为<P,A,C,S,Q,D,F,Ⅹ,R,H,M,Y>。 两路归并排序是一种最简单的归并排序,它将含n个元素的待排序序列看作n个已排序的子 序列。首先将每两个子序列归并,得到n/2个已排序的较大的子序列:再对这些子序列归并, 如此反复,直到最后归并成一个序列,排序即告完成。由上述两路归并的方法可知,对于试 题所给的序列,经两路归并排序的一趟扫描后,序列变成<H,Q,C,Y,A,P,M,S, 快速排序的基本思想是通过一趟扫视将待排序序列分成两个子序列,然后分别对这两个子序 列进行排序,如此重复,以达到最后对整个序列的排序。具体方法是:任选待排序序列中的 某元素(通常选第一个元素),用它的关键码同(子)序列中所有其余元素的关键码相比较,将 所有关键码仍比它小的元素移到它之前,所有关键码较它大的元素都移到它之后。经这样一 趟扫视后,以该元素为界,将(子)序列分成两个子序列。反复对上述子序列作同样的操作, 直至每个子序列都只有一个元素为止。对试题给定的序列,以它的第一个元素为分界元素作 次划分,使序列都只有一个元素为止。对试题给定的序列,以它的第一个元素为分界元素 作一次划分,使序列变成<F,H,C,D,P,A,M,Q,R,S,Y,X 堆将待排序序列看作一棵完全二叉树,若其关键码序列 hI. h2.., hn 满足以下性质 hih2i,hi<h2+1,(i=1,2,,[n2]) 则称该序列是一个堆。即子树根结点hi,其关键码值比它的左、右子结点h2(2n)和 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn921j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 21 页 不是路径上边数的总和。关键路径是指两个结点间具有的最大长度的路径。通过计算可知， (V1，V2，V5，V7，V8)是最短路径，(V1，V6，V5，V3，V8)是关键路径。 【答案】A：⑦ B：③ C：② D：④ E：② 试题 11(1992 年试题 6) 从供选择的答案中选出应填入{ }内的正确答案，把编号写在答卷的对应栏内。 在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会 产生不同的排序中间结果。设要将序列＜Q，H，C，Y，P，A，M，S，R，F，X＞中的关 键码按字母的升序重新排列，则 A 是冒泡排序一趟扫描的结果，B 是初始步长为 4 的希尔 (Shell)排序一趟扫描的结果，C 是两路归并(合并)排序一趟扫描的结果，D 是以第一个元素 为分界元素的快速排序一趟扫描的结果，E 是堆排序初始建堆的结果。 供选择的答案 A～E：①F，H，C，D，P，A，M，Q，R，S，Y，X ②P，A，C，S，Q，D，F，X，R，H，M，Y ③A，D，C，R，F，Q，M，S，Y，P，H，X ④H，C，Q，P，A，M，S，R，D，F，X，Y ⑤H，Q，C，Y，A，P，M，S，D，R，F，X 【解析】 冒泡排序将待排序的记录顺次两两比较，如为逆序则进行交换，将待排序序列依此法从头至 尾处理一遍称作一趟冒泡，一趟冒泡的效果是将关键码值最大的元素交换到了最后位置。对 于试题给定的序列，经一趟冒泡后变成序列＜H，C，Q，P，A，M，S，R，D，F，X，Y ＞。 希尔排序也是一种插入排序，其特点是把待排序序列每隔某个"步长"的元素组成一个子序 列，分别对每个子序列进行直接插入排序，排序后的结果称为一趟扫视。每趟减少相隔步长 ，直至步长为 1，对整个序列作一次扫视。对于试题给定的序列，取初始步为 4，希尔排序 一趟扫视后，将序列变成为＜P，A，C，S，Q，D，F，X，R，H，M，Y＞。 两路归并排序是一种最简单的归并排序，它将含 n 个元素的待排序序列看作 n 个已排序的子 序列。首先将每两个子序列归并，得到 n/2 个已排序的较大的子序列；再对这些子序列归并， 如此反复，直到最后归并成一个序列，排序即告完成。由上述两路归并的方法可知，对于试 题所给的序列，经两路归并排序的一趟扫描后，序列变成＜H，Q，C，Y，A，P，M，S， D，R，F，X＞。 快速排序的基本思想是通过一趟扫视将待排序序列分成两个子序列，然后分别对这两个子序 列进行排序，如此重复，以达到最后对整个序列的排序。具体方法是：任选待排序序列中的 某元素(通常选第一个元素)，用它的关键码同(子)序列中所有其余元素的关键码相比较，将 所有关键码仍比它小的元素移到它之前，所有关键码较它大的元素都移到它之后。经这样一 趟扫视后，以该元素为界，将(子)序列分成两个子序列。反复对上述子序列作同样的操作， 直至每个子序列都只有一个元素为止。对试题给定的序列，以它的第一个元素为分界元素作 一次划分，使序列都只有一个元素为止。对试题给定的序列，以它的第一个元素为分界元素 作一次划分，使序列变成＜F，H，C，D，P，A，M，Q，R，S，Y，X＞。 堆将待排序序列看作一棵完全二叉树，若其关键码序列 h1,h2,…，hn. 满足以下性质： hi≤h2i，hi≤h2i+1，(i=1，2，…，［n/2］) 则称该序列是一个堆。即子树根结点 hi，其关键码值比它的左、右子结点 h2i(2i≤n)和
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! h2+1(2i+1≤n)的关键码值都要小 堆排序的基本思想如下:由于堆的根结点的关键码值是最小的,取走根结点,让剩下的其余 结点重新建成堆,则能从新堆的根结点取走次最小的。如此反复,得到一个递增的排序序列 堆排序的基本问题是如何建堆,建立初始堆的方法是首先将第1个至第n个结点分别看作 是只有一个结点的堆,然后逐步把结点第[n-1]个、第[n2]-1个.第1个结点,分别加 到它们的两棵左、右子树上构成堆,最终变成一个堆 对于试题给定的序列,经上述初始建堆步骤后,序列变成<A,D,C,R,F,Q,M,S, Y,P,H,Ⅹ>。 【答案】A:④B:②C:⑤D:①E:③ 试题12(1991年试题3) 从下列叙述中选出5条正确的叙述,把编号依次写在答卷的A~E栏内 ①m阶B树每一个结点的后件个数都小于等于m ②m阶B树每一个结点的后件个数都大于等于[m/2] ③m阶B-树具有k个后件的非叶子结点含有k-1个键值。 ④m阶B-树的任何一个结点左右子树的高度都相等 ⑤中序遍历一棵查找树的结点就可得到排好序的结点序列 ⑥用指针的方式存储一棵有n个结点的二叉树,最少要n+1个指针。 ⑦任一査找树的平均査找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 ⑧平衡树一定是丰满树 ⑨已知树的前序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个 ⑩0不使用递归,也可实现二叉树的前序、中序及后序遍历 【解析】 m阶B-树是一种平衡的m叉树,具有如下的性质 (1)每个结点的后件个数小于等于m (2)除了根结点和叶结点之外,每个结点的后件个数大于等于(m2) (3)具有k个后件的非叶结点含有k-1个键值 (4)所有叶结点在同一层上,而且不附有信息 m阶B-树是平衡树,其上任一结点的所有子树的高度都是相等的 具有下列性质的二叉树称为査找树:除叶结点外,每个结点的键值大于其左子树上一切结点 的键值,且小于等于其右子树上一切结点的键值 中序遍历法访问二叉树结点的过程是:递归地访问左子树,然后访问树根,再访问右子树。 因此,用中序遍历法遍历一棵二叉查找树可以得到按键值升序排列的结点序列。在用链接表 表示法存储n个结点的二叉树上,最多有2n个指针,其中n+1个是空指针,n-1个指针用 于指向后件。因此,最少要n+1个指针的说法是不对的。 在给定的查找树上,由根结点到所有其他结点的路径长度总和称为内部路径长度。当一棵二 叉树退化为线性链表时,它的内部路径长度最大,等于n(n-1)2,所以退化二叉树的查找时 间(包括平均查找时间)等于线性表顺序查找时间。答案⑦是错误的 具有最小内部路径长度的树是丰满树,对丰满树的查找树进行插入或者删除操作后,会产生 棵非丰满树。平衡二叉树是指其上任一结点的左右子树的高度(或者结点个数)保持一定比 例的树,即平衡树上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近 但是在插入或者删除结点时容易产生仍保持平衡的树。由丰满树同平衡树定义可知,丰满 树一定是平衡树,但是平衡树不一定是丰满树。 用前序遍历法访问一棵树的原则是:递归地访问树根,然后访问左子树,再访问右子树。因 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn922j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 22 页 h2i+1(2i+1≤n)的关键码值都要小。 堆排序的基本思想如下：由于堆的根结点的关键码值是最小的，取走根结点，让剩下的其余 结点重新建成堆，则能从新堆的根结点取走次最小的。如此反复，得到一个递增的排序序列 。堆排序的基本问题是如何建堆，建立初始堆的方法是首先将第 1 个至第 n 个结点分别看作 是只有一个结点的堆，然后逐步把结点第［n-1］个、第［n/2］-1 个…第 1 个结点，分别加 到它们的两棵左、右子树上构成堆，最终变成一个堆。 对于试题给定的序列，经上述初始建堆步骤后，序列变成＜A，D，C，R，F，Q，M，S， Y，P，H，X＞。 【答案】A：④ B：② C：⑤ D：① E：③ 试题 12(1991 年试题 3) 从下列叙述中选出 5 条正确的叙述，把编号依次写在答卷的 A～E 栏内。 ①m 阶 B-树每一个结点的后件个数都小于等于 m。 ②m 阶 B-树每一个结点的后件个数都大于等于［m/2］。 ③m 阶 B-树具有 k 个后件的非叶子结点含有 k-1 个键值。 ④m 阶 B-树的任何一个结点左右子树的高度都相等。 ⑤中序遍历一棵查找树的结点就可得到排好序的结点序列。 ⑥用指针的方式存储一棵有 n 个结点的二叉树，最少要 n+1 个指针。 ⑦任一查找树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。 ⑧平衡树一定是丰满树。 ⑨已知树的前序遍历并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。 ⑩不使用递归，也可实现二叉树的前序、中序及后序遍历。 【解析】 m 阶 B-树是一种平衡的 m 叉树，具有如下的性质： (1)每个结点的后件个数小于等于 m； (2)除了根结点和叶结点之外，每个结点的后件个数大于等于(m/2)； (3)具有 k 个后件的非叶结点含有 k-1 个键值； (4)所有叶结点在同一层上，而且不附有信息。 m 阶 B-树是平衡树，其上任一结点的所有子树的高度都是相等的。 具有下列性质的二叉树称为查找树：除叶结点外，每个结点的键值大于其左子树上一切结点 的键值，且小于等于其右子树上一切结点的键值。 中序遍历法访问二叉树结点的过程是：递归地访问左子树，然后访问树根，再访问右子树。 因此，用中序遍历法遍历一棵二叉查找树可以得到按键值升序排列的结点序列。在用链接表 表示法存储 n 个结点的二叉树上，最多有 2n 个指针，其中 n+1 个是空指针，n-1 个指针用 于指向后件。因此，最少要 n+1 个指针的说法是不对的。 在给定的查找树上，由根结点到所有其他结点的路径长度总和称为内部路径长度。当一棵二 叉树退化为线性链表时，它的内部路径长度最大，等于 n(n-1)/2，所以退化二叉树的查找时 间(包括平均查找时间)等于线性表顺序查找时间。答案⑦是错误的。 具有最小内部路径长度的树是丰满树，对丰满树的查找树进行插入或者删除操作后，会产生 一棵非丰满树。平衡二叉树是指其上任一结点的左右子树的高度(或者结点个数)保持一定比 例的树，即平衡树上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近 ，但是在插入或者删除结点时容易产生仍保持平衡的树。由丰满树同平衡树定义可知，丰满 树一定是平衡树，但是平衡树不一定是丰满树。 用前序遍历法访问一棵树的原则是：递归地访问树根，然后访问左子树，再访问右子树。因
SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 此,前序遍历第一个被访问的结点就是原树的根结点,"不知道树的根结点"的说法是错误 的。二叉树的前序、中序和后序遍历法都是递归的。因此,最适合使用递归程序方法实现这 3种遍历算法。当然不用递归程序方法也能够实现这3种遍历算法,但是程序比较复杂, 般需要用栈或队列操作来实现。 【答案】A:①B:③C:④D:⑤E⑩ 试题13(1990年试题4) 从供选择的答案中选出应填入下列叙述中的{}内的正确答案,把编号写在答案的对应栏内。 在查找算法,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为 ASL=>PiCi 此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为 表中表有记录数。 以下叙述中均假定每一个记录被查找的概率相等,即Pi=/n(i=1,2, 当表中的记录连续存储备在一个一维数组中时,可采用顺序查找与折半查找方法(折半查找 要求表是按关键字有序排列的)。顺序查找时的ASL为A,折半查找时的ASL为B。记录的 关键字有序时,用二叉排序树查找记录,在最坏的情况下,ASL为C。当二叉排序树是 棵平衡树时,ASL为D。在平衡树上删除一个结点后可以通过旋转使其平衡,最坏的情形 下需E次旋转 供选择的答案 A~E:①O1)②Olon2n)③O(on2n)2④ O(nlog2n) 【解析】 顺序査找:比较一次可査到第1个元素,比较两次可查到第2个元素。一般地,比较i次可 查到第ⅰ个元素。 顺序查找的ASL为:ASL=(1/n)+n(n+1)2)=n(n+1)2=O(n) 折半查找:比较一次可找到一个元素;比较两次可找到两个元素:一般地,比较i次可找到 2i-1个元素。总共n个元素,最多需比较log(n+1)次。 折半查找的ASL为:ASL loz、(N+1 -1 而归纳法不难证明 将此式入上式,折半查找的ASL为 ASL=l/n(n+1(log(n+1)+1)=l/n(n+1)log2(n+1)-1 O(log2n) 对于二叉排序树的查找,最坏情况是二叉树中没有结点,有两棵子树。在这种情况下,二叉 排序树查找相当于顺序查找,即最坏情况下,ASLA为ASL=O(n)。 对于平衡的二叉排序树查找,平衡二叉排序树中的每个结点的左右子树高度差不大于1,n 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn923j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 23 页 此，前序遍历第一个被访问的结点就是原树的根结点，"不知道树的根结点"的说法是错误 的。二叉树的前序、中序和后序遍历法都是递归的。因此，最适合使用递归程序方法实现这 3 种遍历算法。当然不用递归程序方法也能够实现这 3 种遍历算法，但是程序比较复杂，一 般需要用栈或队列操作来实现。 【答案】A：① B：③ C：④ D：⑤ ⑩ E 试题 13(1990 年试题 4) 从供选择的答案中选出应填入下列叙述中的{ }内的正确答案，把编号写在答案的对应栏内。 在查找算法，可用平均查找长度(记为 ASL)来衡量一个查找算法的优劣，其定义为： 此处 Pi 为表中第 i 个记录被查找的概率，Ci 为查找第 i 个记录时同关键字比较的次数，n 为 表中表有记录数。 以下叙述中均假定每一个记录被查找的概率相等，即 Pi=1/n(i=1，2，…，n)。 当表中的记录连续存储备在一个一维数组中时，可采用顺序查找与折半查找方法(折半查找 要求表是按关键字有序排列的)。顺序查找时的 ASL 为 A，折半查找时的 ASL 为 B。记录的 关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL 为 C。当二叉排序树是一 棵平衡树时，ASL 为 D。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形 下需 E 次旋转。 供选择的答案 A～E：① ② O(1) O(lon2 n) O(lon ③ 2 n)2 O(nlog ④ 2n) ⑤ ⑥ O(n) O(n2 ) 【解析】 顺序查找：比较一次可查到第 1 个元素，比较两次可查到第 2 个元素。一般地，比较 i 次可 查到第 i 个元素。 顺序查找的 ASL 为：ASL=（1/n）*(n(n+1)/2) =n(n+1)/2=O(n) 折半查找：比较一次可找到一个元素；比较两次可找到两个元素；一般地，比较 i 次可找到 2i-1 个元素。总共 n 个元素，最多需比较 log2(n+1)次。 折半查找的 ASL 为：ASL 而归纳法不难证明： 将此式入上式，折半查找的 ASL 为： ASL=1/n(n+1)(log2(n+1)+1)=1/n(n+1)log2(n+1)-1 =O(log2n) 对于二叉排序树的查找，最坏情况是二叉树中没有结点，有两棵子树。在这种情况下，二叉 排序树查找相当于顺序查找，即最坏情况下，ASLA 为 ASL=O(n)。 对于平衡的二叉排序树查找，平衡二叉排序树中的每个结点的左右子树高度差不大于 1，n
SMI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军)培训资料,请勿散发! 个结点的平衡树的深度和logn是同数量级。对二叉排序树来说,它的査找时间与树的深度 成正比。因此,平衡二叉排序树的ASL为ASL=Oogn) 在平衡树上删除或插入结点往往会破坏树的平衡。通过旋转又可使其重新成为一棵平衡树。 在最坏情况下,从叶子开始一直调整到根为止,需进行的旋转次数与树的深度一致,等于 【答案】:A:⑤B:②C:⑤D:②E② 试题14(1990年试题6) 从供选择的答案中选出应填入下列叙述中的{}内的正确答案,把编号写在答卷的对应栏内。 设T是正则二叉树,它具有6片树叶,那么树T的高度最多可以是A;最小可以是B:树T 的内结点数是C:如果T又是哈夫曼( Huffman)最优树,且各片树叶的权分别是1、2、3、4 5、6,则最优树T的非树叶的权之和是D:权为1的树叶的高度是E。(注:树的根结点高 度为1) 供选择的答案 A、B、C、E:①7②5③6④4⑤3 D:①27②30③45④51⑤64 【解析】 这里要注意正则树的概念,所谓正则二叉树,就是每个非叶结点都有两个子结点。根据这个 原则,我们用下面的2-6(a)、2-6(b)、2-6(c)图来解答本题 a)题A的解答 人(6)利题DE的解答 【答案】:A:③B:④C:④D:④E② 12程序语言基础知识 1.2.1主要知识点 了解程序语言的种类、特点和适用范围,掌握汇编、编译、解释系统的基本原理,以及 程序语言的数据结构和控制结构。特别是编译系统形式的基础知识,应当下功夫掌握。 12.1.1程序语言概述 低级语言又称面向机器语言,它是特定的计算机系统所固有的语言。用机器语言编制出 来的程序可读性很差,程序员难以修改和维护,于是人们考虑改用助记符号来表示机器指 令中操作码和操作数,这就是汇编语言。汇编语言仍然是一种和计算机的机器语言十分接近 的语言,它的书写格式在很大程度上取决于特定计算机的机器指令。它是一种低级语言,这 对于人们抽象思维和交流十分不便。在这个基础上,高级语言就发展起来了。目前已有许多 流行较广的高级语言,如 Fortra、 Cobol、 Pascale、和C++等。这类语言与人们的自然语言 比较接近,大大提高了程序设计的效率,便于人们进行交流 计算机只能理解和执行机器语言。程序语言要在计算机上运行,必须有一个程序,使机 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn924j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 24 页 个结点的平衡树的深度和 log2n 是同数量级。对二叉排序树来说，它的查找时间与树的深度 成正比。因此，平衡二叉排序树的 ASL 为 ASL=O(log2n)。 在平衡树上删除或插入结点往往会破坏树的平衡。通过旋转又可使其重新成为一棵平衡树。 在最坏情况下，从叶子开始一直调整到根为止，需进行的旋转次数与树的深度一致，等于 O(log2n)次。 【答案】：A：⑤ B：② C：⑤ D：② ② E 试题 14 (1990 年试题 6) 从供选择的答案中选出应填入下列叙述中的{ }内的正确答案，把编号写在答卷的对应栏内。 设 T 是正则二叉树，它具有 6 片树叶，那么树 T 的高度最多可以是 A；最小可以是 B；树 T 的内结点数是 C；如果 T 又是哈夫曼(Huffman)最优树，且各片树叶的权分别是 1、2、3、4、 5、6，则最优树 T 的非树叶的权之和是 D；权为 1 的树叶的高度是 E。(注：树的根结点高 度为 1) 供选择的答案： A、B、C、E：① ② ③ ④ ⑤ 7 5 6 4 3 D：① ② ③ ④ ⑤ 27 30 45 51 64 【解析】 这里要注意正则树的概念，所谓正则二叉树，就是每个非叶结点都有两个子结点。根据这个 原则，我们用下面的 2-6(a)、2-6(b)、2-6(c)图来解答本题。 【答案】：A：③ B：④ C：④ D：④ ② E 1.2 程序语言基础知识 1.2.1 主要知识点 了解程序语言的种类、特点和适用范围，掌握汇编、编译、解释系统的基本原理，以及 程序语言的数据结构和控制结构。特别是编译系统形式的基础知识，应当下功夫掌握。 12.1.1 程序语言概述 低级语言又称面向机器语言，它是特定的计算机系统所固有的语言。用机器语言编制出 来的,程序可读性很差，程序员难以修改和维护，于是人们考虑改用助记符号来表示机器指 令中操作码和操作数，这就是汇编语言。汇编语言仍然是一种和计算机的机器语言十分接近 的语言，它的书写格式在很大程度上取决于特定计算机的机器指令。它是一种低级语言，这 对于人们抽象思维和交流十分不便。在这个基础上，高级语言就发展起来了。目前已有许多 流行较广的高级语言，如 Fortra、Cobol、PascalC、和 C++等。这类语言与人们的自然语言 比较接近，大大提高了程序设计的效率，便于人们进行交流。 计算机只能理解和执行机器语言。程序语言要在计算机上运行，必须有一个程序，使机
SMI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军)培训资料,请勿散发! 器能够理解用程序语言书写的用户程序,这就是所谓的语言处理程序。它可以分为两大类: 解释程序和翻译程序。 1.2.1.2程序语言基础知识 程序语言种类繁多,在应用上各有不同的侧重面。 Fortran是第一个被广泛用于科学计算的高级语言。 Algol是另一个早期研制出来的高级语言。它有严格的文法规则,用巴科斯范式BNF 来描述语言的文法。 Algol是一个分程序结构的语言 Coba是一种面向事务处理的高级语言 Pascal语言提供的为数不多而又相当紧凑的机制使得这个语言具有相当强的表达能力 C是一种通用程序设计语言。C作为一种较低级的语言,提供了指针和地址操作的功能。 C提供书写结构良好的程序所需的控制结构。C与UNX操作系统紧密相关,UNX操作系 统及其上的许多软件都是C编写的 还有几种特殊而又重要的程序语言: (1)面向对象的C+ C++是在C语言的基础上发展起来的与C兼容的语言。主要增加了类功能,成为面向 对象的程序设计语言。面向对象程序语言至少包含以下几个重要概念 ①对象是人们要进行研究的任何事物,它包括状态(用数据来描述)和操作(用来改变对象 的状态)两方面。面对对象语言把状态和操作封装于对象体之中,并提供一种访问机制,使 对象状态的具体表示和操作的具体实现都是隐蔽的 ②类是面向对象语言必需提供的用户定义的数据的类型,它将具有相同状态、操作和访 问机制的多个对象抽象成一个对象类。在定义了类以后,属于这种类的一个对象叫作类实例 或类对象 ③继承是面向对象语言的另一个必备要素。类与类之间可以组成继承层次,一个类的定 义(称为子类)可以定义在另一个已定义类(称为父类)的基础上。子类可以继在父类中的属性 和操作,也可以定义自己的属性和操作 (2)逻辑型语言 Prolog 逻辑型语言是一类以形式逻辑为基础的语言。 Prolog是这类语言的代表。 Prolog建立在 关系理论和一阶谓词理论基础上,具有和传统的命令型程序设计完全不同的风格。 Prolog程 序由一些称为事实和规则的Hom子句组成。具有很强的推理功能,适用于书写自动定理证 明、专家系统、自然语言理解等问题的程序。 (3)函数型语言LISP 函数型程序语言是一类以γ演算为基础的语言。LISP是典型的函数型程序语言。函数 是一种对应规则(映射),它使其定义域中每一个值和值域中唯一的值相对应 函数型程序设计语言的优点之一是对表达式中出现的任何函数都可以用其他函数来代 替,只要这些函数调用产生相同的值。由于用函数程序设计语言书写的程序是利用自变量的 值来计算函数的值的,它没有副作用。这些特点有助于程序模块化的实现 1.2.1.3程序语言的数据类型 不同程序语言所提供的数据类型不尽相同。数据是程序操作的对象,具有名称、类型、 存储类、作用域和生存期等属性,使用时要为它分配内存空间。数据名称由用户可通过标识 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn925j1
CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军） 培训资料，请勿散发！ 中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 25 页 器能够理解用程序语言书写的用户程序，这就是所谓的语言处理程序。它可以分为两大类： 解释程序和翻译程序。 1.2.1.2 程序语言基础知识 程序语言种类繁多，在应用上各有不同的侧重面。 Fortran 是第一个被广泛用于科学计算的高级语言。 Algol 是另一个早期研制出来的高级语言。它有严格的文法规则，用巴科斯范式 BNF 来描述语言的文法。Algol 是一个分程序结构的语言。 Cobal 是一种面向事务处理的高级语言。 Pascal 语言提供的为数不多而又相当紧凑的机制使得这个语言具有相当强的表达能力。 C 是一种通用程序设计语言。C 作为一种较低级的语言，提供了指针和地址操作的功能。 C 提供书写结构良好的程序所需的控制结构。C 与 UNIX 操作系统紧密相关，UNIX 操作系 统及其上的许多软件都是 C 编写的。 还有几种特殊而又重要的程序语言： (1)面向对象的 C++ C++是在 C 语言的基础上发展起来的与 C 兼容的语言。主要增加了类功能，成为面向 对象的程序设计语言。面向对象程序语言至少包含以下几个重要概念： ①对象是人们要进行研究的任何事物，它包括状态(用数据来描述)和操作(用来改变对象 的状态)两方面。面对对象语言把状态和操作封装于对象体之中，并提供一种访问机制，使 对象状态的具体表示和操作的具体实现都是隐蔽的。 ②类是面向对象语言必需提供的用户定义的数据的类型，它将具有相同状态、操作和访 问机制的多个对象抽象成一个对象类。在定义了类以后，属于这种类的一个对象叫作类实例 或类对象。 ③继承是面向对象语言的另一个必备要素。类与类之间可以组成继承层次，一个类的定 义(称为子类)可以定义在另一个已定义类(称为父类)的基础上。子类可以继在父类中的属性 和操作，也可以定义自己的属性和操作。 (2)逻辑型语言 Prolog 逻辑型语言是一类以形式逻辑为基础的语言。Prolog 是这类语言的代表。Prolog 建立在 关系理论和一阶谓词理论基础上，具有和传统的命令型程序设计完全不同的风格。Prolog 程 序由一些称为事实和规则的 Horn 子句组成。具有很强的推理功能，适用于书写自动定理证 明、专家系统、自然语言理解等问题的程序。 (3)函数型语言 LISP 函数型程序语言是一类以 γ 演算为基础的语言。LISP 是典型的函数型程序语言。函数 是一种对应规则(映射)，它使其定义域中每一个值和值域中唯一的值相对应。 函数型程序设计语言的优点之一是对表达式中出现的任何函数都可以用其他函数来代 替，只要这些函数调用产生相同的值。由于用函数程序设计语言书写的程序是利用自变量的 值来计算函数的值的，它没有副作用。这些特点有助于程序模块化的实现。 1.2.1.3 程序语言的数据类型 不同程序语言所提供的数据类型不尽相同。数据是程序操作的对象，具有名称、类型、 存储类、作用域和生存期等属性，使用时要为它分配内存空间。数据名称由用户可通过标识