若有定义:int a=7; float x=2.5, y=4.7;则表达式x+a%3*(int)(x+y)%2的值是:( )
0.000000
2.750000
2.500000
3.500000
5
3
4
2
Di jkstra算法
Floyd算法
Prim算法
Kruskal算法
以下哪个结构可以用来存储图( )
栈
二叉树
队列
邻接矩阵
设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较 作为基本运算的归并算法,在最坏情况下至少要做多少次比较?( )
n2
nlogn
2n
2n-1
23
21
20
22
一些数字可以颠倒过来看,例如0、1、8颠倒过来看还是本身,6颠倒过来是9,9颠倒过来看还 是6,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如106颠倒过来 是901。假设某个城市的车牌只有5位数字,每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰 好还是原来的车牌,并且车牌上的5位数能被3整除?( )
40
25
30
20
G是一个非连通无向图(没有重边和自环),共有28条边,则该图至少有( )个顶点
10
9
11
8
排序的算法很多,若按排序的稳定性和不稳定性分类,则( )是不稳定排序。
冒泡排序
直接插入排序
快速排序
归并排序
由数字1,1,2,4,8,8所组成的不同的4位数的个数是( )
104
102
98
100
设变量x为float型且已赋值,则以下语句中能将x中的数值保留到小数点后两位,并将第三位四舍五入的是( )
X=(x*100+0.5)/100.0
x=(int)(x*100+0.5)/100.0
x=(x/100+0.5)*100.0
x=x*100+0.5/100.0
编译器的功能是( )
将源程序重新组合
将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
将低级语言翻译成高级语言
将一种编程语言翻译成自然语言
二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是( )
11 1111 1101
11 1111 1111 1101
0 1111 1111 1111
11 1111 1111 1111
下列属于图像文件格式的有( )
WMV
MPEG
.JPEG
AVI
有正实数构成的数字三角形排列形式如图所示。第一行的数为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[i][j]是从a1,1到ai,j的路径上的数的最大和,并且 C[i][0]= C[0][j]=0,则C[i][j]=( )
mac{C[i-1][j-1],C[i-1][j]}+ ai,j
C[i-1][j-1]+C[i-1][j]
max{C[i-1][j-1],c[i-1][j]}+1
max{C[i][j-1],C[i-1][j]}+ ai,j
2019年CSP-S1提高组初赛阅读程序题:
#include <cstdio> using namespace std; int n; int a[100]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); int ans = 1; for (int i = 1; i <= n; ++i) { if (i > 1 && a[i] < a[i - 1]) ans = i; while (ans < n && a[i] >= a[ans + 1]) ++ans; printf("%d\n", ans); } return 0; }
第16行输出ans时,ans的值一定大于i。( )
程序输出的ans小于等于n。( )
若将第12行的“<”改为“!=”,程序输出的结果不会改变。( )
当程序执行到第16行时,若ans-i>2,则a[i+1]≦a[i]。( )
若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )。
0(log n)
0(n2)
0(nlog n)
0(n)
最坏情况下,此程序的时间复杂度是( )。
0(n2)
0(log n)
0(n)
0(nlog n)
2019年CSP-S1提高组初赛阅读程序题:
#include <iostream> using namespace std; const int maxn = 1000; int n; int fa[maxn], cnt[maxn]; int getRoot(int v) { if (fa[v] == v) return v; return getRoot(fa[v]); } int main() { cin >> n; for (int i = 0; i < n; ++i) { fa[i] = i; cnt[i] = 1; } int ans = 0; for (int i = 0; i < n - 1; ++i) { int a, b, x, y; cin >> a >> b; x = getRoot(a); y = getRoot(b); ans += cnt[x] * cnt[y]; fa[x] = y; cnt[y] += cnt[x]; } cout << ans << endl; return 0; }
输入的a和b值应在[0,n-1]的范围内。( )
第16行改成“fa[i]=0;”, 不影响程序运行结果。( )
1276
1176
1225
1250
此程序的时间复杂度是( )
O(n)
O(log n)
O(n^2)
O(n log n)
2019年CSP-S1提高组初赛阅读程序题:t是s的子序列的意思是:从s中删去若干个字符,可以得到t;特别的,如果s=t,那么t也是s的子序列;空串是任何串的子序列。例如:"acd"是“abcde”的子序列,“acd"是“acd”的子序列,但"adc” 不是“abcde”的子序列。
s[x..y]表示s[x] ...s[y]共y-x+l个字符构成的字符串,若x>y则 s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> using namespace std; const int max1 = 202; string s, t; int pre[max1], suf[max1]; int main() { cin >> s >> t; int slen = s.length(), tlen = t.length(); for (int i = 0, j = 0; i < slen; ++i) { if (j < tlen && s[i] == t[j]) ++j; pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列 } for (int i = slen - 1 , j = tlen - 1; i >= 0; --i) { if(j >= 0 && s[i] == t [j]) --j; suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列 } suf[slen] = tlen -1; int ans = 0; for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){ while(j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列; t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列
程序输出时,suf数组满足:对任意0≤i<slen,suf[i] ≤suf[i+1].( )
当t是s的子序列时,输出一定不为0.( )
程序运行到第23行时,“j-i-1”一定不小于0.( )
当t时s的子序列时,pre数组和suf数组满足:对任意0≤i<slen,pre[i]>suf[i+1].( )
若tlen=10,输出为0,则slen最小为( )
10
12
0
1
若tlen=10,输出为2,则slen最小为( )
0
10
12
1
(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的 经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的 值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个 新技术。
输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤10^7). 接下来n行。第i行的两个整数,分别表示学习第i个技术所需的最低经验值(≤10^7),以及学会第i个技 术后可获得的经验值(≤10^4)。 接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的 数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已O(n^2)的时间复杂完成这个问题,试补全程序。
#include<cstdio> using namespace std; const int maxn = 1001; int n; int cnt[maxn]; int child [maxn][maxn]; int unlock[maxn]; int points; int threshold[maxn], bonus[maxn]; bool find(){ int target = -1; for (int i = 1; i <= n; ++i) if(① && ②){ target = i; break; } if(target == -1) return false; unlock[target] = -1; ③ for (int i = 0; i < cnt[target]; ++i) ④ return true; } int main(){ scanf("%d%d", &n, &points); for (int i = 1; i <= n; ++i){ cnt[i] = 0; scanf("%d%d", &threshold[i], &bonus[i]); } for (int i = 1; i <= n; ++i){ int m; scanf("%d", &m); ⑤ for (int j = 0; j < m; ++j){ int fa; scanf("%d", &fa); child[fa][cnt[fa]] = i; ++cnt[fa]; } } int ans = 0; while(find()) ++ans; printf("%d\n", ans); return 0; }
1处应填( )
unlock[i]<=0
unlock[i]>=0
unlock[i]==0
unlock[i]==-1
②处应填( )
threshold[i]>points
threshold[i]>=points
points>threshold[i]
points>=threshold[i]
③处应填( )
target = -1
- -cnt[target]
bbonus[target]
points += bonus[target]
④处应填( )
cnt [child[target][i]] -=1
cnt [child[target][i]] =0
unlock[child[target][i]] -= 1
unlock[child[target][i]] =0
⑤处应填( )
unlock[i] = cnt[i]
unlock[i] =m
unlock[i] = 0
unlock[i] =-1
(取石子) Alice和Bob两个人在玩取石子游戏,他们制定了n条取石子的规则,第i条规则为:如果剩 余的石子个数大于等于a[i]且大于等于b[i],那么她们可以取走b[i]个石子。他们轮流取石子。如果轮到某 个人取石子,而她们无法按照任何规则取走石子,那么他就输了,一开始石子有m个。请问先取石子的 人是否有必胜的方法?
输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。 接下来n行。第i行有两个正整数a[i]和b[i]。(1≤a[i]≤10^7,1b[i]≤64) 如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”
提示: 可以使用动态规划解决这个问题。由于b[i]不超过,所以可以使用位无符号整数去压缩必要的状态。 Status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。
试补全程序。
代码说明:
“~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0; 而“^”表示二进制异或运算符,它将两个参与运算的数重的每个对应的二进制位一一进行比较,若两个二 进制位相同,则运算结果的对应二进制位为0,反之为1。
U11标识符表示它前面的数字是unsigned long long 类型。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include <cstdio> #include<algorithm> using namespace std; const int maxn = 64; int n, m; int a[maxn], b[maxn]; unsigned long long status, trans; bool win; int main(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]); for(int i = 0; i < n; ++i) for(int j = i + 1; j < n; ++j) if (aa[i] > a[j]){ swap(a[i], a[j]); swap(b[i], b[j]); } status = ①; trans = 0; for(int i = 1, j = 0; i <= m; ++i){ while (j < n && ②){ ③; ++j; } win = ④; ⑤; } puts(win ? "Win" : "Loss"); return 0; }
0
~0ull
~0ull^1
1