复旦附中进修学校公布CSPS组答案（全国首。。。

　　2019CCF非专业级别软件能力认证第一轮
　　（CSPS）提高级C语言试题A卷
　　（B卷与A卷仅顺序不同）
　　认证时间：2019年10月19日
　　考生注意事项：
　　试题纸共有10页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的一律无效
　　不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
　　一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
　　1。若有定义：a7；x2。5，y4。7；则表达式xa3（int）（xy）2的值是：（）
　　A。0。000000B。2。750000C。2。500000D。3。500000
　　答案：D
　　解析：xy转整数等于7，73721，再加x，答案为3。5。
　　2。下列属于图像文件格式的有（）
　　A。WMVB。MPEGC。JPEGD。AVI
　　答案：C
　　解析：WMV是音频格式、MPEG、AVI是视频格式、JPEG是图像格式。
　　3。二进制数11101110010111和01011011101011进行逻辑或运算的结果是（）
　　A。1111111101B。11111111111101C。10111111111111D。11111111111111
　　答案：D
　　解析：将两个二进制数（右）对齐，逐位做或运算，每一位如果有1则或运算结果为1，14位进行或运算计算结果均为1，选D。
　　4。编译器的功能是（）
　　A。将源程序重新组合
　　B。将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
　　C。将低级语言翻译成高级语言
　　D。将一种编程语言翻译成自然语言
　　答案：B
　　解析：编译器将高级语言（例如C，方便人创作）翻译成低级语言（机器语言，方便机器执行）。
　　5。设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）
　　A。X（x1000。5）100。0B。x（int）（x1000。5）100。0；
　　C。x（x1000。5）100。0D。xx1000。5100。0；
　　答案：B
　　解析：x的类型是float，所以（x1000。5）也是float，也就是有小数位，需要先转成int，也就是B选项。
　　6。由数字1，1，2，4，8，8所组成的不同的4位数的个数是（）
　　A。104B。102C。98D。100
　　答案：B
　　解析：穷举法。1。当取出1，1，2，4时，共有C（2，4）212种；2。当取出1，1，2，8，也是12种；3当取出1，1，4，8，也是12种；4当取出1，1，8，8，为C（2，4）是6种；5当取出为1，2，4，8时候，为A（4，4）20种；6当取出1，2，8，8，为12种；7当取出1，4，8，8为12种，8，当取出2，4，8，8为12种。一共102种情况。
　　7。排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。
　　A。冒泡排序B。直接插入排序C。快速排序D。归并排序
　　答案：C
　　解析：若经过排序，这些记录的相对次序保持不变，即在原序列中，r〔i〕r〔j〕，且r〔i〕在r〔j〕之前，而在排序后的序列中，r〔i〕仍在r〔j〕之前，则称这种排序算法是稳定的。快速排序在中枢元素和a〔j〕交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为53343891011，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法。
　　8。G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（）个顶点
　　A。10B。9C。11D。8
　　答案：D
　　解析：n个点最多n（n1）2条边，要不连通，至少去掉n1条边n（n1）2（n1）28，n最小为8。
　　9。一些数字可以颠倒过来看，例如0、1、8颠倒过来看还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）
　　A。40B。25C。30D。20
　　答案：B
　　解析：前2位有0，1，8，6，9，5种选择，第3位只能放0，1，8，后2位由前2位决定。而0，1，8模3正好余0，1，2，所以给定其他4位，第3位有且仅有1种选择，总数5511125。
　　10。一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）
　　A。23B。21C。20D。22
　　答案：A
　　解析：容斥原理，总满分人数数学满分语文满分语文数学满分1512423。
　　11。设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）
　　A。nB。C。2nD。2n1
　　答案：D
　　解析：考虑2个数组分别是（1，3，5）和（2，4，6），共需比较5次。因为结果数组大小是2n，先从两数组取第一个值比较，小的入结果数组，剩下的和另一个数组的下一个数比较，依次这样，直到一个数组为空。另一个数组剩下的元素直接进结果数组。最坏一个数组空，另一个数组还剩1个元素，比较次数就是2n1。
　　12。以下哪个结构可以用来存储图（）
　　A。栈B。二叉树C。队列D。邻接矩阵
　　答案：D
　　解析：邻接矩阵和邻接表可以存储图，其他三项都是数据结构，不是存储结构。
　　13。以下哪些算法不属于贪心算法？（）
　　A。Dijkstra算法B。Floyd算法C。Prim算法D。Kruskal算法
　　答案：B
　　解析：Dijkstra算法需要每次选取d〔i〕最小的边；Prim算法需要每次选在集合E中选取权值最小的边u；kruskal剩下的所有未选取的边中，找最小边。Floyd算法只需要按照顺序取边就可以了。
　　14。有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问一下哪个数是可能的公比？（）
　　A。5B。3C。4D。2
　　答案：B
　　解析：设公比是p，那么2p（2n2）118098，2p（n1）486，可以得到p（n1）243，由于gcd（2，243）gcd（4，243）gcd（5，243）1，所以排除2，4，5，而gcd（3，243）3，所以公比可能是3。
　　15。有正实数构成的数字三角形排列形式如图所示。第一行的数为a2，1，a2，2，第n行的数为an，1，an，2，，an，n。从a1，1开始，每一行的数ai，j只有两条边可以分别通向下一行的两个数ai1，j和ai1，j1。用动态规划算法找出一条从a1，1向下通道an，1，an，2，，an，n中某个数的路径，使得该路径上的数之和最大。
　　令C〔i〕〔j〕是从a1，1到ai，j的路径上的数的最大和，并且
　　C〔i〕〔0〕C〔0〕〔j〕0，则C〔i〕〔j〕（）
　　A。mac｛C〔i1〕〔j1〕，C〔i1〕〔j〕｝ai，j
　　B。C〔i1〕〔j1〕C〔i1〕〔j〕
　　C。max｛C〔i1〕〔j1〕，c〔i1〕〔j〕｝1
　　D。max｛C〔i〕〔j1〕，C〔i1〕〔j〕｝ai，j
　　答案：A
　　解析：每个点的只能够从C（i1，j1）以及C（i1，j）过来，所以最优解肯定是从更大的那个节点到，所以结果包含max（C（i1，j1），C（i1，j）），而计算的是和所以也包含aij这一项。
　　二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填，错误填；除特殊说明外，判断题1。5分，选择题4分，共计40分）
　　1。
　　1include
　　2
　　3
　　4inta〔100〕；
　　5
　　6intmain（）｛
　　7scanf（“d”，n）；
　　8for（inti1；n；i）｛
　　9scanf（“d”，a〔i〕）
　　10intans1
　　11for（inti1；n；i）｛
　　12if（1a〔i〕a〔i1〕）
　　13
　　14（a〔i〕a〔ans1〕）
　　15
　　16printf（“dn”，ans）；
　　17｝
　　18return0；
　　19｝
　　概述：12行if判断如a〔i〕比前一位小，则从i开始，否则从上次开始14行while循环找ans向后找第一个a〔i〕的数12行的判断的意思是，如果后项前项，则重新开始，否则从上项开始（蠕动）
　　整个程序含义是找每个a〔i〕后第一个大于a〔i〕的位置（如果看懂，后面都很好做）
　　判断题
　　1）（1分）第16行输出ans时，ans的值一定大于i。（）
　　答案：错
　　解析：12行if成立，14行while不成立，则16行ansi
　　2）（1分）程序输出的ans小于等于n。（）
　　答案：对
　　解析：13行n，15行n才会自增，所以不会超过n
　　3）若将第12行的“”改为“！”，程序输出的结果不会改变。（）
　　答案：对
　　解析：改成！，无非是多了一些无用的比较，最后结果不变其实12行直接删掉，结果也不会边，只是速度变慢而已
　　4）当程序执行到第16行时，若2，则a〔i1〕a〔i〕。（）
　　答案：对
　　解析：14行，由于ans是第一个大于a〔i〕的，所以a〔i1〕。。a〔ans1〕都不超过a〔i〕，结论成立
　　5）（3分）若输入的a数组是一个严格单调递增的数列，此程序的时间复杂度是（）。
　　A。0（logn）B。0（n2）C。0（nlogn）D。0（n）
　　答案：D
　　解析：单调增，则12行if不会成立，也就是ans只增不减所以复杂度为O（n）
　　6）最坏情况下，此程序的时间复杂度是（）。
　　A。0（n2）B。0（logn）C。0（n）D。0（nlogn）
　　答案：A
　　解析：最坏情况下，12行if总是成立（a单调降）此时14行也会一直运行到ansn，复杂度为12。。nO（n2）
　　2。
　　1include
　　2
　　3
　　4maxn1000；
　　5n；
　　6intfa〔maxn〕，cnt〔maxn〕；
　　7：
　　8intgetroot（intv）｛
　　9if（fa〔v〕v）
　　10returngetroot（fa〔v〕）；
　　11｝
　　12：
　　13intmain（）｛
　　14n；
　　15for（inti0；n；i）｛
　　16fa〔i〕i；
　　17cnt〔i〕1；
　　18｝
　　19intans0；
　　20for（inti0；n1；i）｛
　　21inta，b，x，y，；
　　22b
　　23xgetRoot（a）；
　　24ygetRoot（b）；
　　25anscnt〔x〕cnt〔y〕；
　　26fa〔x〕y；
　　27cnt〔y〕cnt〔x〕；
　　28｝
　　29
　　30return0；
　　31｝
　　判断题
　　1）（1分）输入的a和b值应在【0，n1〕的范围内。（）
　　答案：对
　　解析：从初始化看，下标范围为0n1，所以合并范围也在此内
　　2）（1分）第16行改成“fa〔i〕0；”，不影响程序运行结果。（）
　　答案：错
　　解析：findRoot里用到fa〔v〕v表示组长
　　3）若输入的a和b值均在〔0，n1〕的范围内，则对于任意0in，都有0fa〔i〕n。（）
　　答案：对
　　解析：fa〔i〕表示i同组的上级，下标也在0n1范围内
　　4）若输入的a和b值均在〔0，n1〕的范围内，则对于任意in，都有cnt〔i〕n。（）
　　答案：对
　　解析：cnt表示子连通块大小
　　选择题
　　5）当n等于50时，若a、b的值都在〔0，49〕的范围内，且在第25行时总是不等于y，那么输出为（）
　　A。1276B。1176C。1225D。1250
　　答案：C
　　解析：每两次合并x和y都不同，表示每次都是单独一个去和整体合并。此时cnt〔y〕增加cnt〔x〕的值，也就是加1。1112。。。149504921225
　　6）此程序的时间复杂度是（）
　　A。O（n）B。O（logn）C。O（n）D。O（nlogn）
　　答案：C
　　解析：并查集getRoot函数没有路径压缩，单次查找最坏为O（n）。总效率为O（n2）
　　3。本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别多，如果st，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。
　　S〔x。。y〕表示s〔x〕s〔y〕共yx1个字符构成的字符串，若xy则s〔x。。y〕是空串。t〔x。。y〕同理。
　　1include
　　2include
　　3
　　4max1202；
　　5strings，t；
　　6pre〔max1〕，suf〔max1〕
　　7：
　　8intmain（）｛
　　9
　　10intslens。length（），tlent。length（）；
　　11for（intI0，j0；i）｛
　　12if（s〔i〕t〔j〕）j；
　　13pre〔i〕j；t〔0。。j1〕是s〔0。。i〕的子序列
　　14｝
　　15for（Islen1，jtlen1；I0；i）｛
　　16if（j0s〔i〕t〔j〕）j；
　　17suf〔i〕j；t〔j1。。tlen1〕是s〔i。。slen1〕的子序列
　　18｝
　　19suf〔slen〕tlen1；
　　20intans0；
　　21。for（inti0，j0，i）｛
　　22。while（tmpsuf〔j〕1）j；
　　23。ansmax（ans，jI1）；
　　24。tmppre〔i〕；
　　25。｝
　　26。coutansend1；
　　27。return0；
　　28。｝
　　提示：
　　t〔0。。pre〔i〕1〕是s〔0。。i〕的子序列；
　　t〔suf〔i〕1。。tlen1〕是s〔i。。slen1〕的子序列
　　判断题
　　1。（1分）程序输出时，suf数组满足：对任意0islen，suf〔i〕suf〔i1〕。（）
　　答案：对
　　解析：suf〔i〕是满足t〔suf〔i〕1。。tlen1〕为s〔i。。slen1〕子序列的最小值
　　那么t〔suf〔i1〕1。。。tlen1〕是s〔i1。。slen1〕的子序列t〔suf〔i1〕1tlen1〕也是s〔i。。slen1〕的子序列，但不是最小（最小值是suf〔i〕），因此suf〔i1〕suf〔i〕，单独看15到19行程序也可以直接得出这个结论
　　2。（2分）当t是s的子序列时，输出一定不为0。（）
　　答案：错
　　解析：可以理解题目的输出：s中删去连续多少个字母后t仍然是s的子序列；或者直接用代入，结果是0
　　3。（2分）程序运行到第23行时，“ji1”一定不小于0。（）
　　答案：错
　　解析：第一轮执行22行时tmp0，j0不执行，因此这轮ji1就可能是负数
　　4（2分）当t时s的子序列时，pre数组和suf数组满足：对任意0islen，pre〔i〕suf〔i1〕。（）
　　答案：错
　　解析：可以用简单的样例（如）代入检验，也可以根据pre和suf的定义：如果t是s的子序列，那么0pre〔i〕1，suf〔i1〕1lent1这部分分别是s〔0i〕，s〔i1lens1〕的子序列，不会重叠，所以有pre〔i〕1suf〔i1〕1，也就是pre〔i〕suf〔i1〕1
　　选择题
　　5。若tlen10，输出为0，则slen最小为（）
　　A。10B。12C。0D。1
　　答案：D
　　解析：slen是s的长度，至少需要输入一个长度的字符串，如果t不是s子序列那输出一定是0
　　6。若tlen10，输出为2，则slen最下为（）
　　A。0B。10C。12D。1
　　答案：C
　　解析：输出是2说明s串删去两个连续元素后t仍是s的子序列，因此删去后长度至少为10，删前至少为12
　　三、完善程序（单选题，每题3分，共计30分）
　　1（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
　　输入第一行有两个数，分别为新技术个数n（1n10），以及已有经验值（107）。
　　接下来n行。第i行的两个整数，分别表示学习第i个技术所需的最低经验值（107），以及学会第i个技术后可获得的经验值（104）。
　　接下来n行。第i行的第一个数mi（0min），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
　　下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。
　　1inclde
　　2
　　3constintmaxn1001；
　　4：
　　5
　　6intcnt〔maxn〕
　　7intchild〔maxn〕〔maxn〕；
　　8intunlock〔maxn〕；
　　9intunlock〔maxn〕；
　　10intthreshold〔maxn〕，bonus〔maxn〕；
　　11：
　　12boolfind（）｛
　　13inttarget1；
　　14for（inti1；i）
　　15if（）｛
　　16
　　17
　　18｝
　　19if（target1）
　　20
　　21unlock〔target〕1；
　　22；
　　23for（inti0；icut〔target〕；i）
　　24；
　　25
　　26｝
　　27：
　　28intmain（）｛
　　29scanf（，n，points）；
　　30for（intI1；i｛
　　31cnt〔i〕0；
　　32scanf（，threshold〔i〕，bonus〔i〕；
　　33｝
　　34for（inti1；i｛
　　35
　　36scanf（，m）；
　　37；
　　38for（intj0；j｛
　　39
　　40scanf（，fa）；
　　41child〔fa〕〔cnt〔fa〕〕i；
　　42cnt〔fa〕；
　　43｝
　　44｝
　　45intans0；
　　46while（find（））
　　47
　　48printf（，ans）；
　　49return0；
　　50｝
　　1）处应填（）
　　A。unlock〔i〕0
　　B。unlock〔i〕0
　　C。unlock〔i〕0
　　D。unlock〔i〕1
　　答案：C
　　解析：unlock作用是看是否能解锁任务。根据对问题5的分析，在未解锁前它的值是还有几个依赖任务未解锁。那么解锁条件当然是0个依赖任务，因此是等于0
　　2）处应填（）
　　A。threshold〔i〕points
　　B。threshold〔i〕points
　　C。pointsthreshold〔i〕
　　D。pointsthreshold〔i〕
　　答案：D
　　解析：很简单，解锁条件之二，经验点要大于等于任务的需求点
　　3）处应填（）
　　A。target1
　　B。cnt〔target〕
　　C。bbonus〔target〕
　　D。pointsbonus〔target〕
　　答案：D
　　解析：经验点增加。A肯定不对，target后面还要用。B不对，因为cnt〔i〕是依赖i的任务。C也不对，bonus是只读的
　　4）处应填（）
　　A。cnt〔child〔target〕〔i〕〕1
　　B。cnt〔child〔target〕〔i〕〕0
　　C。unlock〔child〔target〕〔i〕〕1
　　D。unlock〔child〔target〕〔i〕〕0
　　答案：C
　　解析：从前面分析看出unlock是依赖的还没解锁的任务数，解锁一个任务，所有依赖这个任务的unlock值都要减1
　　5）处应填（）
　　A。unlock〔i〕cnt〔i〕
　　B。unlock〔i〕m
　　C。unlock〔i〕0
　　D。unlock〔i〕1
　　答案：B
　　解析：m是任务依赖的任务数，从前面代码看出当unlock〔i〕为1时表示解锁成功，那么D不对。A的话cnt〔i〕此时还没完成赋值，也不对。C有迷惑性，认为unlock是布尔值，但看题目m个依赖任务完成才能解锁该任务，所以不是单纯的布尔，需要每解锁一个前置任务就将unlock减1，直到为0
　　2。（取石子）Alice和Bob两个人在玩取石子游戏，他们制定了n条取石子的规则，第i条规则为：如果剩余的石子个数大于等于a〔i〕且大于等于b〔i〕，那么她们可以取走b〔i〕个石子。他们轮流取石子。如果轮到某个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有m个。请问先取石子的人是否有必胜的方法？
　　输入第一行有两个正整数，分别为规则个数n（1n64），以及石子个数m（107）。
　　接下来n行。第i行有两个正整数a〔i〕和b〔i〕。（1a〔i〕107，1b〔i〕64）
　　如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
　　提示：
　　可以使用动态规划解决这个问题。由于b〔i〕不超过，所以可以使用位无符号整数去压缩必要的状态。
　　Status是胜负状态的二进制压缩，trans是状态转移的二进制压缩。
　　试补全程序。
　　代码说明：
　　“”表示二进制补码运算符，它将每个二进制位的0变成1、1变为0；
　　而“”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为0，反之为1。
　　U11标识符表示它前面的数字是unsignedlonglong类型。
　　1include
　　2include
　　3
　　4
　　5constintmaxn64；
　　6：
　　7intn，m；
　　8inta〔maxn〕，b〔maxn〕；
　　9unsignedlonglongstatus，
　　10
　　11：
　　12intmain（）｛
　　13scanf（“dd”，n，m）；
　　14for（inti0；n；i）
　　15scanf（“dd”，a〔i〕，b〔i〕）；
　　16for（i0；n；i）
　　17for（jiL；n；j）
　　18if（aa〔i〕a〔j〕）｛
　　19swap（a〔i〕，a〔j〕）
　　20swap（b〔i〕，b〔j〕）
　　21｝
　　22S
　　23trans0；
　　24for（inti1，j0；m；i）｛
　　25while（）｛
　　26；
　　27j；
　　28｝
　　29
　　30；
　　31｝
　　32puts（win？“Win”：“Loss”）；
　　33return0；
　　34｝
　　解析：首先使用f（i）表示有i个石子时，是否有必胜策略。所以f（i）！f（ib〔j1〕）or！f（ib〔j2〕）。。。）（a〔j〕i），转换公式，status中每一位定义为win（ij），也就是有ij有必胜策略。因此第一题初始状态为都必输，因为石子有0个，怎么样都是输的。然后trans相当于记录当前状态下能够必胜的策略位置也就是b〔j〕的集合，但是因为要注意这边trans没有清0，因为我们考虑到事实上能转移的状态数是不会减少的，所以这边第二题选B，表示将当前的状态增加到trans里面，同时第三题选择A表示的就是将b〔j〕加到trans里面（记录新增的能够必胜的位置），然后第4题相当于往status记录新的必胜策略的位置（也就是trans），所以按照上述的转移公式f（），第4题答案也就是D了，因为先手必胜的情况等价于，当前状态下能走到的先手必输的情况不为空。最好将status状态更新，具体就是将当前的win记录到status的最低位上即可（第5题）
　　1）处应填（）
　　A。0B。0C。0ull1D。1
　　答案：C
　　2）处应填（）
　　A。a〔j〕B。a〔j〕C。a〔j〕！D。a〔j〕i
　　答案：B
　　3）处应填（）
　　A。1（b〔j〕1）
　　B。status1（b〔j〕1）
　　C。status1（b〔j〕1）
　　D。trans1（b〔j〕1）
　　答案：A
　　4）处应填（）
　　A。B。trans
　　B。D。trans
　　答案：D
　　5）处应填（）
　　A。transwin
　　B。1win
　　C。transstatustranswin
　　D。1win
　　答案：D