CSP-J 模拟试题（12）

您的姓名：
文件型病毒传染的主要对象是
内存地址的最重要特点是( )
最早的计算机的用途时用于( )
一颗完全二叉树， 共有1234个结点， 其叶子结点的个数位()
以下不属于应用层的是()
当A>=B&& B>=C的取值为真实表达式，A>C||B==C的值( )
十进制小数11. 375对应的二进制数是（）
C++中，125^2的值是( )。
设S="abbcce"，不同的非空子串个数有( )个。
一棵6节点二叉树的中序遍历为DBAGECF,先序遍历为ABDCEGF，后序遍历为()
一张有9个节点的无向图最多有()条边
电视台连续播放 6 个广告， 其中含 4 个不同的商业广告和 2 个不同的公益广告， 要求首尾必须播放公益广告， 则共有() 种不同的播放方式(结果用数值表示)
下列排序算法中，平均时间复杂度是O(n^2)的是( )
下列叙述中正确的是( )
在TCP/ IP协议中，TCP和IP分别提供什么服务？( )
17. 二、阅读程序题
1.#include <iostream>
2.#include <cstdio>
3.using namespace std;
4.int i, j, n;
5.int x[101], y[101];
6.int main()
7.{
8.     cin >> n;
9.     for(i=1; i<=n; i++) cin >> x[i];
10.     for(i=1; i<=n-1; i++)
11.          for(j=i+1; j<=n; j++)
12.              if(x[i]>x[j])
13.                 y[j]++;
14.              else if(x[i]<x[j])
15.                  y[i]++;
16.     for(i=1; i<=n; i++)
17.      printf("%5d_", y[i]);
18.     cout << endl;
19.     return 0;
20.}
判断题：
（1）（1分）把第13行与第15行互换位置， 结果不会改变。___________A. 正确 B. 错误
（2） （1分）第14行把if(x[i]<x[j])删掉效果一样。______________A. 正确 B. 错误
（3） 第11行把i+1改成1， 数组y每个元素的值增加1倍。_______________A. 正确 B. 错误
（4） 数组y[i]中存的是x[i]在数列中从大到小的次序。___________A. 正确 B. 错误
选择题：
（5） 此程序的时间复杂度是____________
A. O(log n)     B. O(n log n)    C. O(n^2)    D. O(n)
  (6) 此程序如果n输入4， 然后输入2 4 1 3， 输出结果是____________
A. 1 2 3 4    B. 2 0 3 1    C. 4 3 2 1  D. 1 3 0 2 
18. 阅读程序二：
1.#include <iostream>
2.using namespace std;
3.int main(){
4.     int a[1001], i, j, t, n;
5.     for(i=0; i<=1000; i++)
6.          a[i]=0;
7.     scanf("%d", &n);
8.     for( i=1; i<=n; i++){
9.          scanf("%d", &t);
10.         a[t]++;
11.     }
12.     for(i=1000; i>=0; i--)
13.          for(j=1; j<=a[i]; j++)
14.              printf("%d ", i);
15.     return 0;
16.}
判断题：
1. 输入10个数字， 输出结果是从小到大。_________  A. 对      B. 错
2. 若输入的数字中有两个1， 则输出时出来第一个1是第一个输入的。_________   A. 对 B. 错
3. （2分）若将第13行的”<=”改为”<", 且输入数据为10 2 12 33 34 1 2 87 22 9 0， 则输出2。_________ A. 对 B. 错
4. （2分）若将第12行改为for(i=0; i<=1000; i++), 则程序运行结果不变。_____________ A. 对 B. 错
选择题：
5. 若将第12行改为for(i=1000; i>1; i--); 第13行改为for(j=a[i]; j>1; j--), 输入数据为5 2 12 33 34 44， 则运行结果_________
A. 不变    B. 输出 2 12 33 34 44    C. 无输出      D. 输出 44 34 33 12 2
6. (4分）若将第10行改为++a[t]或a[t++], 则输入5 1 2 3 4 5， 输出结果为_____________
A. 1 2 3 4 5 或 5 4 3 2 1    B. 1 2 3 4 5 或无输出    C. 5 4 3 2 1 或5 4 3 2 1       D. 5 4 3 2 1或无输出
19. 阅读3

1.#include <iostream>
2.using namespace std;
3.const int maxn=100000;
4.int a[maxn], b[maxn], n;
5.int Search(int num, int low, int high)
6.{
7.     int mid;
8.     while(low<=high)
9.     {
10.          mid=(low+high)/2;
11.          if(num>=b[mid]) low=mid+1;
12.          else high=mid-1;
13.     }
14.     return low;
15.}
16.int main()
17.{
18.     int len, pos;
19.     cin >> n;
20.     for(int i=1; i<=n; i++)
21.          cin >> a[i];
22.     b[1]=a[1];
23.     len=1;
24.     for(int i=2; i<=n; i++)
25.     {
26.          if(a[i]>=b[len])
27.          {
28.              len++;
29.              b[len]=a[i];
30.          }
31.          else
32.          {
33.              pos=Search(a[i], 1, len);
34.              b[pos]=a[i];
35.          }
36.     }
37.     cout << len << endl;
38.     return 0;
39.}
判断题：
（1）(1分）输入的a[i]必须在[1, n]范围内。_____________A. 正确 B. 错误
（2）（1分）把第11行的“mid+1”改成“mid”不影响程序运行结果。_____________A. 正确 B. 错误
（3）当数组a单调不降时输出为1。_____________A. 正确 B. 错误
（4）数组b内的元素始终单调不降。_____________A. 正确 B. 错误
选择题：
（5）当输入第一行为20， 第二行为1 20 2 19 3 18 4 17...9 12 10 11时， 输出结果为_________________
A.1 B. 10 C. 11 D. 20
（6）该算法的时间复杂度为____________
A.O( n) B. O(nlog n) C. O(n^2) D. O(n^2longn)
20. 三. 完善程序1

迪杰斯特拉算法是由荷兰计算机科学家迪杰斯特拉于1959年提出的，因此又叫迪克杰斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题，迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

//模拟5完善程序1
1.#include <iostream>
2.using namespace std;
3.int main()
4.{
5.     int edgs;
6.      int points;
7.     int dis[10];
8.     int flag[10];
9.     int infinity=9999999;
10.     cin >> points >> edgs;
11.     int edg[10][10];
12.     for(int i=1; i<=points; i++)//初始化
13.     {
14.          for(int j=1; j<=points; j++)
15.          {
16.              if(i==j)
17.              {
18.                  edg[i][j]=               1             ;
19.              }
20.              else
21.              {
22.                  edg[i][j]=               2           ;
23.              }
24.          }
25.     }
26.     int point1, point2, quanzhi;
27.     for(i=1; i<=edgs; i++)
28.     {
29.          cin >> point1 >> point2 >> quanzhi;
30.          edg[point1][point2]=           3              ;
31.     }
32.     for(i=1; i<=points; i++)
33.     {
34.          dis[i]=edg[1][i];
35.     }
36.     for(i=1; i<=points; i++)
37.     {
38.          flag[i]=0;
39.     }
40.     flag[1]=1;
41.     int min, u;
42.     for(i=1; i<=points-1; i++)
43.     {//源点到源点不用比较， 因此总的次数少一次
44.          min=infinity;
45.          for(int j=1; j<points; j++)
46.          {
47.              if(flag[j]==0&&dis[j]<min)
48.              {//核心思想：依次比较出里源点最近的点
49.                  min=                        4                       ;
50.                  u=j;
51.               }
52.          }
53.          flag[u]=1;
54.          for(int v=1; v<=points; v++)
55.          {
56.              if(edg[u][v]<infinity)
57.              {
58.                  if(dis[u][v]>dis[u]+edg[u][v])
59.                  {
60.                      dis[v]=                          5                                ;
61.                  }
62.              }
63.          }
64.     }
65.     for(i=1; i<=points; i++)
66.     {
67.          cout << dis[i] << ' ';
68.      }
69.     cout << endl;
70. }
（1）1处应填________
A.infinity B. dis[j] C. 0 D. 1
（2）2处应填________
A.infinity B. dis[j] C. 0 D. 1
（3）3处应填_____________
A.quanzhi B. 0 C. inf D. 1
（4）4处应填___________
A.j B. dis[j] C. flag[j] D. i
（5）5处应填____________
A.dis[u] B. edg[u][v] C. dis[u]+edg[u][v] D. infinity
21. 完善程序2
斐波那契序列为1，1，2，3，5，8，13，21，其元素产生的规则是前两个数为1，从第3个数开始，每两个数等于它前面两个数之和，已知任意一个正整数可以表示为若干个互不相同的斐波那契数列之和，例如36=21+13+2
下面的程序是由键盘输入一个正整数n输出组成n的互不相同的斐波那契数。
算法说明：
1.寻找小于等于n的最大斐波那契数列a并以a作为组成n的一个数.
2. 若n!=a，则以n-a作为n的新值重复步骤1，若a=n则结束
1.#include <iostream>
2.#include <cstdio>
3.using namespace std;
4.int n;
5.bool first;
6.int find(int n)
7.{
8.     int a, b, c;
9.     a=1, b=1;
10.     do
11.     {
12.          c=a+b;
13.         (               1                   );
14.     }while(b<n);
15.     if(             2           )
16.          return b;
17.     else
18.          （           3                  ）;
19.}
20.void p(int n)
21.{
22.      int a;
23.      a=find(n);
24.      if(first)
25.      {
26.          printf("%4d", a);
27.          first=false;
28.      } else
29.          （                 4                     ）;
30.      if(a<n) （          5            ）；
31.}
32.int main()
33.{
34.      cin >> n;
35.      first=true;
36.      printf("%5d=", n);
37.      p(n);
38.      cout << endl;
39.      return 0;
40.}
（1）1处应填_________________
A. a=c; b=a;    B. a=b; b=c;    C. a==c; b==a    D. a==b; b==c
（2）2处应填_________________
A. b==n    B. b<n    C. a==n    D. a<n
（3）3处应填_________________
A. return c    B. return b    C. return a+b    D. return a
（4） 4处应填_________________
A. printf(" %4d", a)    B. printf(" + %4d", a)
C. printf(" %4d", b)    D. printf(" + %4d", b)
（5） 5处应填__________________
A. p(a)    B. p(b)    C. p(n-a)    D. p(n-b)








更多问卷 复制此问卷