当前没有测试数据。

阅读程序2

1  #include <bits/stdc++.h>
2  using namespace std;
3  
4  int const MAXN = 1000001;
5  int q2[MAXN];   
6  int a[MAXN];   
7  int n, m;     
8  
9 int max_deque() {
10     int h = 1, t = 0; 
11     for(int i = 1; i <= n; i++) {
12         while(h <= t && q2[h] + m <= i) h++;     
13         while(h <= t && a[q2[t]] < a[i]) t--;
14         q2[++t] = i;
15         if(i >= m) cout << a[q2[h]] << " ";
16     }
17 }
18  
19 int main() {
20     cin >> n >> m;
21     for(int i = 1; i <= n; i++) {
22         scanf("%d", &a[i]);
23     }
24     max_deque();
25     return 0;
26 }

判断题
程序的时间复杂度是 O(n)。（ ）
A. 正确
B. 错误
在程序中，h 和 t 可以看作是一个队列的尾部和头部。（ ）
A. 正确
B. 错误
如果输入的数组是单调递增的，那么程序在执行11行循环时，每循环一次，数组q2中的元素就会多增加一个。（ ）
A. 正确
B. 错误
单选题
对于输入数组[1,2,3,4,5,6,7],m的值为3，程序中数组q2的最大的有效长度是多少？
A. 1
B. 3
C. 4
D. 5
对于输入数组 [1, 3, -1, -3, 5, 3, 6, 7] ,m的值为3，程序的输出将为（ ）
A. 1 3 3 3 5 5 6 7
B. 3 3 5 5 6 7
C. 3 3 3 5 5 6 7
D. 3 3 5 5 6 7
对于长度为 10 的数组,m的值为 4，在最坏情况下，程序中数组 q2 的最大有效长度是多少？
A. 2
B. 3
C. 4
D. 5