【计算机类职业资格】中级软件设计师下午试题-119及答案解析.doc
《【计算机类职业资格】中级软件设计师下午试题-119及答案解析.doc》由会员分享,可在线阅读,更多相关《【计算机类职业资格】中级软件设计师下午试题-119及答案解析.doc(14页珍藏版)》请在麦多课文档分享上搜索。
1、中级软件设计师下午试题-119 及答案解析(总分:75.00,做题时间:90 分钟)一、B试题一/B(总题数:1,分数:15.00)1.一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图(a)所示的树的孩子一兄弟表示如图(b)所示。(分数:15.00)_二、B试题二/B(总题数:1,分数:15.00)2.函数 int Toplogical(LinkedWDigraph G)的功能是对图 G 中的顶点进行拓扑排序,并返回关键路径的长度。其中图 G 表示一个具有 n 个顶点的 AOE 网,图中顶点从
2、1n 依次编号,图 G 的存储结构采用邻接表表示,其数据类型定义如下:typedef struct Gnode /*邻接表的表结点类型*/int adjvex; /*邻接顶点编号*/int weight; /*弧上的权值*/struct Gnode*nextarc; /*指示下一个弧的结点*/Gnode;typedef struct Adjlist /*邻接表的头结点类型*/char vdata; /*顶点的数据信息*/struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/Adjulist;typedef struct LinkedWDigraph /*图的类型*/in
3、t n,e; /*图中顶点个数和边数*/struct Adjlist*head; /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph;例如,某 AOE 网如图 1 所示,其邻接表存储结构如图 2 所示。图 1 AOE 网(分数:15.00)_三、B试题三/B(总题数:1,分数:15.00)快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的三个步骤如下:分解:选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r,使得 Aq大于等于 Apq-1中的每个元素,小于 Aq+1r中的每个元素。q 的值在划分过程中计算。
4、递归求解:通过递归的调用快速排序,对子数组 Apq-1和 Aq+1r分别排序。合并:快速排序在原地排序,故不需合并操作。(分数:15.00)(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,
5、r); PARTITION(A,p,r) x=Ar; i=p-1; for (j=p;j=r-1;j+) if (Aj=x) i=i+1; 交换 Ai和 Aj; 交换U U 1 /U /U和U U 2 /U /U /注:空U 1 /U和空U 2 /U答案可互换,但两空全部答对方可得分 returnU U 3 /U /U (分数:5.00)_(2).(1)假设要排序包含 n 个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O 记号。最佳情况为U U 2 /U /U,平均情况为U U 3 /U /U,最坏情况为U U 4 /U /U。 (2)假设要排序的 n 个元素都具有相同值
6、时,快速排序的运行时间复杂度属于哪种情况?U U 5 /U /U。(最佳、平均、最坏)(分数:5.00)_(3).(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作,请填充其中的空缺处。其中,RANDOM(i,j)表示随机取 i 到 j 之间的一个数,包括 i 和 j。 RANDOMIZED-PARTITION(A,p,r) i=RANDOM(p,r); 交换U U 3 /U /U和U U 4 /U /U; /空U 3 /U和空U 4
7、 /U答案可互换,但两空全部答对方可得分 return PARTITION(A,p,r); (2)随机化快速排序是否能够消除最坏情况的发生?U U 5 /U /U。(是或否)(分数:5.00)_四、B试题四/B(总题数:1,分数:15.00)3.阅读下列说明和 C 代码,将应填入(n)处的字句写在答题纸的对应栏内。说明设某一机器由 n 个部件组成,每一个部件都可以从 m 个不同的供应商处购得。供应商 j 供应的部件 i 具有重量 Wij和价格 Cij。设计一个算法,求解总价格不超过上限 cc 的最小重量的机器组成。采用回溯法来求解该问题:首先定义解空间。解空间由长度为 n 的向量组成,其中每个
8、分量取值来自集合1,2,m,将解空间用树形结构表示。接着从根结点开始,以深度优先的方式搜索整个解空间。从根结点开始,根结点成为活结点,同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买,得到一个新结点。判断当前的机器价格(C 11)是否超过上限(cc),重量(W 11)是否比当前已知的解(最小重量)大,若是,应回溯至最近的一个活结点;若否,则该新结点成为活结点,同时也成为当前的扩展结点,根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买,得到一个新结点。同样判断当前的机器价格(C 11+C21)是否超过上限(cc),重量(W 11+W21)是否比当前已知
9、的解(最小重量)大。若是,应回溯至最近的一个活结点;若否,则该新结点成为活结点,同时也成为当前的扩展结点,原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索,直到找到所要求的解或者解空间中已无活结点为止。C 代码下面是该算法的 C 语言实现。U /U变量说明。n:机器的部件数。m:供应商数。cc:价格上限。w:二维数组,wij表示第 j 个供应商供应的第 i 个部件的重量。c:二维数组,cij表示第 j 个供应商供应的第 i 个部件的价格。best1W:满足价格上限约束条件的最小机器重量。bestC:最小重量机器的价格。bestX:最优解,一维数组,bestX|i表示第 i 个部件来自哪
10、个供应商。cw:搜索过程中机器的重量。cp:搜索过程中机器的价格。x:搜索过程中产生的解,xi表示第 i 个部件来自哪个供应商。i:当前考虑的部件,从 0n-1。j:循环变量。U /U函数 backtrack。int n=3;int m=3;int cc=4;int w33=1,2,3,3,2,1,2,2,2;int c33=1,2,3,3,2,1,2,2,2;int bestW=8;int bestC=0;int bestX3=0,0,0);int cw=0;int cp=0;int x3=0,0,0;int backtrack(int i)int j=0;int found=0;if(in
11、-1)/*得到问题解*/bestW=cw;bestC=cp;for(j=0;jn;j+)U U /U /U;return 1;if(cp=cc)/*有解*/found=1;for(j=0;U U /U /U;j+)/*第 i 个部件从第 j 个供应商购买*/U U /U /U;cw=cw+wij;cp=cp+ciij;if(cp=ccU U /U /U/*深度搜索,扩展当前结点*/if(backtrack(i+1)found=1;/*回溯*/cw=cw-wij;U U /U /U;return found;(分数:15.00)_五、B试题五/B(总题数:1,分数:15.00)阅读下列说明和 C
12、 代码,回答问题。说明设有 n 个货物要装入若干个容量为 C 的集装箱以便运输,这 n 个货物的体积分别为S1,S2,Sn,且有 siC(1in)。为节省运输成本,用尽可能少的集装箱来装运这 n 个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略(Firstfit)首先将所有的集装箱初始化为空,对于所有货物,按照所给的次序,每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(Bestfit)与最先适宜策略类似,不同的是,总是把货物装到能容纳它且目前剩余容量最小的集装箱,使得该箱子装入货物后闲置空间最小。C 代码下面是这两个算法的 C 语言核心代码。U 1 /U变量说
13、明。n:货物数。C:集装箱容量。s:数组,长度为 n,其中每个元素表示货物的体积,下标从 0 开始。b:数组,长度为 n,bi表示第 i+1 个集装箱当前已经装入货物的体积,下标从 0。i,j:循环变量。k:所需的集装箱数。min:当前所用的各集装箱装入了第 i 个货物后的最小剩余容量。m:当前所需要的集装箱数。temp:临时变量。U 2 /U函数 firstfit。int firstfit()inti,j;k=0;for(i=0;in;i+)bi=0;for(i=0;in;i+)U U 1 /U /U;while(C-bjsi)j+;U U 2 /U /U;k=k(j+1)?k:(j+1);
14、returnkU 3 /U函数 bestfit。int bestfit()int i,j,min,m,temp;k=0;for(i=0;in;i+)bi=0;for(i=0;in;i+)min=C;m=k+1;for(j=0;jk+1;j+)temp=C-bj-si;if(temp0tempmin)U U 3 /U /U;m=j;U U 4 /U /U;k=k(m+1)?k:(m+1);return k;(分数:15.00)(1).根据说明和C 代码,填充 C 代码中的空(1)(4)。(分数:5.00)_(2).根据说明和C 代码,该问题在最先适宜和最优适宜策略下分别采用了U U 2 /U /
15、U和U U 3 /U /U算法设计策略,时间复杂度分别为U U 4 /U /U和U U 5 /U /U(用 O 符号表示)。(分数:5.00)_(3).考虑实例 n=10,C=10,各个货物的体积为4,2,7,3,5,4,2,3,6,2。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为U U 3 /U /U和U U 4 /U /U。考虑一般的情况,这两种求解策略能否确保得到最优解?U U 5 /U /U(能或否)。(分数:5.00)_中级软件设计师下午试题-119 答案解析(总分:75.00,做题时间:90 分钟)一、B试题一/B(总题数:1,分数:15.00)1.一般的树结构常采用孩子-
16、兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图(a)所示的树的孩子一兄弟表示如图(b)所示。(分数:15.00)_正确答案:(1)EnQueue(tempQ,root)。 (2)brotherptr=brotherptr-nextbrother。 (3)!IsEmpty(tempQ)。 (4)DeQueue(tempQ, /*邻接顶点编号*/int weight; /*弧上的权值*/struct Gnode*nextarc; /*指示下一个弧的结点*/Gnode;typedef struct Adjlist /*邻接
17、表的头结点类型*/char vdata; /*顶点的数据信息*/struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/Adjulist;typedef struct LinkedWDigraph /*图的类型*/int n,e; /*图中顶点个数和边数*/struct Adjlist*head; /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph;例如,某 AOE 网如图 1 所示,其邻接表存储结构如图 2 所示。图 1 AOE 网(分数:15.00)_正确答案:(1)indegreep-adjvex+。 (2)Stacktop-。 (3)indeg
18、reep-adjvex-。 (4)(vew+p-weight)vep-adjvex。 (5)vew。)解析:解析 此 C 语言程序题考点为拓扑排序和关键路径。在解题之前,先了解几个概念。(1)AVO 网络。一个大工程中有许多项目组,有些项目的实行存在先后关系,某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示,工程的项目称为活动,有向图的顶点表示活动,有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络,简称 AOV 网络,图 3所示是一个 AOV 网络。*图 3 AOE 网络图(2)拓扑排序。对 AOV 网络的顶点进行拓扑排序,就是对全
19、部活动排成一个拓扑序列,使得如在 AOV 网络中存在一条弧(i,j),则活动 i 排在活动 j 之前。对图 3 中的顶点进行拓扑排序,可以得到多个不同的拓扑序列,如02143567,01243657,02143657,01243567。(3)AOE 网络。利用 AOV 网络,对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间,为了能估算某个活动的开始时间,找出那些影响工程完成时间最大的活动,需要利用带权的有向图。图中的顶点表示一个活动结束的事件,图中的边表示活动,边上的权表示完成该活动所需的时间,这种用边表示活动的网络称为 AOE 网络。图 4 所示为一个具有
20、8 个活动的某个工程的 AOE 网络。图中,有 6 个顶点,分别表示事件 V1V6,其中 V1 是工程的开始状态,V4 是工程的结束状态。边上的权表示完成该活动所需的时间。*图 4 AOE 网络图(4)关键路径。在 AOE 网络中某些活动可以并行地进行,所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度,称从开始顶点到结束顶点的最长路径为关键路径,关键路径上的活动为关键活动。如图 4 的 AOE 网络的关键路径为 V1-V2-V6-V4,关键路径长度为 80。了解了上面的这些概念以后,解题就非常容易了。从程序中的注释可知下段程序的作用是求网中各顶点的入度。for(j=1;j=G.n;j
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
本资源只提供5页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 职业资格 中级 软件 设计师 下午 试题 119 答案 解析 DOC
![提示](http://www.mydoc123.com/images/bang_tan.gif)