1、2016年上半年软件水平考试（初级）程序员下午（应用技术）真题试卷及答案与解析 1 阅读以下说明和流程图，填补流程图和问题中的空缺 (1) (5)，将解答填入答题纸的对应栏内。【说明】设整型数组 A1： N每个元素的值都是 l到 N之间的正整数。一般来说，其中会有一些元素的值是重复的，也有些数未出现在数组中。下面流程图的功能是查缺查重，即找出 A1： N中所有缺失的或重复的整数，并计算其出现的次数 (出现次数为 0时表示缺 )。流程图中采用的算法思想是将数组 A的下标与值看作是整数集 1： N上的一个映射，用数组 C1： N依次记录各整数 k出现的次数 ck，并输出所有缺失的或重复的数及其出现
2、的次数。【流程图】【问题】如果数组 A1： 5的元素分别为 3， 2， 5， 5， 1，则算法流程结束后输出结果为： (5)。输出格式为：缺失或重复的数，次数 (0表示缺少 )。 2 阅读以下说明和 C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 说明 1 递归函数 is elem(char ch， char*set)的功能是判断 ch中的字符是否在 set表示的字符集合中，若是，则返回 1，否则返回 0。 C代码 1 int iselem(char ch， char*set) if(*set= 0) return 0； else if ( (1) ) return 1； else r
3、eturn iselem( (2) )； 【说明 2】 函数 char*combine(char*setA， char*setB)的功能是将字符集合 A(元素互异，由setA表示 )和字符集合 B(元素互异，由 setB表示 )合并，并返回合并后的字符集合。 【 C代码 2】 char* combj ne(char*setA， char*setB) int i， lenA， lenB， lenC； lenA=strlen(setA)； lenB=strlen(setB)； char*setC= (char*)malloc(1enA+lenB+1)； if (!setC) return NULL
4、 ； strncpy(setc， setA， lenA)； 将 setA的前 lenA个字符复制后存 入 setc lenc= (3)； for (i=0； i typedef struct int year， month， day； *年，月，日 * DATE； int isLeapYear(int y) *判断 y表示的年份是否为闰年，是则返回 1，否则返回0* return(y 4=0 y 100 1=0)(y 400=0)； int isLegal(DATE date) *判断 date表示的日期是否合法，是则返回 1，否则返回 0* int y=date year， m=date m
5、onth， d=date day； if(y201 0 m12 d31) return 0； if(m=4 m=6 m=9m=i 1)& (1) ) return 0； if(m=2) if(isLeapYear(y) (2) ) return 1； eise if (d2 8) return 0； return 1； int Lteq(DATE dl， DATE d2) *比较日期 d1和 d2，若 dl在 d2之前或相同则返回 1，否则返回 0* long t1， t2； t1=d1 year*10000+d1 month*100+d1 day； t2=d2 year*10000+d2 m
6、onth*100+d2 day； if( (3) ) return 1； else return 0； int main() DATE date， start=1 98 5， 1， 1， end=2 01 0， 12， 31)； FILE*fp； fp=fopen(“dtxt”， “r”)； if( (4) ) return一 1； while(!feof(fp) if(fscanf(fp， “ d d d”， &date year， &date month， &date day)!=3) break； if( (5) ) *判断是否为非法日期 * continue； if( (6) ) *调
7、用 Lteq判断是否在起至日期之间 * printf(“ d d d n”， date year， date month， date day)； fclose(fp)； return 0； 4 阅读以下说明和 C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。 (1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值。 (2)若它的右子树非空，则右子树上所有结点的 值均大于根结点的值。 (3)左、右子树本身就是两棵二叉查找树。二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，具
8、体的过程是：每读入一个元素，建立一个新结点，若二叉查找树非空，则将新结点的值与根结点的值相比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉查找树为空，则新结点作为二叉查找树的根结点。根据关键码序列 46， 25， 54， 1 3， 29， 91构造一个二叉查找树的过程如图 41所示。设二叉查找树采用二叉链表存储，结点类型定义如下： typedef int KeyType； typedef struct BSTNode KeyType key； struct BSTNode*left， *right ； BSTNode，*BSTree； 图 4一 1(g)所示二叉查找树的二
9、叉链表表示如图 4-2所示。函数 int InsertBST(BSTree*rootptr,KeyType kword)功能是将关键码 kword插入到由 rootptr指示出根结点的二叉查找树中。若插入成功，函数返回 1，否则返回 0。【 C代码】 int InsertBST(BSTree*rootptr， KeyType kword) *在二叉查找树中插入一个键值为 kword的结点，若插入成功返回 1，否则返回 0； *rootptr为二叉查找树根结点的指针 * BSTree P， father； (1)； *将 father初始化为空指针 * P=*rootptr； *P指向二叉查找树
10、的根结点 * while(p (2) ) *在二叉查找树中查找键值 kword的结点 * father=p； if ( kwordkey) p=p一 left； else p=p一 right； if( (3) )return 0； *二叉查找树中已包含键值 kword，插入失败： p=(BSTree)malloc (4) )； *创建新结点用来保存键值 kword* if(!p)return 0 ； *创建新结点失败 * p一 key= kword； p一 left=NULL； p一 right： NULL； if (!father ) (5) =p； *二叉查找树为空树时新结点作为树根插入
11、 * else if ( kwordkey) (6) ； *作为左孩子结点插入 * else (7) ； *作为右孩子 结点插入 * return l； *InsertBST* 5 阅读下列说明和 C+代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】以下 C+代码实现两类交通工具 (Flight和 Train)的简单订票处理，类Vehicle、 Flight、 Train之间的关系如图 61所示。 【 C+代码】 #include#includeusing namespace std； clasS Vehiclepublic：virtualVehicle()void book(in
12、t n) 订 n张票 if(getTicket()=n) decreaseTicket(n)； else coutv； V pushback(new Flight()； V push back(new Train()； V push back(new Flight()； V push_back(new Train()； V push_back(new Train()； cout： iterator it=V begin()； it !=V end()； it+) if(NULL!=*it) delete*it； *it=NULL； V clear()； return 0； 运行该程序时输出如下
13、： 欢迎订票 ! 剩余票数： 215 剩余票数： 2014 剩余票数： (6) 剩余票数： (7) 剩余票数： (8) 6 阅读以下说明和 Java代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】以下 Java代码实现两类交通工具 (Flight和 Train)的简单订票处理，类Vehicle、 Flight、 Train之间的关系如图 5-1所示。 Java代码 import Java.util ArrayList； import Java.util List； abstract clasS Vehicle void book(int n) 订 n张票 if(getTicket(
14、)=n) decreaseTicket(n)； else System out println(“余票不足 !”)； abstract int getTicket()； abstract void decreaseTicket(int n)； ； class Flight (1) private (2)tickets=216； Flight的票数 int getTicket() return tiCkets ； void decreaseTicket(int n) tickets=ticketsn； class Train (3) private(4)tickets=201 6； Train的
15、票数 int getTicket() return tickets； void decreaseTicket(int n) tickets=ticketsn； public class Test public static void main(Stringargs)2016年上半年软件水平考试（初级）程序员下午（应用技术）真题试卷答案与解析 1 【正确答案】 (1)Ai (2)Ck+1 (3)1 (4)k， Ck (5)4， 0 5， 2 【试题解析】 本题考查程序设计算法即流程图的设计。 先以问题中的简例来理解算法过程。 已知 A1： 5=3， 2， 5， 5， 1。初始时计数数组 c1：
16、5=0， 0， 0， 0， 0。 再逐个处 理数组 A的各个元素 (根据 Ai的值在 cAi中计数加 1)： A1=3，计数 c3=1； A2： 2，计数 c2=1； A3=5，计数 c5=1； A4=5，计数 c5=2； A5=1，计数 c1=1。最后，计算得到 c1： 5=1， 1， 1， 0， 2)，即表明 A1： 5中数 4缺失，数 5有 2，其他数都只有 1个。 再看流程图。左面先对数组 C初始化 (赋值都是 0)。再对 Ai各个元素逐个进行处理。将 Ai送 k，再对 ck计数加 1。因此， (1)处应填 Ai， (2)处 应填ck+1ck 。 流程图右面需要输出计算结果。对于 k的
17、循环，当 ck=1时 (非缺非重 )不需要输出；否则，应按要求的格式输出：缺或重的数，以及出现的次数。为此， (3)处应填 1(与 1比较 )， (4)处应填 k， ck。 再看简例的输出，先输出 4， 0(数 4缺失 )；再输出 5， 2(数 5有 2个 )。 2 【正确答案】 (1)set0=ch 或 *set=ch或等价形式 (2)ch， set+1或 ch， +set或等价形式 (3)lenA或等价形式 (4)!iselem(setBi， setA) 或等价形式 (5)setC1enC 或 *(setC+lenC)或等价形式 【试题解析】 本题考查 C程序设计的基本结构和运算逻辑。 函
18、数 is_elem(char ch， char*set)的功能是判断给定字符是否在一个字符串中，其运算逻辑是：若 ch所存的字符等于字符数组 set的第一个字符，则结束；否则再与set中的第二个字符比较，依此类推，直到串尾。因此空 (1)处应填入 “set【 0】 =ch”或其等价表示。题目要求该函数以递归方式处理，并在空 (2)处填入递归调用时的实参。显然，根据函数 is elem的首部信息，递归调用时第一个参数仍然为 “ch”，第二个参数是需给出 set中字符串的下一个字符的地址 (第一次递归时为字符串第二个字符的地址，第二次递归时实际为字符串第三个字符的地址，由于传进来时与 ch进行比较
19、的字符都是 *set，那么下一个字符就都表示为 set +1)，即为&set1，或者为 set+1，所以空 (2)处应填入参数 “ch， set+1”或其等价表示。 函数 combine(char*setA， char*setB)的功能是将字符集合 A和字符集合 B合并，并返回合并后的字符集合，处理思路是：现将 A集合的元素全部复制给集合C(stmcpy(setC， setA， lenA)，然后按顺序读取集合 B中的字符，判断其是否出现在 A中。如果来自集合 B的字符已经在 A中，则忽略该字符，否则，将其加入集合 C。 变量 lenC表示集合 C的元素个数，其初始值应等于 lenA，因此空 (
20、3)应填入“lenA”。 根据注释，空 (4)应填入 “!is_elem(setBi， setA)”，判断来自集合 B的元素 setBi是否在集合 setA中。空 (5)处的代码作用是设置字符数组 setC的尾部字符 “ 0”，由于 lenC的值跟踪了该集合中元素数目的变化，其最后的值正好表示了 setC的元素个数，所以该空应填入 “setC1enC”或其等价表示。 3 【正确答案】 (1)d30 或 d=31或等价形式 (2)d2010 m12 d31)的日期先排除，接下来考虑小月份，即 4、 6、 9、 11这四个月份不存在 3 1日，所在这几个 月中若出现 3 1日或更大值，就是非法日期
21、，即空 (1)处应填入 “d30”或其等价形式。当月份为 2时，需要考虑是否闰年，闰年的 2月是 29天、平年是 28天，因此空 (2)处应填入 “dkey!=kword 或等价形式 (3)P 或 p!=0或 p!=NULL (4)sizeof(BSTNode)或等价形式 (5)*rootptr (6)father-left=P (7)father-right=P 【试题解析】 本题考查 C程序设计的基本结构和数据结构的实现。 根据二叉查找树的定义，其左子树中结点的关键码均小于树根结点的关键码，其右子树中结点的关键码均大于根结点的关键码，因此，将一个新关键码插入二叉查找树时，若等于树根或某结点
22、的关键码，则不再插入，若小于树根，则将其插入到左子树中，否则将其插入到右子树中。 根据注释，空 (1)处需将 father设置为空指针，应填入 “father=NULL”或其等价形式。 空 (2)所在语句用于查找新关键码的插入位置， p指向当前结点。查找结果为两种：若找到，则 p指向的结点的关键码等于新关键码，若没有找到，则 p得到空指针值。因此空 (2)处应填入 “p-key!=kword”或其等价形式，在得到结果前使得查找过程可以继续，并且用 father记录新插入结点的父结点指针。 空 (3)处应填入 “p”或其等价形式，表明查找到了与 kword相同的结点，无须再插入该关键码。 空 (
23、4)处应填入 “sizeof(BSTNode)”，在申请 新结点空间时提供结点所需的字节数。 空 (5)处应填入 “*rootptr”，使得新结点作为树根结点时，树根结点的指针作为二叉链表的标识能得到更新。 根据注释，空 (6)应填入 “father-left=P”、空 (7)应填入 “father-right=P”。 5 【正确答案】 (1)public Vehicle (2)static int (3)public Vehicle (4)static int (5)(*vi) book (6)212 (7)2010 (8)2005 【试题解析】 本题考查 C+语言程序设计，涉及类、继承、对
24、象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。 先考查题目说明，实现两类交通工具 (Flight和 Train)的简单订票处理，根据说明进行设计，题目说明中图 6 1的类图给出了类 Vehicle、 Flight、 Train之间的关系。涉及到交通工具类 Vehicle、其子类 Flight和 Train两类具体交通工具。简单订票就针对这两类具体的交通工具，每次订票根据所选订票的交通工具和所需订票数进行操作。 不论哪类交通工 具，订票操作 book在余票满足条件的情况下将余票减少所订票数，不足时则给出 “余票不足 ”提示，所以在父类 Vehic
25、le中定义并实现 void book(int n)函数。每类具体交通工具获取自身类型的票数 (getTicket)，订票也只减少自身类型票数 (decreaseTicket(int n)等类以及相关操作。因此，在父类 Vehicle中，分别定义针对上述两个操作的虚函数： Virtual int getTicket() = 0 ； Virtual void decreaseTicket(int)=0 ； 在 C+中， virtual作为虚函数的关键字， “=0； ”表示为纯虚函数，包含虚函数的类本身也是虚拟类，而且，虚函数必须由其子类实现。从题目说明给出的类图(图 61)也可以看出， Vehic
26、le的两种具体类 (子类 )为 Flight和 Train。 C+中，子类继承父类用 “： ”，即： class子类名：继承的方式父类名 考查主控函数 main()，需要将 Flight和 Train类型的对象加入模板类型为Vehicle的向量中，因此， Flight和 Train的实现分别为： class Flight： public Vehicle clas s Train： public Vehicle Flight类和 Train类中必须实现 getTicket和 decreaseTicket函数才能进行获取票数和减少余票的操作。因此，这两个类中都实现了 getTicket和 decr
27、easeTicket函数。 Flight和 Train两类具体交通工具的票数需要分别记录，并且每次订票操作需要对总数进行操作，所以需要定义为类变量，同一类的所有对象共享此变量。在C+中，定义类变量的方式是将变量定义为静态变量，即用 static关键字修饰。同时分析对票数的使用， getTicket和 decreaseTicket两个函数的返回值和参数都用类型 int，因此，票数 tickets也定义为 int。综合上述两个方面知， tickets定义为static int类型。而且，在 C+中， staticint类型的变量必须在类外进行初始化，即： int Train： tickets=20
28、16； 初始化 Train的票数为 2016 int Flight： tickets=216； 初始化 Flight的票数为 216 主函数： main()中实现了订票系统的简要控制逻辑，其中创建欲进行订票的对象、持有对象的集合、订票逻辑等。定义 vector向量类型变量 v，此处采用模板类集合，在 v中，可以持有 Vehicle类型及其子类型的对象指针。vector向量中的函数 push back(E e)用于给向量的最末端添加元素，采用向量元素下标 index获取向量中索引位置为 index的元素，即对象指针， size()用以获取向量的元素个数。主控逻辑中创建 Flight和 Train
29、两个具体类的一些订票请求对象加入 v中，因为 Flight和 Train均为 Vehicle的子类型，而且是具体类，所以满足加入元素的要求，故采用 new Flight()和 new Train()来创建相应的对象加入 v中；然后通过 for循环使每个订票请求对象进行订票，并输出剩余票数： for(int i=0； i链表集合类型变量 v，此处采用泛型集合，在 v中，可以持有 Vehicle类型及其子类型的对象。 ArrayAst链表集合中的方法 add(E e)用于给链表集合的最末端添加元素， get(intindex)用以获取链表集合中索引位置为index的元素， size()用以获取链表
30、集合的元素个数。主控逻辑中创建 Flight和Train两个具体类的一些订票请求对象加入 v中，因为 Flight和 Train均为Vehicle的子类型，而已是具体类，所以满足加入元素的要求，故采用 newFlight()和 new Train()来创建相应的对象加入 v中；然后通过 for循环使每个订票请求对象进行订票，并输出剩余票数： for (int i=0； iv si ze()； i+) v get(i) book(i+1)； 订 i+1张票 system out println(“剩务专票数： ” +v get(i) getTicket()； 即从 v中取每个对象，调用 book
31、方法进行订票操作。 v get(i)获得 v中位置为 i的元素，即 Vehicle类型的对象， Java中，动态绑定机制使得不同对象接收同一消息后发生不同的响应，即具体行为由位置为 i的对象决定。此处无须类型转换，这是因为在父类 Vehicle中，已经定义了 book方法，并且申明了 book所调用的getTicket和 decreaseTicket方法接口，子类分别加以实现。另外，在上述getTicket和 decreaseTicket两个方法执行时，因为每次操作 tickets为 static静态类型，所以，每个操作均作用在当前类变量的剩余票数，即具体子类型的有唯一一个当前剩余票数，每次操
32、作都是上次对象修改之后的值的基础上继续更新。 在 main()方法中，依次新建并加入了 5个对象，按顺序类型分别为： Flight、Train、 Flight、 Train、 Train，加入 v中的 index分别为 0、 1、 2、 3、 4。在 for循环中，按顺序获取链表集合中的对象元素，并进行订票，数量为 i+1张，然后输出剩余票数。因此，采用 v get(i) book(i+1)进行订票，采用 v get(i)。getTicket()获得当前对象元素所属类的剩余票数。其中 Flight的剩余票数 216一1=215、 2153=212； Train的剩余票数为 20162=2014、 2014 4=2010、 20105=2005。按对象顺序则为： 215、 2014、 212、 2010、 2005。 综上所述，空 (1)和 (3)需要表示继承 Vehicle抽象类，即 extends Vehicle；空 (2)和 (4)需要分别表示 Flight和 Train中 tickets变量为静态整型变量，即 stmic int；空 (5)处为调用获取 V中对象元素并订票的 V get(i) book；空 (6)为 212；空 (7)为2010；空 (8)为 2005。
