软件设计师-常用算法设计

试卷详情

软件设计师-常用算法设计
[填空题]
阅读下列说明，回答问题1至问题3，将解答填入对应栏内。
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下：
(1)分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
(2)递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
(3)合并：快速排序在原地排序，故不需要合并操作。
[问题1]
下面是快速排序的伪代码，请填补其中的空缺。
伪代码中的主要变量说明如下：
A：待排序数组；
p，r：数组元素下标，从p到r；
q：划分的位置；
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)；

PARTITION(A，p，r)
X=A[r]；i=p-1；
for(j=p；j≤r-1；j++)
if(A[j]≤x)
i=i+1；
交换A[j]和A[j]

交换 (1) 和 (2) //注：空(1)和空(2)答案可以互换，但两个空全部答对方可得分
return (3)

[问题2]
(1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排
[填空题]
阅读以下说明和C程序，将应填入 (n) 处的字句写在对应栏内。
[说明]
假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。
程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：
c[i][i]：将任务i分配给工人j的费用。
task[i]：值为0表示任务i未分配；值为j表示任务i分配给工人j。
worker[k]：值为0表示工人k未分配任务；值为1表示工人k已分配任务。
mincost：最小总费用。
[程序]
#include＜stdio.h＞
#define N 8 /*N表示任务数和工人数*/
int c[N][N]；
unsigned int mincost=65535； /*设置min的初始值，大于可能的总费用*/
int task[N]，temp[N]，worker[N]；
void plan(int k，unsigned int cost)
int i；
if( (1) ＆＆cost＜mincost)
mincost=cost；
for(i=0；i＜N；i++)temp[i]=task[i]；

eise
for(i=0；i＜N；i++) /*分配任务k*/
if(worker[i]==0 ＆＆ (2) )
worker[i]=1；task[k]= (3) ；
plan( (4) ，cost+c[k][i])；
(5) ；task[k]=0；
/*if*/

/*plan*/
void main（　）
int i，j；
[填空题]
阅读以下说明和C代码，将应填入 (n) 处的字句写在对应栏内。
[说明]
在一个简化的绘图程序中，支持的图形种类有点(point)和圆(ckcle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型shape_t、point_t和circle_t分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。
[C代码]
typedef enumpoint，circle)shape_type； /*程序中的两种图形：点和圆*/
typedef struct /*基本的图形类型*/
shape_type type； /*图形种类标识：点或者圆*/
void(*destroy)（　）； /*销毁图形操作的函数指针*/
void(*draw)（　）； /*绘制图形操作的函数指针*/
shape_t；
typedef struct(shape_t common；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)"，this-＞x，this-＞y)；
/*绘制点对象*/
shape_t* createPoint(va_list* ap)/*创建点对象，并设置其属性*/
point_t* p_point；
if((p_point=(point_t*)malloc(sizeof(point_t)))==NULL)return NULL；
p_point-＞common.type=point；p_point-＞common.destroy=destroyPoint；
p_point-＞
[填空题]
阅读下列说明，回答问题1至问题3，将解答填入对应栏内。
[说明]
希赛公司供应各种标准的营养套餐。假设菜单上共有n项食物m₁，m₂，…，m_n，每项食物m_i的营养价值为v_i，价格为p_i，其中i=1，2，…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。
[问题1]
下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)。
伪代码中的主要变量说明如下：
n：总的食物项数；
v：营养价值数组，下标从1到n，对应第1项到第n项食物的营养价值；
p：价格数组，下标从1到n，对应第1项到第n项食物的价格；
M：总价格标准，即套餐的价格不超过M；
x：解向量(数组)，下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中；
nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下：
MaxNutrientValue(n，v，p，M，x)
1 for i=0 to n
2 nv[i][0]=0
3 for j=1 to M
4 nv[0][j]=0
5 for i=1 to n
6 for j=1 to M
7 if j＜p[i] //若食物m_i不能加入到套餐中
8 nv[i][j]=nv[i-1][j]
9 else if (1)
10 nv[i][j]=nv[i-1][j]
11 else
12 nv[i][j]
[简答题]
阅读下列说明和c代码，回答问题1至问题3，将解答写在对应栏内。
[说明]
某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m个位置。对于元素值重复的情况，依次放入第m-1，m-2，…个位置。例如，如果元素值小于等于4的元素个数有10个，其中元素值等于4的元素个数有3个，则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。算法的具体步骤如下。
步骤1：统计每个元素值的个数。
步骤2：统计小于等于每个元素值的个数。
步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。
[C代码]
下面是该排序算法的c语言实现。
(1)常量和变量说明
R：常量，定义元素取值范围中的取值个数，如上述应用中R值应取6；
i：循环变量；
n：待排序元素个数；
a：输入数组，长度为n；
b：输出数组，长度为n；
c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。
(2)函数sort
1 void sort(int n，int a[]，int b[])
2 int c[R]，i；
3 for(i=0；i＜ (1) ；i++)
4 c[i]=0；
5
6 for(i=0；i＜n；i++)
7 c[a[i]]= (2) ；
8
9 for(i=1；i＜R；i++)
10 c[i]= (3)
11
12 for(i=0；i＜n；i++)
13 b[c[a[i]]-1]= (4) ；
14 c[a[i]]=c[a[i]]-1；
15
16
根据说明和C代码，填充C