16.前序遍历序列与中序遍历序列相同的二叉树为（ ）。
前序遍历的顺序依次为“根结点-左子树-右子树”，中序遍历的顺序依次为“左子树-根结点-右子树”。所以当二叉树只有根结点或非叶子结点只有右子树时前序遍历与中序遍历相同
19.设某算法的计算时间表示为递推关系式 T(n)= T(n-1)+ n（n为正整数）及 T(0)= 1，则该算法的时间复杂度为（ ）。
=T(n-2)+(n-1)+n
=n*(n+1)/2 O(n^2)
（打印月历）输入月份 m(1<m<12)，按一定格式打印 2015 第m月的月历。

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将每个月的日期输出到对应的星期上。
(1)1月偏移数为4，故填offset=4
(2)计算第m月的偏移，加上前一个月的天数模7 offset + dayNum[i]) % 7
(3)输出第m个月的日期dayNum[m]
(4)输出i表示的日期i
(5)如果是七的倍数换行，(offset + i) % 7

(中位数）给定n（n为奇数且小于 1000）个整数，整数的范围在0~m 0<m<2^31之间，请使用二分法求这n个整数的中位数。所谓中位数，是指将这n个数排序之后，排在正中间的数。

include [HTML_REMOVED]

using namespace std;
const int MAXN = 1000;
int n,i,lbound,rbound,mid,m,count;
int x[MAXN];
int main()
{
cin >> n >> m;
for(i = 0; i < n; i)
cin >> x[i];
lbound = 0;rbound = m;
while(①) {
mid=(lbound+rbound)/2;
②;
for(i = 0; i < n; i)
{
if(③)
④;
}
if(count > n/2)
lbound = mid + 1;
else
⑤;
}
cout << rbound << endl;
return 0;
}
(3)if(count > n/2) lbound = mid+1;表示：如果count的个数超过了一半，再到更大的值区间中搜索中位数，即mid不够大。所以此空应填入x[i]>mid。
(4)count++
(5)调整右边界rount=mid

D n=(n-1)(D n-1+D n-2)

性质1：在二叉树的第i层上最多有2^(i-1)个结点（i≥1）。
性质2：深度为k的二叉树至多有2^k-1个结点（k≥1）。
性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
性质4：具有n个结点的完全二叉树的深度为|log（2^n）+1|
性质5：如果对一棵有n个结点的完全二叉树（其深度为|log（2^n）+1|）的结点按层序编号