初中组基础知识题目

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

1. 完整的计算机系统应该包括（） {{ select(1) }}

• 运算器、存储器、控制器
• 外部设备和主机
• 主机和应用程序
• 配套的硬件和软件系统

2. 文件传输使用的协议是（） {{ select(2) }}

• SMTP
• FTP
• UDP
• TELNET

3. 根据 NAT 协议，下列地址中( )属于 C 类地址。 {{ select(3) }}

• 10.1.56.23
• 172.15.34.128
• 192.168.32.17
• 172.128.45.34

4. 在 Linux 系统中，cp 命令的作用是（ ） {{ select(4) }}

• 更改文档或目录的日期时间
• 创建一个新的目录
• 复制一个文件到另一个位置
• 查看指定文件的内容

5. 现有一个文件夹，其中包含 1000 张图片，图片的分辨率以 1240*720,1920*1080,1600*900三个分辨率交替存储，每张图片均为 32 位图像，则这个文件夹最少要用（ ）GB 的 U 盘存储。 {{ select(5) }}

• 2
• 4
• 6
• 8

6. 总共有 6 个不同的元素进栈，能得到（）种不同的出栈序列。 {{ select(6) }}

• 123
• 121
• 132
• 130

7. 已知一个根节点再第一层的完全二叉树的第 6 层有 8 个叶子节点，则该完全二叉树的至少有（）个节点。 {{ select(7) }}

• 39
• 23
• 111
• 119

8. 一个有 n 个顶点和 n 个边组成的无向图一定是（ ） {{ select(8) }}

• 连通的
• 无环的
• 有环的
• 不连通的

9. 已知一个二叉树的中序遍历为 HBDIAEFCG,先序遍历为 ABHDICEFG,则该二叉树的后序遍历为（） {{ select(9) }}

• IHDBEFGCA
• IHDBFEGCA
• HIDBFGECA
• HIDBFEGCA

10. 23|15+9^16&69 的结果是（） {{ select(10) }}

• 31
• 5
• 28
• 3

11. 若序列的原始状态为{73,94,46,20,77,61,51,28,81,58}，使用快速排序进行排序，以第一个记录为基准值，第一次划分结果（） {{ select(11) }}

• {20,73,58,46,77,28,51,61,81,94}
• {58,20,51,61,28,73,77,81,94,46}
• {46,20,61,51,28,58,73,94,77,81}
• {58,28,46,30,51,61,73,77,81,94}

12. 求出下列算法的时间复杂度（）

    int y=0;
    while((y+1)*(y-1)<=n)
    {
     y++;
    }
    

    {{ select(12) }}

• 𝑂(𝑙𝑜𝑔𝑛)
• 𝑂(𝑛)
• 𝑂($n^\frac{1}{2}$)
• 𝑂($N^2$ )

13. 已知有向图 G 如下图所示，使用 kruskal 算法求图 G 的最小生成树，加到最小生成树中的边依次是( ) {{ select(13) }}

• (a,e),(c,e),(b,e),(b,c),(b,d)
• (b,c),(b,d),(b,e),(a,e),(c,e)
• (a,e),(b,e),(c,e),(b,d),(b,c)
• (b,c),(e,d),(e,b),(c,d),(d,a)

14. 设一批产品共 10 件，其中 4 件是次品，现进行放回抽样，即为取一个检查完放回后继续抽取，总共抽取三次，恰好其中两件为残次品的概率为（） {{ select(14) }}

• $\frac{3}{10}$
• $\frac{36}{125}$
• $\frac{1}{2}$
• $\frac{13}{25}$

15. 假定编译器规定 int 和 short 长度范围分别为 32 位和 16 位，执行以下代码：

    unsigned short x=65530;
    unsigned int y=x;
    

    得到的 y 的机器码（） {{ select(15) }}

• 0000 7FFAH
• 0000 FFFAH
• FFFF 7FFAH
• FFFF FFFAH

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

第一题

1. #include <bits/stdc++.h>
2. long long n, m, t, a[1000005]; 
3. using namespace std;
4. int main() {
5.   cin >> n >> m; 
6.   while (m > 0) {
7.     t++; 
8.     m--; 
9.     if (m <= 0) 
10.      break; 
11.      a[t] = a[t - 1] + 1; 
12.      while (m > (1 << n - a[t]) && a[t] <= n) {
13.         m -= 1 << n - a[t];
14.         a[t]++; 
15.      } 
16.   } 
17.   if (t != 1) 
18.     for (int i = 1; i < t; i++) 
19.       cout << a[i] << " ";
20.   else 
21.     puts("0");
22.   return 0;
23. }

16. 第 21 行的"0"改成’0’，程序运行会报错（ ）。 {{ select(16) }}

• 正确
• 错误

17. 输入的 n 如果是负整数，程序运行不会报错（ ）。 {{ select(17) }}

• 正确
• 错误

18. 第 11 行的功能是对 a 数组求前缀和（ ）。

    {{ select(18) }}

• 正确
• 错误

19. 输入的 n 最大可以到 1000000（ ）。

    {{ select(19) }}

• 正确
• 错误

20. 输入 4 12， 输出（ ）。

    {{ select(20) }}

• 0
• 2 3
• 2 3 4
• 1 2 3

21. 当输入 n 为 3，m 为 1~8 之间的整数时，平均输出整数的个数(保留一位小数)是（ ）。

    {{ select(21) }}

• 1.0
• 1.6
• 1.8
• 2.0

第二题

1. #include<iostream>
2. #include<cstring>
3. using namespace std;
4. string a,b;
5. int f[2010][2010];
6. int Dfs(int i, int j){ 
7.   if(f[i][j]!=-1) 
8.     return f[i][j]; 
9.   if(i==0) 
10.    return f[i][j]=j;
11.  if(j==0) 
12.    return f[i][j]=i;
13.   int c=1;
14.   if(a[i-1]==b[j-1]) 
15.     c=0; 
16.   return f[i][j]=min(min(Dfs(i-1,j)+1,Dfs(i,j-1)+1),Dfs(i-1,j-1)+c);
17. }
18. int main(){
19.   cin>>a>>b;
20.   memset(f,-1,sizeof(f));
21.   int len1=a.length(),len2=b.length();
22.   Dfs(len1,len2);
23.   cout<<f[len1][len2];
24.   return 0;
25. }
注：输入的字符串只包含小写字母 a\~z。

22. 第 7 行和第 20 行的-1 如果改成-2，程序运行结果可能不一样（ ） {{ select(22) }}

• 正确
• 错误

23. n 是输入两个字符串长度的最大值，程序的时间复杂度为（ ）。 {{ select(23) }}

• 正确
• 错误

24. 输出的最小值为-1（ ）。 {{ select(24) }}

• 正确
• 错误

25. 设 len1 和 len2 为执行完第 21 行后的值，则程序输出的最大值为 len1+len2（ ）。 {{ select(25) }}

• 正确
• 错误

26. 输入为 sfdqxbw gfdgw，输出（ ）。 {{ select(26) }}

• 2
• 3
• 4
• 5

27. 保证输入的两个字符串长度均为 100，且只包含小写字母 a~z，第一个字符串为"acegikmoqsuwyace...uwy...ace...moq"，第二个字符串为"abcdefghijklmnopqrstuvwxy...abc...wxyabcd"（“...”表示省略了中间的字符），输出为（ ）。（4 分） {{ select(27) }}

• 4
• 13
• 50
• 96

第三题

1. #include<iostream>
2. #define mod 9901
3. using namespace std;
4. int a,b,sa,cal[10010][2],cnt=0,ans=1;
5. int f(int ml,int nl){
6.    int s=1;
7.    while(nl>0){
8.      if(nl&1){
9.        s=s*ml%mod;
10.     }
11.     ml=ml*ml%mod;
12.     nl=nl>>1;
13.   }
14.   return s%mod;
15. }
16. int s(int x,int y){
17.   int res=0;
18.   y=y*b;
19.   if(x%mod==1){
20.     res=(y+1)%mod;
21.   }
22.   else{
23.     res=(f(x%mod,y+1)-1)%mod * f((x-1)%mod,mod-2)%mod;
24.   }
25.   return res%mod;
26. }
27. int main(){
28.   cin>>a>>b;
29.   if(a==0){
30.     cout<<0<<endl;
31.     return 0;
32.   }
33.   for(int i=2;i*i<=a;i++){
34.     if(a%i==0){
35.       cnt++;
36.       cal[cnt][0]=i;
37.       cal[cnt][1]=1;
38.       a=a/i;
39.       while(a%i==0){
40.         cal[cnt][1]++;
41.         a=a/i;
42.       }
43.     }
44.   }
45.   if(a!=1){
46.     cnt++;
47.     cal[cnt][0]=a;
48.     cal[cnt][1]=1;
49.   }
50.   for(int i=1;i<=cnt;i++){
51.     ans=ans*s(cal[i][0],cal[i][1])%mod;
52.   }
53.   cout << (ans%mod+mod)%mod;
54.   return 0;
55. }

28. 第 33 行的 i*i 改成 i,运行结果不变（ ）。 {{ select(28) }}

• 正确
• 错误

29. 第 2 行 9901 换成 1e9+7，运行结果不变（ ）。 {{ select(29) }}

• 正确
• 错误

30. cal[cnt][0]随着 cnt 的增大而增大（ ）。 {{ select(30) }}

• 正确
• 错误

31. 第 25 行删除%mod，结果不变（ ）。 {{ select(31) }}

• 正确
• 错误

32. 输入为 2 3，输出（ ）。 {{ select(32) }}

• 4
• 8
• 9
• 15

33. 输出为 4319，输入可能是以下哪组数据（ ）。 {{ select(33) }}

• 210 2
• 210 3
• 330 5
• 330 6

34. 输入为 217823 1，输出为（ ）。 {{ select(34) }}

• 1
• 2
• 9901
• 22

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

1、(奇数区间) 给定一个长度为 n 的数列：𝑎₁, 𝑎₂, ⋯ 𝑎_n，如果其中一段连续的子序列𝑎_i , 𝑎_i+1, ⋯ 𝑎_j (𝑖 ≤ 𝑗)中，奇数比偶数多，我们就称这个区间[i,j] 是奇数区间。求给定的 n个数中有多少个奇数区间。

#include <bits/stdc++.h>
using namespace std;
const int off = 1e6 + 1;
const int maxn = 1e6 + 5;
int a[maxn], s[maxn], c[2 * maxn];
int n;
long long ans;
int lowbit(int x)
{
    return x & -x;
}
long long getSum(int x)
{
    long long res = 0;
    while (x > 0)
    {
        res += c[x];
        ① ;
    }
    return res;
}
void add(int x, int k)
{
    while ( ② )
    {
        c[x] += k;
        ③ ;
    }
}
int main()
{
    cin >> n;
    add(off, 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = ④ ;
        ans += getSum( ⑤ );
        add(s[i] + off, 1);
    }
    cout << ans << endl;
    return 0;
}

35. ①处应该填（ ） {{ select(35) }}

• x -= lowbit(x)
• x = lowbit(x)
• x += lowbit(x)
• x--

36. ②处应该填（ ） {{ select(36) }}

• x < off
• x <= n
• x! = 0
• x <= 2 ∗ off

37. ③处应该填（ ） {{ select(37) }}

• x -= lowbit(x)
• x = lowbit(x)
• x += lowbit(x)
• x++

38. ④处应该填（ ） {{ select(38) }}

• s[i - 1] + a[i] % 2 ? 1 : -1
• s[i - 1] + a[i] % 2 == 1 ? -1 : 1
• s[i - 1] + a[i] % 2 != 0 ? 1 : -1
• s[i - 1] + !a[i] % 2 ? 1 : -1

39. ⑤处应该填（ ） {{ select(39) }}

• 0
• s[i] + off − 1
• s[i − 1]
• s[i] + off

2、（最近公共祖先）已知一棵有根的多叉树，每次询问下求给定的两个点的最近公共祖先。其中输入的第一行 3 个整数为结点个数，询问次数，根节点序号。祖先结点:指一个结点本身或者它父节点的祖先。最近公共祖先：在一棵有根树中，对于任意两个结点的公共祖先中距离两者最近的结点。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
vector<int> edge[MAXN];
int depth[MAXN], lg[MAXN];
int pa[MAXN][22];
int n, m, r, x, y;
void dfs(int fa, int sn, int dep)
{
    depth[sn] = dep;
    pa[sn][0] = fa;
    for (int i = 1; ① ; i++)
    {
        pa[sn][i] = pa[pa[sn][i - 1]][i - 1];
    }
    for (int i = 0; i < edge[sn].size(); i++)
    {
        int fn = edge[sn][i];
        if (fn == fa)
        {
            continue;
        }
        dfs( ② );
    }
}
int solve(int x, int y)
{
    if (depth[x] < depth[y])
    {
        swap(x, y);
    }
    while (depth[x] > depth[y])
    {
        x = ③ ;
    }
    if (x == y)
    {
        return x;
    }
    for (int k = lg[depth[x]] - 1; k >= 0; --k)
    {
        if ( ④ )
        {
            x = pa[x][k], y = pa[y][k];
        }
    }
    return pa[x][0];
}
int main()
{
    cin >> n >> m >> r;
    for (int i = 1; i <= n; i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs( ⑤ );
    while (m--)
    {
        cin >> x >> y;
        cout << solve(x, y) << endl;
    }
    return 0;
}

40. ①处应该填（ ）

    {{ select(40) }}

• i < pa[sn]. size()
• i <= lg[deptℎ[fn]
• i < lg[dep]
• i <= lg [deptℎ[sn]]

41. ②处应该填（ ）

    {{ select(41) }}

• sn, fn, dep + 1
• fn, sn, dep + 1
• sn, fn, dep
• fn, sn, dep

42. ③处应该填（ ）

    {{ select(42) }}

• lg [deptℎ[x] − deptℎ[y]]
• pa[x][lg [deptℎ[x] − deptℎ[y]] − 1]
• pa[y][lg[deptℎ[x]
• pa[y][lg [deptℎ[y] − deptℎ[x]]

43. ④处应该填（ ）

    {{ select(43) }}

• pa[k][y] == pa[k][x]
• ! pa[x][k]
• pa[x][k]! = pa[y][k]
• pa[x][k] == pa[y][k]

44. ⑤处应该填（ ）

    {{ select(44) }}

• r, 0,0
• 0, r, 0
• r, 0,1
• 0, r, 1