软件设计师常用算法设计一.docx
- 文档编号:10318140
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:23
- 大小:26.36KB
软件设计师常用算法设计一.docx
《软件设计师常用算法设计一.docx》由会员分享,可在线阅读,更多相关《软件设计师常用算法设计一.docx(23页珍藏版)》请在冰点文库上搜索。
软件设计师常用算法设计一
软件设计师-常用算法设计
(一)
(总分:
135.02,做题时间:
90分钟)
一、
(总题数:
1,分数:
15.00)
阅读下列说明,回答问题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个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O记号。
最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况?
(7)。
(最佳、平均、最坏)
[问题3]
(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。
有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作,请填充其中的空缺处。
其中,RANDOM(i,j)表示随机取i到j之间的一个数,包括i和j。
RANDOMIZED-PARTITION(A,p,r)
i=RANDOM(p,r);
交换(8)和(9);//注:
空(8)和空(9)答案可以互换,但两个空全部答对方可得分
returnPARTITION(A,p,r);
(2)随机化快速排序是否能够消除最坏情况的发生?
(10)。
(是或否)
(分数:
15.00)
填空项1:
__________________ (正确答案:
i+1)
解析:
填空项1:
__________________ (正确答案:
A[i+1])
解析:
填空项1:
__________________ (正确答案:
A[r])
解析:
(1)和空
(2)答案可以互换。
填空项1:
__________________ (正确答案:
O(nlgn)或O(nlog2n))
解析:
填空项1:
__________________ (正确答案:
O(nlgn)或O(nlog2n))
解析:
填空项1:
__________________ (正确答案:
O(n2))
解析:
填空项1:
__________________ (正确答案:
最坏)
解析:
填空项1:
__________________ (正确答案:
A[i])
解析:
填空项1:
__________________ (正确答案:
A[r])
解析:
(8)和空(9)答案可以互换。
填空项1:
__________________ (正确答案:
否)
解析:
二、
(总题数:
1,分数:
15.00)
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。
[说明]
希赛公司供应各种标准的营养套餐。
假设菜单上共有n项食物m1,m2,…,mn,每项食物mi的营养价值为vi,价格为pi,其中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)
1fori=0ton
2nv[i][0]=0
3forj=1toM
4nv[0][j]=0
5fori=1ton
6forj=1toM
7ifj<p[i]//若食物mi不能加入到套餐中
8nv[i][j]=nv[i-1][j]
9elseif
(1)
10nv[i][j]=nv[i-1][j]
11else
12nv[i][j]=nv[i-1][j-p[i]]+v[i]
13j=M
14fori=ndownto1
15if
(2)
16x[i]=0
17else
18x[i]=1
19(3)
20returnxandnv[n][M]
[问题2]
现有5项食物,每项食物的营养价值和价格如表21-2所示。
表21-2食物的营养价值和价格表
编码
营养价值
价格
ml
200
50
m2
180
30
m3
225
45
m4
200
25
m5
50
5
若要求总价格不超过100的营养价值最大的套餐,则套餐应包含的食物有(4)(用食物项的编码表示),对应的最大营养价值为(5)。
[问题3]
问题1中伪代码的时间复杂度为(6)(用O符号表示)。
(分数:
15.00)
填空项1:
__________________ (正确答案:
nv[i-][j]≥nv[i-1][j-p[i]]+v[i])
解析:
填空项1:
__________________ (正确答案:
nv[i][j]=nv[i-1][j])
解析:
填空项1:
__________________ (正确答案:
j=j-p[i])
解析:
填空项1:
__________________ (正确答案:
m2、m3、m4(注:
答案中食物编码无前后顺序关系。
))
解析:
填空项1:
__________________ (正确答案:
605)
解析:
填空项1:
__________________ (正确答案:
O(nM),或O(n×M),或O(n*M))
解析:
三、
(总题数:
1,分数:
15.00)
阅读下列说明和c函数,将应填入(n)处的字句写在对应栏内。
[说明]
已知集合A和B的元素分别用不含头结点的单链表存储,函数Difference()用于求解集合A与B的差集,并将结果保存在集合A的单链表中。
例如,若集合A=5,10,20,15,25,30,集合B=5,15,35,25,如图21-10(a)所示,运算完成后的结果如图21-10(b)所示。
链表结点的结构类型定义如下:
typedefstructNode
ElemTypeelem;
structNode*next;
NodeType;
[C函数]
voidDifference(NodeType**LA,NodeType*LB)
NodeType*pa,*pb,*pre,*q;
pre=NULL;
(1);
while(pa)
pb=LB;
while(
(2))
pb=pb->next;
if((3))
if(!
pre)
*LA=(4);
else
(5)=pa->next:
q=pa;
pa=pa->next;
free(q);
else
(6);
pa=pa->next;
(分数:
15.00)
填空项1:
__________________ (正确答案:
pa=*LA)
解析:
填空项1:
__________________ (正确答案:
pb&&pb->elem!
=pa->elem,或其等价表示)
解析:
填空项1:
__________________ (正确答案:
pb)
解析:
填空项1:
__________________ (正确答案:
pa->next,或(*pa).next,或其等价表示)
解析:
填空项1:
__________________ (正确答案:
pre->next,或(*pre).next,或其等价表示)
解析:
填空项1:
__________________ (正确答案:
pre=pa)
解析:
四、
(总题数:
1,分数:
15.00)
阅读下列说明,回答问题1和问题2,将解答填入对应栏内。
[说明]
现需要在某城市中选择一个社区建一个大型超市,使该城市的其他社区到该超市的距离总和最小。
用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置,即在给定图中选择一个顶点,使该顶点到其他各顶点的最短路径之和最小。
首先,算法需要求出每个顶点到其他任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后,对每个顶点计算其他各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。
[问题1]
本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。
已知图G的顶点集合为V=1,2,…,n),W=Wijn*n为权重矩阵。
设
为从顶点i到顶点j的一条最短路径的权重。
当k=0时,不存在中间顶点,因此
;当k>0时,该最短路径上所有的中间顶点均属于集合1,2,…,k。
若中间顶点包括顶点k,则
;若中间顶点不包括顶点k,则
。
于是得到如下递归式:
因为对于任意路径,所有的中间顶点都在集合1,2,…,n内,因此矩阵
给出了任意两个顶点之间的最短路径,即对所有i,j∈V,
表示顶点i到顶点j的最短路径。
下面是求解该问题的伪代码,请填充其中的空缺
(1)~(6)。
伪代码中的主要变量说明如下:
W:
权重矩阵;
n:
图的顶点个数;
SP:
最短路径权重之和数组,SP[i]表示顶点i到其他各顶点的最短路径权重之和,i取值为1~n;
min_SP:
最小的最短路径权重之和;
min_v:
具有最小的最短路径权重之和的顶点;
i:
循环控制变量;
j:
循环控制变量;
k:
循环控制变量。
LOCATE-SHC)PPINGNALL(W,n)
1D(0)=W
2for
(1)
3fori=1ton
4forj=1ton
5if
6
(2)
7else
8(3)
9fori=1ton
10SP[i]=0
11forj=1ton
12(4)
13min_SP=SP[1]
14(5)
15fori=2ton
16ifmin_SP>SP[i]
17min_SP=SP[i]
18min_v=i
19return(6)
[问题2]
问题1中伪代码的时间复杂度为(7)(用O符号表示)。
(分数:
14.98)
填空项1:
__________________ (正确答案:
k=1ton)
解析:
填空项1:
__________________ (正确答案:
)
解析:
填空项1:
__________________ (正确答案:
)
解析:
填空项1:
__________________ (正确答案:
)
解析:
填空项1:
__________________ (正确答案:
min_v=1)
解析:
填空项1:
__________________ (正确答案:
min_v)
解析:
填空项1:
__________________ (正确答案:
O(n3))
解析:
五、
(总题数:
1,分数:
15.00)
阅读下列说明和C函数代码,将应填入(n)处的字句写在对应栏内。
[说明]
对二叉树进行遍历是二叉树的一个基本运算。
遍历是指按某种策略访问二又树的每个结点,且每个结点仅访问一次的过程。
函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedefstructBtNode
ElemTypedata;/*结点的数据域,ElemType的具体定义省略*/
structBtNode*lchiid,*rchiid;/*结点的左、右孩子指针域*/
BtNode,*BTree;
在函数InOrderO中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点的单向链表(简称链栈),其结点类型定义如下:
typedefstructStNode/*链栈的结点类型*/
BTreeelem;/*栈中的元素是指向二叉链表结点的指针*/
StructStNode*link;
StNode;
假设从栈顶到栈底的元素为en,en-1,…,e1,则不含头结点的链栈示意图如图21-11所示。
[C函数]
intInOrder(BTreeroot)/*实现二叉树的非递归中序遍历*/
BTreeptr;/*ptr用于指向二叉树中的结点*/
StNode*q;/*q暂存链栈中新创建或待删除的结点指针*/
StNode*stacktop=NULL;/*初始化空栈的栈顶指针stacktop*/
ptr=root;/*ptr指向二叉树的根结点*/
while(
(1)||stacktop!
=NULL)
while(ptr!
=NULL)
q=(StNode*)malloc(Sizeof(StNode));
if(a==NULL)
return-1;
q->elem=ptr;
(2);
stacktop=q;/*stacktop指向新的栈顶*/
ptr=(3);/*进入左子树*/
q=stacktop;
(4);/*栈顶元素出栈*/
visit(q);/*visit是访问结点的函数,其具体定义省略*/
ptr=(5);/*进入右子树*/
free(q);/*释放原栈顶元素的结点空间*/
return0;
/*Inorder*/
(分数:
15.00)
填空项1:
__________________ (正确答案:
q->elem->rchild)
解析:
填空项1:
__________________ (正确答案:
ptr!
=NULL,或ptr!
=0,或ptr)
解析:
填空项1:
__________________ (正确答案:
q->link=stacktop)
解析:
填空项1:
__________________ (正确答案:
ptr->lchild)
解析:
填空项1:
__________________ (正确答案:
stacktop=stacktop->link,或stacktop=q->link)
解析:
六、
(总题数:
1,分数:
15.00)
阅读下列说明,回答问题1和问题2,将解答填入对应栏内。
[说明]
0-1背包问题可以描述为:
有n个物品,i=1,2,…,n,第i个物品价值为vi,重量为wi(vi和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,即
,且总重量不超过背包容量,即
,其中,xi∈0,1,xi=0表示第i个物品不放入背包,xi=1表示第i个物品放入背包。
[问题1]
用回溯法求解此0-1背包问题,请填充伪代码中的空缺
(1)~(4)。
回溯法是一种系统的搜索方法。
在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。
对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。
为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。
现在假设已经设计了BOUND(v,w,k,w)函数,其中v、w、k和W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。
对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无须再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:
背包容量;n:
物品个数;w:
重量数组;v:
价值数组;fw:
获得最大价值时背包的重量;fp:
背包获得的最大价值;X:
问题的最优解。
变量说明如下:
cw:
当前的背包重量;cp:
当前获得的价值;k:
当前考虑的物品编号;Y:
当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X)
1cw←cp←0
2
(1)
3fp←-1
4Whiletrue
5whilek≤nandcw+w[k]≤Wdo
6
(2)
7cp←cp+v[k]
8Y[k]←1
9k←k+1
10ifk>nthen
11iffp<cpthen
12fp←cp
13fw←cw
14k←n
15X←Y
16elseY(k)←0
17whileBOUND(cp,cw,k,W)≤fpdo
18whilek≠0andY(k)≠1do
19(3)
20ifk=0thenreturn
21Y[k]←0
22cw←cw←w[k]
23cp←cp←v[k]
24(4)
[问题2]
考虑表21-3所示的实例,假设有3个物品,背包容量为22。
图21-12是根据上述算法构造的搜索树,其中结点的编号表示搜索树生成的顺序,边上的数字I/O分别表示选择/不选择对应物品。
除了根结点之外,每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值,右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。
为获得最优解,应该选择物品(5),获得的价值为(6)。
表21-30-1背包问题实例
物品1
物品2
物品3
重量
15
10
10
价值
30
18
17
单位价值
2
1.8
1.7
对于表21-3所示的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为(7);而采用上述的回溯法,搜索树的结点数为(8)。
(分数:
15.04)
填空项1:
__________________ (正确答案:
k←1,或其等价形式)
解析:
填空项1:
__________________ (正确答案:
cw←cw+w[k],或其等价形式)
解析:
填空项1:
__________________ (正确答案:
k←k-1,或其等价形式)
解析:
填空项1:
__________________ (正确答案:
k←k+1,或其等价形式)
解析:
填空项1:
__________________ (正确答案:
物品2和物品3)
解析:
填空项1:
__________________ (正确答案:
35)
解析:
填空项1:
__________________ (正确答案:
15)
解析:
填空项1:
__________________ (正确答案:
8)
解析:
七、
(总题数:
1,分数:
15.00)
阅读下列说明和C代码,回答问题1至问题3,将解答写在对应栏内。
[说明]
对有向图进行拓扑排序的方法如下。
(1)初始时拓扑序列为空。
(2)任意选择一个入度为0的顶点,将其放入拓扑序列中,同时从图中删除该顶点以及从该顶点出发的弧。
(3)重复
(2),直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列,则完成拓扑排序;否则,由于有向图中存在回路无法完成拓扑排序)。
函数int*TopSort(LinkedDigraphG)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。
其中,图G中的项点从1开始依次编号,顶点序列为v1,v2,…,vn,图G采用邻接表表示,其数据类型定义如下:
#defineMAXVNUM50/*最大顶点数*/
typedefstructArcNode/*表结点类型*/
intadjvex;/*邻接顶点编号*/
StructArcNode*nextarc;/*指示下一个邻接顶点*/
ArcNode;
typedefstructAdjList/*头结点类型*/
charvdata;/*顶点的数据信息*/
ArcNode*firstarc;/*指向邻接表的第一个表结点*/
AdjList;
typedefstructLinkedDigraph/*图的类型*/
intn;/*图中顶点个数*/
AdjListVhead[MAXVNUM];/*所有顶点的头结点数组*/
LinkedDigraph;
例如,某有向图G如图21-13所示,其邻接表如图21-14所示。
函数TopSort中用到了队列结构(Queue的定义省略),实现队列基本操作的函数原型如表21-4所示。
表21-4函数原型
函数原型
说明
voidInitQueue(Queue*Q)
初始化队列(构造一个空队列)
boolIsEmpty(QueueQ)
判断队列是否为空,若是则返回true,否则返回false
voidEnQueue(Queue*Q,inte)
元素入队列
voidDeQueue(Queue*Q,int*p)
元素出队列
[C代码]
int*TopSort;(LinkedDigraphG)
ArcNode*p;/*临时指针,指示表结点*/
QueueQ;/*临时队列,保存入度为0的顶点编号*/
intk=0;/*临时变量,用作数组元素的下标*/
intj=0,w=0;/*临时变量,用作顶点编号*/
int*topOrder,*inDegree;
topOrder=(int*)malloc((G.n+1)*sizeof(int));/*存储拓扑序列中的顶点编号*/
inDegree=(int*)malloc((G.n+1)*siZeof(int)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件 设计师 常用 算法 设计