[计算机类试卷]软件水平考试(中级)软件设计师下午(应用技术)试题模拟试卷55及答案与解析.doc
《[计算机类试卷]软件水平考试(中级)软件设计师下午(应用技术)试题模拟试卷55及答案与解析.doc》由会员分享,可在线阅读,更多相关《[计算机类试卷]软件水平考试(中级)软件设计师下午(应用技术)试题模拟试卷55及答案与解析.doc(17页珍藏版)》请在麦多课文档分享上搜索。
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)#的分
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 试卷 软件 水平 考试 中级 设计师 下午 应用技术 试题 模拟 55 答案 解析 DOC
