1、中级软件设计师下午试题-108 及答案解析(总分：59.00，做题时间：90 分钟)一、试题一(总题数：1，分数：-1.00)1.【说明】所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。函数中使用的预定义符号如下：#define M 100typedef struct/*x 为两端点 p1、p2 之间的距离，p1、p2
2、 所组成边的长度*/float x;int p1, p2;tdr;typedef struct/*p1、p2 为和端点相联系的两个端点，n 为端点的度*/int n, P1, p2;tr;typedef struct/*给出两点坐标*/float x,y;tpd;typedef int tlM;int n=10;【函数】float distance(tpd a,tpd b);/*计算端点 a、b 之间的距离*/void sortArr(tdr aM, int m);/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m 为边的条数*/int isCircuit(trM, int i,
3、 int j);/*判断边(i, j)选入端点关系表 rM后，是否形成回路，若形成回路返回 0*/void selected(tr rM, int i, int j);/*边(i,j)选入端点关系表 r*/void course(tr rM, tl 1M);/*从端点关系表 r 中得出回路轨迹表*/void exchange(tdr aM, int m, int b);/*调整表排序表，b 表示是否可调，即是否有边长度相同的边存在*/void travling(tpd pdM, int n, float dist, t1 locusM)/*dist 记录总路程*/tdr drM;/*距离关系表
4、*/tr rM;/*端点关系表*/int i, j, k, h, m;/*h 表示选入端点关系表中的边数*/int b;/*标识是否有长度相等的边*/k=0;/*计算距离关系表中各边的长度*/for(i=1;in;i+)for(j=i+1;j=n;j+)k+;drk.x= (1) ;drk.p1=i;drk.p2=j;m=k;sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/dob=1;dist=0;k=h=0;dok+;i=drk.p1;j=drk.p2;if(ri.n=1)h+;dist+=drk.x;else if( (4) )/*最后一边选入 r 成回路，则该边必须加
5、入且得到解*/selected(r,i,j);h+;dist+=drk.x;while(k!=n)if(h=n)/*最后一边选入构成回路，完成输出结果*/course(r,locus);else/*找不到解，调整 dr，交换表中边长相同的边在表中的顺序，并将 b 置 0*/(5) ;while(!b);（分数：-1.00）_二、试题二(总题数：1，分数：15.00)2.说明下面的流程图(如图所示)用 N - S 盒图形式描述了数组 A 中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位
6、于 Ai，并且数组中下标小于 i 的元素的值均小于基准数，下标大于 i 的元素的值均大于基准数。设数组 A 的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以 4 为基准数的划分过程如下：（分数：15.00）_三、试题三(总题数：1，分数：15.00)3.【说明】银行客户需要从 ATM 取 100 元，他向 ATM 的读卡机插卡，读卡机读取他的卡号，然后 ATM 屏幕初始化，ATM 提示输入密码，客户输入密码(123456)，ATM 打开他的账户，密码有效，因此 ATM 提示选择事务，客户选择取钱，ATM 提示输入金额，客户输入 100 元，ATM
7、 验证账户上有足够的钱，就从账上减去 100 元，ATM 吐出 100 元，并退出的卡。【问题】根据上面的描述，在下面填写，完成未完成的协作图。1插卡(客户一读卡机)2_(_)3_(_)4提示输入 PIN (123456) (ATM 显示屏客户)5_(_)6_(_)7验证 PIN(_)8提示选择事务(_)9_(客户ATM 屏幕)10提示金额(ATM 屏幕客户)11输入金额(客户ATM 屏幕)12取钱(ATM 屏幕的账户)13_(_)14_(_)15_(_)16提供收据(客户的账户取钱机)17_(_)*（分数：15.00）_四、试题四(总题数：1，分数：15.00)【说明】快速排序是一种典型的分
8、治算法。采用快速排序对数组 Apr排序的 3 个步骤如下。1分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组 (可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1)中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。2递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。3合并：快速排序在原地排序，故不需合并操作。（分数：15.00）(1).【问题 1】下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r: 数组元素下标，从 p 到 rq: 划分的位置x：枢轴元素i：整型
9、变量，用于描述数组下标。下标小于或等于 i 的元素的值小于或等于枢轴元素的值j：循环控制变量，表示数组元素下标QUICKSORT (A，p，r)if (p r)q=PARTITION(A，p，r) ；QUICKSORT(A，p，q-1)；QUICKSORT(A，q+1，r)；PARTITION(A，p，r)x=Ar；i=p-1；for(j=p；jr-1；j+)if (Ajx)i=i+1；交换 Ai和 Aj交 (1) 和 (2) /注：空(1)和空(2)答案可互换，但两空全部答对方可得分 return (3) （分数：5.00）_(2).【问题 2】(1)假设要排序包含 n 个元素的数组，请给出
10、在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳，平均、最坏)（分数：5.00）_(3).【问题 3】(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i，j)表示随机取 i 到 j 之间的一个数，包括 i 和 j。
11、RANDOMIZED- PARTITION(A，p，r)i=RANDOM(p，rl)；交换 (8) 和 (9) ；/注：空(8)和空(9)答案可互换，但两空全部答对方可得分return PARTITION (A，p，r)；(2)随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否)（分数：5.00）_五、试题五(总题数：1，分数：15.00)4.【说明】栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stock Top)，而另一端称为栈底(Stock Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空
12、(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如下图所示)。（分数：15.00）_中级软件设计师下午试题-108 答案解析(总分：59.00，做题时间：90 分钟)一、试题一(总题数：1，分数：-1.00)1.【说明】所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按
13、长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。函数中使用的预定义符号如下：#define M 100typedef struct/*x 为两端点 p1、p2 之间的距离，p1、p2 所组成边的长度*/float x;int p1, p2;tdr;typedef struct/*p1、p2 为和端点相联系的两个端点，n 为端点的度*/int n, P1, p2;tr;typedef struct/*给出两点坐标*/float x,y;tpd;typedef int tlM;int n=10;【函数】float distance
14、(tpd a,tpd b);/*计算端点 a、b 之间的距离*/void sortArr(tdr aM, int m);/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m 为边的条数*/int isCircuit(trM, int i, int j);/*判断边(i, j)选入端点关系表 rM后，是否形成回路，若形成回路返回 0*/void selected(tr rM, int i, int j);/*边(i,j)选入端点关系表 r*/void course(tr rM, tl 1M);/*从端点关系表 r 中得出回路轨迹表*/void exchange(tdr aM, int
15、 m, int b);/*调整表排序表，b 表示是否可调，即是否有边长度相同的边存在*/void travling(tpd pdM, int n, float dist, t1 locusM)/*dist 记录总路程*/tdr drM;/*距离关系表*/tr rM;/*端点关系表*/int i, j, k, h, m;/*h 表示选入端点关系表中的边数*/int b;/*标识是否有长度相等的边*/k=0;/*计算距离关系表中各边的长度*/for(i=1;in;i+)for(j=i+1;j=n;j+)k+;drk.x= (1) ;drk.p1=i;drk.p2=j;m=k;sortArr(dr,
16、m);/*按距离大小从小到大排序形成排序表*/dob=1;dist=0;k=h=0;dok+;i=drk.p1;j=drk.p2;if(ri.n=1)h+;dist+=drk.x;else if( (4) )/*最后一边选入 r 成回路，则该边必须加入且得到解*/selected(r,i,j);h+;dist+=drk.x;while(k!=n)if(h=n)/*最后一边选入构成回路，完成输出结果*/course(r,locus);else/*找不到解，调整 dr，交换表中边长相同的边在表中的顺序，并将 b 置 0*/(5) ;while(!b);（分数：-1.00）_正确答案：(1) dis
17、tance(pdi,pdj)(2) !isCircuit(r,i,j)(3) selected(r,i,j)(4) h=n-1(5) exchange(dr,m,b)解析：解析 本题主要是函数调用的问题。空(1)是计算各边的长度，根据函数的声明及说明，应填 distance(pdi，pdj)。由注释可见空(2)是判断边(i，j)加入 r 后是否形成回路，若形成了回路，不加入。由语句“dist+=drk.x;”可知此处是将边加入，故此处应该是不形成回路条件。参照 isCircuit 函数声明及说明可知，若形成回路返回 0，故空(2)填“!isCircuit(r,i,j)”。空(3)是将边(i,j
18、)加入到 r 中，参照 selected 函数声明及说明，可得空(3)填 selected(r, i,j)。由注释可见空(4)是最后一条边条件，变量 h 表示的是“选入端点关系表中的边数”，而 n 各节点回路应该包含 n 条边，这点也可从后面 h=n 输出解看出，故空(4)填 h=n-1。空(5)是进行调整，调用 exchange 函数，正确调用形式为 exchange(dr,m,b)。二、试题二(总题数：1，分数：15.00)2.说明下面的流程图(如图所示)用 N - S 盒图形式描述了数组 A 中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端
19、移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于 Ai，并且数组中下标小于 i 的元素的值均小于基准数，下标大于 i 的元素的值均大于基准数。设数组 A 的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以 4 为基准数的划分过程如下：（分数：15.00）_正确答案：(1)j- (2)i+ (3)Aipivot 或jpivot (4) A，L，k-1 或 A，L，k(5)A，k+1，H 或 A，k，H)解析：解析 题目考查快速排序算法。快速排序采用了一种分治的策略，通常称为分治法。其基本思想是：将原问题分解为若干个规模更小，但结构与
20、原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的具体过程为：第一步，在待排序的 n 个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成 2 组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这 2 组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的 2 组元素分别进行快速排序，直到所有记录都排到相应的位置为止。在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量 pivot 中，如图中的第步所示。这样基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如
21、图中的第步所示，找到一个比基准元素小的元素时为止，将其前移，如图中的第步所示。然后再从前向后扫描，如图中的第步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第步所示。由题目中给出的流程图可知，以第一个元素作为基准数，并将 Alow备份至 pivot，i 用于从前向后扫描的位置指示器，其初值为 low, j 用于从后往前扫描的位置指示器，其初值为 high。当 ij 时退出循环。退出循环时，将 pivot 赋给当前的 Ai(Aipivot)。递归函数的目的是执行一系列调用，直到到达某一点时递归终止。
22、为了保证递归函数正常执行，应该遵守下面的规则：1)每当一个递归函数被调用时，程序首先应该检查基本的条件是否满足，例如，某个参数的值等于 0，如果是这种情形，函数应停止递归。2)每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得“更简单”，即这些参数应该逐渐靠近上述基本条件。例如，一个正整数在每次递归调用时会逐渐变小，以至最终其值到达 0。本题中，递归函数 sort(int A，int L, int H)有 3 个参数，分别表示数组 A 及其下界和上界。根据流程图可知，这里的 L 相当于流程图中的 i，这里的 H 相当于流程图中的 j。因为 P()返回基准数所在数组A 中的下标
23、，也就是流程图中最后的“Aipivot”中的 i。根据快速排序算法，在第一趟排序后找出了基准数所在数组 A 中的下标，然后以该基准数为界(基准数在数组中的下标为 k)，把数组 A 分成 2 组，分别是 AL,k-1)和 Ak+1,H)，最后对这 2 组中的元素再使用同样的方法进行快速排序。三、试题三(总题数：1，分数：15.00)3.【说明】银行客户需要从 ATM 取 100 元，他向 ATM 的读卡机插卡，读卡机读取他的卡号，然后 ATM 屏幕初始化，ATM 提示输入密码，客户输入密码(123456)，ATM 打开他的账户，密码有效，因此 ATM 提示选择事务，客户选择取钱，ATM 提示输入
24、金额，客户输入 100 元，ATM 验证账户上有足够的钱，就从账上减去 100 元，ATM 吐出 100 元，并退出的卡。【问题】根据上面的描述，在下面填写，完成未完成的协作图。1插卡(客户一读卡机)2_(_)3_(_)4提示输入 PIN (123456) (ATM 显示屏客户)5_(_)6_(_)7验证 PIN(_)8提示选择事务(_)9_(客户ATM 屏幕)10提示金额(ATM 屏幕客户)11输入金额(客户ATM 屏幕)12取钱(ATM 屏幕的账户)13_(_)14_(_)15_(_)16提供收据(客户的账户取钱机)17_(_)*（分数：15.00）_正确答案：(1插卡(客户读卡机)2读卡
25、号(读卡机读卡机)3屏幕初始化(读卡机ATM 屏幕)4提示输入 PIN(ATM 显示屏客户)5输入 PIN(123456)(客户ATM 屏幕)6打开账户(ATM 屏幕客户的账户)7验证 PIN(ATM 屏幕客户的账户)8提示选择事务(ATM 屏幕客户)9选择事务(取钱)(客户ATM 屏幕)10提示金额(ATM 屏幕客户)11输入金额(100 元)(客户ATM 屏幕)12取钱(100 元)(ATM 屏幕客户的账户)13验钱(100 元)(客户的账户客户的账户)14扣钱(100 元)(客户的账户客户的账户)15提供钱(100 元)(客户的账户取钱机)16提供收据(客户的账户取钱机)17退卡(客户的
26、账户读卡机)解析：解析 这道题和模拟试题 4 中的试题 3 是相似的，一个需求描述的时序图和协作图是可以相互转换的，所以，这个取钱过程的时序图的分析方法同样可以用在协作图的分析上。根据上述的分析方法并结合题中已经给出的提示可以得出答案，答案如下。四、试题四(总题数：1，分数：15.00)【说明】快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下。1分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组 (可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1)中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。2递
27、归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。3合并：快速排序在原地排序，故不需合并操作。（分数：15.00）(1).【问题 1】下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r: 数组元素下标，从 p 到 rq: 划分的位置x：枢轴元素i：整型变量，用于描述数组下标。下标小于或等于 i 的元素的值小于或等于枢轴元素的值j：循环控制变量，表示数组元素下标QUICKSORT (A，p，r)if (p r)q=PARTITION(A，p，r) ；QUICKSORT(A，p，q-1)；QUICKSORT(A，q+1，r)；PAR
28、TITION(A，p，r)x=Ar；i=p-1；for(j=p；jr-1；j+)if (Ajx)i=i+1；交换 Ai和 Aj交 (1) 和 (2) /注：空(1)和空(2)答案可互换，但两空全部答对方可得分 return (3) （分数：5.00）_正确答案：(1)Ai+1 (2)Ar (3)i+1注：空(1)和空(2)答案可以互换)解析：(2).【问题 2】(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间
29、复杂度属于哪种情况? (7) 。(最佳，平均、最坏)（分数：5.00）_正确答案：(4)O(nlgn)或 O(log2n) (5)O(nlgn)或 O(nlog2n)(6)O(n2) (7)最坏)解析：(3).【问题 3】(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i，j)表示随机取 i 到 j 之间的一个数，包括 i 和 j。RANDOMIZED- PARTITION(A，p，r)i=
30、RANDOM(p，rl)；交换 (8) 和 (9) ；/注：空(8)和空(9)答案可互换，但两空全部答对方可得分return PARTITION (A，p，r)；(2)随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否)（分数：5.00）_正确答案：(8)Ai (9)Ar (10)否注；空(8)和空(9)答案可以互换)解析：试题四分析本题考查算法的设计与分析技术。问题 1 考查快速排序算法的伪代码，快速排序最核心的处理是进行划分，即 PARTITION 操作，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素
31、的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图所示：五、试题五(总题数：1，分数：15.00)4.【说明】栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stock Top)，而另一端称为栈底(Stock Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，
32、可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如下图所示)。（分数：15.00）_正确答案：(1)S=NULLS-pTop=NULL (2)S-pTop-data (3)newNode(4)S-pTop-next，或 lastTop-next (5)244)解析：解析 本题考查基本程序设计能力。堆栈是软件设计中常使用的一种经典数据结构，题目给出的操作都是任何堆栈都具有的基本操作。堆栈的存储结构通常采用数组或链表形式，但无论采用哪种存储结构，整体上呈现的是后进先出的特点，即后进入堆栈的元素先出栈。题目中给出的结构体 Stack 仅包含一个指向栈顶元素的指针(栈顶指针)，
33、当且仅当堆栈中没有元素时，该指针应为 NULL。当向堆栈中增加元素时，首先需要动态创建该元素的存储区，并且栈顶指针指向该元素。当元素出栈时，栈顶指针则指向出栈元素的紧前一个元素。结构体 List 表示栈中元素，包含对应的数据和指向紧上次入栈的元素指针 next，对于第 1 个入栈的元素，指针 next 为NULL,而其他元素中的指针 next 一定不为 NULL。C 语言中，如果用一个整数型表达式表示条件判定语句的话，该表达式的值为。则表示假，非 0 表示真。从给定程序代码可以看出，对于函数 IsEmpty，若其返回值为 0 则表示堆栈非空，否则表示堆栈为空。因此，对于空(1)，必须填写可表示
34、堆栈为空的判定语句：S=NULLS-p)Top=NULL，这 2 个条件中只要有 1 个条件满足，则表明堆栈 S 为空。对于空(2)，此时需要返回栈顶元素中的数据，而栈顶元素为 S-pTop，所以对应的数据应该为 S-pTop-data。对于压栈操作 Push，在为新元素获取存储空间后，必须调整堆栈的栈顶指针 S-pTop 指向新元素的存储区，即 S-pTop=newNode。对于弹栈操作 Pop，弹出栈顶元素 lastTop 后，需要调整栈顶指针，使其指向被弹出元素的下一个元素，即 S-pTop=S-pTop-next，或 S-pTop=lastTop-next。对于 main 函数中宏 MD(x)，在程序预编译时会按字符替换为“x2”。所以在 main 函数中，首先入栈的元素为“12”，即整数 4，第 2 个入栈的元素为“22”，即整数 8，其次将 8 弹出，然后再将“32+1”入栈，C 语言中“+”优先级高于“”，所以此时入栈者为整数 24，而此时堆栈中有 2个元素，其中栈顶元素为 24，下一元素为 4。最后，若堆栈非空，则循环完成显示栈顶元素的值、弹出栈顶元素的操作，直至堆栈为空。所以程序执行时的输出内容为“244”。
