cspj-模拟题15

ID: 66

Type: Objective

Tried: 0

Accepted: 0

Difficulty: (None)

Uploaded By:

jike1994

Tags>

2024

睿爸信奥考前模拟

一、单项选择题 (共15题，每题2分，共计30分；每题有且仅有一个正确选项)

字符D的ASCII码为68, 则字符Q的ASCII码是: ({{ select(1) }})

81
82
83
视具体的计算机而定

比120大的最小素数是({{ select(2) }})。

以下程序段执行完毕后，i和s的值分别是({{ select(3) }})
```
int i, s = 0;
for (i = 1; i <= 5; i = i + 2)
    s = s + i;
```

5 和 7
5 和 9
7 和 9
9 和 7

4.十进制数0.5与八进制数({{ select(4) }})值相等。

5.下列各种说法中，正确的是({{ select(5) }})。

计算机通过ip地址来访问网络中的其他设备。
家里的千兆宽带的带宽为1000Mbps, 下载最高速度是1000MB/S。
常见的计算机网络操作系统包括Unix、Linux、Android等。
开源软件可以自由地进行复制、修改和传播，不需要得到授权。

6.甲乙丙丁四个人被安排完成三份工作，每份工作至少需要一个人完成，且一个人只能去完成一份工作，甲乙有矛盾不能完成同一份工作，有多少种合理的安排方式?({{ select(6) }})。

7.我们称质因数中只含有3和5的正整数为“好数”，将所有好数从小到大排列组成数列3,5,9,15,25,…, 那么第10个好数是({{ select(7) }})。

8.一棵二叉树的中序遍历为DGBAECHF, 后序遍历为GDBEHFCA, 则前序遍历是({{ select(8) }})。

ABCDFGHE
ABDGCEFH
ACBGDHEF
ACEFHBGD

9.设A=true, B=false, C=true, D=false, 以下逻辑运算表达式值为真的是({{ select(9) }})。

(B∨C∨D)∧D∧A
((¬A∧B)∨C)∧¬D
(A∧B)∨(C∧D∨¬A)
A∧(D∨¬C)∧B

10.一棵树T有2个度数为2的结点、有1个度数为3的结点、有3个度数为4的结点，那么树T有({{ select(10) }})个树叶。

11.学号为1到30的小朋友顺时针排成一圈，从1号小朋友开始顺时针报数，从数1开始数下去,1, 2, 3, …, 28, 29, 30, 31, 32, 一圈又一圈, 问当数到数字n, 所在的小朋友的学号为多少?({{ select(11) }})。

(n+1)%30-1
(n-1)%30
1+(n-1)%30
(n+1)%30

12.徐老师拥有面值为1、2、…、100共一百枚硬币，他可以从中选出若干枚硬币来组成1~100的所有面值，那么徐老师最少需要选取({{ select(12) }})枚硬币。

13.数位之和为10的四位数有({{ select(13) }})种。

14.假设我们用d=(a1, a2…, a₅), 表示无向图G的5个顶点的度数, 下面给出的哪组d值合理 ({{ select(14) }})。

{1, 2, 2, 1, 1}
{5, 4, 3, 2, 1}
{2, 2, 2, 2, 2}
{3, 3, 3, 2, 2}

15.双向链表中有两个指针域 llink 和 rlink，分别指向该结点的前驱和后继。设 p 指向链表中的一个结点，它的左右结点均非空。现要求删除结点 p，则下面语句序列中错误的是({{ select(15) }})。

p-> rlink-> llink=p-> rlink;p-> llink-> rlink=p-> llink; delete(p)
p-> llink-> rlink=p-> rlink;p-> rlink-> llink=p-> llink; delete(p)
p-> rlink-> llink=p-> llink;p-> rlink-> llink-> rlink=p-> rlink; delete(p)
p-> llink-> rlink=p-> rlink;p-> llink-> rlink-> llink=p-> llink; delete(p)

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

第一小题

#include <bits/stdc++.h>
using namespace std;
int n;
int cnt;
int f(int n) {
   if (n == 1 || n == 2) {
       return 1;
   }
   cnt++;
   return f(n - 1) + f(n - 2) + 1;
}
int main(){
    cnt = 0;
    cin >> n;
    f(n);
    cout << cnt << endl;
    return 0;
}

16.cnt表示f函数被调用的次数。({{ select(16) }})

17.若输入3, 则输出3。({{ select(17) }})

18.该程序中 cnt=0可以删掉, 输出结果不变。({{ select(18) }})

19.在代码执行过程中，可能会多次调用f(3)。({{ select(19) }})

20.若输入20, 输出 ({{ select(20) }})。

192
13529
6764
20

21.若将 cnt++;移动到 if里的 return 1;之前,输入20, 输出 ({{ select(21) }})。

6763
13529
6766
6765

第二小题

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int height[N], num[N], n, ans;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
       cin >> height[i];
       num[i] = 1;
       for (int j = 0; j < i; j++) {
          if ((height[j] < height[i]) && (num[j] >= num[i]))
               num[i] = num[j] + 1;
       }
    }
    ans = 0;
    for (int i = 0; i < n; i++) {
       if (num[i] > ans) ans = num[i];
    }
    cout << ans << endl;
    return 0;
}

22.如果程序运行正常，n最大可以取99。({{ select(22) }})

23.程序功能：输入长度为n的整数序列，求最长上升子序列的长度。({{ select(23) }})

24.若将 for (int j = 0; j < i; j++) 改为 for (int j = 0; j <= i; j++) , 程序运行时会发生错误。({{ select(24) }})

25.本程序的时间复杂度为({{ select(25) }})。

O(n)
O(n^2)
O(nlogn)
O(logn)

26.若输入

6
2 5 3 11 12 4

则输出为({{ select(26) }})。

27.若输入

5
2 3 4 5 6

则 num[i] = num[j] + 1; 执行({{ select(27) }})次。

第三小题

#include <bits/stdc++.h>
using namespace std;

#define N 1010
int n, m, f[N][N];
int maxx = 0;
char c;
struct node {
    int len, h;
} a[N];
stack<node> S;

void ask(int x) {
   memset(a, 0, sizeof(a));
   a[1].h = f[x][1], a[1].len = 1;
   while (S.size()) S.pop();
   S.push(a[1]); //初始化
   for (int i = 2; i <= m; i++) {
       int w = 0;
       while (S.size() && f[x][i] <= S.top().h) { //需要弹栈
          w += S.top().len;
          maxx = max(maxx, w * S.top().h);
          S.pop(); //更新答案并弹栈
      }
      a[i].h = f[x][i], a[i].len = w + 1; //已入栈的比他高的矩形个数加1
      S.push(a[i]);
  }
  int w = 0;
  while (S.size()) { //用剩余矩形更新答案
      w += S.top().len;
      maxx = max(maxx, S.top().h * w);
      S.pop();
  }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
       for (int j = 1; j <= m; j++) {
            cin >> c;
            if (c == 'F') f[i][j] = f[i - 1][j] + 1;
       }
    for (int i = 1; i <= n; i++) ask(i); //解决子问题
    cout << maxx << endl;
    return 0;
}

28.若删除第14行, 程序结果不变。({{ select(28) }})

29.若删除第16行, 程序结果不变。({{ select(29) }})

30.若将第6行改为 int maxx = -1; 程序结果可能会产生错误。({{ select(30) }})

31.单次 ask 函数的时间复杂度是 O(m)。({{ select(31) }})

32.若输入为：

3 4
FXFX
FFFX
XFFX

输出为({{ select(32) }})。

33.若输入为：

3 4
FXFX
FFFF
XFFF

maxx变化了({{ select(33) }})次。

三、完善程序 (单选题，每小题3分，共计30分)

第一小题

（链表反转）单向链表反转是一道经典算法问题，比如有一个链表是这样的, 1-> 2->3-> 4->5, 反转后成为 5->4->3->2->1。现给定如下链表节点的定义：

struct Node {
     int value;
     Node* next;
};

非递归实现：

 Node* Reverse(Node* header) {
     if (header == NULL || header->next == NULL) {
         return header;
     }
     Node *pre = header, *cur = header->next;
     pre->next = NULL;
     while (cur != NULL) {
         Node* next = ①;
         ② = pre;
         pre = cur;
         cur = next;
     }
     return pre;
  }

递归实现：

Node* Reverse(Node* head) {
     if (head == NULL || head->next == NULL) {
         return head;
     }
     Node* newhead = ③;
     ④ = head;
     head->next = ⑤;
     return newhead;
}

34.① 中应填 ({{ select(34) }})

pre->next
cur->next
header->next
NULL

35.② 中应填 ({{ select(35) }})

pre->next
cur->next
header->next
NULL

36.③ 中应填 ({{ select(36) }})

Reverse(head)
Reverse(pre)
Reverse(cur)
Reverse(head->next)

37.④ 中应填 ({{ select(37) }})

pre->next->next
cur->next->next
head->next->next
NULL

38.⑤ 中应填 ({{ select(38) }})

pre->next
cur->next
head->next
NULL

第二小题

（距离统计）请完善下面的程序，使用BFS统计一张边权都为1 的图中，从给定起点到所有点的距离：

 #include <algorithm>
 #include <cstdio>
 #include <vector>
 #define N 200020
 using namespace std;
 int n, m;
 vector<int> G[N];
 int q[N], hd, t1;
 int dis[N];
 void BFS(①) {
     hd = 1, t1 = 0;
     for (int i = 1; i <= n; i++) dis[i] = -1;
     q[++t1] = st, dis[st] = 0;
     while (②) {
         int u = q[hd++];
         for (int i = 0; i < G[u].size(); i++) {
             int v = G[u][i];
             if (③) continue;
             dis[v] = dis[u] + 1;
             q[++t1] = v;
         }
     }
 }
 int main() {
     scanf("%d%d", &n, &m); // 输入点n和边m
     for (int i = 1; i <= m; i++) {
         int x, y;
         scanf("%d%d", &x, &y); // 输入x到y 一条无向边
         G[x].push_back(y);
         ④;
     }
     int st; // 起点
     scanf("%d", &st);
     BFS(st);
     for (⑤) printf("%d ", dis[i]);
 }

39.① 处应填 ({{ select(39) }})

int u
int *st
int &st
int st

40.② 处应填 ({{ select(40) }})

hd < t1
hd > t1
hd <= t1
hd >= t1

41.③ 处应填 ({{ select(41) }})

dis[v] != -1
dis[v] <= dis[u]
dis[v] > dis[u]
vis[v] == true

42.④ 处应填 ({{ select(42) }})

G[y].push_back(x)
G[y].insert(x)
G[y][x] = 1
G[y].push(x)

43.⑤ 处应填 ({{ select(43) }})

int i = 1; i <= n; i++
int i = 0; i < n; i++
int i = 1, i <= n, i++
int j = 1; j <= n; j++

#ACSP1015. cspj-模拟题15

一、单项选择题 (共15题，每题2分，共计30分；每题有且仅有一个正确选项)

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

第一小题

第二小题

第三小题

三、完善程序 (单选题，每小题3分，共计30分)

第一小题

第二小题

Status

Development

Support

#ACSP1015. cspj-模拟题15

cspj-模拟题15

一、单项选择题 (共15题，每题2分，共计30分；每题有且仅有一个正确选项)

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

第一小题

第二小题

第三小题

三、完善程序 (单选题，每小题3分，共计30分)

第一小题

第二小题

Status

Development

Support

SIGN IN