2020CSP-J3

一、單項選擇題（共15題，每題2分，共計30分;每題有且僅有一個正確選項）

1、檔案型病毒傳染的主要物件是（）
A.文本檔案
B.系統檔案
C.可執行檔案
D. .EXE 和.COM檔案
2、24 針列印機的解析度約為180dpi. Dpi 數越大，列印精度越高，其中單位dpi是指（）
A.印點/厘米
B.印點/毫米
C.印點/英寸
D.印點/寸
3、記憶體地址的最重要特點是（）
A.隨機性
B.唯一性
C.順序性
D.連續性
4、多媒體計算機是指（）
A.具有多種功能的計算機
B.具有多種外設的計算機
C.能處理多種媒體的計算機
D.能借助多種媒體操作的計算機
5、最早的計算機的用途是用于（）
A.科學計算
B.自動控制
C.系統仿真
D.輔助設計
6、CPU中（）機構相當于運算器中的一個存盤單元，它的存取速度比存盤器要快得多，
A.存放器
B.輔存
C.主存
D.暫存器
7、計算機軟體我們一般指的是（）
A.系統軟體和實用軟體
B.實用軟體和自由軟體
C.培訓軟體和管理軟
D.編輯軟體和科學計算軟體
8、作業系統在第幾代計算機開始應用（）
A.第一代
B.第二代
C.第三代
D.第四代
9、計算機中的數有浮點與定點兩種，其中用浮點表示的數，通常由( )這兩部分組成（）
A.指數與基數
B.尾數與小數
C.階碼與尾數
D.整數與小數
10.如果用一個位元組來表示整數，最高位用作符號位，其他位表示數值，例如: 0000001 表示+1，1000001 表示-1，試問這樣表示法的整數A的范圍應該是（      ）
A. -127<=A<=127		B. -128<=A<=128		C. -128<=A<128		D. -128<=A<=127
11.下列敘述中，正確的是（    ）
A.線性表的線性存盤結構優于鏈表存盤結構
B.佇列的操作方式是先進后出
C.堆疊的操作方式是先進先出
D.二維陣列是指它的每個資料元素為一個線性表的線性表
12.用某種排序方法對線性表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.
那么，排序方法是（）
A. 選擇排序			B. 希爾排序			C. 合并排序			D. 快速排序
13.如果某二叉樹的前序為STUWV， 中序為UWTVS，那么該二叉樹的后序是（）
A. WUVTS			B. UWVTS			C. VWUTS			D. WUTSV
14.下面關于資料結構的敘述中，正確的敘述是（）
A.順序存盤方式的優點是存盤密度大，且插入、洗掉運算效率高
B.鏈表中的每一個結點都包含一個指標
C.包含n個結點的二叉排序樹的最大檢索長度為log(2n)
D.將一棵樹轉換為二又樹后，根結點沒有右子樹
15.運算式(1+34)*5-56/7的后綴運算式為（）
A.1 34+5 56 7-*/       
B.-*+1 34 5/56 7
C.1 34 +5*56 7/-
D.1 34 5* +56 7/

二、閱讀程式（程式輸入不超過陣列或字串定義的范圍；判斷題正確填 T，錯誤填F；除特殊說明外，判斷題1.5分，選擇題4分，共計40分）
1） 漢諾塔問題:古代有一個梵塔，塔內有三個座A、B、C，A座上有n個盤子，盤子大小不等，大的在下，小的在上.有一個和尚想把這n個盤子從A座移到B座，但每次只能允許移動一個盤子，并且在移動程序中，3個座上的盤子始終保持大盤在下，小盤在上，程式如下:
1.#include <iostream>
2.using namespace std;
3.void hanoi(int n,char a,char b,char c){
4.  if(n==1)
5.    cout<<n<<" "<<a<<" "<<c<<endl;
6.  else{
7.    hanoi(n-1,a,c,b);
8.    cout<<n<<" "<<a<<" "<<c<<endl;
9.    hanoi(n-1,b,a,c);
10.  }
11.}
12.int main(){
13.  int n;
14.  cin>>n;
15.  hanoi(n,'A','B','C');
16.  return 0;
17.}
判斷題
16.（1分）當n≥0時，程式不會出現死回圈， 
17.（1分）輸出共有n行，	
18. 當n > 0時，將第4行的“==”改為“<=”，程式輸出必定不變， 
19. 將第5行的“n”改為“1”，程式輸出結果必定不變，
選擇題
20.（3分）此程式的時間復雜度是（   ）
A. O(n)				B. O(n^2)				C. O(n^3)				D. O(2^n)
21. 若要求程式輸出不超過15行，則下列哪個n的值是合法的（   ）
A. 0					B. 4					C. 5					D. 6

2）
1.#include <cstdio>
2.#define N 1005
3.
4.using namespace std;
5.int num[N];
6.
7.int main(){
8.  int al=1,n,x;
9.  scanf("%d",&n);
10.  num[1]=1;
11.  for(int i=1;i<=n;++i){
12.    x=0;
13.    for(int j=1;j<=al;++j){
14.      num[j]=num[j]*5+x;
15.      x=num[j]/10;
16.      num[j]%=10;
17.    }
18.    if(x>0) num[++al]=x;
19.  }
20.  printf("0.");
21.  for(int i=al;i<n;++i){
22.    putchar('0');
23.  }
24.  for(int i=al;i>=1;i--){
25.    printf("%d",num[i]);
26.  }
27.  putchar('\n');
28.  return 0;
29.}
判斷題
22.（1分）程式輸出的是5^n的值，   
23.（1分）程式執行到第27行時，i的值為1，   
24. 對于任意1≤i≤al，都有0≤num≤9， 
25. 程式輸出的是一個小數，且小數末尾可能有多余的0，
選擇題
26. 此程式的時間復雜度是（   ）
A. O(n)				B. O(n^2)				C. O(n^3)				D. O(n log n)
27. 若n=3，則輸出為（   ）
A. 8					B. 0.125				C. 0.8				D. 125

3） 在起點和終點之間，有N塊巖石(不含起點和終點的巖石)，在比賽程序中，選手們將從起點出發，每一步跳向相鄰的巖石，直至到達終點，
     為了提高比賽難度，組委會計劃移走一些巖石，使得選手們在比賽程序中的最短跳躍距離盡可能長，由于預算限制，組委會至多從起點和終點之間移走M塊巖石(不能移走起點和終點的巖石)，
    輸入檔案第一行包含三個正整數L, N, M，分別表示起點到終點的距離，起點和終點之間的巖石數，以及組委會至多移走的巖石數，
     接下來N行，每行一個整數，第i行的整數a[i] (0 < a[i] < L)表示第i塊巖石與起點的距離，這些巖石按與起點距離從小到大的順序給出，且不會有兩個巖石出現在同一個位置，
     輸出檔案只包含一個整數，即最短跳躍距離的最大值，
1.#include <iostream>
2.using namespace std;
3.int l,n,m,a[50005],ans;
4.bool check(int dis)
5.{
6.  int count=0,last=0;
7.  for(int i=1;i<=n;i++)
8.    if(a[i]-last<dis) count++;
9.      else last=a[i];
10.  if (count>m) return 0;return 1;
11.}
12.int main()
13.{
14.    ios::sync_with_stdio(0);
15.    cin>>l>>n>>m;
16.    for(int i=1;i<=n;i++)
17.      cin>>a[i];
18.    a[n+1]=l;
19.    int fl=0,fr=l;
20.    while(fl<=fr)
21.    {
22.      int mid=(fl+fr)/2;
23.      if(check(mid)) fl=mid+1,ans=mid;
24.      else fr=mid-1;
25.    }
26.    cout<<ans;
27.    return 0;
28.}
判斷題
28.（1分）將第19行的“fl=0”改為“f1=1”，程式輸出結果必定不變， 
29.（2分）程式執行到第26行時，必有fl>fr，  
30.（2分）若第23行執行的check(mid)==1, 則最終的ans≤此時的mid，  
31.（2分）程式執行到第10行時，count 的值表示：如果最短跳躍距離恰好為dis，那么最少需要移走幾塊巖石，    
選擇題
32. 此程式的時間復雜度是（    ）
A. O(n^ 2)				B. O(nl)				C. O(n log l)			D. O(n log n)
33. 若輸入為：
25 5 2
2
11
14
17
21
則輸出為（    ）
A. 3 					B. 4					C. 5					D. 6

三、完善程式（每小題3分，共計30分）
1)  迪杰斯特拉演算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉演算法，是從一個頂點到其余各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題，迪杰斯特拉演算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止，
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]=  ①  ;
19.      }
20.      else
21.      {
22.        edg[i][j]=  ②  ;
23.      }
24.    }
25.  }
26.  int point1,point2,quanzhi;
27.  for(int i=1;i<=edgs;i++)
28.  {
29.    cin>>point1>>point2>>quanzhi;
30.    edg[point1][point2]=  ③  ;
31.  }
32.  for(int i=1;i<=points;i++)
33.  {
34.    dis[i]=edg[1][i];
35.  }
36.  for(int i=1;i<=points;i++)
37.  {
38.    flag[i]=0;
39.  }
40.  flag[1]=1;
41.  int min,u;
42.  for(int i=1;i<=points-1;i++)
43.  {//從源點到源點不用比較，因此總的次數少一次
44.    min=infinity;
45.    for (int j=1;j<points;j++)
46.    {
47.      if (flag[i]==0&&dis[j]<min)
48.      {//核心思想：依次比較出離源點最近的點
49.        min=  ④  ;
50.        u=j;
51.      }
52.    }
53.    flag[u]=1;
54.    for(int v=1;v<=points;v++)
55.    {//找出離源點最近的點更新dis里面的源點到各個點的值是否最小
56.      if (edg[u][v]<infinity)
57.      {
58.        if (dis[v]>dis[u]+edg[u][v])
59.        {
60.          dis[v]=   ⑤   ;
61.        }
62.      }
63.    }
64.  }
65.  for(int i=1;i<=points;i++)
66.  {
67.    cout<<dis[i]<<" ";
68.  }
69.  cout<<endl;
70.}
34.①處應填（    ）
A. infinity			B. dis[j]				C. 0					D. 1
35.②處應填（    ）
A. infinity			B. dis[j]				C. 0					D. 1
36.③處應填（    ）
A. quanzhi			B. 0					C. infinity			D. 1
37.④處應填（    ）
A. j					B. dis[j]				C. flag[j]				D. i
38.⑤處應填（    ）
A. dis[u]				B. edg[u][v]			C. dis[u]+edg[u][v]	D. infinity

2）完全背包問題
     容量為10的背包，有5種物品，每種物品數量無限，其重量分別為5, 4, 3, 2，1，其價值分別為1，2，3，4，5，
     設計演算法，實作背包內物品價值最大，代碼如下(輸出50)
1.#include<iostream>
2.#include<algorithm>
3.
4.using namespace std;
5.
6.int main()
7.{
8.  int total_weight=10;
9.  int w[6]={0,5,4,3,2,1};
10.  int v[6]={0,1,2,3,4,5};
11.  int dp[11]={  ①  };
12.
13.  for(int i=1;i<=  ② ;i++)
14.    for(int j=w[i];j<= ③ ;j++)
15.      dp[j]= ④ ;
16.  
17.  cout<< ⑤ <<endl;
18.  return 0;
19.}

39.①處應填（    ）
A. 0				B. 5				C. 10			D. 15
40.②處應填（    ）
A. 5				B. 6				C. 10			D. 15
41.③處應填（    ）
A. 5				B. 6				C. 10			D. 15
42.④處應填（    ）
A.dp[j]+v[i]
B.dp[j-w[i]]+v[i]
C.min(dp[j],dp[j-w[i]]+v[i])
D.max(dp[j],dp[j-w[i]]+v[i])
43.⑤處應填（    ）
A. v[10]			B. dp[10]		C.w[10]			D. total_weight

要答案的可以私聊我^_^