程序员考试同步辅导（下午科目）（第3版）

全国计算机技术与软件专业技术资格(水平)考试得到社会各界的广泛认可。本系列图书自出版以来，被众多考生选用为考试参考书，多次再版、重印，为考生备考提供了有力的帮助，深受广大读者的厚爱。作为一套为考生备考使用的图书，本系列图书具有以下特色：
(1) 全面剖析命题特点。通过分析研究近几年的考题，统计出各章所占的分值和考点的分布情况，引导考生把握命题规律。
(2) 突出严谨性与实用性。按照考试大纲，与官方教程同步，内容严谨，应试导向准确。
(3) 考点浓缩，重点突出。精心筛选考点，突出重点与难点，针对性强。同时对于考试中出现的而指定教材没有阐述的知识点进行了必要的补充。
(4) 例题典型，分析透彻。所选例题出自真题，内容真实相关，例题分析细致深入，解答准确完整，以帮助考生增强解题能力，突出实用性。
(5) 习题丰富，附有答案。每章都提供了一定数量的习题供考生自测，并配有参考答案与解析，有利于考生巩固所学知识，提高解题能力。
(6) 全真试题实战演练。试题题型、考点分布、题目难度与真题相当，便于考生熟悉考试方法、试题形式，全面了解试题的深度和广度。

 

《程序员考试同步辅导(下午科目)(第3版)》是按照人力资源和社会保障部、工业和信息化部*颁布的全国计算机技术与软件专业技术资格(水平)考试大纲和指定教材而编写的考试用书。全书共6章，内容包括常用算法和数据结构，程序流程图和N-S图，C语言，C 语言，Java语言程序设计，程序员考试(下午科目)样卷与答案解析等，主要从考试大纲要求、考点辅导、典型例题分析和专项习题训练几个方面对各部分内容加以系统地阐释。

《程序员考试同步辅导(下午科目)(第3版)》具有考点分析透彻、例题典型、习题丰富等特点，非常适合参加程序员考试的考生使用，也可以作为高等院校或培训班的教材。

本系列图书由东南大学、厦门大学、南京理工大学、江南大学、中国药科大学、南京财经大学、常州大学、常州工学院、黄山学院、陆军炮兵防空兵学院、江苏科技大学、河海大学文天学院等30余所高校的教师共同研究、编写而成，他们多为“双师型”教师，既奋斗在教学一线，又参与诸多项目的研发，对计算机网络、软件开发有着丰富的教学经验、项目经验，同时对软考考试大纲和命题规律有较深入的研究，在他们的指导下，相信广大考生可顺利通关。

目    录
第1章  常用算法和数据结构    1
1.1  排序算法    1
1.1.1  考点辅导    1
1.1.2  典型例题分析    9
1.1.3  同步练习    10
1.1.4  同步练习答案    13
1.2  查找算法    15
1.2.1  考点辅导    15
1.2.2  典型例题分析    19
1.2.3  同步练习    23
1.2.4  同步练习答案    23
1.3  数据结构    24
1.3.1  考点辅导    24
1.3.2  典型例题分析    59
1.3.3  同步练习    71
1.3.4  同步练习答案    76
1.4  本章小结    79
1.5  达标训练题及参考答案    79
1.5.1  达标训练题    79
1.5.2  参考答案    81
第2章  程序流程图和N-S图    83
2.1  流程图和N-S图的基础知识    83
2.1.1  考点辅导    83
2.1.2  典型例题分析    85
2.1.3  同步练习    95
2.1.4  同步练习答案    97
2.2  经典算法的描述    98
2.2.1  考点辅导    98
2.2.2  典型例题分析    98
2.2.3  同步练习    101
2.2.4  同步练习答案    102
2.3  信息处理的模拟    103
2.3.1  考点辅导    103
2.3.2  典型例题分析    103
2.3.3  同步练习    108
2.3.4  同步练习答案    108
2.4  本章小结    109
2.5  达标训练题及参考答案    109
2.5.1  达标训练题    109
2.5.2  参考答案    111
第3章  C语言    114
3.1  C语言的程序结构    114
3.1.1  考点辅导    114
3.1.2  典型例题分析    115
3.1.3  同步练习    116
3.1.4  同步练习答案    117
3.2  C语言的数据类型、运算符和表达式    117
3.2.1  考点辅导    117
3.2.2  典型例题分析    118
3.2.3  同步练习    120
3.2.4  同步练习答案    122
3.3  C语言的基本语句    124
3.3.1  考点辅导    124
3.3.2  典型例题分析    125
3.3.3  同步练习    130
3.3.4  同步练习答案    131
3.4  标准输入输出函数    132
3.4.1  考点辅导    132
3.4.2  典型例题分析    134
3.4.3  同步练习    135
3.4.4  同步练习答案    136
3.5  数组和函数    136
3.5.1  考点辅导    136
3.5.2  典型例题分析    141
3.5.3  同步练习    152
3.5.4  同步练习答案    157
3.6  指针    159
3.6.1  考点辅导    159
3.6.2  典型例题分析    164
3.6.3  同步练习    173
3.6.4  同步练习答案    175
3.7  本章小结    177
3.8  达标训练题及参考答案    177
3.8.1  达标训练题    177
3.8.2  参考答案    186
第4章  C 语言    190
4.1  C 程序基础    190
4.1.1  考点辅导    190
4.1.2  典型例题分析    192
4.1.3  同步练习    194
4.1.4  同步练习答案    195
4.2  类、成员、构造函数及析构函数    196
4.2.1  考点辅导    196
4.2.2  典型例题分析    199
4.2.3  同步练习    209
4.2.4  同步练习答案    212
4.3  模板    213
4.3.1  考点辅导    213
4.3.2  典型例题分析    215
4.3.3  同步练习    220
4.3.4  同步练习答案    223
4.4  继承和多态    224
4.4.1  考点辅导    224
4.4.2  典型例题分析    226
4.4.3  同步练习    232
4.4.4  同步练习答案    234
4.5  本章小结    234
4.6  达标训练题及参考答案    235
4.6.1  达标训练题    235
4.6.2  参考答案    237
第5章  Java语言程序设计    239
5.1  Java语言的程序结构和基本语法    239
5.1.1  考点辅导    239
5.1.2  典型例题分析    241
5.1.3  同步练习    243
5.1.4  同步练习答案    244
5.2  类、成员、构造函数    245
5.2.1  考点辅导    245
5.2.2  典型例题分析    248
5.2.3  同步练习    260
5.2.4  同步练习答案    263
5.3  继承及接口    265
5.3.1  考点辅导    265
5.3.2  典型例题分析    267
5.3.3  同步练习    272
5.3.4  同步练习答案    274
5.4  本章小结    274
5.5  达标训练题及参考答案    275
5.5.1  达标训练题    275
5.5.2  参考答案    278
第6章  程序员考试(下午科目)样卷与答案解析    280
6.1  样卷    280
6.1.1  样卷一    280
6.1.2  样卷二    285
6.1.3  样卷三    292
6.1.4  样卷四    296
6.1.5  样卷五    303
6.1.6  样卷六    308
6.1.7  样卷七    313
6.1.8  样卷八    320
6.1.9  样卷九    326
6.1.10  样卷十    331
6.2  答案解析    337
6.2.1  样卷一答案解析    337
6.2.2  样卷二答案解析    340
6.2.3  样卷三答案解析    343
6.2.4  样卷四答案解析    345
6.2.5  样卷五答案解析    348
6.2.6  样卷六答案解析    350
6.2.7  样卷七答案解析    353
6.2.8  样卷八答案解析    355
6.2.9  样卷九答案解析    358
6.2.10  样卷十答案解析    361
参考文献    364

前    言
　　
　　全国计算机技术与软件专业技术资格(水平)考试自实施起至今已经历了20多年，在社会上产生了很大的影响，其权威性得到社会各界的广泛认可。为了适应我国信息化发展的需求，人事部(现为人力资源和社会保障部)、信息产业部(现为工业和信息化部)在2004年决定将考试的级别拓展到计算机技术与软件各个方面，将网络程序员级别考试改为网络管理员级别考试，2009年又对网络管理员级别考试大纲进行了重新调整，以满足社会上对各种信息技术人才的需要。本书第1版自2004年、第2版自2010年出版以来，被众多考生选用为考试参考教材，多次重印，深受广大读者好评。为了帮助考生复习迎考，根据最新考试大纲及网络新技术的发展，本书对第2版同名书进行修订，主要修订内容如下。
　　(1)    知识点更新。本书在第2版的基础上，严格按最新大纲，对知识点做了彻底的更新，更符合考试大纲对考试的要求。
　　(2)    结构调整。参考最新指定官方教程、最新考试大纲及最新题型编写章节，便于考生使用《程序员教程(第5版)》同步复习，同时更加突出重点与难点，针对性强，减轻了考生复习的工作量。
　　(3) 例题与习题更新。2015年至2017年的6次考试真题全部被分类解析到例题中，2013年和2014年的4次考试真题全部被分类归入同步练习中，达标训练则使用了2011下半年的考试真题和2012年的两次考试真题。考生能从以前的考题中，更好地熟悉考试的难度与广度，顺利通过考试。
　　(4) 更加突出重点。第3版沿袭前一版的框架，每一小节分4个版块，即考点辅导、典型例题分析、同步练习、同步练习答案。其中，考点辅导部分主要以专题的方式，重点介绍程序员上午考试所需的各个方面的知识；典型例题分析是本书的重点，它详尽细致地剖析了2015年至2017年所有的真题和例题；同步练习每道题都配有标准答案，对读者所学的知识和能力起到巩固、拓宽和提高的作用。
　　(5) 对语言进行了锤炼，讲述更准确、概念清晰，覆盖所有考试大纲考点，并突出重点和难点。
　　(6) 书中所有例题与习题进行了精选，确保所有题目符合考试大纲要求，例题选取典型、有梯度、有广度，分析详尽；题目的难易度、分布率与真实考试相当；题目答案正确、解析科学；无重复题目、雷同题目。
　　本书非常适合备考程序员的考生使用，也可作为高等学校相关专业或培训班的教材。
　　本书第1版由杨明、杨萍编写。第2版是对第1版的修订与升级，具体由崔艳春、孔德丽编写。第3版是对第2版的修订与升级，由崔艳春、陈亚天主编，任立涛、左从菊任副主编，参与本书组织、编写和资料收集的还有高云、卫星、张德成、刘綦、朱明、朱锦龙、闫鸿滨、杨继琼、何淑娟、江明星、赵卫、姚耀、何光明等。在此对作品的全体参与人员表示衷心的感谢。
　　在本书编写的过程中，参考了许多相关的书籍和资料，目录详见参考文献，本书从中汲取了许多营养，在此表示感谢。需要特别提出感谢的是来自互联网的各位不知道姓名的网友们的无私奉献，正是由于他们，才使本书的内容更完善、详尽。
　　由于时间仓促和水平有限，书中难免存在错漏和不妥之处，敬请读者批评指正。
　　
　　
     编  者

第1章  常用算法和数据结构
大纲要求：
排序算法。
查找算法。
数据结构(线性表、栈、队列、数组、树、图)。
1.1  排 序 算 法
1.1.1  考点辅导
1. 选择排序
若设R[1…n]为待排序的n个记录，R[1…i-1]已按照主关键字由小到大排序，且任意x∈R[1…i-1]，y∈R[i…n]满足x.key≤y.key，则选择排序的主要思路如下。
(1)反复从R[i…n]中选出关键字最小的结点R[k]。
(2)若i≠k，则将R[i]与R[k]交换，使得R[1…i]有序且保持原来的性质。
(3)i增1，直到i为n。
为方便描述，被查找的顺序表C类型定义如下：

#define MAXSIZE 1000                 /*顺序表的长度*/    
typedef int KeyType;                /*关键字类型为整数类型*/
typedef struct{
    KeyType key;                        /*关键字项*/
    InfoType otherinfo;                /*其他数据项*/
}RecType;                               /*记录类型*/
typedef struct {
    RecType  r[MAXSIZE 1];               /*r[0]空作为哨兵*/
    int length;                        /*顺序表长度*/
}SqList;                                  /*顺序表类型*/

顺序存储线性表的选择排序算法如下：

void Sqsort(SqList &q)
{
    int i, j, k, temp;
    for(i=0;i    {
        k=i;
        for(j=i 1;j            if(q.r[j].key            if(k!=i)
            {
                temp=q.r[k];
                q.r[k]=q.r[i];
                q.r[i]=temp;
            }
    }
}

可见，选择排序不管原先序列是否有序，其排序需要比较的次数均为n(n-1)/2；同时，由于相等的两个元素，位置相对在前的可能被交换到后面，故该选择排序是不稳定的。
2. 直接插入排序
若设R[1…n]为待排序的n个记录，R[1…i-1]已按照主关键字由小到大排序，则直接插入排序的主要思路如下。
(1)寻找R[i]在R[1…i-1]中的插入位置，确保R[i]插入后保持有序。
(2)i增1，若i小于等于n，则转到(1)执行，否则结束。
顺序线性存储结构下的直接插入排序算法如下：

void Dinsert(SqList &q)
{
    int i,j,k;
    for(i=1;i    {
        for(t=q.r[i],j=i-1;j>=0 && t.key            q.r[j 1]=q.r[j];
        q.r[j 1]=t;
    }
}

【点评】
(1)对n个结点的线性表采用直接插入排序，当线性表已是从小到大排序时，内循环每执行一次，只需要进行1次比较，整个排序过程只进行n-1次比较。当线性表已是从大到小排序时，对外循环执行i次，内循环要进行i次比较，整个排序过程需要进行n(n-1)/2次比较。可见，对n个结点的线性表采用直接插入排序，最少比较次数为n-1，最多比较次数为n(n-1)/2。
(2)直接插入排序是在有序表的基础上进行的，所以排序效率较高且比较稳定。