#C1211. CSP-J 初赛模拟题1

CSP-J 初赛模拟题1

一、单项选择题

（共15题，每题2分，共计30 分；每题有且仅有一个正确选项）

【第 1 题】

以下断电后仍能保存数据的有（ ）。 {{ select(1) }}

  • 硬盘
  • 高速缓存
  • 显存
  • RAM

【第 2 题】

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

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

【第 3 题】

计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。

{{ select(3) }}

  • ROM 和 RAM
  • CPU
  • ROM
  • RAM

【第 4 题】

在以下各项中，（ ）不是操作系统软件。 {{ select(4) }}

  • Solaris
  • Linux
  • Windows Vista
  • Sybase

【第 5 题】

设栈 S 的初始状态为空，元素 a,b,c,d,e,f 依次入栈 S，出栈的序列为 b,d,f,e,c,a，则栈 S 的容量至少应该是（ ）。 {{ select(5) }}

  • 6
  • 5
  • 4
  • 3

【第 6 题】

对有序数组 {5,13,19,21,37,56,64,75,88,92,100} 进行二分查找，成功查找元素 19 的查找长度（比较次数）是（ ）。 {{ select(6) }}

  • 1
  • 2
  • 3
  • 4

【第 7 题】

面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（ ）。 {{ select(7) }}

  • 面向对象程序设计通常采用自顶向下设计方法进行设计。
  • 面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。
  • 支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有 C++、JAVA、C# 等。
  • 面向对象的程序设计的雏形来自于 Simula 语言，后来在 SmallTalk 语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk 语言仍然被视为面向对象语言的基础。

【第 8 题】

在 32×32 点阵的"字库"中，汉字"北"与"京"的字模占用字节数之和（ ）。 {{ select(8) }}

  • 512
  • 256
  • 384
  • 128

【第 9 题】

设 T 是一棵有 n 个顶点的树，下列说法不正确的是（ ）。 {{ select(9) }}

  • T 有 n 条边
  • T 是连通的
  • T 是无环的
  • T 有 n-1 条边

【第 10 题】

在 C++ 程序中，表达式 200|10 的值是（ ）。 {{ select(10) }}

  • 20
  • 1
  • 220
  • 202

【第 11 题】

关于图灵机下面的说法哪个是正确的（ ）。 {{ select(11) }}

  • 图灵机是世界上最早的电子计算机。
  • 由于大量使用磁带操作，图灵机运行速度很慢。
  • 图灵机只是一个理论上的计算模型。
  • 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

【第 12 题】

阅读下面程序，输入：wer2345d-h454-82qqq，则输出为（ ）。

#include <iostream>
using namespace std;

void expand(char s1[], char s2[]) {
    int i, j, a, b, c;
    j = 0;
    for (i = 0; (c = s1[i]) != '\0'; i++)
        if (c == '-') {
            a = s1[i - 1];
            b = s1[i + 1];
            if (isalpha(a) && isalpha(b) || isdigit(a) && isdigit(b))
            /*函数 isalpha(a) 用于判断字符 a 是否为字母，isdigit(b) 用于判断字符 b 是否为数字,如果是,返回 1，否则返回 0 */
            {
                j--;
                do
                    s2[j++] = a++;
                while (tolower(a) < tolower(s1[i + 1]));
            }
            /*函数 tolower(a) 的功能是当字符 a 是大写字母,改为小写,其余情况不变*/
            else
                s2[j++] = c;
        } 
		else
        	s2[j++] = c;
			
    s2[j] = '\0';
}

int main() {
    char s1[100], s2[300];
    printf("input s1:");
    cin >> s1;
    expand(s1, s2);
    printf("%s\n", s2);

	return 0;
}

{{ select(12) }}

  • input s1:wer2345defgh45456782qqq
  • wer2345defgh45456782qqq
  • input s1:wer2345ddefgh454456782qqq
  • input s1:wer2345ddefggh4544567882qqq

【第 13 题】

阅读下面程序，则输出第二行为（ ）。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a1[51] = {0};
    int i, j, t, t2, n = 50;
    for (i = 2; i <= sqrt(n); i++)
        if (a1[i] == 0) {
            t2 = n / i;
            for (j = 2; j <= t2; j++)
                a1[i * j] = 1;
        }
    t = 0;
    for (i = 2; i <= n; i++)
        if (a1[i] == 0) {
            printf("%d ", i);
            t++;
            if (t % 10 == 0)
                printf("\n");
        }
    printf("\n");
}

{{ select(13) }}

  • 31 37 41 43 47
  • 2 3 5 7 11 13 17 19 23 29
  • 32 38 41 44
  • 17 19 23 29

【第 14 题】

将 n 个数 (1,2,…,n) 划分成 r 个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为 S(n,r)。例如，S(4,2)=7，这 7 种不同的划分方法依次为 {(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)}，{(12),(34)},{(13),(24)},{(14),(23)}。当 n=6,r=3 时，S(6,3)=（ ）。

{{ select(14) }}

  • 128
  • 120
  • 80
  • 90

【第 15 题】

某城市的街道是一个很规整的矩形网络（见下图），有 7 条南北向的纵街，5 条东西向的横街。现要从西南角的 A 走到东北角的 B ，最短的走法共有多少种？（ ）。

image

{{ select(15) }}

  • 180
  • 200
  • 210
  • 220

二、阅读程序

（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

阅读程序（一）

1. #include <iostream>
2. using namespace std;
3.
4. typedef unsigned long long INT;
5.
6. INT f(INT n) {
7.     INT lowint = n & 0x0000ffff;
8.     INT highint = n & 0xffff0000;
9.
10.    INT res = (lowint << 16) + (highint >> 16);
11.
12.    return res;
13. }
14. 
15. INT g(INT n) {
16.     INT res = n >> 16;
17.     for (int i = 0; i < 16; i++)
18.         if (n >> i & 1)
19.             res += 1 << (i + 16);
20.     return res;
21. }
22. 
23. int main() {
24.     INT n;
25.     cin >> n;
26.
27.     cout << f(n) << endl << g(n);
28.
29.     return 0;
30. }

假设输入的 n 是小于 2322^{32} 的非负整数，完成下面的判断题和单选题。

判断题

  1. 假定输入的数字为大于等于 −232-2^{32} 的负整数，该程序运行可能会发生异常。 {{ select(16) }}
  • 正确
  • 错误
  1. 删除第 10 行的括号，对程序结果没有影响。 {{ select(17) }}
  • 正确
  • 错误
  1. 该程序输出的两个结果总是相同的。 {{ select(18) }}
  • 正确
  • 错误

单选题

  1. 如果输入的 n 为 0，则输出的第一个结果是（ ）。 {{ select(19) }}
  • 0
  • 10
  • 100
  • 1000
  1. 如果输入的 n 为 1，则输出的第一个结果是（ ）。 {{ select(20) }}
  • 1
  • 65535
  • 65536
  • 32768
  1. 如果输入的 n 为 2202^{20}，则输出的第二个结果是（ ）。 {{ select(21) }}
  • 1024
  • 16
  • 1048567
  • 4

阅读程序（二）

1. #include <bits/stdc++.h>
2. using namespace std;
3. 
4. const int N = 300;
5. int n;
6. int w[N];
7. unordered_map<int, int> mp;
8.
9. void build(int p) {
10.     if (p >= (1 << n))
11.         return;
12. 
13.     build(2 * p);
14.     build(2 * p + 1);
15.
16.     w[p] = max(w[2 * p], w[2 * p + 1]);
17. }
18. 
19. int main() {
20.     cin >> n;
21.
22.     for (int i = 0; i >> n == 0; i++) {
23.         cin >> w[i + (1 << n)];
24.         mp[w[i + (1 << n)]] = i + 1;
25.     }
26.
27.     build(1);
28.
29.     cout << mp[min(w[2], w[3])] << endl;
30. 
31.     return 0;
32. }

假设输入的 n 是小于 8 的正整数，接下来输入的数字互不相等，均不超过 10000，完成下面的判断题和单选题。

判断题

  1. 将第 7 行 unordered_map 替换为 map，程序结果不变。 {{ select(22) }}
  • 正确
  • 错误
  1. 将第 22 行 i>>n == 0 替换为 i < 1<<n，程序结果不变。 {{ select(23) }}
  • 正确
  • 错误
  1. 如果输入 n 之后的数字，出现至少两个数字相等的情况，该程序运行可能会发生异常。 {{ select(24) }}
  • 正确
  • 错误

单选题

  1. 该程序的时间复杂度为（ ）。 {{ select(25) }}
  • O(n)O(n)
  • O(2n)O(2^n)
  • O(nlogn)O(nlogn)
  • O(logn)O(logn)
  1. 假定输入的 n=3，接下来输入的数字为 4 2 3 1 10 5 9 7，则最终结果为（ ）。 {{ select(26) }}
  • 1
  • 2
  • 7
  • 8
  1. 假定输入的 n=6，程序执行完 27 行后，w 数组中将储存（ ）个非零数。 {{ select(27) }}
  • 63
  • 64
  • 128
  • 127

阅读程序（三）

1. #include <iostream>
2. #include <string>
3. #include <algorithm>
4. using namespace std;
5.
6. const int N = 30;
7.
8. int rules[N][N];
9. string K, B, A, K2, B2;
10.
11. int work(char b, char k) {
12. 	for (int i = 0; i < 26; i++) {
13.		if (rules[i][k - 'A'] + 'A' == int(b))
14.			return i;
15. 	}	
16. }
17.
18. int main() {
19.
20.	  cin >> K >> B;
21.	  K2 = K, B2 = B;
22.	  transform(K2.begin(), K2.end(), K2.begin(), ::toupper);
23.	  transform(B2.begin(), B2.end(), B2.begin(), ::toupper);
24.
25.	  for (int i = 0; i < 26; i++) {
26.		  for (int j = 0; j < 26; j++) {
27.			  if (i + j < 26)
28.				  rules[i][j] = i + j;
29.			  else
30.				  rules[i][j] = i + j - 26;
31.		  }
32.	  }
33.
34.	  for (int i = 0; i < B.size(); i++) {
35.		  int t = work(B2[i], K2[i % K2.size()]);
36.		  if (B[i] >= 'a' && B[i] <= 'z') cout << char(t + 97);
37.		  else cout << char(t + 65);
38.	  }
39.
40.	  return 0;
41. }

输入的第一行是一个字符串，长度不超过100，其中仅包含大小写字母。 输入的第二行是一个字符串，长度不超过1000，其中仅包含大小写字母。

判断题

  1. 输入的第一行字符串大小写互换后不会影响最终结果。 {{ select(28) }}
  • 正确
  • 错误
  1. 输入的第二行字符串大小写互换后不会影响最终结果。 {{ select(29) }}
  • 正确
  • 错误
  1. 对将第 22 行和第 23 行 toupper 替换为 tolower，程序结果不变。 {{ select(30) }}
  • 正确
  • 错误
  1. 将第 13 行 int(b) 改为 b，程序结果不变。

{{ select(31) }}

  • 正确
  • 错误

单选题

  1. 输入第一行字符串为“aaaa”，第二行字符串为“bbbbbbbb”，结果为（ ）。 {{ select(32) }}
  • bbbbbbbb
  • cccccccc
  • dddddddd
  • zzzzzzzz
  1. 输入第一行字符串为“abcd”，第二行字符串为“bcdebcde”，结果为（ ）。 {{ select(33) }}
  • bbbbbbbb
  • abcdbcde
  • wxyzwxzy
  • cccccccc
  1. 输入第一行字符串为“hellonoi”，第二行字符串为“hellonoi”，结果为（ ）。 {{ select(34) }}
  • dddddddd
  • ifmmpopj
  • hellonoi
  • aaaaaaaa

三、完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序（一）

（字符串替换）给定一个字符串 SS（SS 仅包含大小写字母），下面的程序将 SS 中的每个字母用规定的字母替换，并输出 SS 经过替换后的结果。

程序的输入是两个字符串，第一个字符串是给定的字符串 SS，第二个字符串 S′S^{'} 由 26 个字母组成，它是 a∼za∼z 的任一排列，大小写不定，S′S^{'} 规定了每个字母对应的替换字母：S′S^{'} 中的第一个字母是字母 AA 和 aa 的替换字母，即 SS 中的 AA 用该字母的大写替换，SS 中的 aa 用该字母的小写替换；S′S^{'} 中的第二个字母是字母 BB 和 bb 的替换字母，即 SS 中的 BB 用该字母的大写替换，SS 中的 bb 用该字母的小写替换；……以此类推。

#include <iostream>
#include <cstring>
using namespace std;

char change[26], str[5000];

void CheckChangeRule() {
    int i;
    for (i = 0; i < [ ① ]; i++) {
        if ( [ ② ] )
            change[i] -= 'A' - 'a';
    }
}

void ChangeString() {
    int i;
    for (i = 0; i < strlen(str); i++) {
        if ( [ ③ ] )
            str[i] = change[str[i] - 'A'] - 'a' + 'A';
        else
            [ ④ ] 
    }
}

int main() {
    int i;
    cin >> str;
    cin >> change;
    CheckChangeRule();
       [ ⑤ ]
    cout << str << endl;
    return 0;
}
  1. ① 处应填（ ）。

{{ select(35) }}

  • strlen(change)
  • strlen(str)
  • 25
  • 27
  1. ② 处应填（ ）。

{{ select(36) }}

  • change[i] >= 'a' || change[i] <= 'z'
  • change[i] >= 'a' && change[i] <= 'z'
  • change[i] >= 'A' && change[i] <= 'Z'
  • change[i] >= 'A' || change[i] <= 'Z'
  1. ③ 处应填（ ）。

{{ select(37) }}

  • str[i] >= 'a' || str[i] <= 'z'
  • str[i] >= 'A' && str[i] <= 'Z'
  • str[i] >= 'a' && str[i] <= 'z'
  • str[i] >= 'a' || str[i] <= 'z'
  1. ④ 处应填（ ）。

{{ select(38) }}

  • str[i] = change[str[i] - 'a'];
  • str[i] = change[str[i] - 'A'];
  • str[i] = change[str[i] - 'a']-'a'+'A';
  • str[i] = change[str[i] - 'a']+'a'-'A';
  1. ⑤ 处应填（ ）。

{{ select(39) }}

  • ChangeString(CheckChangeRule());
  • ChangeString(str);
  • ChangeString(change);
  • ChangeString();

完善程序（二）

（找第 k 大的数） 给定一个长度为 10610^6 的无序正整数序列, 以及另一个数 n(1≤n≤106)n(1≤n≤10^6)，然后以类似快速排序的方法找到序列中第 n 大的数（关于第 n 大的数：例如序列 {1,2,3,4,5,6} 中第 3 大的数是 4）。

#include <iostream>
using namespace std;

int a[1000001], n, ans = -1;
void swap(int &a, int &b) {
    int c;
    c = a;
    a = b;
    b = c;
}

int FindKth(int left, int right, int n) {
    int tmp, value, i, j;
    if (left == right)
        return left;
    tmp = rand() % (right - left) + left;
    swap(a[tmp], a[left]);
    value = [ ① ];
    i = left;
    j = right;
    while (i < j) {
        while (i < j && [ ② ]) j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        } else
            break;
        while (i < j && [ ③ ]) i++;
        if (i < j) {
            a[j] = a[i];
            j - -;
        } else
            break;
    }
    [ ④ ] 
	if (i < n) 
		return FindKth([ ⑤ ]);
    if (i > n)
        return [ ⑥ ] 
    return i;
}

int main() {

    int i;
    int m = 1000000;
    for (i = 1; i <= m; i++)
        cin >> a[i];
    cin >> n;
    ans = FindKth(1, m, n);
    cout << a[ans];
	
    return 0;
}
  1. ① 处应填（ ）。

{{ select(40) }}

  • a[left]
  • a[left+1]
  • a[right]
  • a[right-1]
  1. ② 处应填（ ）。

{{ select(41) }}

  • a[i]<value
  • a[j]=value
  • a[j]<value
  • a[i]=value
  1. ③ 处应填（ ）。

{{ select(42) }}

  • a[i]>value
  • a[i]=value
  • a[j]>value
  • a[j]=value
  1. ④ 处应填（ ）。

{{ select(43) }}

  • a[i]>value;
  • a[i]=value;
  • a[j]>value;
  • a[j]<value;
  1. ⑤ 处应填（ ）。

{{ select(44) }}

  • left,i,n
  • i,right,n
  • i+1,right,n
  • left,i-1,n
  1. ⑥ 处应填（ ）。

{{ select(45) }}

  • FindKth(i+1,right,n);
  • FindKth(i,right,n);
  • FindKth(left,i-1,n);
  • FindKth(left,i,n);

Statistics

Related

In following contests:

CSP-J 真题+模拟题

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. Copyright：
  3. 沪ICP备2023029987号-1
  4. Worker 0, 24ms
  5. Powered by Hydro v4.10.6 Community