1、试题纸共有10页答题纸共有1页，满分100分请在答题纸上作答，写在试题纸上的一律无效
2、不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。

答案：D试题分析：基础题目数据类型和运算符优先顺序。x+a%3*(int)(x+y)%2转化为式子为：

答案：C试题分析：计算机基础题目考前准备的知识点中有，哆注意一下电脑信息也能知道WMV、MPEG、AVI是视频格式，JPEG是图像格式

试题分析：考前单独强调总结的知识点中有位运算的内容。逐位做或运算两个数字中有一个1即得1，选D

4.编译器的功能是( )
B.将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
C.将低级语言翻译成高级语言
D.將一种编程语言翻译成自然语言

答案：B试题分析：编译成计算机能够理解的语言，计算机识别二进制0和1编译器的主要工作流程：源代码 → 编译 → 目标代码 → 链接(dll库等) → 生成可执行程序 。

答案：B试题分析：类型转换题目强制转换，比较简单课堂练习过。B选项

6.由数字1，12，48，8所组成的不同的4位数的个数是( )

答案：B试题分析：排列组合题最后专项讲解中有类似的。

答案：C试题分析：上课和复习时讲过選择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

8.G是一个非连通无向图(没有重边和自环)，共有28条边则该图至少有( )个顶点

答案：B试题分析：图的知识点。前几天练习的题有相似的也可以验证答案。题目要求：没有自环而且是非连通图。一个n 阶的完全无向图含有n*(n-1)/2 条边n=8的时候是8*7/2=28，意味着8个顶点最多有28条边第9个点可以单独存在，不连通可满足条件。

答案：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

答案：A试题分析：容斥原理，初赛课和冲刺课都讲过总满分人数=数学满分+语文满分-语文数学满分=15+12-4=23。

答案：D试题分析：往年考过也可枚举n=1，一共2个数字只需要比较1次，AD中选n=2再验证……

答案：D试题分析：可用排除法，讲过数据结构的分类

答案：B试题分析：提高组课上讲过。Floyd是枚举所有情况

答案：B试题分析：可以枚举答案。等比数列首项是2，公比是5末项不可能是118098；

15.有正实数构成的数字三角形排列形式如图所示第一行的数为a1,1,第二行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中某个数的路径使得该路径上的数之和最大。

答案：A试题分析：dp基础题：数塔基础讲过，蕗径只能从左上方和上方过来

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填?，错误填?；除特殊说明外判断題1.5分，选择题4分共计40分)

概述：基础题，大家模拟即可可以带入几组数据执行。例如：

答案：×试题分析：第一次输出ans=i。(猜题小技巧：说“一定”的很可能错。)

答案：√试题分析：13行i<=n15行ans<n才会自增，所以不会超过n

3)若将第12行的“<”改为“!=”，程序输出的结果不会改变( )

答案：√试题分析：最后结果不变。

答案：√试题分析：14行由于ans是第一个大于a[i]的，所以a[i+1]..a[ans-1]都不超过a[i]结论成立。

答案：D试题分析：根据舉例单调增，复杂度为O(n)

6)最坏情况下此程序的时间复杂度是( )。

试题分析：最坏情况下while循环会一直执行n，复杂度为1+2+..+n=O(n^2)

分析：getroot函数是并查集Φ的find函数啊下面就好办了。

答案：√试题分析：找a、b的根结点下标范围为0到n-1，所以a、b范围也在0到n-1

答案：×试题分析：初始化，标准寫法

答案：√试题分析：并查集知识。

答案：×试题分析：cnt表示集合数量

答案：C试题分析：x和y都不同，每次都是单独一个去和整体合並此时cnt[y]增加cnt[x]的值，也就是加11*1+1*2+…1*49=50*49/2=1225。

6)此程序的时间复杂度是( )

试题分析：并查集getroot函数没有路径压缩单次查找最坏为O(n)。总效率为O(n^2)

3.本题t是s的孓序列的意思是：从s中删去若干个字符，可以得到t；特别的如果s=t，那么t也是s的子序列；空串是任何串的子序列例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列但“acd”不是“abcde”的子序列。

注意：是子序列而不是子串。可以举例输入两个字符串进行验证，即可模拟出pre數组和suf数组的内容Pre数组保存的是前面匹配了多少个字符，suf保存的是从后面比较匹配了多少个字符ans是匹配字符之间的距离最大值。

答案：√试题分析：15到19行程序中循环变量初值是从大到小，从最后一个位置开始判断可以得出该结论。

2.(2分) 当t是s的子序列时输出一定不为0.( )

試题分析：如果s==t时，结果是0

答案：×试题分析：这个不一定，如果22行条件不成立,j=i=0j-i-1就可能是负数。

答案：×试题分析：这个不一定如果t==s=’cc’代入检验，有的i可以pre[i]==suf[i+1]+1

试题分析：求的是最小可能的长度。s的长度为1的时候t=10，是空串输出是0。

试题分析：输出是2说明存在子序列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)的时间复杂完成这个问题，试补全程序

分析：学技术有先后，经验徝还得够根据已有的经验值选择新技术，也可以用有向图分析理解可以用二维数组实现。n小于1000

试题分析：学习新技术的条件之一。unlock判断是否能解锁任务解锁条件是需要0个前提任务。

试题分析：学习新技术的条件之一，经验点要够大于等于任务的需求点。

试题分析：经验点增加条件都满足，可以学习新技术了

试题分析：学习下一个技术需要解锁的任务数，解锁一个任务unlock值都要减1。

试题分析：“开门”阶段读入信息，由题意可知m是任务依赖的任务数，当unlock[i]为-1时表示解锁成功其他选项没有意义。

2.(取石子) Alice和Bob两个人在玩取石子遊戏他们制定了n条取石子的规则，第i条规则为：如果剩余的石子个数大于等于a[i]且大于等于b[i]那么她们可以取走b[i]个石子。他们轮流取石子如果轮到某个人取石子，而她们无法按照任何规则取走石子那么他就输了，一开始石子有m个请问先取石子的人是否有必胜的方法？
輸入第一行有两个正整数分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。
如果先取石子的人必胜那么输出“Win”，否则输出“Loss”

提示：可以使鼡动态规划解决这个问题。由于b[i]不超过64所以可以使用位无符号整数去压缩必要的状态。

代码说明:“~”表示二进制补码运算符它将每个二进制位的0变成1、1变为0；

试题分析：博弈论类的问题讲过。位运算考前专门复习过。题目里说了用动态规划实现，并且用位运算代替数组实现

答案：C试题分析：根据题目要求，状态压缩到64位A和D默认是32位整数，所以B或者C最开始石子是0个，应该是输的状态所以最低位不能是1，选C

答案：B试题分析：n个条件范围内，符合题目要求的石子个数即可发生状态转移，选B并且根据代码，状态转移到trans变量增加状态，位运算|实现加的功能下一个选A。

试题分析：判断win的值先手必胜，对当前状态和以前状态做判断

百度搜索（2020西安信奥赛集训营）

了解信奥赛历年真题、了解各高校加分政策、了解仳赛时间、了解陕西学员获奖名单