一、 单项选择题
(共15题,每题2分,共计30分:每题有且仅有一个正确选项)
1. 在 Linux 系统中,如果你想显示当前工作目录的路径,应该使用哪个命令?( )
A pwd
B cd
C ls
D echo
题解: A
pwd:这个命令是“print working directory”的缩写,它的作用是显示当前工作目录的路径。
cd:这个命令是“change directory”的缩写,它的作用是切换当前工作目录。
ls:这个命令是“list”的缩写,它的作用是列出当前工作目录下的文件和文件夹。
echo:这个命令用于在终端输出指定的文本。
2. 假设一个长度为n的整数数组中每个元索值互不相同,且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?( )
A O(n)
B O(logn)
C O(nlogn)
D O(1)
题解: A
每个元索值互不相同,且这个数组是无序的,所以要逐一比较,需要比较n-1次
3. 在 C++中,以下哪个函数调用会造成溢出?( )
A int foo(){ return 0;}
B int bar(){int x=1;return x; }
C void baz(){ int a[1000];baz();)
D void qux(){ return; }
题解: C
C选项为,递归调用,没用递归出口,会造成存放函数的栈越来越多,最终程序溢出
4. 在一场比赛中,有10名选手参加、前三名将获得金、银、牌。若不允许并列、且每名
选手只能获得一枚奖牌,则不同的颁奖方式其有多少种?( )
A 120
B 720
C 504
D 1000
题解 B
题目要求不允许并列,从10名中选3名,A(10,3)=10*9*8=720
5. 下面哪个数据结构最适合实现先进先出(FIFO)的功能?( )
A 栈
B 队列
C 线性表
D 二叉搜索树
题解 B
A 栈是一种后进先出(LIFO)的数据结构,它遵循“先进后出”的原则
B 队列是一种先进先出(FIFO)的数据结构,它遵循“先进先出”的原则。在队列中,第一个进入的元素总是第一个被取出。因此,队列非常适合实现先进先出(FIFO)的功能。
C 线性表是一种基本的数据结构,它可以用来表示一系列有序的数据元素。
D 二叉搜索树是一种特殊的二叉树,它的每个节点都满足左子树的所有节点的值小于等于该节点的值,右子树的所有节点的值大于等于该节点的值
6. 已知f(1)=1.且对于n≥2有f(n)=f(n-1)+f(⌊n/2⌋),则f(4)的值为:( )
A 4
B 5
C 6
D 7
题解 B
根据递归公式计算,一般可以通过递推写表的方式
本题数据较少,可以直接计算每一项
f(1)=1
f(2)=f(1)+f(1)=2
f(3)=f(2)+f(1)=2+1=3
f(4)=f(3)+f(2)=3+2=5
7. 假设有一个包含n个顶点的无向图,且该图是欧拉图。以下关于该图的描述中哪一项不一定正确?( )
A 所有顶点的度数均为偶数
B 该图连通
C 该图存在一个欧拉回路
D 该图的边数是奇数
题解 D
A 欧拉图没有奇点,没有奇数条边,所以所有顶点的度数都是偶数
B 欧拉图可以从一点出发,遍历所有点后回到原点,所以改图是连通的
C 欧拉图可以从一点出发,遍历所有点后回到原点,形成一个回路,称为欧拉回路
D 图的边数不一定是奇数,每个点被访问一次,边数为偶数时也可以是欧拉图
8. 对数组进行二分查找的过程中,以下哪个条件必须满足?( )
A 数组必须是有序的
B 数组必须是无序的
C 数组长度必须是2的幂
D 数组中的元素必须为整数
题解 A
而非查找的前提条件是必须是有序序列,这个是二分的关键
9. 考虑一个自然数n以及一个数m,你需要计算n的逆元(即n在m意义下的乘法逆元),下列哪种算法最为适合?( )
A 使用暴力法依次尝试
B 使用扩展欧几里得算法
C 使用快速幂法
D 使用线性筛法
题解 B
逆元使用使用扩展欧几里得算法
10. 在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函效和冲突解决策略。已知某哈希表中有n个键值对,表的装载因子为a(0 < a <= 1)。在使用开放地址法解决冲突的过程中,最坏情况下查找一-个元素的时间复杂度为( )
A O(1)
B O(logn)
C O(1/(1-a))
D O(n)
题解 D
哈希表,使用哈希函数数学计算,一般时间复杂度为O(1)
如果有冲突,通过哈希函数计算后,还需要对有冲突的进行比较查找
特殊情况哈希函数都计算到一个值,就等于使用比较进行查找计算
找到对应值需要,O(n)的时间复杂度
11. 假设有一棵h层的完全二叉树,该树最多包含多少个结点?( )
A 2^h-1
B 2^(h+1)-1
C 2^h
D 2^(h+1)
题解 A
除了最下层,其他每层都饱满,最下层的结点都集中在该层最左边的若干位置上
最多是满二叉树的情况
根据满二叉树的性质,结点数
1层 2^1-1=1
2层 2^2-1=3
3层 2^3-1=7
….
h层 2^h-1
12. 设有一个10个顶点的完全图,每两个顶点之间都有一条边。有多少个长度为4的环?( )
A 120
B 210
C 630
D 5040
题解 C
从10个点选4个的排列,A(10,4)=10*9*8*7
4个点的环,每个点没有位置关系顺序,所以A(10,4)/4
环上顺时针是一个环,所以A(10,4)/2=10*9*6=630
13. 对于一个整数n。定义f(n)为n的各位数字之和。问使f(f(x))=10 的最小自然数x是多少?( )
A 29
B 199
C 299
D 399
题解 B
f(f(x))=10
数字和是10的有19,28,37,46….
需要看ABCD相关选项中,哪一个的数字和是上面的
f(29)=11
f(199)=19 -对应上面的19
f(299)=20
f(399)=21
14. 设有一个长度为n的01字符串,其中有k个1,每次操作可以交换相邻两个字符。在最坏情况下将这k个1移到字符串最右边所要的交换次数是多少? ( )
A k
B k*(k-1)/2
C (n-k) *k
D (2n-k-1)*k/2
题解 C
移动交换类似冒泡排序,最坏的情况是k个1都在左端的情况,逐一比较移动到最右端比较n-k次
需要进行k趟
所以总交换次序为(n-k)*k
15. 如图是一张包含7个顶点的有向图,如果要除其中一些边,使得从节点1到节点7没有可行路径,且删除的边数最少,请问总共有多少种可行的删除边的集合?( )
A 1
B 2
C 3
D 4
题解 D
枚举共4种可行方案
1 删除1->2 ,4->6
2 删除2->5,4->6
3 删除4->6,5->7
4 删除5->7,6->7
二、 阅读程序
(程序输入不超过数组成字符串定义的范围:判断题正确填√,错误填×;除特殊说明外, 判断题1.5分,选择题3分,共计40分)
a. 题目代码
#include <iostream>
using namespace std;
const int N=1000;
int c[N];
int logic(int x,int y) {
return (x&y)^((x^y)|(~x&y));
}
void generate(int a, int b, int *c) {
for(int i=0;i<b; i++){
c[i]=logic(a,i)%(b + 1);
}
}
void recursion(int depth,int *arr,int size){
if(depth<0||size<= 1) return;
int pivot = arr[0];
int i=0,j=size -1;
while(i<=j){
while(arr[i] < pivot) i++;
while(arr[j] < pivot) j--;
if(i<=j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j]= temp;
i++; j--;
}
}
recursion(depth-1,arr,j + 1);
recursion(depth-1,arr+i,size-i);
}
int main() {
int a,b,d;
cin >> a >> b >> d;
generate(a,b,c);
recursion(d,c,b);
for(int i=0; i < b; ++i) cout << c[i] <<" ";
cout << endl;
判断题
16. 当1000 >= d >= b时,输出的序列是有序的。( )
题解 T
17 当输入”5 5 1″时,输出为”1 1 5 5 5”( )
题解 F
18 假设数组c长度无限制,该程序所实现的算法的时间条度是0(b)的。( )
题解 F
单选题
19 函数int logic(int x,int y)的功能是( )
A 按位与
B 按位或
C 按位异或
D 以上都不是
题解 B
20 (4分)当输入为“10 100 100”时,输出的第100个数是( )
A 91
B 94
C 95
D 98
题解 C
b.
#include <iostream>
#include <string>
using namespace std;
const int P = 998244353,N=1e4+10,M=20;
int n,m;
string s;
int dp[1<<M];
int solve() {
dp[0]=1;
for(int i=0;i<n; ++i){
for(int j=(1<<(m-1))-1;j>=0;--j){
int k = (j<<1)|(s[i]-'0');
if(j|=0 || s[i]=='1') {
dp[k]=(dp[k]+dp[j])%P;
}
}
}
int ans = 0;
for(int i=0; i<(1<<m);++i){
ans = (ans + 1ll*i*dp[i])%P;
}
return ans;
}
int solve2 {
int ans =0;
for(int i=0;i<(1<<n);++i){
int cnt = 0;
int num = 0;
for(int j=0; j<n;++j) {
if(i&(1<<j)) {
num = num*2+(s[j] - '0');
cnt++;
}
}
if(cnt <= m)(ans += num)%=p;
}
return ans;
}
int main(){
cin >> n >> m;
cin >> s;
if(n<=20) {
count << solve2 << endl;
}
count << solve() << endl;
return0;
}
假设输入的s是包含 n个字符的 01串,完成下面的判断题和单选题
判断题
21. 假设数组 dp 长度无限制,函数solve()所实现的算法时间复杂度是 O(n*2^m) ( )
题解 T
22. 输入“11 2 10000000001”时,程序输出两个数32和23 ( )
题解 T
23. (2分)在 n<=10 时,solve()的返回值始终小于 4^10 ( ) 题解 T
单选题
24 当n=10 且 m=10 时,有多少种输入使得两行的结果完全一致? (
A 1024
B 11
C 10
D 0
题解 B
25 当n<=6 时,solve()的最大可能返回值为 ( ) A 65 B 211 C 665 D 2059 题解 C
26 若n=8,m=8,solve和solve2的返回值的最大可能的差值为 ( )
A 1477
B 1995
C 2059
D 2187
题解 C
c.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 5;
const int P1 = 998244353,P2 = 1000000007;
const int B1 = 2,B2 = 31;
const int K1 = 0,K2 = 13;
typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];
struct H {
int h1,h2,l;
H(bool b = false) {
h1 = b + K1;
h2 = b+ K2;
l= 1;
}
H operator + (const H &h)const {
H hh;
hh.l =l+ h.l;
hh.h1 = (1ll * h1 * p1[h.l] + h.h1)% P1;
hh.h2 = (1ll *h2* p2[h.l]+ h.h2)% P2;
return hh;
}
bool operator == (const H &h) const {
return l== h.l && h1 == h.h1 && h2 == h.h2;
}
bool operator < (const H &h) const {
if (l != h.l)return l < h.l;
else if (h1 != h.h1)return h1 < h.h1;
else return h2 < h.h2;
}
}h[maxn];
void init() {
memset(p, 1, sizeof(p));
p[0]= p[1]= false;
p1[0]= p2[0]= 1;
for (int i= 1;i<= n; i++){
p1[i]=(1ll*B1*p1[i-1])% P1;
p2[i]=(1ll * B2 *p2[i-1])% P2;
if (!p[i])continue;
for (int j= 2*i;j<= n;j+= i){
p[j] = false;
}
}
}
int solve(){
for(inti=n;i;i--){
h[i] = H(p[i]);
if (2*i+1<= n){
h[i] = h[2 *i]+ h[i] + h[2 *i+ 1];
} else if (2 *i<= n){
h[i] = h[2 * i] + h[i];
}
}
cout << h[1].h1 << endl;
sort(h + 1,h +n+ 1);
int m=unique(h+1,h+n+1)-(h + 1);
return m;
}
int main() {
cin>>n;
init();
cout << solve() << endl;
}
判断题
27. 假设程序运行前能自动将 maxn 改为 n+1,所实现的算法的时间复杂度是O(nlogn) ( )
题解 T
28. 时间开销的瓶颈是init()函数( )
题解 F
29. 若修改常数 B1 或 K1 的值,该程序可能会输出不同呢的结果( )
题解 T
单选题
30. 在 solve()函数中,h[]的合并顺序可以看作是( ) A 二叉树的 BFS 序
B 二叉树的先序遍历
C 二叉树的中序遍历
D 二叉树的后序遍历
题解 C
31. 输入10 ,输出的第1行是( )
A 83
B 424
C 54
D 110101000
题解 A
32. (4分)输入16 ,输出的第2行是( )
A 7
B 9
C 10
D 12
题解 C
三、完善程序
(单选题,每小题3分,共计 3 分)
1序列合并
有两个长度为N的单调不降序列 A和 B,序列的每个元素都是小于10^9 的非负整数。在A和B中各取一个 数相加可以得到N^2个和,求其中第k小的和。上述参数满足 N <= 10^5 和1 <= K <= N^2。
试补全程序。
[code title=cpp]
#include <iostream>
using namespace std;
const int maxn = 100005;
int n;
long long k;
int a[maxn], b[maxn];
int *upper_bound(int *a, int *an, int ai){
int l=0,r= (1);
while (l < r) {
int mid =(l +r) >> 1;
if( (2) ){
r = mid;
} else {
l= mid + 1;
}
}
return (3);
}
long long get_rank(int sum) {
long long rank = 0;
for (int i = 0;i < n; i++){
rank += upper_bound(b, b + n, sum - a[i])- b;
}
return rank;
}
int solve() {
int l= 0,r= (4);
while (l < r) {
int mid = ((long long)l + r) >> 1;
if( (5) ) {
l= mid + 1;
} else {
r = mid;
}
}
return l;
}
int main(){
cin >> n >> k;
for (int i= 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
cout << solve() << endl;
return 0;
}
[/code]
33. 1处应该填写( )
A an-a
B an-a-1
C ai
D ai+1
题解 A
34. 2处应该填写( )
A a[mid] > ai
B a[mid] >= ai
C a[mid] < ai
D a[mid] <= ai
题解 A
35. 3处应该填写( )
A a+l
B a+l+1
C a+l-1
D an-l
题解 A
36. 4处应该填写( )
A a[n-1]+b[n-1]
B a[n]+b[n]
C 2*maxn
D maxn
题解 A
37. 5处应该填写( )
A get_rank(mid) < k
B get_rank(mid) <= k
C get_rank(mid) > k
D get _rank(mid) >= k
题解 A
2 次短路
已知一个n个点m条边的有向图 G,并且给定图中的两个点s和t,求次短路(长度严格大于最短路的最短 路径)。如果不存在,输出一行“-1”。如果存在,输出两行,第一行表示次短路的长度,第二行表示次短 路的一个方案
试补全程序
#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
const int maxn=2e5 +10,maxm=1e6+ 10,inf=522133279;
int n, m, s, t;
int head[maxn],nxt[maxm], to[maxm],w[maxm], tot = 1;
int dis[maxn << 1],*dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];
void add(int a, int b, int c) {
++tot;
nxt[tot] = head[a];
to[tot] = b;
w[tot] = c;
head[a] = tot;
}
bool upd (int a, int b, int d, priority_queue<pair < int, int> > &q) {
if (d >= dis[b])return false;
if (b < n) (1);
q.push( (2) );
dis[b] = d;
pre[b] = a;
return true;
}
void solve() {
priority_queue<pair<int, int> >q;
q.push(make_pair(0, s));
memset(dis, (3),sizeof(dis));
memset(pre, -1, sizeof(pre));
dis2 = dis + n;
pre2 = pre + n;
dis[s] = 0;
while (!q.empty()){
int aa = q.top().second; q.pop();
if (vis[aa])continue;
vis[aa] = true;
int a = aa % n;
for (int e = head[a]; e ; e = nxt[e]){
int b = to[e],c = w[e];
if (aa < n) {
if (!upd(a, b, dis[a]+ c, q))
(4);
} else {
upd(n + a, n + b, dis2[a] + c, q);
}
}
}
}
void out(int a){
if (a != s) {
if (a < n)out(pre[a]);
else out( 5);
}
printf("%d%c", a %n + 1, " \n"[a == n + t]);
}
int main(){
scanf("%d%d%d%d", &n, &m,&s,&t);
s--,t--;
for (int i = 0; i < m; ++i){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a -1,b -1,c);
}
solve();
if (dis2[t]==inf)puts("-1");
else {
printf("%d\n", dis2[t]);
out(n + t);
}
return 0;
}
38. 1处应填( )
A upd(pre[b], n+b, dis[b], q)
B upd(a, n+b, d, q)
C upd(pre[b], b, dis[b], q)
D upd(a, b, d, q)
题解 A
39. 2处应填( )
A make_pair(-d, b)
B make_pair(d, b)
C make_pair(b, d)
D make_pair(-b, d)
题解 A
40. 3处应填( ) A 0xff
B 0x1f
C 0x3f
D 0x7f
题解 B
41. 4处应填( )
A upd(a, n+b, dis[a]+c, q)
B upd(n+a, n+b, dis2[a]+c, q)
C upd(n+a, b, dis2[a]+c, q)
D upd(a, b, dis[a]+c, q)
题解 A
42. 5处应填( )
A pre2[a%n]
B pre[a%n]
C pre2[a]
D pre[a%n]+1
题解 A