（CSP-J）入门级C++语言试题A卷（B卷与A卷仅顺序不同）
认证时间：年10月19日
第一部分
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.中国的国家顶级域名是（）
A..cnB..chC..chnD..china
答案：A
解析：常识，中国国家顶级域名即是.cn
2.二进制数11和11进行逻辑与运算的结果是（）
A.11B.11
C.01D.11
答案：D
解析：逻辑“与”基本常识，当且仅当2个数对应位都为1时，答案该位为1
3.32位整型变量占用（）个字节。
A.32B.C.4D.8
答案：C
解析：一个字节是8位，因此32位对应4个字节
4.若有如下程序段，其中s、a、b、c均已定义为整型变量，且a、c均已赋值(c大于0)
s=a;for(b=1;b=c;b++)s=s-1;则与上述程序段功能等价的赋值语句是(）
A.s=a-c;B.s=a-b;C.s=s-c;D.s=b-c;
答案：A
解析：s初始化为a;for循环执行c次，每次s减1,共减c,所以s=a-c
5.设有个已排好序的数据元素，采用折半查找时，最大比较次数为（）
A.7B.10C.6D.8
答案：A
解析：对折半查找，第一次(1+)/2=50,第二次(1+50)/2=25,第三次(1+25)/2=13,第四次(1+13)/2=7,第五次(1+7)/2=4,第六次(1+4)/2=2,第七次(1+2)/2=1。
6.链表不具有的特点是（）
A.插入删除不需要移动元素
B.不必事先估计存储空间
C.所需空间与线性表长度成正比
D.可随机访问任一元素
答案：D
解析：链表没有下标，不可随机访问
7.把8个同样的球放在5个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）提示:如果8个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法
A.22B.24C.18D.20
答案：C
解析：整数拆分问题，8拆成至多5个数之和（不计顺序），可按袋子个数分类讨论：1个袋子1种，2个袋子4种，3个袋子5种，4个袋子5种，5个袋子3种，共18种
8.—棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i,则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的最大下标至少为（）。
A.6B.10C.15D.12
答案：C
解析：堆式编号，最大值是最深的那层最靠右侧的节点，编号为((1*2+1)*2+1)*2+1=15
9.以内最大的素数是（）
A.89B.97C.91D.93
答案：B
解析：91=7*13，93=3*31，,且为素数.
10.和的最大公约数是（）
A.27B.33C.29D.31
答案：C
解析：辗转相除法,最大公约数为：(,)=(,58)=(58,29)=29
11.新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。方案一每次连续跑3公里可以消耗千卡(耗时半小时);方案二每次连续跑5公里可以消耗干卡(耗时1小时)。小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。另外，教练建议小胖每周最多跑21公里，否则会损伤膝盖。请问如果小胖想严格执行教练的训练方案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（）
A.0B.C.D.
答案：C
解析：设方案1,2各i,j天，由题意，3*i+5*j=21,i+j=7,j=3.求*i+*j的最大值。枚举所有情况，当i=2,j=3时，最大值，或使用线性规划求解。
12.一副纸牌除掉大小王有52张牌，四种花色，每种花色13张。假设从这52张牌中随机抽取13张纸牌，则至少()张牌的花色一致。
A.4B.2C.3D.5
答案：A
解析：抽屉原理，13张牌最坏情况就是4种花色分別为3,3,3,4张，至少4张一个样花色。
13.—些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是9,9颠倒过来看还6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如颠倒过来是。假设某个城市的车牌只由5位数字组成，每一位都可以取0到9。请问这个城市最多有多少个车牌倒过来怡好还是原来的车牌？（）
A.60B.C.75D.
答案：C
解析：前俩位位有5种选法（0,1,6,8,9),第3位有3种(0,1,8),第4,5位由前2位决定，答案为5*5*3*1*1=75
14.假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF,则其前序遍历序列为()。
A.ABCDEFGHIJ
B.ABDEGHJCFI
C.ABDEGJHCFI
D.ABDEGHJFIC
答案：B
解析：后续遍历是“左右根”，中序遍历是“左根右”，后序最后的A是根，中序中看的DBGEH是左子树，右边的CIF是右子树，以此类推可求画出树的形态，再求前序
15.以下哪个奖项是计算机科学领域的最高奖?(）
A.图灵奖B.鲁班奖C.诺贝尔奖D.普利策奖
答案：A
解析：鲁班奖是国内建设工程；诺贝尔奖为物理、化学、医学、文学、和平；普利策奖是新闻奖，图灵奖由美国计算机协会（ACM）于年设立，专门奖励那些对计算机事业作出重要贡献的个人。
第二部分
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填，错误填；除特殊说明外，判断题1.5分，选择题4分，共计40分）
1.
概述：将字符串下标是n约数位置的小写字母转大写
判断题
1)输入的字符串只能由小写字母或大写字母组成。（）
答案：错
解析：输入的字符串也可以包含数字等其它字符。
2)若将第8行的“i=1”改为“i=0”，程序运行时会发生错误。()
答案：对
解析：除数不能为0，％0会发生错误。
3)若将第8行的“i=n”改为“i*i=n”，程序运行结果不会改变。（）
答案：错
解析：循环条件为=n,也就是n也会执行到。同时n%n==0恒为True,所以修改后少了n这次循环，也就会改变结果了
4)若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（）
答案：对
解析：对的，因为大写的Ascii值比较小，也就是从c=a恒为False,所以s的值不会改变，所以是对的
选择题
5)若输入的字符串长度为18,那么输入的字符串跟输出的字符串相比，至多有()个字符不同。
A.18B.6C.10D.1
答案：B
解析：因为18=2*3^2,也就是因数个数为(1+1)*(1+2)=6,也就是判定条件最多满足六次，所以最多有6个
6)若输入的字符串长度为（），那么，输入的字符串跟输出的字符串相比，至多有36个字符不同。
A.36B.000C.1D.
答案：B
解析：因为000=2^5*5^5，也就是因数个数为(5+1)*(5+1)=36，也即是判定条件最多满足36次，所以最多有36个
2.
假设输入的n和m都是正整数，x和y都是在[1,n]的范围内的整数，完成下面的判断题和选择题
判断题
1）当m0时，输出的值一定小于2n。
答案：对
解析：由限定条件可知，0x,y=n,当m大于0时，一定存在某个数被选中，使得ans2*n。
2）执行完第27行的“++ans”时，ans一定是偶数。
答案：错
解析：由于数对是一个左值与一个右值相匹配，所以ans最终一定是偶数，但是第27行的”++ans“在23行循环内部，其中间结果可能是负数。
3)a和b不可能同时大于0。
答案：错
解析：反例：当m为1,并且输入x=1，y=1的时候，可以使得a[1]和b[1]同时为1
4)若程序运行到第13行时，x总是小于y,那么第15行不会被执行。
答案：错
解析：反例m=2,x=1,y=2.x=1,y=3
选择题
5)若m个x‘两两不同，且m个y两两不同，则输出的值为（）
A.2n-2mB.2n+2C.2n-2D.2n
答案：A
解析：如果各不相同的话，m次循环，会导致2m个位置从0变到整数，答案为2n-2m
6)若m个x两两不同，且m个y都相等，则输出的值为()
A.2n-2B.2nC.2mD.2n-2m
答案：A
解析：都不相同的话14行和16行不会执行，因此每次输入会有一组a,b赋值一共有m组;y都相同的话b[y]中会保留最小的一个x,所以只存了一组值，空着2n-2
3.
概述：构造数列a的笛卡尔树（根节点最小且保持中序遍历），并求节点深度与b的加权和
判断题
1)如果a数组有重复的数字，则程序运行时会发生错误。()
答案：错
解析：每次找a数组中第一次出现的最小值，所以有重复的数不会导致程序出错
2)如果b数担全为0,则输出为0()
答案：对
解析：因为递归最底层lr返回0,而倒数第二层返回值是O+0+depth*b[mink],如果b是0的话也是0,以此类推，返回结果总是0
选择题
3)当n=时，最坏情况下，与第12行的比较运算执行的次数最接近的是（）
A.B.C.6D.
答案：A
解析：最坏情况下a有序，mink每次都切在一段，递归进行层，执行次数为+99+,+…1约等于
4)当n=时，最好情况下，与第12行的比较运算执行的次数最接近的是（）
A.B.6C.D.
答案：D
解析：最好情况下，每次都均分，每层递归总次数为,层数为logn约等于6,总次数月6*=
5)当n=10时，若b组满足，对任意Osin，都有b=i+1,那么输出最大为（）
A.B.C.D.
答案：D
解析:n=10时,深度最大能够达到10,最大输出为1*b[0]+2*b[1]+...+10*b[9]=1*1+2*2+3*3+4*4+5*5+6*6+7*7+8*8+9*9+10*10=
6)(4分)当n=时，若b数组满足，对任意0=in，都有b=1,那么输出最小为（）
A.B.C.D.
答案：B
解析：b=1,即求一个节点的二叉树，节点深度之和最小，贪心法，结论是节点的完全二叉树。1*1+2*2+4*3+8*4+16*5+32*6+37*7=
第三部分
三、完善程序（单选题，每题3分，共计30分）
提示：
“”表示二进制左运算符，例如
而“”表示二进制异或运算符，它将两个参与运算的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为0,反之为1.
1)①处应填（）
A.n%2B.0C.tD.1
答案：C
解析：递归边界，res只有这一处赋值，BD显然错。n%2的话01只跟n有关，错，因此只有t是对的
2)②处应填（）
A.x-step，y-stepB.x，y-step
C.x-step.yD.x,y-step
答案：D
解析：step是边长的一半，借鉴15,16行，参数x,y是当前左上角坐标。14-17
分别是左上，左下，右上，右下四个子矩阵
3)③处应填（）
A.x-step,y-stepB.x+step,y+step
C.x-step,yD.x,y-step
答案：B
解析：同上
4)④处应填（）
A.n-1,n%2B.n,0
C.n,n%2D.n-1,0
答案：B
解析：此处是递归计算的入口，即题目最终所求的大小为2^n*2^n，由单个数字0变化来的矩阵，因此递归函数的另俩个参数为n,0
5)⑤处应填()
A.1(n+1)B.1n
B.n+1D.1(n-1)
答案：B
解析：size是输出矩阵的边长，也就是2^n,用位运算写就是1n
2.(计数排序）计数棑序是一个广泛使用的排序方法.下而的程序使用双关键字计数排序，将n对00以内的整数，从小到大排序。
例如有三对整数（3,4)、（2,4)、（3,3),那么排序之后应该是(2,4)、(3,3)、(3,4).输入第一行为n,接下来n行，第i行有两个数a和b,分別表示第i对整数的第一关键字和第二关键字。从小到大排序后输出。
数据范围：
提示：应先对第二关键字排序，冉对第一关键字排序.数组ord[]存储第二关键字排序的结果，数组rest[]存储双关键字样序的结果，试补全程序。
1)①处应填（）
A.++cnt
B.++cnt[b]
C.++cnt[a*maxs+b]
D.++cnt[a]
答案：B
解析：此处是对第二关键字进行计数排序。题目中给出提示，先按第二关键字排序。并且根据填空2对ord进行更改，可知此时是対第二关键字进行排序。
2)②处应填（）
A.ord[--cnt[a]]=i
B.ord[--cnt[b]]=a
C.ord[--cnt[a]]=b
D.ord[--cnt[b]]=i
答案：D
解析：cnt[b]表示按第二关键字，第i个数排第几位。ord表示第i小的数在原序列的位置
3)③处应填（）
A.++cnt[b]
B.++cnt[a*maxs+b]
C.++cnt[a]
D.++cnt
答案：C
解析：对第一关键字计数，并做各关键词的数量统计工作，因此将a对应的元素数量自增一。
4)④处应填（）
A.res[-cnt[a[ord]]]=ord
B.res[-cnt[b[ord]]]=ord
C.res[-cnt[b]]=ord
D.res[-cnt[a]]=ord
答案：A
解析：对应填空2ord记录了第二关键字第i小的数在原序列的位置。此时res记录了第一关键字第i小的数在原序列的位置。
5)⑤处应填（）
A．a,b
B.a[res],b[res]
C.a[ord[res]],b[ord[res]]
D.a[res[ord]],b[res[ord]]
答案：B
解析：此处是按顺序输出排序结果，由于之前已经按照第二、第一关键字进行计数排序，所以此时第i个元素的原始下标为res。
CCF非专业级别软件能力认证第一轮
（CSP-S）提高级C++语言试题A卷
（B卷与A卷仅顺序不同）
认证时间：年10月19日
第一部分
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.若有定义：inta=7;floatx=2.5,y=4.7；则表达式x+a%3*(int)(x+y)%2的值是：（）
A.0.B.2.70
C.2.00D.3.00
答案：D
解析：x+y转整数等于7，取模运算与乘法优先级一样，所以7%3*7%2=1
2.下列属于图像文件格式的有（）
A.WMVB.MPEGC.JPEGD.AVI
答案：C
解析：WMV是音频、MPEG、AVI是视频、JPEG是图像。
3.二进制数11和11进行逻辑或运算的结果是（）
A.11B.01
C.10D.11
答案：D
解析：考察基本的位运算，将两个数字靠右对齐（若一样长前面用0补），一位一位做或运算，or运算的规则是有1则1，14位进行或运算计算结果均为1，选D。
4.编译器的功能是（）
A.将源程序重新组合
B.将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
C.将低级语言翻译成高级语言
D.将一种编程语言翻译成自然语言
答案：B
解析：编译器将高级语言（例如C++、java、pascal等人类比较容易看的懂的）翻译成低级语言（机器语言，方便机器执行，因为机器只认识01）。
5.设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（）
A.X=(x*+0.5)/.0
B.x=(int)(x*+0.5)/.0;
C.x=(x/+0.5)*.0
D.x=x*+0.5/.0;
答案：B
解析：x的类型是float,所以（x*+0.5）也是float,也就是有小数位，需要先转黄成int格式,也就是B选项。
6.由数字1，1，2，4，8，8所组成的不同的4位数的个数是（）
A.B.C.98D.
答案：B
解析：暴力枚举
1.当取出1，1，2，4时，共有C(2,4)*2=12种；
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种。
一共种情况。
7.排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。
A.冒泡排序B.直接插入排序
C.快速排序D.归并排序
答案：C
解析：简单的判断就是基于swap的排序算法都是不稳定的。若经过排序，这些记录的相对次序保持不变，即在原序列中，r=r[j]，且r在r[j]之前，而在排序后的序列中，r仍在r[j]之前，则称这种排序算法是稳定的。快速排序在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法。
8.G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（）个顶点
A.10B.9C.11D.8
答案：B
解析：完全图边数=n*(n-1)/2。于是28条边的联通图至少需要8个点，但是本题说的是非联通图，再多加一个孤立点，8+1=9。
9.一些数字可以颠倒过来看，例如0、1、8颠倒过来看还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如颠倒过来是。假设某个城市的车牌只有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种选择，总数=5*5*1*1*1=25。
10.一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（）
A.23B.21C.20D.22
答案：A
解析：容斥原理，总满分人数=数学满分+语文满分-语文数学满分=15+12-4=23。
11.设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）
A.nB.nlognC.2nD.2n-1
答案：D
解析：一个数组被取完后就不需要比较了，所以最好情况n次最坏情况2n-1。
12.以下哪个结构可以用来存储图（）
A.栈B.二叉树C.队列D.邻接矩阵
答案：D
解析：邻接矩阵和邻接表可以存储图，其他三项都是数据结构，不是存储结构。
13.以下哪些算法不属于贪心算法？（）
A.Dijkstra算法B.Floyd算法
C.Prim算法D.Kruskal算法
答案：B
解析：Dijkstra算法需要每次选取d最小的边;Prim算法需要每次选在集合E中选取权值最小的边;kruskal剩下的所有未选取的边中,找最小边。Floyd是暴力不是贪心。
14.有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和，中间一项是，请问一下哪个数是可能的公比？（）
A.5B.3C.4D.2
答案：B
解析：设公比是p，那么2*p^(2n-2)=,2*p^(n-1)=,可以得到p^(n-1)=，由于gcd(2,)=gcd(4,)=gcd(5,)=1,所以排除2，4，5，而gcd(3,)=3，所以公比可能是3。
15.有正实数构成的数字三角形排列形式如图所示。第一行的数为a2,1，a2,2，第n行的数为an,1，an,2，…，an,n。从a1,1开始，每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1，an,2，…，an,n中某个数的路径，使得该路径上的数之和最大。
令C[j]是从a1,1到ai,j的路径上的数的最大和，并且C[0]=C[0][j]=0，则C[j]=（）
A.mac{C[i-1][j-1],C[i-1][j]}+ai,j
B.C[i-1][j-1]+C[i-1][j]
C.max{C[i-1][j-1],c[i-1][j]}+1
D.max{C[j-1],C[i-1][j]}+ai,j
答案：A
解析：数字三角形原题。每个点的只能够从C(i-1,j-1)以及C(i-1,j)过来，所以最优解肯定是从更大的那个节点到，所以结果包含max(C(i-1,j-1),C(i-1,j)),而计算的是和所以也包含aij这一项。
第二部分
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填，错误填；除特殊说明外，判断题1.5分，选择题4分，共计40分）
1.
概述：12行if判断如a比前一位小，则从i开始，否则从上次开始14行while循环找ans向后找第一个a的数12行的判断的意思是，如果后项=前项，则重新开始，否则从上项开始（蠕动）整个程序含义是找每个a后第一个大于a的位置（如果看懂，后面都很好做）
判断题
1)（1分）第16行输出ans时，ans的值一定大于i。（）
答案：错
解析：12行if成立，14行while不成立，则16行ans==i
2)（1分）程序输出的ans小于等于n。（）
答案：对
解析：13行i=n，15行ansn才会自增，所以不会超过n
3)若将第12行的“”改为“!=”，程序输出的结果不会改变。（）
答案：对
解析：其实12行直接删掉，结果也不会变，只是速度变慢而已
4)当程序执行到第16行时，若ans-i2，则a[i+1]≦a。（）
答案：对
解析：14行，由于ans是第一个大于a的，所以a[i+1]..a[ans-1]都不超过a，结论成立
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行也会一直运行到ans=n，复杂度为1+2+..+n=O(n^2)
2.
判断题
1）（1分）输入的a和b值应在[0,n-1]的范围内。（）
答案：对
解析：从初始化看，下标范围为0~n-1，所以合并范围也在此内
2)(1分)第16行改成“fa=0;”,不影响程序运行结果。（）
答案：错
解析：findRoot里用到fa[v]==v表示组长
3）若输入的a和b值均在[0,n-1]的范围内，则对于任意0≤i＜n，都有0≤fa＜n。（）
答案：对
解析：fa表示i同组的上级，下标也在0~n-1范围内
4）若输入的a和b值均在[0,n-1]的范围内，则对于任意0≤i＜n，都有1≤cnt≤n。（）
答案：错
解析：当a==b时，cnt的值翻倍，会超出n，对比第五空。
选择题
5）当n等于50时，若a、b的值都在[0,49]的范围内，且在第25行时总是不等于y，那么输出为（）
A.B.C.D.0
答案：C
解析：每两次合并x和y都不同，表示每次都是单独一个去和整体合并。此时cnt[y]增加cnt[x]的值，也就是加1。1*1+1*2+...1*49=50*49/2=
6）此程序的时间复杂度是（）
A.O(n)B.O(logn)C.O(n2)D.O(nlogn)
答案：C
解析：并查集getRoot函数没有路径压缩，单次查找最坏为O(n)。总效率为O(n^2)
3.本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别多，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x..y]是空串。t[x..y]同理。
提示：
t[0..pre-1]是s[0..i]的子序列；
t[suf+1..tlen-1]是s[i..slen-1]的子序列
判断题
1.（1分）程序输出时，suf数组满足：对任意0≤i＜slen，suf≤suf[i+1].()
答案：对
解析：suf是满足t[suf+1..tlen-1]为s[i..slen-1]子序列的最小值那么t[suf[i+1]+1...tlen-1]是s[i+1..slen-1]的子序列=t[suf[i+1]+1…tlen-1]也是s[i..slen-1]的子序列，但不是最小（最小值是suf），因此suf[i+1]=suf，单独看15到19行程序也可以直接得出这个结论
2.(2分)当t是s的子序列时，输出一定不为0.（）
答案：错
解析：可以理解题目的输出：s中删去连续多少个字母后t仍然是s的子序列；或者直接用s=t=a代入，结果是0
3.（2分）程序运行到第23行时，“j-i-1”一定不小于0.（）
答案：错
解析：第一轮执行22行时tmp=0,j=0不执行，因此这轮j-i-1就可能是负数
4（2分）当t时s的子序列时，pre数组和suf数组满足：对任意0≤i＜slen，pre＞suf[i+1].()
答案：错
解析：可以用简单的样例（如t=s=a）代入检验，也可以根据pre和suf的定义：如果t是s的子序列，那么0~pre-1，suf[i+1]+1~lent-1这部分分别是s[0~i],s[i+1~lens-1]的子序列，不会重叠，所以有pre-1suf[i+1]+1，也就是pre=suf[i+1]+1
选择题
5.若tlen=10，输出为0，则slen最小为（）
A.10B.12C.0D.1
答案：D
解析：slen是s的长度，至少需要输入一个长度的字符串，如果t不是s子序列那输出一定是0
6.若tlen=10，输出为2，则slen最下为（）
A.0B.10C.12D.1
答案：C
解析：输出是2说明s串删去两个连续元素后t仍是s的子序列，因此删去后长度至少为10，删前至少为12
第三部分
三、完善程序（单选题，每题3分，共计30分）
1（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n（1≤n≤10），以及已有经验值（≤10^7）.
接下来n行。第i行的两个整数，分别表示学习第i个技术所需的最低经验值（≤10^7），以及学会第i个技术后可获得的经验值（≤10^4）。
接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
下面的程序已O（n^2）的时间复杂完成这个问题，试补全程序。
1)①处应填（）
A.unlock＜=0
B.unlock＞=0
C.unlock==0
D.unlock==-1
答案：C
解析：unlock作用是看是否能解锁任务。根据对问题5的分析，在未解锁前它的值是还有几个依赖任务未解锁。那么解锁条件当然是0个依赖任务，因此是等于0
2)②处应填（）
A.threshold＞points
B.threshold＞=points
C.points＞threshold
D.points＞=threshold
答案：D
解析：很简单，解锁条件之二，经验点要大于等于任务的需求点
3)③处应填（）
A.target=-1
B.--cnt[target]
C.bbonus[target]
D.points+=bonus[target]
答案：D
解析：经验点增加。A肯定不对，target后面还要用。B不对，因为cnt是依赖i的任务。C也不对，bonus是只读的
4)④处应填（）
A.cnt[child[target]]-=1
B.cnt[child[target]]=0
C.unlock[child[target]]-=1
D.unlock[child[target]]=0
答案：C
解析：从前面分析看出unlock是依赖的还没解锁的任务数，解锁一个任务，所有依赖这个任务的unlock值都要减1
5)⑤处应填（）
A.unlock=cnt
B.unlock=m
C.unlock=0
D.unlock=-1
答案：B
解析：m是任务依赖的任务数，从前面代码看出当unlock为-1时表示解锁成功，那么D不对。A的话cnt此时还没完成赋值，也不对。C有迷惑性，认为unlock是布尔值，但看题目m个依赖任务完成才能解锁该任务，所以不是单纯的布尔，需要每解锁一个前置任务就将unlock减1，直到为0
2.(取石子）Alice和Bob两个人在玩取石子游戏，他们制定了n条取石子的规则，第i条规则为：如果剩余的石子个数大于等于a且大于等于b，那么她们可以取走b个石子。他们轮流取石子。如果轮到某个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n（1≤n≤64),以及石子个数m（≤10^7）。
接下来n行。第i行有两个正整数a和b。（1≤a≤10^7,1b≤64)如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b不超过，所以可以使用位无符号整数去压缩必要的状态。
Status是胜负状态的二进制压缩，trans是状态转移的二进制压缩。
试补全程序。
代码说明:
“~”表示二进制补码运算符，它将每个二进制位的0变成1、1变为0；
而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为0，反之为1。
U11标识符表示它前面的数字是unsignedlonglong类型。
解析：首先使用f(i)表示有i个石子时，是否有必胜策略。所以f(i)=!f(i-b[j1])or!f(i-b[j2])...)(a[j]=i),转换公式，status中每一位定义为win(i-j),也就是有i-j有必胜策略。因此第一题初始状态为都必输，因为石子有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.~0ullC.~0ull^1D.1
答案：C
2）处应填（）
A.a[j]iB.a[j]==iC.a[j]!=iD.a[j]i
答案：B
3)③处应填（）
A.trans
=1ull(b[j]-1)
B.status
=1ull(b[j]-1)
C.status+=1ull(b[j]-1)
D.trans+=1ull(b[j]-1)
答案：A
4)④处应填（）
A.~status
transB.status＆trans
B.status
transD.~status＆trans
答案：D
5）⑤处应填（）
A.trans=status
trans^win
B.status=trans1^win
C.trans=status^trans
win
D.status=status1^win
答案：D