1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 55及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 对文法 GS： Sa| |(T)； TT ， S|S：回答问题 1问题 3。1 对文法 G进行改写，然后对每个非终结符写出不带回溯的递归子程序。 2 经改写后的文法是否是 LL(1)的 ?指出它的预测分析表中 (1) (3)处的内容。 3 说明输入串 (a， a)#是否为 G的句子。 4 阅读下列说明、流程图和算法，将应填入 (n)处的字句写在答题纸的对应栏内。 【说明】 下面的流程图 15用 N-S盒图形式描述了数组 A中的元素被划分的过程。其划分方法是：以数组中的
2、第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Ai，并且数组中下标小于 i的元素的值均小于基准数，下标大于 i的元素的值均大于基准数。设数组 A的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组 (4， 2， 8， 3， 6)，以 4为基准数的划分过程如下：【算法说明】 将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数 血 p(int A， int low， int high)实现了上述流程图的划分过程并返回基准数在数组 A中的下标。递归函数 void sort(in
3、t A， iht L； int H)的功能是实现数组 A中元素的递增排序。 【算法】 void sort(int A， int1， int H) if (L H) k=p(A, L, R)： /p()返回基准数在数组 A中的下标 sort(4)； /小于基准数的元素排序 sort(5)； /大于基准数的元素排序 5 【程序说明】 定义一个多边形结构： struct polygon实现以下内容： (1)建立该结构的链表：create函数是创建链表，每输入一个结点的数据，就把该结点加入到链表当中，它返回创建的链表的头指针。 (2)显示链表的各个结点数据：结点数据包括：多边形顶点数、各顶点的纵横坐标
4、、当多边形顶点数为 0时，链表创建结束。 (3)编写一个函数 disp，删除链表中的所有结点。需要注意的是：要先释放结点数据内存，再删除结点，如果在释放结点数据内存单元之前删除结点，则无法找到结点数据内存单元的地址，也就无法释放数据的内存单元。 【程 序】 #include “iostxeam. h“ #include “iomanip. h“ stmct polygon int n; int *x; int *y; polygon *next; ; void Push(polygon* newNode = new polygon; newNode- next=(1); newNode- x
5、= new intn; newNode- y = new intn; newNode- n=(2); for(int i=0; i =(3); i+) cout “请输入多边形各顶点 x、 y坐标 , 坐标值之间用空格分隔 : “; cin newNode- xi newNode- yi; (4)= head; /在 head前不需要额外的 * head = newNode; polygon *create() polygon* head = NULL; polygon* tail; int n; cout “请输入多边形顶点的个数 (顶点个数为 0时结束 ): “; cin n; if(n=
6、O) return (5); Push(head,(6); tail = head; cout “请输入多边形顶点的个数 (顶点个数为 0时结束 ): “; cin n; while(n!=0) Push(tail- next,(7); / 在 tail- next增加结点 tail = tail- next; /advance tail to point to last node cout “请输入多边形顶点的个数 (顶点个数为 0时结束 ): “; cin n; remm head; void disp(polygon *head) inti, No=l; eout setw( 10) “
7、x“ setw(6) “y“ endl; while(head !=NULL) cout “第 “ No “结点 : “ endl; for(i=0;i =head- n-1;i+) cout setw(10) head- x i setw(6) head- yi endl; (8); he ad=(9); /Match while statement void del(polygon *head) polygon *p; while(head!=NIILL p=(10); head=head- next; delete p- x; delete p- y; delete p; /Match
8、while statement void main() polygon *head; head=create(); disp(head); del(head); 6 阅读以下算法说明和问题模型图，根据要求回答问题 1、问题 2。 说明 某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点 AP(Access Poin)。假设每个无线 AP覆盖范围的半径是 6米，因此必须使得每台笔记本电脑上的无线网卡到某个无线 AP的直线距离不超过 6米。为了简化问题，假设所有无线网卡在同一直线上，并且无线 AP沿该直线放置。该问题可以建模为如图 1-13所示，其中直线表示无 线网卡所在的直线，实心正方形表
9、示无线网卡。现采用贪心策略实现用尽可能少的无线 AP覆盖所有的无线网卡。 实现贪心算法的流程如图 1-14所示。其中， di(1iN)表示第 i张无线网卡到通道A端的距离， N表示无线网卡的总数，无线网卡的编号按照无线网卡到通道 A端的距离从小到大进行编号： sk表示第 k(k1)个无线 AP到通道 A端的距离。算法结束后 k的值为无线 AP的总数。6 请填补图 1-14流程图中 (1) (4)空缺处的内容。 7 该贪心算法的时间复杂度为 (5)。 二、选答题（共 3道大题， 每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 8
10、阅读以下说明和 JAVA 2代码，将应填入 (n)处的字句写在对应栏内。 说明 以下程序为类类型的变量应用实例，通过异常处理检验了类 CCircle的变量的合法性，即参数半径应为非负值。仔细阅读代码和相关注释，将程序补充完整。 JAVA代码 /定义自己的异常类 class CCircleException extends Exception / 定义类 CCircle class CCircle private double radius; public void setRadius ( double r ) (1) if ( r 0 ) (2) else (3) Public void sh
11、ow ( ) System. out. println ( “area=“+3.14*radius*radius ); public class ciusample public static void main ( String args ) CCircle cir=new CCircle( ); (4) cir. setRadius ( -2.0 ) (5) System. out. println ( e+“ throwed“ ) ; cir. show( ) ; 9 阅读以下说明和 C+码，将应填入 (n)处的字名写在的对应栏内。 说明 设计一个普通函数 distance (Point
12、 public: Point(int i, int j) (1) int getx( ) return x; int gety( ) return y; void disp( ) (2) ; float distance( Point (3) return d; void main( ) (4) p1. disp ( ); cout “与 ”; p2. diap( ); cout “之间距离 =” distance (p1,p2) end1; 10 阅读以下函数说明、图和 C程序代码，将 C程序段中 (1) (6)空缺处的语句填写完整。 说明 散列文件的存储单位称为桶 (BUCKET)。假如一
13、个桶能存放 m个记录，当桶中已有 m个同义词 (散列函数值相同 )的记录时，存放第 m+1个同义词会发生 “溢出 ”。此时需要将第 m+1个同义词存放到另一个称为 “溢 出桶 ”的桶中。相对地，称存放前 m个同义词的桶为 “基桶 ”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。 例如，设散列函数为 Hash(Key)=Key mod7，记录的关键字序列为 15， 14， 21， 87， 96， 293， 35， 24， 149， 19， 63， 16， 103， 77， 5，153， 145， 356， 51， 68
14、， 705， 453，建立的散列文件内容如图 2-27所示。 为简化起见，散列文件的存储单位以内存单元表示。 函数 InsertToHashTable(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值 0；否则返回值 -1。 采用的散列函数为 Hash(NewElemKey)=NewElemKey%P，其中 P设定基桶的数目。 函数中使用的预定义符号如下。 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 55答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 改写文法为： (0)Sd (1)S (2)S(T)
15、(3)TSN (4)N,SN (5)N 非终结符 FIRST集 FOLLOW集 S a， ， ( #, T a， ， ( N , 对左部为 N的产生式可知： FIRST( ， SN)； ， FIRST() ： FOLLOW(N)= 2 【正确答案】 文法是 LL(1)的。 (1)SN (2)(T) (3)C 3 【正确答案】 输入串 (a， a)#是文法的句子。 【试题解析】 对于文法 Sd|(T) TT,S|S 由于 SELECT(N ，SN)SELECT(N)= ， = ，所以文法是。 LL(1)的。 也可由预测分析表中无多重入口判定文法是 LL(1)的。 (3)对输入串 (a,a)#的分
16、析过程为： 栈 当前输入符 剩余输入符 所用产生式 (STACK) (CUR CHAR) (1NOUT STRING) (OPERATION) #S ( a,a)#. #)T( ( a,a)#. S(T) #)T a ,a)#. . #)NS a ,a)#. TSN #)Na a ,a) Sa #)N ， a)#. . #)NS， ， a)#. N,SN #)NS a )#. . #)Na a )#. Sa #)N ) #. . #) ) #. N # # 可见输入串 (a， a)#是文法的句子。 4 【正确答案】 (1)j- (2) i+ (3)Aipivot 或 jpivot (4)A，
17、L， k-1或 A， L， k (5)A， k+I， H或 A， k， H 【试题解析】 题目考查快速排序算法。 快速排序采用了一种分治的策略，通常称为分治法，其基本思想足：将原问题分解为若干个规模更小，但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程为：第一步，在待排序的 n个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成 2组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大十该排序码，并把该记录排在这 2组中间，这个过程称为一次划分。第二步，采用同样的方法，对划分出来的 2组元素分别进行快速排序，直到所
18、有记录都排到相应的位置为止。 在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量pivot 中，如图中的第 步所示。这样基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描。如图中的第 步所示，找到一个比基准元素小的元素时为止，将其前移，如图中的第 步所示。然后再从前向后扫描，如图中的第 步所示，找到一个比基准元素大的元素时为止，将其后移，如图中的第 步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置为止，如图中的第 步所示。 由题目中给出的流程图可知，以第一个元素作为基 准数，并将 Alow备份至pivot， i用于从前向后扫描的位置指示器
19、，其初值为 low， j用于从后往前扫描的位置指示器，其初值为 high。当 i j时进行循环： 1从后向前扫描数组 A，在 i j的情况下，如果被扫描的元素 A刚 pivot，就继续向前扫描 (j-)；如果被扫描的元素 Aj pivot就停止扫描，并将此元素的值赋给目前空闲着的 Ai。 2这时，再从前向后扫描，在 i j的情况下，如果被扫描的元素 A刚 pivot，就继续向后扫描 (i+)；如果被扫描的元素 Aj pivot就停止扫 描，并将此元素的值赋给目前空闲着的 Aj。 3这时又接第 (1)步，直到 i j时退出循环。退出循环时，将 pivot赋给当前的Ai (Aipivot) 。 递
20、归函数的目的是执行一系列调用，直到到达某一点时递归终止。为了保证递归函数正常执行，应该遵守下面的规则： 1每当一个递归函数被调用时，程序首先应该检查基本的条件是否满足，例如，某个参数的值等于 0，如果是这种情形，函数应停止递归。 2每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得 “更简单 ”，即这些参 数应该逐渐靠近上述基本条件。例如，一个正整数在每次递归调用时会逐渐变小，以至最终其值到达 0。 本题中，递归函数 sort(iht A， int L int H)有 3个参数，分别表示数组 A及其下界和上界。根据流程图可知，这里的 L相当于流程图中的 i，这里的 H相当于流
21、程图中的 j。因为 p()返回基准数所在数组 A中的下标，也就是流程图中最后的“Aipivot” 中的 i。根据快速排序算法，在第一趟排序后找出了基准数所在数组A中的下标，然后以该基准数为界 基准数在数组中的下标为 k)，把数组 A分成2组，分别是 AL， ， k-1和 Ak+l， ， H，最后对这 2组中的元素再使用同样的方法进行快速排序。 5 【正确答案】 (1)NULL (2) n (3)n-1 (4)newNode- next (5)head (6) n (7) h (8)NO+ (9)head- next (10)head 【试题解析】 如果掌握了链表的创建、遍历和删除的方法，解决本
22、题应该并不困难。要显示链表各结点的数据，就是要把各结点找到，然后把该结点的的每一个x、 y坐标打印出来。不过，与普通的链表也有不同的地方：就是该链 表的结点数据是指针。要在链表结点中存入数据，必须先动态分配存储数据的内存单元；要删除链表中的各个结点，必须先释放结点数据的内存单元，否则会造成内存泄露。 6 【正确答案】 本试题的题干说明中已将无线网卡分布问题建模 (如图 1-13所示 )。其中，直线表示无线网卡所在的直线，实心正方形表示无线网卡。而要求解的问题是要求如何在该直线上布局无线 AP，使其能覆盖所有的无线网卡，并且所用无线AP的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题
23、。 分析该问题，发现其具有最优子结构，并且具有贪心选择性质，故该问 题可以用贪心算法来求解。贪心算法思想是：问题的规模为 N，从第 1个无线网卡 (最左端 )开始布局无线 AP，把第 1个无线 AP放置在该无线网卡右方的 6米处，此时该无线 AP会覆盖从第 1个无线网卡到该无线网卡右方直线长度为 12米的所有无线网卡，假设覆盖了 N1个无线网卡。此时问题规模变成了 N-N1，接着把第 1个无线 AP覆盖的无线网卡去掉，再从 N-N1中选择第 1个 (最左端 )无线网卡开始布局无线 AP，将第 2个无线 AP放置在该无线网卡右方的 6米处。依此布局，直到覆盖所有的无线网卡。 图 1-22是问题解
24、的模型。其中，直线表示无线网 卡所在的直线，实心正方形表示无线网卡，实心圆形表示无线 AP，虚线圆以对应无线 AP为圆心，直径为无线 AP的覆盖范围，即对应无线 AP的覆盖范围 (12米 )。 实现贪心算法的流程见题干的图 1-14。由于 “算法结束后 k的值为无线 AP的总数 ”，因此在算法开始处需要对变量 k赋初值，即 (1)空缺处所填写的内容是 “k=0”。 该贪心算法中， N表示无线网卡的总数，且无线网卡的编号按照无线网卡到通道 A端的距离从小到大进行编号， di(1iN)表示第 i个无线网卡到通道 A端的距离。当判断第 i个无线网卡未超过无线网卡总数 N，而 求解下一个无线网卡 (即
25、第 i+1个无线网卡，或第 j个无线网卡 )所归属的无线 AP时，也需要判断第 j个无线网卡是否超过无线网卡总数 N，以及第 j个无线网卡与第 i个无线网卡之间的距离是否超过 12米，因此 (2)空缺处所在的判断条件是 “j =N dj-di =12”，即该空缺处所填写的内容是 “j =N”或其等价形式。 若第 j个无线网卡未超过无线网卡总数 N，且第 j个无线网卡与第 i个无线网卡之间的距离未超过 12米，则可以求解再下一个无线网卡 (即第 i+2个无线网卡，或第 j+1个无线网卡 )所归属的无线 AP。反之，则需要 记录无线 AP的总数 k，即 (3)空缺处所填写的内容是 “k=k+1”或
26、其等价形式；以及记录第 k(k1)个无线 AP到通道 A端的距离，即 (4)空缺处所填写的内容是 “di+6”或其等价形式。 当求解完第 k个无线AP(覆盖了 N1个无线网卡 )的布局后，需要把第 k个无线 AP覆盖的无线网卡去掉，再从 N-N1中选择第 1个 (最左端 )无线网卡开始布局第 k+1个无线 AP。依此不断求解，直到覆盖所有的无线网卡。 7 【正确答案】 虽然该贪心算法中包含两个循环，但实际上只是遍历所有无线网卡一次，因此算法复杂度是 O(N)。 二 、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答
27、有效。 8 【正确答案】 (1)throws CCircleException (2)throw new CCircleException()； /抛出异常 (3)radius=r； (4)try (5)catch(CCircleException e) /捕捉由 setRadius()抛出的异常 【试题解析】 本题主要考查 JAVA语言中 Class类型的变量应用。本段代码 中对于类 Ccircle的半径变量进行合法性检验，如果圆 Ccircle的半径为负值，则抛出异常处理。 9 【正确答案】 x=i; y=j; clout “(“ d = sqrt(p1. getx( ) - p2. ge
28、tx( ) ) *( p1. getx( ) - p2. getx( ) ) +(p1. gety( ) - p2. gety( ) ) *( p1. gety () - p2. gety( ) ); Point p1(2,2) ,p2(5,5); 10 【正确答案】 这是一道要求读者掌握如何在散列文件中插入一个新的数据元素的编程题。本题的解答思路如下。 在散列文件中插入一个新的数据元素的基本思路是，首先将要插入的元素代入到散列函数中，从而计算出该元素的散列地址。然后按照散列地址，在基桶中查找空闲单元，若找到，则将元素插入，若基桶已满，则在溢出桶中查找空闲单元。若溢出桶中也查找不到，则申请新的
29、溢出桶，然后将元素存入。 在散列文件中查找一个元素的基本思路是，查找指定元素记录时，首先在基桶中查找，若找到，则成功返回，否则沿指针到溢出桶中进行查找。 在本试 题中，将元素存储在预先设定的基桶或根据需要申请的溢出桶中，只要基桶中有空闲单元，就将新元素 NewElemkey插入在基桶中，若基桶中无空闲单元，则看是否存在溢出桶，若存在，则在溢出桶中查找空闲单元，若不存在溢出桶或溢出桶中无空闲单元，则申请一个溢出桶并存入新元素。 在基桶查找空闲单元时，使用的桶号为 Index，由此可知 (1)空缺处所填写的内容是 “Index=NewElemKey%P”，或“Index=Hash(NewElemK
30、ey)”等其他等价形式。 一旦在基桶中找到空闲单元，即“Bucket1ndex.keyDatai=NULLKEY”(0i ITEMS)，则可将元素 NewElemkey放入 BucketIndex.keyDatai，至此元素已经插入散列桶中，函数可返回，因此 (2)空缺处所填写的内容是 “i ITEMS”。反之， 若在基桶中没有找到空闲单元，则需查找溢出桶。 “t=BucketIndex.Link”，指针 t首先指向桶号 Index的第一个溢出桶。以下的代码完成在溢出桶中查找空闲单元的功能。 由于每个溢出桶都可以存储 ITEMS个元素，因此在溢出桶中查找空闲单元与在基桶中的查找 过程相同，代码
31、如下。 若在指针 t指向的溢出桶中找到空闲单元则插入元素，否则，由 “t=t- Link”得到下一个溢出桶的指针，因此 “k ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条件。显然，在桶号 Index的基桶和其所有溢出桶都已满的情况下， t的值为空指针。此时才需要申请新的溢出桶并建立链接关系，因此在上面查找溢出桶中空闲单元时，进行指针 t的后移 “t=t- Link前应先用 front记录 t的值，以便于后面建立链接关系。所以 (3)空缺处应给 front置初值，即所填写的内容是 “front=BucketIndex”，或 “front=Bucket+Index”等其他等价形式。 (4)空缺处用于判断该溢出桶是否已满，即所填写的内容是 “k=ITEMS(或 k =ITEMS)”。如果该溢出桶已满，则继续查找下一个溢出桶，直到查找到空闲单元为止。 若所有溢出桶都不存在空闲单元 (即 t=NULL)，则申请新的溢出桶，并将新的溢出桶的首地址保存在原有的最后一个溢出桶的 Link域中 (即 front- Link=s)。因此 (5)空缺处所填写的内容是 “t=NULL”， (6)空缺处用于建立新申请溢出桶的链接关系 “front-Link=s”。
