《软件设计师历年试题分析与解答》PDF电子书.pdf_P11-P15

SMI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军)培训资料,请勿散发! 对,直到全部满足为止。冒泡排序和快速排序又是交换排序的两种具体方法。冒泡排序将待排序的记录两两比较,若为逆序则交换。在升序排序过程中,关键码大的记录下沉,关键码小的记录上浮,故称冒泡。将序列按照此方法不到尾处理一遍后,当前处理范围内最大的记录被交换到最后,如此往复,最后得到一个有序的记录序列。问题B比较简单,顺次将关键字序列两两比较,第1趟处理结果显然选③。快速排序是对冒泡排序的一种改进,方法是:在待排序序列中确定一个记录,以它为基准用交换的方法将所有的记录分成两部分,即关键码值比它小的一部分和比它大的一部分。再分别对两个部分实施上述过程,一直重复到排序完成。问题C解答比较简单。取第一个记录F为基准,将比F大的移到后面,比F小的移到前面。一般采用从两端往中间加入的移动方式,第1趟排序的过程: F, B,, G, E,A,I, D, C, H C, B, J, G, E, A, I, D, F, H C, B, F, G,E,A, I, D,, H C, B, D, G,E, A,I, F,J, H C, B, D, F, E, A, I, G, J, H C,B,D,A,E,F,I,G,J,H-第一趟结束归并排序要求待排序列已经部分排序,形成了若干子序列。归并排序就是将已排序的子序列进行合并,得到完全排序的序列。合并时比较各子序列的第1个记录,便可找出第2个记录。如此继续,一遍扫描即可得出结果。具体的方式分为二路归并和多路归并。采用二路归并对有n个记录的序列进行排序时,应先将序列分成n/2个子序列,使每个子序列包含2个(或1 个)记录,在此子序列内进行排序。然后再将记录序列分成n/4个子序列(即从前往后两两合并子序列),再在子序列内进行排序。重复上述过程,直到只有一个子序列,则排序完成。理解了这个过程,则问题D的解答就会非常简单。先将待排序列(F,B,J,G,E,A,I, D,C,H)两两合并,分成5个子序列,在各子序列内排序,第一趟结局显然为(B,F,G J,A,E, D,I, C, H) 选择排序的基本思想是每次从待排序的记录中选择出码值最小(或最大)的记录,顺序放在已排序的记录序列的最后,直到全部排完为止。堆排序是选择排序的一种,采用堆排序时,首先要按层次序列来建立对应的完全二叉树,然后按筛选法建立立堆。在建堆的过程中,要记住堆的特征,作为堆的二叉树具有这样的特征:树根的关键码值小于树叶的关键码值:堆的调整过程是从最下层开始的,先将二叉树的树根与左子树进行比较,如果树叶小于树根,则交换;然后比较树根与右子,若树叶小于树根,则交换。同时,在交换的过程中如果影响到下层的堆,需要同时调整下层的堆。题中E问题的解答用示意图说明。在这里,初始建成的完全二叉树如图2-1(a所示。在调整完最下层的子树后,整个子树的结构如图2-1(b)所示。调整完第2层后,整个二叉树的结构如图2-1(c)所示。最后一次调整的结果就是题中问题E 的答案②。法G 温里部1()两图21三文树图当转一【答案】:A:③B:③C:②D:①E:② 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn411j1

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 11 页对，直到全部满足为止。冒泡排序和快速排序又是交换排序的两种具体方法。冒泡排序将待排序的记录两两比较，若为逆序则交换。在升序排序过程中，关键码大的记录下沉，关键码小的记录上浮，故称冒泡。将序列按照此方法不到尾处理一遍后，当前处理范围内最大的记录被交换到最后，如此往复，最后得到一个有序的记录序列。问题 B 比较简单，顺次将关键字序列两两比较，第 1 趟处理结果显然选③。快速排序是对冒泡排序的一种改进，方法是：在待排序序列中确定一个记录，以它为基准，用交换的方法将所有的记录分成两部分，即关键码值比它小的一部分和比它大的一部分。再分别对两个部分实施上述过程，一直重复到排序完成。问题 C 解答比较简单。取第一个记录 F 为基准，将比 F 大的移到后面，比 F 小的移到前面。一般采用从两端往中间加入的移动方式，第 1 趟排序的过程： F，B，J，G，E，A，I，D，C，H C，B，J，G，E，A，I，D，F，H C，B，F，G，E，A，I，D，J，H C，B，D，G，E，A，I，F，J，H C，B，D，F，E，A，I，G，J，H C，B，D，A，E，F，I，G，J，H--第一趟结束归并排序要求待排序列已经部分排序，形成了若干子序列。归并排序就是将已排序的子序列进行合并，得到完全排序的序列。合并时比较各子序列的第 1 个记录，便可找出第 2 个记录。如此继续，一遍扫描即可得出结果。具体的方式分为二路归并和多路归并。采用二路归并对有 n 个记录的序列进行排序时，应先将序列分成 n/2 个子序列，使每个子序列包含 2 个(或 1 个)记录，在此子序列内进行排序。然后再将记录序列分成 n/4 个子序列(即从前往后两两合并子序列)，再在子序列内进行排序。重复上述过程，直到只有一个子序列，则排序完成。理解了这个过程，则问题 D 的解答就会非常简单。先将待排序列(F，B，J，G，E，A，I， D，C，H)两两合并，分成 5 个子序列，在各子序列内排序，第一趟结局显然为(B，F，G， J，A，E，D，I，C，H)。选择排序的基本思想是每次从待排序的记录中选择出码值最小(或最大)的记录，顺序放在已排序的记录序列的最后，直到全部排完为止。堆排序是选择排序的一种，采用堆排序时，首先要按层次序列来建立对应的完全二叉树，然后按筛选法建立立堆。在建堆的过程中，要记住堆的特征，作为堆的二叉树具有这样的特征：树根的关键码值小于树叶的关键码值；堆的调整过程是从最下层开始的，先将二叉树的树根与左子树进行比较，如果树叶小于树根，则交换；然后比较树根与右子，若树叶小于树根，则交换。同时，在交换的过程中如果影响到下层的堆，需要同时调整下层的堆。题中 E 问题的解答用示意图说明。在这里，初始建成的完全二叉树如图 2-1(a)所示。在调整完最下层的子树后，整个子树的结构如图 2-1(b)所示。调整完第 2 层后，整个二叉树的结构如图 2-1(c)所示。最后一次调整的结果就是题中问题 E 的答案②。【答案】：A：③ B：③ C：② D：① E：②

SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 试题3(1999年试题2) 从供选择的答案中,选出应填入下面叙述中{}内的最确切的解答,把相应编号写在答卷的对应栏内给定数据结构(V,E),V为结点的有限集合,V={V1,V2,V3,V4,V5,V6,V7,V8} E是V上关系的集合。 E={<V1,V2>,<V3,V4>,<V5,V8>,<V6,<Ⅵ,V3>,V4<,V5>,V6<, <V1,V3>,V4<,V5>,<V2,V4>,V4<,V6>=它所对应的图表是{A},这就是图的存储结构主要有邻接表和{C},若用邻接表来存储一个图,则需要保存一个{D}存储的结点表和若干个{E}存储的关系(又称边表)。供选择的答案 B:①树②无向图③有向图④无回路图 C:①转称矩阵②邻接矩阵③状态矩阵④优先矩阵 D:①顺序②链接③散列④分块【解析】本题是一道关于图的试题,应该说是比较简单的。在数据结构(V,E中,有关系<V1,V2>和<V1,V3>,这样很快就答案案③和④排除了, 然后再看答案①②。在数据结构(V,E)中,还有关系<V2,V4>,这在答案②中没有反映出来,所以又排除了答案②。既然确定了答案①就是正确的答案,仔细观察该图形,由于关系<V1,V2>、<Vl,VⅤ3>、<V2,V4>,<V3,V4>以及关系<V4,V6>、<V6 V5>、<V4,V5>的特殊性,我们排除了该图是树、有向图、无回路图的可能性,数据结构(V,E)是图。图的存储结构主要有邻接表和邻接矩两种。邻接矩阵是表示结点间的相邻关系的矩阵,若G 是一个具有n个结点的图,则G的临界阵是如下定义的n×n矩阵 A[j]=0,表示(V,V)或者(j,V)是G的边 A[订]=1,表示(V,V或者(V,Ⅵ)不是G的边用邻接表来存储一个图,需要保存一个顺序存储的结点表和n个链接存储的边表。结点表的每个表目对应于图的一个结点,每个表目包括两个字段:一个是结点的数据或指向结点数据的指针,另一个是指向此结点的边表的指针。图的每一个结点都有一个边表,一个结点的边表的每个表目对应于与该结点相关联的一条边。它的每个表目也包括两个字段:一个是与此相边相关联的另一个结点的序号,另一个是指向边表的下一个表目的指针。对于有向图来说 ,用邻接表保存该图可以保存每个结点的出边表或入边表【答案】:A:①B:②C:②D:①E:② 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn9812j1

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 12 页试题 3(1999 年试题 2) 从供选择的答案中，选出应填入下面叙述中{ }内的最确切的解答，把相应编号写在答卷的对应栏内。给定数据结构(V，E)，V 为结点的有限集合，V={V1，V2，V3，V4，V5，V6，V7，V8}， E 是 V 上关系的集合。 E={＜V1，V2＞，＜V3，V4＞，＜V5，V8＞，＜V6，＜V1，V3＞，V4＜，V5＞，V6＜，＜V1，V3＞，V4＜，V5＞，＜V2，V4＞，V4＜，V6＞＝它所对应的图表是{ A }，这就是 { B }。图的存储结构主要有邻接表和{ C }，若用邻接表来存储一个图，则需要保存一个{ D }存储的结点表和若干个{ E }存储的关系(又称边表)。供选择的答案 A： B：①树 ②无向图 ③有向图 ④无回路图 C：①转称矩阵 ②邻接矩阵 ③状态矩阵 ④优先矩阵 D：①顺序 ②链接 ③散列 ④分块【解析】本题是一道关于图的试题，应该说是比较简单的。在数据结构(V，E)中，有关系＜V1，V2＞和＜V1，V3＞，这样很快就答案案③和④排除了，然后再看答案①②。在数据结构(V，E)中，还有关系＜V2，V4＞，这在答案②中没有反映出来，所以又排除了答案②。既然确定了答案①就是正确的答案，仔细观察该图形，由于关系＜V1，V2＞、＜V1，V3＞、＜V2，V4＞，＜V3，V4＞以及关系＜V4，V6＞、＜V6， V5＞、＜V4，V5＞的特殊性，我们排除了该图是树、有向图、无回路图的可能性，数据结构(V，E)是图。图的存储结构主要有邻接表和邻接矩两种。邻接矩阵是表示结点间的相邻关系的矩阵，若 G 是一个具有 n 个结点的图，则 G 的临界阵是如下定义的 n×n 矩阵： A［ij］=0，表示(Vi，Vj)或者(Vj，Vi)是 G 的边； A［ij］=1，表示(Vi，Vj)或者(Vj，Vi)不是 G 的边；用邻接表来存储一个图，需要保存一个顺序存储的结点表和 n 个链接存储的边表。结点表的每个表目对应于图的一个结点，每个表目包括两个字段：一个是结点的数据或指向结点数据的指针，另一个是指向此结点的边表的指针。图的每一个结点都有一个边表，一个结点的边表的每个表目对应于与该结点相关联的一条边。它的每个表目也包括两个字段：一个是与此相边相关联的另一个结点的序号，另一个是指向边表的下一个表目的指针。对于有向图来说，用邻接表保存该图可以保存每个结点的出边表或入边表。【答案】：A：① B：② C：② D：① E：②

SAI软件设计师辅导与培训资料:历年试题分析与解答(彭旺军) 训资料,请勿散发! 试题4(1998年试题3 从供选择的答案中,选出应填入下面叙述中{}内的最确切的答案,把相应编号写在人卷的对应栏内。在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和时间)复杂性对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序和直接选择排序时,若先选出大元素,则第一趟扫描结果分别是{A 和{B};:采用快速排序(以中间元素518为基准)的第一趟扫描结果是{C}。设被排序数据序列有n个元素,冒泡排序和直接选择排序的复杂性是{D};快速排序的复杂性是{E} 供选择的答案 ~C:①(181,132,314,205,541,518,946,827,746,984) ②(541,132,827,746,518,181,946,314,205,984) ③(205,132,314,181,518,746,946,984,541,827) ④(541,132,984,746,827,181,946,314,205,518) ⑤(132,541,746,518,181,946,314,205,827,984) ⑥(132,541,746,984,181,518,314,946,205,827) D、E:① O(nlog2n)②On)③ncn)④On2 ⑤Oog2n)2⑥ O(n log2n 【解析】冒泡排序:冒泡排序的过程很简单。首先将第1个数与第2个数相比较,若为逆序则交换两数,然后比较每两个数与第3个数,依次类推,直到第n-1个数与第n个数进行过比较为止。上述过程称为一趟冒泡排序,结果是最大的数被称鲐了最后。然后进行第2趟,对前面n-1 个数进行冒泡排序,结果是次大的数被移到了n-1的位置上。一般来说,第i趟冒泡排序是从第1个数到第n-计+1的位置上,整个排序过程需进行k(14k≤n)趟分析冒泡排序的效率,若初始序列为正序,则只进行一次排序。在排序过程中只进行n-1次比较,不交换数据。若为逆序,则需进行n-1趟排序,需进行n(n-1y2次比较,交换数据的数量组也相同。因此,冒泡排序的复杂性是O(n2)。快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序的数据分成两部分 ,其中一部分的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,最后达到整个序列有序。快速排序的复杂是 O(nlog2n) 直接选择排序,又称简单选择排序,其基本思想是每一趟在n-i+1(i=1,2,…,n-1)个数据中选择最小的数据作为有序序列中的第i个数据。一趟直接选择排序的基本操作为通过ni 次关键字的比较,从n-计+1个数据中选出关键字最小的数据,并和第i个数据交换。直接选择排序过程中,所需交换数据的次数较少,最小值为"0",最大值为3(n-1)"。然而,无论数据的初始次序如何,它所需进行的关键字的比较次数相同,均为n(n-1)2,因此,直接选择排序的复杂性是O(n2) 对于题中给定的整数序列(541,132,984,746,518,181,946,314,205,827进行从小到大排序,若先选出较大的元素,则对于冒泡排序,第1趟操作为541←→132,984←→746 984←→518,984←→181,9844946,984←→314,984←→205,984←→827,其结果得到的序列为(132,541,746,518,181,946,314,205,827,984);对于直接选择排序 ,第1趟操作为984←→827,其结果得到的序列为(541,132,827,746,518,181,946, 14,205,984) 采用快速排序(以中间元素518为基准)的第1趟扫描结果是(205,132,314,181,518,746 中国系统分析员, http://www.csai.cn,0731-8662005,trecsai.comcn9813j1

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 13 页试题 4(1998 年试题 3) 从供选择的答案中，选出应填入下面叙述中{ }内的最确切的答案，把相应编号写在人卷的对应栏内。在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用冒泡排序和直接选择排序时，若先选出大元素，则第一趟扫描结果分别是{ A } 和{ B }；采用快速排序(以中间元素 518 为基准)的第一趟扫描结果是{ C }。设被排序数据序列有 n 个元素，冒泡排序和直接选择排序的复杂性是{ D }；快速排序的复杂性是{ E }。供选择的答案 A～C：①(181，132，314，205，541，518，946，827，746，984) ②(541，132，827，746，518，181，946，314，205，984) ③(205，132，314，181，518，746，946，984，541，827) ④(541，132，984，746，827，181，946，314，205，518) ⑤(132，541，746，518，181，946，314，205，827，984) ⑥(132，541，746，984，181，518，314，946，205，827) D、E：①O(nlog2n) O(n) (nccn) O(n ②③ ④ 2 ) ⑤O(log2n)2 O(n ⑥ 2 log2n) 【解析】冒泡排序：冒泡排序的过程很简单。首先将第 1 个数与第 2 个数相比较，若为逆序则交换两数，然后比较每两个数与第 3 个数，依次类推，直到第 n-1 个数与第 n 个数进行过比较为止。上述过程称为一趟冒泡排序，结果是最大的数被称鲐了最后。然后进行第 2 趟，对前面 n-1 个数进行冒泡排序，结果是次大的数被移到了 n-1 的位置上。一般来说，第 i 趟冒泡排序是从第 1 个数到第 n-i+1 的位置上，整个排序过程需进行 k(1≤k≤n)趟。分析冒泡排序的效率，若初始序列为正序，则只进行一次排序。在排序过程中只进行 n-1 次比较，不交换数据。若为逆序，则需进行 n-1 趟排序，需进行 n(n-1)/2 次比较，交换数据的数量组也相同。因此，冒泡排序的复杂性是 O(n2 )。快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最后达到整个序列有序。快速排序的复杂是 O(nlog2n)。直接选择排序，又称简单选择排序，其基本思想是每一趟在 n-i+1(i=1，2，…，n-1)个数据中选择最小的数据作为有序序列中的第 i 个数据。一趟直接选择排序的基本操作为通过 n-i 次关键字的比较，从 n-i+1 个数据中选出关键字最小的数据，并和第 i 个数据交换。直接选择排序过程中，所需交换数据的次数较少，最小值为"0"，最大值为 3(n-1)"。然而，无论数据的初始次序如何，它所需进行的关键字的比较次数相同，均为 n(n-1)/2，因此，直接选择排序的复杂性是 O(n2 )。对于题中给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大排序，若先选出较大的元素，则对于冒泡排序，第 1 趟操作为 541←→132，984←→746 ，984←→518，984←→181，984←→946，984←→314，984←→205，984←→827，其结果得到的序列为(132，541，746，518，181，946，314，205，827，984)；对于直接选择排序，第 1 趟操作为 984←→827，其结果得到的序列为(541，132，827，746，518，181，946， 314，205，984)。采用快速排序(以中间元素 518 为基准)的第 1 趟扫描结果是(205，132，314，181，518，746

CSAI 软件设计师辅导与培训资料：历年试题分析与解答（彭旺军）培训资料，请勿散发！中国系统分析员， http://www.csai.cn， 0731-8662005， tr@csai.com.cn 第 14 页，946，984，827)。【答案】：A：⑤ B：② C：③ D：④ E：① 试题 5(1997 年试题 4) 从供选择的答案中，选出应填入下面的叙述中{ }内的最确切的解答，把相应编号写在答卷的对应栏内。设数据结构(D，R)由数据结点集合 D={di|1≤i≤7}及其上的关系 R 组成。 1.当 R={＜di-1，d|di-1，di D ∈ ，2≤i≤7}，这个数据结构对应于 A。 2.当 R={＜d4，d2＞，d1＞，＜d2，d3＞，＜d4，d6＞，＜d6，d5＞，＜d6，d7＞}，这个结构的图形是 B，用 C 遍历法可以得到 A 的数据结构。 3.当 R={＜d1，d2＞，＜d1，d3＞，＜d2，d4＞，＜d4，d5＞，＜d4，d5＞，＜d4，d6＞，＜d4，d7＞}，这个结构的图形是 D。用 E 遍历法可以得到 A 的数据结构。供选择的答案 A、B、D：①二叉树 ②队列 ③二叉排列序树 ④线性表 ⑤无向图 ⑥有向无回路 C、E：①前序 ②中序 ③后序 ④深度优先 ⑤广度优先【解析】该题要求考生熟练掌握数据结构中常用的线性表、二叉树、树、图的结构及其遍历方法。数据结构(D，R)中，D 由 7 个数据组成，R 决定这 7 个数据的排列方式。 (1)R={＜di-1，d|di-1，di D ∈ ，2≤i≤7 } 其对应的数据结构可以表示为 d1→d2→d3→d4→d5→d6→d7，它对应一个线性表。 (2)R={＜d4，d2＞，＜d2，d1＞，＜d2，d3＞，＜d4，d6＞，＜d6，d5＞，＜d6，d7＞} 其对应的数据结构可以表示为：这棵二叉树利用中序遍历法得到序列为 d1d2d3d4d5d6d7。 (3)R={＜d1，d2＞，＜d1，d3＞，＜d2，d4＞，＜d3，d4＞，＜d4，d5＞，＜d4，d6＞，＜ d4，d7＞}，对应的数据结构为一个有向无回路图，利用广度优先遍历法得到的序列为 d1d2d 3d4d5d6d7，正好对应(1)中的线性表结构。【答案】：A B C D E ④ ① ② ⑥ ⑤ 试题 6(1996 年试题 1) 从供选择的答案中，选出应填入下面叙述中{ }内的最确切的解答，把相应编号写在答卷的