入门级CSP-J第5套初赛模拟试题

ID: 4706

客观题

尝试: 6

已通过: 2

难度: 10

上传者:

椰子

标签>

初赛模拟试题

CSP-J

一、单项选择题（共15题，每题2分，共计30分）

文件型病毒传染的主要对象是( )。 {{ select(1) }}

文本文件
系统文件
可执行文件
.EXE和.COM文件

24针打印机的分辨率约为180dpi。dpi数越大,打印精度越高。其中单位dpi是指()。 {{ select(2) }}

印点/厘米
印点/毫米
印点/英寸
印点/寸

内存地址的最重要特点是()。 {{ select(3) }}

随机性
唯一性
顺序性
连续性

多媒体计算机是指( )。 {{ select(4) }}

具有多种功能的计算机
具有多种外设的计算机
能处理多种媒体的计算机
能借助多种媒体操作的计算机

最早的计算机的用途是用于( )。 {{ select(5) }}

科学计算
自动控制
系统仿真
辅助设计

CPU中()机构相当于运算器中的一个存储单元,它的存取速度比存储器要快得多。 {{ select(6) }}

存放器
辅存
主存
寄存器

计算机软件我们一般指的是()。 {{ select(7) }}

系统软件和实用软件
实用软件和自由软件
培训软件和管理软件
编辑软件和科学计算软件

操作系统在第几代计算机开始应用( )。 {{ select(8) }}

第一代
第二代
第三代
第四代

计算机中的数有浮点与定点两种,其中用浮点表示的数,通常由哪两部分组成( )。 {{ select(9) }}

指数与基数
尾数与小数
阶码与尾数
整数与小数

如果用一个字节来表示整数,最高位用作符号位,其他位表示数值。例如:00000001表示+1,10000001表示-1,试问这样表示法的整数A的范围应该是()。 {{ select(10) }}

-127<=A<=127
-128<=A<=128
-128<=A<128
-128<=A<=127

下列叙述中,正确的是()。 {{ select(11) }}

线性表的线性存储结构优于链表存储结构
队列的操作方式是先进后出
栈的操作方式是先进先出
二维数组是指它的每个数据元素为一个线性表的线性表

用某种排序方法对线性表 25,84,21,47,15,27,68,35,20进行排序,结点变化如下: (1)25,84,21,47,15,27,68,35,20; (2)20,15,21,25,47,27,68,35,84; (3)15,20,21,25,35,27,47,68,84; (4)15,20,21,25,27,35,47,68,84. 那么,排序方法是()。 {{ select(12) }}

选择排序
希尔排序
合并排序
快速排序

如果某二叉树的前序为STUWV,中序为UWTVS,那么该二叉树的后序是( )。 {{ select(13) }}

WUVTS
UWVTS
VWUTS
WUTSV

下面关于数据结构的叙述中,正确的叙述是( )。 {{ select(14) }}

顺序存储方式的优点是存储密度大,且插入、删除运算效率高
链表中的每一个结点都包含一个指针
包含n个结点的二叉排序树的最大检索长度为log2 n
将一棵树转换为二叉树后,根结点没有右子树

表达式(1+34)*5-56/7的后缀表达式为()。 {{ select(15) }}

1 34+5 56 7-*/
-*+1 34 5/56 7
1 34+5 * 56 7 / -
1 34 5 *+56 7 /

二、阅读程序（共计40分；标注分值的按标注计，未标注判断题每题1.5分，选择题每题4分）

（一）汉诺塔问题

#include<iostream>
using namespace std;
void hanoi(int n,char a,char b,char c) {
    if(n==1)
        cout<<n<<" "<<a<<" "<<c<<endl;
    else{
        hanoi(n-1,a,c,b);
        cout<<n<<" "<<a<<" "<<c<<endl;
        hanoi(n-1,b,a,c);
    }
}
int main(){
    int n;
    cin>>n;
    hanoi(n,'A','B','C');
    return 0;
}

判断题 16. (1分)当 n>=0 时,程序不会出现死循环。() {{ select(16) }}

正确
错误

(1分)输出共有2^n行。() {{ select(17) }}

正确
错误

当 n>0 时,将第4行的"=="改为"<=",程序输出结果必定不变。() {{ select(18) }}

正确
错误

将第5行的"n"改为"1",程序输出结果必定不变。() {{ select(19) }}

正确
错误

选择题 20. (3分)此程序的时间复杂度是()。 {{ select(20) }}

O(n)
O(n^2)
O(n^3)
O(2^n)

若要求输出不超过15行,则下列哪个n的值是合法的?() {{ select(21) }}

（二）高精度小数计算

#include<cstdio>
#define N 1005
using namespace std;
int num[N];

int main()
{
    int al=1,n,x;
    scanf("%d", &n);
    num[1]=1;
    for(int i=1;i<=n;++i){
        x=0;
        for(int j=1;j<=al;++j){
            num[j]=num[j]*5+x;
            x=num[j]/10;
            num[j]%=10;
        }
        if(x>0) num[++al]=x;
    }
    printf("0.");
    for(int i=al;i<n;++i) {
        putchar('0');
    }
    for(int i=al;i>=1;i--){
        printf("%d",num[i]);
    }
    putchar('\n');
    return 0;
}

判断题 22. (1分)程序输出的是5^n的值。() {{ select(22) }}

正确
错误

(1分)程序执行到第27行时,i的值为1。() {{ select(23) }}

正确
错误

对于任意 1<=i<=al ,都有 0<= num[i] <=9 。() {{ select(24) }}

正确
错误

程序输出的是一个小数,且小数末尾可能有多余的0。() {{ select(25) }}

正确
错误

选择题 26. 此程序的时间复杂度是()。 {{ select(26) }}

O(n)
O(n^2)
O(n^3)
O(n log n)

若 n=3 ,则输出为()。 {{ select(27) }}

8
0.125
0.8
125

（三）跳石头（二分答案）

在起点和终点之间，有N块岩石（不含起点和终点）。选手从起点出发，每一步跳向相邻的岩石，直至到达终点。组委会计划移走一些岩石，使得选手的最短跳跃距离尽可能长。至多移走M块岩石（不能移走起点和终点）。

#include<iostream>
using namespace std;
int l,n,m,a[50005],ans;
bool check(int dis)
{
    int count=0,last=0;
    for(int i=1;i<=n;i++)
        if(a[i]-last<dis) count++;
        else last=a[i];
    if(count>m) return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    a[n+1]=l;
    int fl=0,fr=l;
    while(fl<=fr)
    {
        int mid=(fl+fr)/2;
        if(check(mid)) fl=mid+1, ans=mid;
        else fr=mid-1;
    }
    cout<<ans;
    return 0;
}

判断题 28. (1分)将第19行的"fl=0"改为"fl=1",程序输出结果必定不变。() {{ select(28) }}

正确
错误

(2分)程序执行到第26行时,必有fl>fr。() {{ select(29) }}

正确
错误

(2分)若第23行执行的check(mid)==1,则最终的ans小于或等于此时的mid。() {{ select(30) }}

正确
错误

(2分)程序执行到第10行时,count的值表示:如果最短跳跃距离恰好为dis,那么最少需要移走几块岩石。() {{ select(31) }}

正确
错误

选择题 32. 此程序的时间复杂度是()。 {{ select(32) }}

O(n^2)
O(nl)
O(n log l)
O(n log n)

若输入为: 25 5 2 2 11 14 17 21 则输出为( )。 {{ select(33) }}

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

（一）Dijkstra最短路径

迪杰斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决有向图中最短路径问题，以起始点为中心向外层层扩展，直到扩展到终点为止。

#include<iostream>
using namespace std;
int main()
{
    int edgs;
    int points;
    int dis[10];
    int flag[10];
    int infinity=9999999;
    cin>>points>>edgs;
    int edg[10][10];
    for(int i=1;i<=points;i++)//初始化
    {
        for(int j=1;j<=points;j++)
        {
            if(i==j)
            {
                edg[i][j]= ①
            }
            else
            {
                edg[i][j]= ②
            }
        }
    }
    int point1,point2,quanzhi;
    for(i=1;i<=edgs;i++)
    {
        cin>>point1>>point2>>quanzhi;
        edg[point1][point2]= ③
    }
    for(i=1;i<=points;i++)
    {
        dis[i]=edg[1][i];
    }
    for(i=1;i<=points;i++)
    {
        flag[i]=0;
    }
    flag[1]=1;
    int min,u;
    for(i=1;i<=points-1;i++)
    {
        min=infinity;
        for(int j=1;j<=points;j++)
        {
            if(flag[j]==0&&dis[j]<min)
            {
                min= ④
                u=j;
            }
        }
        flag[u]=1;
        for(int v=1;v<=points;v++)
        {
            if(edg[u][v]<infinity)
            {
                if(dis[v]>dis[u]+edg[u][v])
                {
                    dis[v]= ⑤
                }
            }
        }
    }
    for(i=1;i<=points;i++)
    {
        cout<<dis[i]<<" ";
    }
    cout<<endl;
}

①处应填( )。 {{ select(34) }}

infinity
dis[j]
0
1

②处应填()。 {{ select(35) }}

infinity
dis[j]
0
1

③处应填()。 {{ select(36) }}

quanzhi
0
inf
1

④处应填()。 {{ select(37) }}

j
dis[j]
flag[j]
i

⑤处应填()。 {{ select(38) }}

dis[u]
edg[u][v]
dis[u]+edg[u][v]
infinity

（二）完全背包

容量为10的背包，有5种物品，每种物品数量无限，其重量分别为5,4,3,2,1，价值分别为1,2,3,4,5。设计算法实现背包内物品价值最大。

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

int main()
{
    int total_weight=10;
    int w[6]={0,5,4,3,2,1};
    int v[6]={0,1,2,3,4,5};
    int dp[11]={ ① };
    for(int i=1;i<= ② ;i++)
        for(int j=w[i];j<= ③ ;j++)
            dp[j]= ④
    cout<< ⑤ <<endl;
    return 0;
}

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

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

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

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

dp[j]+v[i]
dp[j-w[i]]+v[i]
min(dp[j],dp[j-w[i]]+v[i])
max(dp[j],dp[j-w[i]]+v[i])

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

v[10]
dp[10]
w[10]
total_weight

#CSP005. 入门级CSP-J第5套初赛模拟试题