一、 单项选择题

（共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