1、软件水平考试中级软件设计师下午应用技术（数据结构与算法应用）模拟试卷 1及答案与解析 一、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 1 一般的树结构常采用孩子 -兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图 15-1(a)所示的树的孩子兄弟表示如图 15一 1(b)所示。 函数LevelTraVerse()的功能是对给定树进行层序遍历。例如，当对图 15 1(a)中的树进行层序遍历时，结点的访问次序为 DBAEFPC。 对
2、树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表 15一 1所示。 Bool、 Status类型定义如下： typedef enumFALSE=0， TRUE=1)Bool； typedef enumOVERFLOW=一 2，UNDERFLOW=一 1， ERROR=0， OK=1Status；树的二叉链表结点定义如下：typedef struct Node char data； struct Node*firstchild， *nextbrother； Node，*TreeNode；【函数代码】 Status LevelTraverse(TreeNode root) *层序遍历
3、树，树采用孩子一兄弟表示法， root是树根结点的指针 * Queue temQ ； TreeNode ptr， brOtherptr； if(!root)return ERROR； InitQueue(&tempQ)； (1)； brotherptr=root一 nextbrother； while( brotherptr ) EnQueue( tempQ， brotherptr)； (2)， *end-while* while( (3) ) (4)， printf(” c t”， ptr一 data)； if( (5) )continue； (6)， brotherptr=ptr一 fir
4、stchild一 nextbrother； while(brotherptr) EnQueue(&tempQ， brotherptr)； (7)； *endwhile* *end-while* return OK； *LevelTraverse* 2 函数 int Toplogical(LinkedWDigraph G)的功能是对图 G中的顶点进行拓扑排序，并返回关键路径的长度。其中图 G表示一个具有 n个顶点的 AOE网，图中顶点从1 n依次编号，图 G的存储结构采用邻接表表示，其数据类型定义如下： typedef struct Gnode *邻接表的表结点类型 * int adj vex；
5、 *邻接顶点编号 * int weight； *弧上的权值 * struct Gnode*nextarc； *指示下一个弧的结点 * Gnode； typedef struct Adj list *邻接表的头结点类型 * char vdata； *顶点的数据信息 * struct Gnode*Firstadj； *指向邻接表的第一个表结点 * Adjulist； typedef struct LinkedWDigraph *图的类型 * int n， e； *图中顶点个数和边数 * struct Adj list*head； *旨向图中第一个顶点的邻接表的头结点 * LinkedWDigrap
6、h； 例如，某 AOE网如图 15-2所示，其邻接表存储结构如图15-3所示。 【函数代码】 int Toplogical(LinkedWDigraph G)Gnode*p； int j r W r top=0； int*Stack， *ve， *indegree； ve=(int*)malloc(G n+1)*sizeof(int)；indeqree=(int*)malloc(G n+1)*sizeof(int)； *存储网中各项点的入度 * Stack：(int*)malloc(G n+1)*sizeof(int)； *存储入度为 0的顶点的编号 *if(!ve !indegree !St
7、ack) exit(0)； for(J=1； jnextarc； *while* *for* for(j=1； j0) W= (2)； printf(“ c”， G headw vdata)； P=G headw Firstadj； while(P) (3) ； if(!indegreep一 adjvex) Stack+top=P一 adjvex； if( (4) ) vep一 adjvex=vew+p一 weight； p=P一 nextarc； *while* *while* return (5) ； *Toplogical* 3 快速排序是一种典型的分治算法。采用快速排序对数组 Ap r
8、排序的三个步骤如下： 分解：选择一个枢轴 (pivot)元素划分数组。将数组 Ap r划分为两个子数组 (可能为空 )Ap q一 1和 Aq+l_ r，使得 Aq大于等于 Alp q-1中的每个元素，小于 Aq+1 r中的每个元素。 q的值在划分过程中计算。 递归求解：通过递归的调用快速排序，对子数组 Apq一 1和 Aq+1 r分别排序。 合并：快速排序在原地排序，故不需合并操作。 【问题 1】 下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下： A：待排序数组。 P， r：数组元素下标，从 P到 r。 q：划分的位置。 x：枢轴元素。 i：整型变量，用于描述数组下标。下
9、标小于或等于 i的元素的值小于或等于枢轴元素的值。 j循环控制变量，表示数组元素下标。 QUICKSORT(A， p， r) if (pn一 1) *得到问题解 * beStW=cw； bestC=cp； for(j=0； j 4 阅读下列说明和 C代码，回答问题 1问题 3，将解答写在答题纸的对应栏内。 【说明】 设有 n个货物要装入若干个容量为 C的集装箱以便运输，这 n个货物的体积分别为 S1， S2， ， Sn，且有 siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n个货物。 下面分别采用最先适宜策略和最优适宜策略来求解该问题。 最先适宜策略 (Firstfit)首先将所
10、有的集装箱初始化为空， 对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。 最优适宜策略 (Bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。 【 C代码】 下面是这两个算法的 C语言核心代码。 (1)变量说明。 n：货物数。 C：集装箱容量。 s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0开始。 b：数组，长度为 n， bi表示第 i+1个集装箱当前已经装入货物的体积，下标从0。 i， j：循环变量。 k：所需的集装箱数。 min：当前所用的各集装箱装入了第 i个货物后的最小
11、剩余容量。 m：当前所需要的集装箱数。 temp：临时变量。 (2)函数 firstfit。 int firstfit() inti， j； k=0： ； for(i=0； i(j+1)?k： (j+1)； returnk (3)函数 bestfit。 int bestfit() int i , j f min t m t temp； k=0； for(i=0； iO &temp(m+1)?k： (m+1)； return k： 5 根据【说明】和【 C代码】，填充 C代码中的空 (1) (4)。 6 根据【说明】和【 C代码】，该问题在最先适宜和最优适宜策略下分别采用了 (5)和 (6)算法
12、设计策略，时间复杂度分别为 (7)和 (8) (用 0符号表示 )。 7 考虑实例 n=10， C=10，各个货物的体积为 4， 2， 7， 3， 5， 4， 2， 3， 6， 2。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为 (9) 和 (10)。考虑一般的情况，这两种求解策略能否确保得到最优解 ? (11) (能或否 )。 软件水平考试中级软件设计师下午应用技术（数据结构与算法应用）模拟试卷 1答案与解析 一、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 1 【正确答案】 (1)EnQueue
13、(&tempQ， root)。 (2)brotherptr=brotherptr-nextbrother。 (3)!IsEmpty(tempQ)。 (4)DeQueue(&tempQ， &ptr)。 (5)!ptr-firstchild。 (6)EnQueue(&tempQ， ptr-firstchild)。 (7)brotherptr=brotherptr-nextbrother。 【试题解析】 解答此题的关键在于理解用队列层序遍历树的过程。算法的流程是这样的：首先将树根结点入队，然后将其所有兄弟结点入队 (当然，由于是根结点，故无兄弟结点 )；完成这一操作以后，便开始出队、打印；在打印完了
14、之后，需要进行一个判断，判断当前结点有无孩子结点，若有孩子结点，则将孩子结点入队，同时将孩子结点的所有兄弟结点入队；完了以后继续进行出队操作，出队后再次判断当前结点是否有孩子结点，并重复上述过程，直至所有结点输出。 这一描述可能过于理论，难以理解，接下来以本题为例来说明此过程。首先将树根结点 D入队，并同时检查是否有兄弟结点，对于兄弟结点应一并入队。这里的 D没有兄弟结点，所以队列此时应是： D 接下来执行出队操作。 D出队，出队以后检查 D是否有子结点，经检查， D有子结点 B，所以将 B入队，同时将 B的兄弟结点： A和 E按顺序入队。得到队列： B A E 接下来再执行出队操作。 B出队
15、，同时检查 B是否有子结点， B无子结点，所以继续执行出队操作。 A出队，同时检查 A是否有子结点， A有子结点 F，所以将 F入队，同时将 F的兄弟结点 P入队。得到队列： E F P 接下来再次执行出队操作。 E出队， E有子结点 C，所以 C入队。得： F P C 接下来再次执行出队操作。 F出队， F无子结点，继续出队操作， P出队，仍无子结点，最后 C出队，整个过程结束。 通过对算法的详细分析，现在便可轻松得到答案。 (1)应是对根结点 root执行入队操作，即 EnQueue(&tempQ， root)。 (2)在一个循环当中，循环变量是brotherptr，此变量无语句对其进行更
16、新，所以 (2)必定是更新 brotherptr。结合前面的算法 分析可知 (2)应填： brotherptr=brotherptr-nextbrother。 (3)、 (4)加上后面的语句 “printf(“ c t”， ptr-data)； ”是控制数据的输出，这些数据应是从队列中得到，所以此处必有出队操作，同时在出队之前应判断队列是否为空，所以(3)、 (4)填： !IsEmpty(tempQ)和 DeQueue(&tempQ， &ptr)。 (5)实际上是问 “在什么情况下，要持续进行出队操作 ?”，前面的算法分析中已指出：若出队结点无子结点，则继续进行出队操作，所以 (5)填 !pt
17、r-flrstchild。 (6)和 (7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队，所以 (6)填：EnQueue(&tempQ， ptr-firstchild)。 (7)和 (2)相同，填 brotherptr=brotherptr-nextbrother。 2 【正确答案】 (1)indegreep-adjvex+。 (2)Stacktop-。 (3)indegreep-advex-。 (4)(Vew+p-weight)vep-adjvex。 (5)Vew。 【试题解析】 此 C语言程序题考点为拓扑排序和关键路径。在解题之前，先了解几个概念。 (1)AVO网络。一个大工程
18、中有许多项目组，有些项目的实行存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称 AOV网络，图 15-4所示是一个 AOV网络。 (2)拓扑排序。对 AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得如在 AOV网络 中存在一条弧 (i， j)，则活动 i排在活动 j之前。对图 15-4中的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如 02143567， 01243657， 02143657，01243
19、567。 (3)AOE网络。利用 AOV网络，对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间，为了能估算某个活动的开始时间，找出那些影响工程完成时间最大的活动，需要利用带权的有向图。图中的顶点表示一个活动结束的事件，图中的边表示活动，边上的权表示完成该活动所需的时间，这种用边表示活动的网络称为 AOE网络 。图 155所示为一个具有 8个活动的某个工程的 AOE网络。图中，有 6个顶点，分别表示事件 V1V6，其中 V1是工程的开始状态， V4是工程的结束状态。边上的权表示完成该活动所需的时间。 (4)关键路径。 在 AOE网络中某些活动可以并行地进行，所以
20、完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动为关键活动。如图 15-5的AOE网络的关键路径为 V1一 V2一 V6一 V4，关键路径长度为 80。 了解了上面的这些概念以后，解题就非常容易了。 从程序中的 注释可知下段程序的作用是求网中各顶点的入度。 for( j =1； jnextarc； 从已知的代码结合邻接表来看，首先 p指向了邻接表弟 1个结点 V1的 Firstadj域，然后用 while循环遍历了 V1的Firsta， dj指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表
21、中出现的次数，就可知道其入度。又因为程序前面有： indegree=(int*)malloc(G n+1)*sizeof(int) )； *存储网中各顶点的入度 * 所以第 (1)空应填 indegreep-adjex+。 接下来看第 (2)空，第 (2)空是给 w赋值，接下来是打印第 w号结点的数据，这也就意味着 w号结点是拓扑排序选出来的结点，所以 w必是一个入度为 0的结点。然而在此之前已经有程序把所有的入度为0的结点保存在 Stack数组中了，而且 Stack数组是模拟的一个栈，其控制指针只有 top，所以我们应该从 Stack中取出栈顶元素赋值给 w。所以第 (2)空填Stackto
22、p-。注意这里不能用 “Stacktop”，因为前面有入栈语句“Stack+top=j； ”。 接下来看下面的程序段。 while(p) (3) ； if(!indegreep一 adjvex) stack+top =p一 adjvex； if (4) vep一 adjvex =Vew+p一 weight； p=p一 nextarc； 此段程序的作用是：把选出结点所关联的边去掉，即原来 V1有到 V3的边 al=30和到 V2的边 a2=10，当 V1结点选出以后，a1， a2也要随之消失。这时 V3和 V2的入度要更新，也就是把 V3和 V2的入度分别减 1。所以第 (3)空应填 indeg
23、reep-adjvex-。第 (4)空看起来比较棘手，因为前面没有说明 ve是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定 if (4) Vep一 adjvex=vew+p一 weight；的功能是计算关键路径长度。 ve的初值最开始都是 0，而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点 vx， vevx中存的都是最长路径即可。也就是说，首先选出的是 V1，从 V1 V2只有一条路径，所以 vev2=a2=10，从 V1V3只有一条路径，所以 vev3=a1=30。然后选出
24、 V2结点 ,V2选出以后，因为V2 V6有 a5=50，所以现在到 V6的最长路径为 vev6=vev2+a5=60。经过若干步后，当程序选中 V3结点时，会产生到 V6的另外一条路径 V1-V3-V6，这条路径的长度为 50，这条路径比现存的路径长度 vev6短，所以单纯的更新语句 “vep一 adjvex=vew+p-weight”不能正确保存最长路径，为了保证 ve中保存的路径最长，应该有判断 (vewpp-weight)vep-adjvex。所以第 (4)空应该填 “(vew+p-weight)vep-adjvex”。 第 (5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最
25、长路径长度，才是整个图的关键路径呢 ?这一点可以从关键路径的定义着手： “称从开始顶点到结束顶点的最长路径为关键路径 ”，所以最后一个选出结点的 ve存放的便是关键路径。所以第 (5)空应填 vew。 3 【正确答案】 【问题 1】 (1)Ai+1或 Ar。 (2)Ar或 Ai+1。 (3)i+1。 【问题2】 (4)O(nlgn)或 O(nlog2n)。 (5)O(nigh)或 O(nlog2n)。 (6)O(n2)。 (7)最坏。 【问题3】 (8)Ai。 (9)Ar。 (10)否。 【试题解析】 该题主要考查考生对分治算法的快速排序的理解，对伪代码、快速排序的复杂度的掌握，做题的关键是要
26、读懂题干，理解题干中对算法的描述。 问题 1考查的是算法的伪代码表示。分治法的设计思想是将一个难以直接解决的问题，分解成一些规模较小的相同问题，各个击破。其快速排序算法的核心处理是进行划分，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组。一个子 数据组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。以最后一个元素为枢轴元素进行划分，从左到右依次访问数组的每一个元素，与枢轴元素比较大小，并进行元素的交换。在问题 l给出的伪代码中，当循环结束后， Ap i中的值小于等于枢轴元素值 x，而 Ai+1 r-1中的值应大于 x。此时 Ai+1
27、是第一个比 Ar大的元素，于是 Ar与 Ai+1交换，得到划分后的两个子数组。由于划分操作 (即PARTITION操作 )返回枢轴元素的值，因此返回值为 i+1。 问题 2考查的是算法的时间复杂度分析。当每次都能做均匀划分时，是算法的最佳情况，其时间复杂度为 T(N)=2T(n 2)+O(N)，即时间复杂度为 O(nigh)：算法的最坏情况是每次为极不均匀划分，即长度为 n的数组划分后一个子数组为 n-1，一个为 0，其时间复杂度为 T(N)=T(n1)+O(N)，即时间复杂度为 O(n2)；算法的平均情况分析起来比较复杂，假设数组每次划分为 9 10： 1 10，此时时间复杂度可以通过计算得
28、到为 O(nigh)；也就是说在平均情况下快速排序仍然有较好的性能。问题 2中假设要排序的 n个元 素都具有相同值时，快速排序的运行时间复杂度，属于最坏情况，因为每次都划分为长度为 n一 1和 0的两个子数组。 问题 3中，由于随机化的快速排序的划分调用了 PARTITION操作，而传统划分每次以数组的最后一个元素作为枢轴元素。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。 4 【正确答案】 (1)bestXD=xj。 (2)jm。 (3)xi=j。 (4)CWbestW。 (5)cp=cpcij。 【试题解 析】 本题
29、考查回溯法的应用。 在题目的描述中告诉了回溯法的基本思想。其实回溯法主要有两个过程，一个是向前探索，只要在当前满足设定的判定条件时，才向前探索；而另外一个就是回溯，在两种情况下，需要回溯，其分别是当不满足设定条件时和求的一个解的时候。 下面具体分析本试题。根据题目给出的注释，已知第 (1)空所处的位置是得到问题的一个解时，根据题目描述，应该是将这个解记录下来，存放到 bestX数组当中，而求得的解是保存在 x数组当中的，因此这里需要循环将 x数组中的元素值赋给 bestX数组，因此第 (1)空答案为 bestXj=xj。 第 (2)空是 for循环中的循环判定条件，根据题目注释知道该循环的作用
30、是确定第 i个部件从第 j个供应商购买，那么在确定第 i个部件到底是从哪个供应商购买时，需要比较从各供应商购买的情况，因此循环的次数为供应商数，因此第 (2)空答案是 jm。结合这个循环体当中的语句和对回溯法的理解，可以发现循环下面的语句是要考虑将第 i个部件从供应商 j当中购买，也就是 j是当前解的一部分，因此需要将 j记录到解当中来，所以第 (3)空应该是 xi=j。 第 (4)空是 if语句中的一个条件，根据题 目注释，可以知道如果该 if语句表达式的计算结果为真，需要进行深度搜索，扩展当前结点，那么如果要继续向前探索，就需要满足设定的条件，也就是当前总重量要小于 bestW，而当前总价
31、格要小于等于 cc，因此第 (4)空的答案应该填 cwbestW。 根据题目注释，第 (5)空是在回溯下面的语句，根据回溯的原则可以知道，回溯 时，要将当前考虑的结点的重量和价格从总重量和总价格中减去，因此第 (5)的答案是 cp： cpciD。 5 【正确答案】 (1)j=0。 (2)bj=bj+si及其等价形式 。 (3)min=temp。 (4)bm=bm+si及其等价形式。 6 【正确答案】 (5)贪心。 (6)贪心。 (7)O(n2)。 (8)O(n2)。 7 【正确答案】 (9)5。 (10)4。 (11)否。 【试题解析】 本题考查最先适宜策略和最优适宜策略。这两种策略在题目的描
32、述中给出了清楚的解析，对于最先适宜策略，其关键是每次将一个货物装入第一个能容纳它的集装箱中；而对于最优适宜策略，则总是把货物装到能容纳它且目前剩余容量最小的集装箱。 下面具体分析程序。函数 firstfit是实现 最先适宜策略的，从程序不难看出，第 (1)空所在的 for循环，就是要将 n各货物装入到集装箱。根据算法的描述，是依次从第一个集装箱找，找到合适的就装入货物，依次没装入一个货物，都是依次从第一个集装箱找。结合后面的程序不难知道 j标识这当前是第几个集装箱。因此每装入一个货物后，要将 j清 0，标识从头再找，因此第 (1)空的答案是 j=0。而接下来的 while循环，从其条件表达式 C-bj0&temp2)。 第 3个问题，其实是这个题目中最简单的问题，也是算法的一个实际应用。对于这个实例，如果采用最先适宜策略，那么货物 4， 2， 3存放在第一个集装箱，而 7， 2存放在第二个集装箱， 5， 4存放在第三个集装箱， 3， 6存放在第四个集装箱，而 2存放在第五个集装箱。 如果采用最优适宜策略，那么货物 4， 2， 4)存放在第一个集装箱，而 7， 3存放在第二个集装箱， 5， 2， 3存放在第三个集装箱， 6， 2存放在第四个集装箱。 因为这两种方法都是采用的贪心策略，那么在一般情况下，是不能确保得到最优解的。
