2016年下半年 软考初级程序员 应用技术

1、全国计算机技术与软件专业技术资格（水平）考试2016年下半年 程序员 下午试卷（考试时间 14:0016:30 共 150 分钟）请按下述要求正确填写答题纸1.在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。2.在答题纸的指定位置填写准考证号、出生年月日和姓名。3.答题纸上除填写上述内容外只能写解答。4.本试卷共6道题，试题一至试题四是必答题，试题五至试题六选答 1 道。每题 15 分，满分 75 分。5.解答时字迹务必清楚，字迹不清时，将不评分。6.仿照下面例题，将解答写在答题纸的对应栏内。例题2016 年下半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。因为正确的解答是“11 月 4 日”，故在答题纸的对应栏内写上“11”和“4”（参看下表）。例题解答栏（1）11（2）4试题一（共15分）阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。【说明】设有整数数组A1：N（N1），其元素有正有负。下面的流程图在该数组中寻找连续排列的若干个元素，使其和达到最大值，并输出其起始下标K、元素个数L以及最大的和值M。例如，若数组元素

2、依次为3，-6，2，4，-2，3，-1，则输出K=3，L=4,M=7。该流程图中考察了A1：N中所有从下标i到下标j（ji）的各元素之和S，并动态地记录其最大值M。 【流程图】注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值试题二（共15分）阅读以下代码，回答问题：1至问题3 ，将解答填入答题纸的对应栏内。【代码1】#includevoid swap(int x, int y) int tmp =x; x= y; y= tmp;int maim() int a= 3, b= 7; printf(a1= %d b1=%dn,a,b);Swap( a, b);Printf(a2 = %d b2=%dn”,a,b)；return 0;【代码2】#include#define SPACE /空格字符Int main()char str128 =”Nothing is impossible! “;int i,num =0,wordMark=0;for(i=0;stri;i+)If(stri=SPACE)WordMark=0;elseIf(wordM

3、ark=0)wordMark=1;Mun+;Printf(“%d/n”,num)retun 0;【代码3】#include#define SPACE “/空格字符int countStrs(char *);int main()char str128 = Nothing is impossible! ;Printf(%d/n,（1）(str)retum 0;int countStrs(char *p)int num=0, wordMark= 0;for(;（2）；p+) If(（3）=SPACE) wordMark= 0;elseif( !wordMark ) wordMark = 1;+numreturn（4） 【问题1】（4分）写出代码1运行后的输出结果。 【问题2】（3分）写出代码2运行后的输出结果。 【问题3】（8分）代码3的功能与代码2完全相同，请补充3中的空缺，将解答写入答题纸的对应栏内。试题三（共15分）阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素（即将元素从小到大排序后，取第k个元

4、素）。对一个整数序列进行快速排序的方法是：在待排序的整数序列中取第一个数作为基准值，然后根据基准值进行划分，从而将待排序的序列划分为不大于基准值者（称为左子序列）和大于基准值者（称为右子序列），然后再对左子序列和右子序列分别进行快速排序，最终得到非递减的有序序列。例如，整数序列“19, 12, 30, 11,7,53, 78, 25的第3小元素为12。整数序列“19, 12,7,30, 11, 11,7，53. 78, 25, 7的第3小元素为7。函数partition（int a, int low,int high）以alow的值为基准，对alow、alow+l、ahigh进行划分，最后将该基准值放入ai (lowihigh)，并使得alow、alow+l、，、Ai-1都小于或等于ai，而ai+l、ai+2、ahigh都大于ai。函教findkthElem(int a,int startIdx,int endIdx,inr k)在astartIdx、astartIdx+1、.、aendIdx中找出第k小的元素。 【代码】#include #include Int partition（

5、int a ，int low, int high）/对 alow.high进行划分，使得alow.i中的元素都不大于ai+1.high中的元素。int pivot=alow； /pivot表示基准元素Int i=low,j=high;while(（1）)While(ipivot)-j;ai=ajWhile(ipivot)+i;aj=ai（2）； /基准元素定位return i；Int findkthElem（int a，int startIdx，int endIdx, int k）/整数序列存储在astartldx.endldx中，查找并返回第k小的元素。if (startldx0 |endIdxendIdx | kendIdx |k-1startIdx)Return-1; /参数错误if(startIdxendldx)int loc=partition(a, startIdx, endldx)； 进行划分，确定基准元素的位置if (loc=k-1) 找到第k小的元素 return （3） ；if(k-l loc) /继续在基准元素之前查找return findkthElem(a， （

6、4） ，k）；else 继续在基准元素之后查找return findkthElem(a， （5） ，k);return astartIdx；int main()int i, k;int n;int a = 19, 12, 7, 30, 11, 11, 7, 53, 78, 25, 7;n= sizeof(a)sizeof(int) /计算序列中的元素个数for (k=1;kn+1；k+)for(i=0;in;i+)printf(“%d/t”,ai);printf(“n”);printf(“elem %d=%dn,k,findkthElem(a,0,n-1,k);/输出序列中第k小的元素return 0；试题四阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是：访问顶点v；访问V的所有未被访问的邻接顶点W1 ,W2 ,.,Wk；依次从这些邻接顶点W1 ,W2 ,.,Wk出发，访问其所有未被访问的邻接顶点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。显然，上述过程

7、可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u，可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。例如，对于图4-1所示的有向图G，从a出发进行广度优先遍历，访问顶点的一种顺序为a、b、c、e、f、d。设图G采用数组表示法（即用邻接矩阵arcs存储），元素arcsij定义如下：图4-1的邻接矩阵如图4-2所示，顶点af对应的编号依次为05.因此，访问顶点a的邻接顶点的顺序为b，c，e。函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。相关的符号和类型定义如下：#define MaxN：50 *图中最多顶点数*typedef int AdjMatrixMaxNMaxN；typedef structint vexnum，edgenum; *图中实际顶点数和边（弧）数*AdjMatrix arcs； *邻接矩阵*)Graph；typedef int QElemType；enum ERROR=0;OK=l;代码中用到的队列运算的函数原型如表4-1所述，队列类型名为QUEUE。表4-1 实现队列运算的函数原型及说明 【代码】int B

8、FSTraverse(Graph G)/图G进行广度优先遍历，图采用邻接矩阵存储unsigned char*visited； /visited用于存储图G中各顶点的访问标志，0表示未访问int v，w；u；QUEUEQ Q;申请存储顶点访问标志的空间，成功时将所申请空间初始化为0visited=(char*)calloc(G.vexnum, sizeof(char);If(（1）)retum ERROR;（2） ； /初始化Q为空队列for( v=0; vG.vexnum; v+)if(!visitedv) /从顶点v出发进行广度优先遍历printf(%d”，v)； /访问顶点v并将其加入队列visitedv=l；（3） ；while(！isEmpty(Q)（4） ； /出队列并用u表示出队的元素for(v=0;vG.vexnum; w+)if（G.arcsuw!=0& （5） ) /w是u的邻接顶点且未访问过printf(%d”，w)； /访问顶点wvisitedw=1；EnQueue(&Q, w);free(visited);return OK;)/BFSTraverse试题五阅读以下说明和Java程序，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】以下Java代码实现一个简单的聊天室系统（ChatRoomSystem），多个用户(User)可以向聊天室( ChatRoom)发送消息，聊天室将消息展示给所有用户。类图如图5-1所示。 【Java代码】class ChatRoom

《2016年下半年 软考初级程序员 应用技术》由会员想****。分享，可在线阅读，更多相关《2016年下半年 软考初级程序员 应用技术》请在金锄头文库上搜索。