26.卷1的答案

1.已知2010年小明·的生日在8月28日——周六 ，从2011到2020，有几次生日在周末？

做法：一个一个算下去,注意，平年365天，闰年366天，一共2次。

2.前序：ABDGKEHCFIJ，中序：GKDBHEACLFJ，问：后序？

做法：首先必须搞清楚前序、中序与后序的遍历方法。

NO.1 树（tree）-CSDN博客

然后，拿一张纸，画出这棵树，最终得出结论：KGDHEBLJFCA。

3.把10个西瓜（一模一样 ）装在4个一模一样的袋子中（也就是7111与1117算同一种），不能为空，问有几种？

做法：一个一个算下去，一共有7111,6211,5311,5221,4411,4321,3322,2224...9种！！！

4.某进制数：347 r=3213 4，则r=？

做法：用进制转换器试一试，结果是8。

5.switch语句中case语句必须在default语句之前。（）

做法：平时积累可知，case不一定在default之前。

6.链表的特点有什么？

做法：平时积累可知，链表插入删除不用移动元素。

7.如果对4 2 8 3 5 7 1 6进行冒泡排序，会发生几次交换？

做法：签到题，13种。（等等，我没错......）

8.T（n）=T（n-1）+n,T（1）=1,时间复杂度为？

做法：

1. 首先，通过递推式T(n)=T(n−1)+n，T(1)=1来展开T(n)：
   • 当n=2时，T(2)=T(1)+2。
   • 当n=3时，T(3)=T(2)+3=T(1)+2+3。
   • 当n=4时，T(4)=T(3)+4=T(1)+2+3+4。
   • 以此类推，当n=n时，T(n)=T(1)+2+3+⋯+n。
2. 然后，由于T(1)=1，所以T(n)=1+2+3+⋯+n。
   • 根据等差数列求和公式Sn​=2n(n+1)​，这里T(n)=2n(n+1)​。
3. 最后，分析时间复杂度：
   • T(n)=2n(n+1)​=21​n2+21​n。
   • 根据时间复杂度的定义，在计算时间复杂度时，只考虑最高次项，所以T(n)的时间复杂度为O(n2)。

综上，该算法的时间复杂度为O(n2)。

9.x&~(1<<n)可以将x的第n位设置为1吗？

做法：考查位运算，答案：nonononono。

10.一棵n层的满二叉树，总结点的数量和叶子节点数量之差是几？

做法：平时积累可知，答案：2^n-1-2^(n-1)。

11.代码题

#include<bits/stdc++.h>
using namespace std;//一个标准的递归代码
int f(int a,int b)
{if(a==b){return 1;}else if(a<b){return f(a+1,b)+1;}else{return f(a,b*2)+1;}} 
int main()
{int a,b;cin>>a>>b;cout<<f(a,b);return 0;
}

输入2 8，经过递归计算，得数为7。

#include<bits/stdc++.h>
#include<cmath>
using namespace std;
unsigned long long k,len;
int n;
bool flag; 
int main()
{cin>>n>>k;len=pow(2,n-1);while(len){if(!flag){if(k<len) cout<<"0";else if(k>=len){cout<<"1";k-=len;flag=true;}}else if(flag){if(k<len){cout<<"1";flag=false;}else if(k>=len){cout<<"0";k-=len;}}len>>=1;}return 0;
}

1.将第15行和第24行，k-=len改为1<<(n-1),程序运行不变。

解析：len为2的整数次幕，所以k在二进制下与len做异或其实就是将最高位设置为0，相当于减len。

2.输出结果110110111，问k=?

解析：递推即可，最低位为1，在1位编码中是第2个。

第2位为1，在2位编码中应该是2+（2-2+1）=3个。

第3位为1，在3位编码中应该是4+（4-3+1）=6个。

第4位为0，在4位编码中应该是6个。

第5位为1，在5位编码中应该是16+（16-6+1）=27个。

第6位为1，在6位编码中应该是32+（32-27+1）=38个。

第7位为0，在7位编码中应该是38个。

第8位为1，在8位编码中应该是128+（128-38+1）=219个。

第9位为1，在9位编码中应该是256+（256-219+1）=294个。

故k=293。

#include<bits/stdc++.h>
#include<cmath>
using namespace std;
int main()
{int n,k;cin>>n>>k;vector<int> cnt(31,0),a(n);for(int i=0;i<n;++i){cin>>a[i];for(int j=30;j>=0;--j){if(a[i]&(1<<j)) ++cnt[i];if(need<=k){k-=need;ans+=(1<<i);}}}cout<<ans<<"\n";return 0;
}

1.输入4 4 3 1 3 1。输出的数据为？

解析：对3 1 3 1做4次操作，可以把这4个数字中最高位第30位变为1，即（1<<30）+(3&1)=1073741825

2.输入1 30 0。输出的数据为？

解析：对0这一个数字，从最高位开始赋值为1，经过30次操作，也就是（01111111 11111111 11111111 11111110），即2的31次方-1-1

#include<bits/stdc++.h>
#include<cmath>
using namespace std;//本题主要考察贪心思想
int a[1000005],b[1000005];
int cnta[1000005]={1e9},cntb[1000005]={1e9};
int nowa[1000005],nowb[1000005];
int main()
{int n,m,x,now=0;scanf("%d%d%d",&n,&m,&x);for(int i=0;i<n;i++){scanf("%d",&a[i]);if(!i||a[i]==a[i-1]){now++;}else cnta[now]++,now=1;}cnta[now]++;now=0;for(int i=0;i<m;i++){scanf("%d",&b[i]);if(!i||b[i]==b[i-1]){now++;}else cntb[now]++,now=1;}cntb[now]++;int ans=0,nowans=0,pa=n,pb=m;for(int i=0;i<x;i++){while(nowa[pa]==cnta[pa]) pa--;nowa[pa]++;nowans+=pa;}ans=nowans;for(int i=1;i<=x;i++){while(!nowa[pa]) pa++;nowa[pa]--; nowans-=pa;while(nowb[pb]==cntb[pb]) pb--;nowb[pb]++;nowans+=pb;ans=max(ans,nowans);}printf("%d\n",ans);return 0;
}

1.输入：

3 5 1
1 1 1
2 2 2 2 2

则输出？

解析：经过桶排序计算，cnta[3]=1,表示出现3次的数字有1个，cnt[5]=1，表示出现5次的数字有1个。X=1，也就是说要选一个数字能够覆盖更多的数字，因此选择2，可以覆盖5个数字。

2.对于任意合法输入，ans 最大可达到？

解析：根据数据范围可知，x最多可选n+m个，即2*10的6次方个。

#include<bits/stdc++.h>
#include<cmath>
using namespace std;
string a,b;
int c1[26],c2[26],ans=INT_MAX;
int main()
{cin>>a>>b;int n=a.size(),m=b.size();for(int i=0;i<n;i++) c1[a[i]-'a']++;//填空1for(int i=0;i<m;i++) c2[b[i]-'a']++;for(int i=0;i<26&&ans!=0;i++){int ca=n-c1[i],cb=m-c2[i];ans=n=min(ans,ca+cb);//填空2if(i==0) continue;//填空3int r1=0,r2=0;for(int j=i;j<26;j++) r1+=c1[j];for(int j=0;j<i;j++) r1+=c2[j];for(int j=0;j<i;j++) r2+=c1[j];for(int j=i;j<26;j++) r2+=c2[j];//填空4ans=min(ans,min(r1,r2));//填空5}cout<<ans;return 0;
}