1、中级软件设计师下午试题-142 及答案解析(总分：100.01，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)说明 快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下。 (1)分解：选择一个枢轴(Pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。 (2)递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。 (3)合并：快速排序在原地排序，故不需合并操作。（分数：20.01）(1).
2、下面是快速排序的伪代码，请填补横线处的空缺。伪代码中的主要变量说明如下。 A：待排序数组。 P，r：数组元素下标，从 P 到 r。 q：划分的位置。 x：枢轴元素。 i：整型变量，用于描述数组下标。下标小于或等于 i 的元素的值小于或等于枢轴元素的值。 j：循环控制变量，表示数组元素下标。 QUICKSORT (A, p, r) if (pr) 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 (
3、Ajx) i=i+1; 交换 Ai和 Aj 交换_和_/注：空_和空_答案可互换，但两空全部答对方可得分 return _ （分数：6.67）_(2).(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O 标记。最佳情况为_，平均情况为_，最坏情况为_。 (2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? _。(最佳、平均、最坏)（分数：6.67）_(3).(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机
4、化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i, j)表示随机取 ij 之间的一个数，包括 i 和 j。 RANDOMIZED-PARTITION (A, p, r) i=RANDON (p, r); 交换_和_; /注：两个空的答案可互换，但两空全部答对方可得分 return PARTITION (A, p, r); (2)随机化快速排序是否能够消除最坏情况的发生? _。(是或否)（分数：6.67）_二、试题二(总题数：1，分数：20.00)1.说明 栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端
5、称为栈顶(Stack Top)，而另一端称为栈底(Stack Bottom)。栈的基本操作包括创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储，如下图所示。 （分数：20.00）_三、试题三(总题数：1，分数：20.00)2.说明 在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了
6、类型 shape_t、point_t 和 circle_t 分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。 C 程序 typedef enum point, circle shape_type; /* 程序中的两种图形：点和圆 */ typedef struct /* 基本的图形类型 */ shape type type; /* 图形种类标识：点或者圆 */ void (*destroy) (); /* 销毁图形操作的函数指针 */ void (*draw)(); /* 绘制图形操作的函数指针 */ shape_t; typedef struct shape_t common;
7、int x; int y; point_t; /* 定义点类型，x、y 为点坐标 */ void destroyPoint (point_t* this) free(this); printf (“Point destoryed!n“);) /* 销毁点对象 */ void drawPoint (point_t* this) printf(“P(%d, %d)“, thisx, thisy);) /* 绘制点对象 */ shape_t* createPoint(va_list* ap) /* 创建点对象，并设置其属性 */ point_t* p point; if (p_point=(poin
8、t_t*) malloc (sizeof(point_t)=NULL) return NULL; p_pointcommon. type = point; p_pointcommon. destroy = destroyPoint; p_pointcommon. draw=drawPoint; p_pointx = va_arg (*ap, int); /* 设置点的横坐标 */ p_pointy = va_arg(*ap, int); /* 设置点的纵坐标 */ return (shape_t*)p_point; /* 返回点对象指针 */ tyPedef struct /* 定义圆类型 *
9、/ shape_t common; point_t *center; /* 圆心点 */ int radius; /* 圆半径 */ circle_t; void destroyCircle(circle_t* this) free (_); free(this); printf(“Circle destoryed!n“); void drawCircle (circle_t* this) printf (“C(“); _draw( thiscenter); /* 绘制圆心*/ printf (“, %d)“, thisradius); shape_t* createCircle(va lis
10、t* ap) /* 创建一个圆，并设置其属性 */ circle_t* p_circle; if (p_circle=(circle_t*)malloc(sizeof(circle_t)=NULL)return NULL; p_circlecommon. type=circle; p_circlecommon. destroy=destroyCircle; p_circlecommon. draw=drawCircle; _ =createPoint(ap); /* 设置圆心 */ p_circleradius=va arg(*ap, int); /* 设置圆半径 */ return p_ci
11、rcle; shape t* createShape(shape_type st, ) /* 创建某一种具体的图形 */ va_list ap; /* 可变参数列表 */ shape_t* P_shape = NULL; _ (ap, st); if ( st = point) p_shape=createPoint( ap); /* 创建点对象 */ if ( st = circle) p_shape=createCircle(ap); /* 创建圆对象 */ va_end(ap); return p-shape; int main() int i; /* 循环控制变量，用于循环计数 */
12、shape t* shapes2; /* 图形指针数组，存储图形的地址 */ shape_s0 = createShape ( point, 2, 3); /* 横坐标为 2，纵坐标为 3 */ shapes1 = createShape( circle, 20, 40, 10); /* 圆心坐标(20, 40), 半径为 10 */ for (i=0; i2; i+) shapesidraw(shapesi); printf(“n“); /* 绘制数组中图形 */ for( i=1; i=0; i-) shapesidestroy(shapesi); /* 销毁数组中图形 */ return
13、 0; 运行结果如下： p(2, 3) _ Circle destoryed! Point destoryed! （分数：20.00）_四、试题四(总题数：1，分数：20.00)3.说明 在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图1 所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子
14、节点。 每个节点有一个 d 值，表示从其父节点到该节点的信号衰减量。例如，在图 1 中，节点 w、p、q 的 d 值分别为 2、1、3，树根节点表示信号源，其 d 值为 0。 每个节点有一个 M 值，表示从该节点出发到其所有叶子节点的信号衰减量的最大值。显然，叶子节点的 M值为 0。对于非叶子节点 j，M(j)=maxM(k)+d(k)|k 是 j 的子节点。 在此公式中，要计算节点的 M 值，必须先算出其所有子节点的 M 值。 在计算 M 值的过程中，对于某个节点 i，若其有一个子节点 k 满足 d(k)+Mfk)大于容忍值，则应在 k 处放置放大器，否则，从节点 i 到某叶子节点的信号衰减
15、量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点 i 处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图 1 中，从节点 P 到其所有叶子节点的最大衰减值为 4。若容忍值为 3，则必须在 s 处放置信号放大器，这样可使得节点 p 的 M 值为2。同样，需要在节点 q、v 处放置信号放大器，如图 2 阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。 （分数：20.00）_五、试题五(总题数：1，分数：20.00)4.说明 一般的树型结构常采用孩子-兄弟表示法表示，即用二叉链表作树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点
16、和下一个兄弟节点。例如，下图(a)中所示的树的孩子-兄弟表示如下图(b)中所示。 （分数：20.00）_中级软件设计师下午试题-142 答案解析(总分：100.01，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)说明 快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下。 (1)分解：选择一个枢轴(Pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。 (2)递归求解：通过递归的调用快速排序，对子数组 Apq-1
17、和 Aq+1r分别排序。 (3)合并：快速排序在原地排序，故不需合并操作。（分数：20.01）(1).下面是快速排序的伪代码，请填补横线处的空缺。伪代码中的主要变量说明如下。 A：待排序数组。 P，r：数组元素下标，从 P 到 r。 q：划分的位置。 x：枢轴元素。 i：整型变量，用于描述数组下标。下标小于或等于 i 的元素的值小于或等于枢轴元素的值。 j：循环控制变量，表示数组元素下标。 QUICKSORT (A, p, r) if (pr) q=PARTITION (A, p, r); QUICKSORT (A, p, q-1); QUICKSORT (A, q+1, r); PARTIT
18、ION (A, p, r) x=Ar; i=p-1; for (j=p; jr-1; j+) if (Ajx) i=i+1; 交换 Ai和 Aj 交换_和_/注：空_和空_答案可互换，但两空全部答对方可得分 return _ （分数：6.67）_正确答案：()解析：Ai+1 Ar 注：第一个空和第二个空的内容可互换。 (i+1)或+i 或者 A+i Ar或 Aq i(其中第一个空和第二个空的内容可互换)(2).(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O 标记。最佳情况为_，平均情况为_，最坏情况为_。 (2)假设要排序的 n 个元素都具有相
19、同值时，快速排序的运行时间复杂度属于哪种情况? _。(最佳、平均、最坏)（分数：6.67）_正确答案：()解析：O(nlog2n)或 O(nlgn) O(nlog2n)或 O(nlgn) O(n 2 ) 最坏(3).(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i, j)表示随机取 ij 之间的一个数，包括 i 和 j。 RANDOMIZED-PARTITION (A, p, r) i=R
20、ANDON (p, r); 交换_和_; /注：两个空的答案可互换，但两空全部答对方可得分 return PARTITION (A, p, r); (2)随机化快速排序是否能够消除最坏情况的发生? _。(是或否)（分数：6.67）_正确答案：()解析：Ai Ar 注：第一个空和第二个空可互换。 否二、试题二(总题数：1，分数：20.00)1.说明 栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stack Top)，而另一端称为栈底(Stack Bottom)。栈的基本操作包括创建栈(NewStack)、判断栈是否为空(IsEmpty)、
21、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储，如下图所示。 （分数：20.00）_正确答案：()解析：S=NULL | SpTop=NULL SpTopdata newNode SpTopnext 24 4三、试题三(总题数：1，分数：20.00)2.说明 在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型 shape_t、point
22、_t 和 circle_t 分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。 C 程序 typedef enum point, circle shape_type; /* 程序中的两种图形：点和圆 */ typedef struct /* 基本的图形类型 */ shape type type; /* 图形种类标识：点或者圆 */ void (*destroy) (); /* 销毁图形操作的函数指针 */ void (*draw)(); /* 绘制图形操作的函数指针 */ shape_t; typedef struct shape_t common; int x; int y; po
23、int_t; /* 定义点类型，x、y 为点坐标 */ void destroyPoint (point_t* this) free(this); printf (“Point destoryed!n“);) /* 销毁点对象 */ void drawPoint (point_t* this) printf(“P(%d, %d)“, thisx, thisy);) /* 绘制点对象 */ shape_t* createPoint(va_list* ap) /* 创建点对象，并设置其属性 */ point_t* p point; if (p_point=(point_t*) malloc (si
24、zeof(point_t)=NULL) return NULL; p_pointcommon. type = point; p_pointcommon. destroy = destroyPoint; p_pointcommon. draw=drawPoint; p_pointx = va_arg (*ap, int); /* 设置点的横坐标 */ p_pointy = va_arg(*ap, int); /* 设置点的纵坐标 */ return (shape_t*)p_point; /* 返回点对象指针 */ tyPedef struct /* 定义圆类型 */ shape_t common
25、; point_t *center; /* 圆心点 */ int radius; /* 圆半径 */ circle_t; void destroyCircle(circle_t* this) free (_); free(this); printf(“Circle destoryed!n“); void drawCircle (circle_t* this) printf (“C(“); _draw( thiscenter); /* 绘制圆心*/ printf (“, %d)“, thisradius); shape_t* createCircle(va list* ap) /* 创建一个圆，
26、并设置其属性 */ circle_t* p_circle; if (p_circle=(circle_t*)malloc(sizeof(circle_t)=NULL)return NULL; p_circlecommon. type=circle; p_circlecommon. destroy=destroyCircle; p_circlecommon. draw=drawCircle; _ =createPoint(ap); /* 设置圆心 */ p_circleradius=va arg(*ap, int); /* 设置圆半径 */ return p_circle; shape t* c
27、reateShape(shape_type st, ) /* 创建某一种具体的图形 */ va_list ap; /* 可变参数列表 */ shape_t* P_shape = NULL; _ (ap, st); if ( st = point) p_shape=createPoint( ap); /* 创建点对象 */ if ( st = circle) p_shape=createCircle(ap); /* 创建圆对象 */ va_end(ap); return p-shape; int main() int i; /* 循环控制变量，用于循环计数 */ shape t* shapes2
28、; /* 图形指针数组，存储图形的地址 */ shape_s0 = createShape ( point, 2, 3); /* 横坐标为 2，纵坐标为 3 */ shapes1 = createShape( circle, 20, 40, 10); /* 圆心坐标(20, 40), 半径为 10 */ for (i=0; i2; i+) shapesidraw(shapesi); printf(“n“); /* 绘制数组中图形 */ for( i=1; i=0; i-) shapesidestroy(shapesi); /* 销毁数组中图形 */ return 0; 运行结果如下： p(2,
29、 3) _ Circle destoryed! Point destoryed! （分数：20.00）_正确答案：()解析：thiscenter thiscentercommon p_circlecenter va_start C(P(20，40)，1 0)四、试题四(总题数：1，分数：20.00)3.说明 在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图1 所示。信
30、号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。 每个节点有一个 d 值，表示从其父节点到该节点的信号衰减量。例如，在图 1 中，节点 w、p、q 的 d 值分别为 2、1、3，树根节点表示信号源，其 d 值为 0。 每个节点有一个 M 值，表示从该节点出发到其所有叶子节点的信号衰减量的最大值。显然，叶子节点的 M值为 0。对于非叶子节点 j，M(j)=maxM(k)+d(k)|k 是 j 的子节点。 在此公式中，要计算节点的 M 值，必须先算出其所有子节点的 M 值。 在计算 M 值的过程中，对于某个节点 i，若
31、其有一个子节点 k 满足 d(k)+Mfk)大于容忍值，则应在 k 处放置放大器，否则，从节点 i 到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点 i 处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图 1 中，从节点 P 到其所有叶子节点的最大衰减值为 4。若容忍值为 3，则必须在 s 处放置信号放大器，这样可使得节点 p 的 M 值为2。同样，需要在节点 q、v 处放置信号放大器，如图 2 阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。 （分数：20.00）_正确答案：()解析：root rootchildp
32、tr0 rootchildptri placeBoosters(p) degradation五、试题五(总题数：1，分数：20.00)4.说明 一般的树型结构常采用孩子-兄弟表示法表示，即用二叉链表作树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，下图(a)中所示的树的孩子-兄弟表示如下图(b)中所示。 （分数：20.00）_正确答案：()解析：EnQueue(&tempQ, root) brotherptr=brotherptrnextbrother !IsEmpty(tempQ) DeQueue(&tempQ, &ptr) !ptrfirstchild EnQueue(&tempQ, ptrfirstchild) brotherptr=brotherptnextbrother
