题目答案
D
题目解析
前序遍历的顺序依次为“根结点-左子树-右子树”，中序遍历的顺序依次为“左子树-根结点-右子树”。所以当二叉树只有根结点或非叶子结点只有右子树时，前序遍历和中序遍历的顺序都退化成了：根、右子树，故二者得到的序列相同。要使中序遍历序列与前序遍历序列相同，每个非叶子结点都不能有左子树。
（打印月历）输入月份 m(1 \le m \le 12)m(1≤m≤12)，按一定格式打印 20152015 第 mm 月的月历。
例如，2015 年一月的月历打印效果如下（第一列为周日）：
include[HTML_REMOVED]
using namespace std;
const int dayNum[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};
int m, offset, i;
int main()
{
cin >> m;
cout <<”S M T W T F S”<<endl;//’ ‘为tab制表符
①;
for (i = 1; i < m; i)
offset = ②;
for (i = 0; i < offset; i)
cout <<’ ‘;
for (i = 1; i <= ③;i++)
{
cout << ④;
if(i==dayNum[m]||⑤==0)
cout << endl;
else
cout << ‘ ‘;
}
return 0;
}
题目答案
填空位置 ①：
offset = 4
填空位置 ②：
(offset + dayNum[i]) % 7
填空位置 ③：
dayNum[m]
填空位置 ④：
i
填空位置 ⑤：
(offset + i) % 7
题目解析
首先我们先看到较为简单的第三、四两空，这两空对应的过程显然就是输出日历了。for循环内应该是对每一天输出一个日期，因此循环范围就应该是这个月的天数，也就是dayNum[m]。什么时候应该输出换行符呢？要么就是所有日期输出完毕了（i==dayNum[m]），要么就是输出了一个星期之后进行换行，所以这里对应的就是每个星期结束，也就是当i为 77 的倍数时进行换行。下面再回过来看前两空。通过上面一个for循环可以看出来这个offset是用来控制月历开始的时候要输出多少的空位，再参照题目给出的第一个月的月历就可以知道offset初值应该是 44，即第一空对应需要做的事情。但是这个offset只是对于第一个月正确，因此需要再加上所有小于 11 月的月份的天数，计算offset的方法即为(offset+dayNum[i]) % 7。
(中位数）给定 nn（nn 为奇数且小于 10001000）个整数，整数的范围在00~mm（0 \lt m \lt 2^{31}0<m<2
31
）之间，请使用二分法求这 nn 个整数的中位数。所谓中位数，是指将这 nn 个数排序之后，排在正中间的数。
1
include [HTML_REMOVED]
2
using namespace std;
3
const int MAXN = 1000;
4
int n,i,lbound,rbound,mid,m,count;
5
int x[MAXN];
6
int main()
7
{
8
cin >> n >> m;
9
for(i = 0; i < n; i)
10
cin >> x[i];
11
lbound = 0;rbound = m;
12
while(①) {
13
mid=(lbound+rbound)/2;
14
②;
15
for(i = 0; i < n; i)
16
{
17
if(③)
18
④;
19
}
20
if(count > n/2)
21
lbound = mid + 1;
22
else
23
⑤;
24
}
25
cout << rbound << endl;
26
return 0;
27
}
28
题目答案
填空位置 ①：
lbound < rbound
填空位置 ②：
count = 0
填空位置 ③：
x[i] > mid
填空位置 ④：
count++
填空位置 ⑤：
rbound = mid
题目解析
这是一道经典的左闭右闭的二分题，整个题目的过程为：先二分答案，再遍历整个数组验证。第一空是二分的条件，所以应该为lbound<rbound。第二空应该是将计数器count初始化操作，第三空、第四空就对应着统计大于（或小于）mid的数值个数的条件与过程，第五空则是调整右边界，可以参照左边界的调整方法仿写为rbound=mid。
