CSP-J 初赛模拟题 11

ID: 265

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

admin

标签>

初赛

J组

一、单项选择（满分 30 分，每题 2 分）

关于 ASCII，下面哪个说法是正确的？

ASCII 码就是键盘上所有键的唯一编码。
一个 ASCII 码使用一个字节的内存空间就能够存放。
最新扩展的 ASCII 编码方案包含了汉字和其他欧洲语言的编码。
ASCII 码是英国人主持制定并推广使用的。

分辨率为 $1600\times 900$ 、16 位色的位图，存储图像信息所需的空间为（　）。

2812.5 KB
4218.75 KB
4320 KB
2880 KB

若某算法的计算时间表示为递推关系式：

$$T(N)=2T\left(\frac{N}{2}\right)+N\log N,\qquad T(1)=1,$$

则该算法的时间复杂度为（　）。

$O(N)$
$O(N\log N)$
$O(N\log^2 N)$
$O(N^2)$

有向图中每个顶点的度等于该顶点的（　）。

入度
出度
入度和出度之和
入度和出度之差

在 C++ 语言中，表达式 23|2^5 的值是（　）。

$\left(2070\right)_{16}+\left(34\right)_8$ 的结果不是（　）。

$\left(8332\right)_{10}$
$\left(208C\right)_{16}$
$\left(100000000110\right)_2$
$\left(20214\right)_8$

已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），后根遍历是 4 6 5 2 7 3 1，则该二叉树的不可能的中根遍历是（　）。

4 2 6 5 1 7 3
4 2 5 6 1 3 7
4 2 3 1 5 6 7
4 2 5 6 1 7 3

一个圆上有 6 个顶点 ABCDEF，以其中三点为顶点，可以连出多少个三角形？

从 A 点只能向上或者向右走，沿方格线到达 B 点，共有多少种走法？

自然数中 0～9 任意选四个不同的数，组成一个四位数，共可以组成多少个这样的四位数？

5040
4536
3024
210

一个数列，其中任意五个相邻项之和为 2010。已知第一个数是 1，第 9 个数是 9，第 17 个数是 9，第 2008 个数是 3，求第 2010 个数是多少？

1988
1998
2022
2032

在两条直线上，分别有五个点和四个点，从中任选三个点组成三角形，有（　）种情况。

完全二叉树共有 $2\times N-1$ 个结点，则它的叶节点数是（　）。

$N-1$
$N/2$
$N$
$N/2-1$

在含有 $n$ 个元素的双向链表中查询是否存在关键字为 $k$ 的元素，最快情况下运行的时间复杂度是（　）。

$O(1)$
$O(\log n)$
$O(n)$
$O(n\log n)$

有以下结构体说明和变量定义，如图所示，指针 p,q,r 分别指向一个链表中的三个续结点。

struct node {
    int data;
    struct node *next;
} *p, *q, *r;

现要将 q 和 r 所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是（　）。

q->next = r->next; p->next = r; r->next = q;
p->next = r; q->next = r->next; r->next = q;
q->next = r->next; r->next = q; p->next = r;
r->next = q; q->next = r->next; p->next = r;

二、阅读程序（满分 40 分，判断题 1.5 分，选择题除特殊说明外 3 分）

判断题请选择“正确”或“错误”。

阅读 1

01  #include <bits/stdc++.h>
02  long long n, m, t, a[1000005];
03  int main() {
04      scanf("%lld%lld", &n, &m);
05      while (m > 0) {
06          t++;
07          m--;
08          if (m <= 0)
09              break;
10          a[t] = a[t - 1] + 1;
11          while (m > (1 << n - a[t]) && a[t] <= n) {
12              m -= 1 << n - a[t];
13              a[t]++;
14          }
15      }
16      if (t != 1)
17          for (int i = 1; i < t; i++)
18              printf("%lld ", a[i]);
19      else
20          puts("0");
21      return 0;

原卷程序截图到第 21 行为止，未显示 main 函数最后的右花括号。

第 20 行的 "0" 改成 '0'，程序运行会报错。（　）

正确
错误

输入的 n 如果是负整数，程序运行不会报错。（　）

正确
错误

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

正确
错误

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

正确
错误

输入 4 12，输出（　）。

0
2 3
2 3 4
1 2 3

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

阅读 2

01  #include<iostream>
02  #include<cstring>
03  using namespace std;
04  string A,B;
05  char s1[2005],s2[2005];
06  int edit[2005][2005];
07  int dfs(int i,int j){
08      if(edit[i][j]!=-1)
09          return edit[i][j];
10      if(i==0)
11          return edit[i][j]=j;
12      if(j==0)
13          return edit[i][j]=i;
14      int bonus=1;
15      if(s1[i]==s2[j])
16          bonus=0;
17      return edit[i][j]=min(min(dfs(i-1,j)+1,dfs(i,j-1)+1),dfs(i-1,j-1)+bonus);
18  }
19  int main(){
20      cin>>A>>B;
21      memset(edit,-1,sizeof(edit));
22      int len1=A.length(),len2=B.length();
23      for(int i=1;i<=len1;i++)
24          s1[i]=A[i-1];
25      for(int i=1;i<=len2;i++)
26          s2[i]=B[i-1];
27      dfs(len1,len2);
28      cout<<edit[len1][len2];
29      return 0;
30  }

输入的字符串只包含小写字母 a～z。

第 8 行和第 21 行的 -1 如果改成 -2，程序运行结果可能不一样。（　）

正确
错误

$n$ 是输入的两个字符串长度的最大值，程序的时间复杂度为 $O(3^n)$ 。（　）

正确
错误

输出的最小值为 -1。（　）

正确
错误

len1 和 len2 为执行完第 22 行后的值，输出的最大值为 len1+len2。（　）

正确
错误

输入为 sfdqxbw gfdgw，输出（　）。

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

阅读 3

01  #include<iostream>
02  #include<cstdio>
03  #define mod 9901
04  using namespace std;
05  int a,b,sa,n[10010][2],cot=0,ans=1;
06  int q(int ml,int nl){
07      int s=1;
08      while(nl>0){
09          if(nl%2==1){
10              s=(s%mod)*(ml%mod)%mod;
11          }
12          ml=ml*ml%mod;
13          nl=nl>>1;
14      }
15      return s%mod;
16  }
17  int sum(int x,int y){
18      int k=0;
19      y=y*b;
20      if(x%mod==1){
21          k=(y+1)%mod;
22      }
23      else{
24          k=(q(x%mod,y+1)-1)%mod*q((x-1)%mod,mod-2)%mod;
25      }
26
27      return k%mod;
28  }
29  int main(){
30      scanf("%d%d",&a,&b);
31      if(a==0){
32          printf("0\n");
33          return 0;
34      }
35      for(int i=2;i*i<=a;i++){
36          if(a%i==0){
37              cot++;
38              n[cot][0]=i;
39              n[cot][1]=1;
40              a=a/i;
41              while(a%i==0){
42                  n[cot][1]++;
43                  a=a/i;
44              }
45          }
46      }
47      if(a!=1){
48          cot++;
49          n[cot][0]=a;
50          n[cot][1]=1;
51      }
52      for(int i=1;i<=cot;i++){
53          ans=ans*sum(n[i][0],n[i][1])%mod;
54      }
55      printf("%d\n",(ans%mod+mod)%mod);
56      return 0;
57  }

第 35 行的 i*i 改成 i，运行结果不变。（　）

正确
错误

第 3 行 9901 换成 1e9+7，运行结果不变。（　）

正确
错误

n[cot][0] 随着 cot 的增大而增大。（　）

正确
错误

第 27 行删除 %mod，结果不变。（　）

正确
错误

输入为 2 3，输出（　）。

输出为 542，输入可能是以下哪组数据？（　）

210 5
210 6
330 5
330 6

输入为 217823 1，输出为（　）。

1
2
9901
22

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

完善 1

众所周知，2 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…。我们说 2 的正整数次幂最后一位的循环长度是 4（实际上 4 的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：

数字	循环	循环长度
2	2,4,8,6	4
3	3,9,7,1	4
4	4,6	2
5		1
6		1
7	7,9,3,1	4
8	8,4,2,6	4
9	9,1	2

这时问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数 $n$ 的正整数次幂来说，它的后 $k$ 位是否会发生循环？如果循环的话，循环长度是多少呢？

注意：

如果 $n$ 的某个正整数次幂的位数不足 $k$ ，那么不足的高位看做是 0。
如果循环长度是 $L$ ，那么说明对于任意的正整数 $a$ ， $n$ 的 $a$ 次幂和 $a+L$ 次幂的最后 $k$ 位都相同。
$1\le n<10^{100}$ ， $1\le k\le100$ 。

输入共一行，包含 2 个整数 $n$ 和 $k$ 。 $n$ 和 $k$ 之间用一个空格隔开，表示要求 $n$ 的正整数次幂的最后 $k$ 位的循环长度。

输出一个整数，表示循环长度。如果循环不存在，输出 -1。

试补全程序：

#include<bits/stdc++.h>
using namespace std;
int k;
struct BNR{
    int a[105];
    int len;
    BNR(){
        memset(a,0,sizeof(a));
        len=0;
    }
};
typedef BNR bign;

void cpy(①,bign y){
    x.len=y.len;
    for(int i=1;i<=x.len;i++)
        x.a[i]=y.a[i];
}

void in(①){
    char ch=getchar();x.len=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch<='9'&&ch>='0')
        x.len++,x.a[x.len]=(int)ch-'0',ch=getchar();
    for(int i=1;i<=x.len/2;i++)
        swap(x.a[i],②);
}

void out(①){
    for(int i=x.len;i>=1;i--)
        cout<<x.a[i];
    cout<<endl;
}

void AAA(①,bign y){
    for(int i=1;i<=min(y.len,k);i++)
        x.a[i]+=y.a[i];
    x.len=0;
    for(int i=1;i<=k;i++){
        if(x.a[i])x.len=max(x.len,i);
        x.a[i+1]+=x.a[i]/10,x.a[i]%=10;
    }
}

bign z;
void BBB(①,bign y){
    z.len=0;
    memset(z.a,0,sizeof(z.a));
    for(int i=1;i<=min(x.len,k);i++)
        for(int j=1;③<=k;j++)
            z.a[③] += x.a[i]*y.a[j];
    for(int i=1;i<=k;i++)
    {
        if(z.a[i])z.len=max(z.len,i);
        z.a[i+1]+=z.a[i]/10,z.a[i]%=10;
    }
    cpy(x,z);
}

int main()
{
    bign n;
    in(n);
    cin>>k;
    bign p;
    p.len=1;
    p.a[1]=④;
    bign ans,now,t,kt=n,f,mmm=n;

    cpy(ans,p);cpy(now,n);cpy(kt,n);cpy(mmm,n);
    for(int i=1;i<=k;i++){
        cpy(kt,mmm);cpy(f,ans);cpy(mmm,p);
        int flag=0;
        if(i==1)BBB(now,kt);
        for(int j=1;j<=10;j++)
        {
            BBB(mmm,kt);
            if(⑤){
                flag=1;
                break;
            }
            BBB(now,kt);
            AAA(ans,f);
        }
        if(!flag){
            cout<<"-1";return 0;
        }
    }
    out(ans);
    return 0;
}

① 处应填（　）。

bign x
bign &x
bign x[]
bign *x

② 处应填（　）。

x.a[x.len-i]
x.a[x.len/2-i]
x.a[x.len/2-i+1]
x.a[x.len-i+1]

③ 处应填（　）。

i+j-1
i+j
i
z.len-i-j

④ 处应填（　）。

0
1
k
-1

⑤ 处应填（　）。

now.a[i]!=n.a[i]
now.a[i]!=n.a[j]
now.a[i]==n.a[i]
now.a[i]==n.a[j]

完善 2

二叉树是一种基本的数据结构，它要么为空，要么由根节点、左子树和右子树组成，同时左子树和右子树也分别是二叉树。

当一颗二叉树高度为 $m-1$ 时，则共有 $m$ 层。除 $m$ 层外，其他各层的结点数都达到最大，且结点节点都在第 $m$ 层时，这就是一个满二叉树。

现在，需要你用程序来绘制一棵二叉树，它由一颗满二叉树去掉若干结点而成。对于一颗满二叉树，我们需要按照以下要求绘制：

结点用小写字母 o 表示。对于一个父亲结点，用 / 连接左子树，同样用 \ 连接右子树。
定义 [i,j] 为位于第 $i$ 行第 $j$ 列的某个字符。若 [i,j] 为 /，那么 [i-1,j+1] 与 [i+1,j-1] 要么为 o，要么为 /。若 [i,j] 为 \，那么 [i-1,j-1] 与 [i+1,j+1] 要么为 o，要么为 \。同样，若 [i,j] 为第 1～ $m$ 层的某个节点（即 o），那么 [i+1,j-1] 为 /，[i+1,j+1] 为 \。
对于第 $m$ 层节点，也就是叶子结点，若两个属于同一个父亲，那么它们之间由 3 由 3 个空格隔开；若两个结点相邻但不属于同一个父亲，那么它们之间由 1 个空格隔开。第 $m$ 层左数第 1 个节点之前没有空格。

最后需要在一颗绘制好的满二叉树上删除 $n$ 个结点（包括它的左右子树，以及与父亲的连接），原有的字符用空格替换。

输入的第 1 行包含 2 个正整数 $m$ 和 $n$ ，为需要绘制的二叉树层数已经从 $m$ 层满二叉树中删除的结点数。接下来 $n$ 行，每行两个正整数，表示第 $i$ 层第 $j$ 个结点需要被删除。

例如，输入：

4 0

输出：

输入：

输出：

提示：关于树枝长度的规律：

层数	1	2	3	4	5
树枝长 `len`	1	2	5	11	23
规律	1	$1+(2-1)$	$(1+2)+(3-1)$	$(1+2+5)+(4-1)$	$(1+2+5+11)+(5-1)$