参考答案
B D A A C
B C A D A
A B B A D
A A A A B
A B A D B
D A A A B
D C B A C
A D A B A
B C
单选题
1.小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有（）种选择时间段的方案。
[A]31
[B]18
[C]21
[D]33
解析过程
由于时间段数量较少（仅7个），可以通过分类讨论被选中时间段的数量k来计算方案数。k=1:7种;k=2:10种;k=3:1种;总方案数:7+10+1=18种。
2.给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么?
[A]EDBGFCA
[B]EDGBFCA
[C]DEBGFCA
[D]DBEGFCA
解析过程
跟具题意得以下图示：A / \ B C / \ D F \ \ E G
3.考虑一个有向无环图，该图包含 4 条有向边：(1,2),(1,3),(2,4) 和 (3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序?
[A]1,2,3,4
[B]4,3,2,1
[C]2,3,4,1
[D]3,4,2,1
解析过程
根据给定的有向无环图（边为 (1,2)、(1,3)、(2,4) 和 (3,4)），拓扑排序必须满足：对于每条有向边 (u,v)，u 在排序中出现在 v 之前。具体约束包括： 1 必须在 2 之前（因边 (1,2)）。 1 必须在 3 之前（因边 (1,3)）。 2 必须在 4 之前（因边 (2,4)）。 3 必须在 4 之前（因边 (3,4)）。
4.一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有多少种可能的组合?( )
[A]1420
[B]1770
[C]1540
[D]2200
解析过程
班级总人数为10+12=22人。总的三人小组数为组合数$C^3_{22}$=1540不满足条件的组合（即全是男生的小组）数为$C^3_{10}$=120因此，至少包含 1 个女生的组合数为：1540−120=1420
程序题
1.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int f(string x,string y){
int m=x.size();
int n=y.size();
vector<vector<int>>v(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(x[i-1]==y[j-1]){
v[i][j]=v[i-1][j-1]+1;
}else{
v[i][j]=max(v[i-1][j],v[i][j-1]);
}
}
}
return v[m][n];
}
bool g(string x,string y){
if(x.size() != y.size()){
return false;
}
return f(x+x,y)==y.size();
}
int main(){
string x,y;
cin>>x>>y;
cout<<g(x,y)<<endl;
return 0;
}
拼接字符串和子序列匹配
2.
#include <iostream>
#include <cmath>
using namespace std;
int solve1(int n){
return n*n;
}
int solve2(int n){
int sum=0;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
if(n/i==i){
sum+=i*i;
}else{
sum+=i*i+(n/i)*(n/i);
}
}
}
return sum;
}
int main(){
int n;
cin>>n;
cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
return 0;
}
- 如果输入的 n 为质数 p 的平方，那么 solve2(n) 的返回值为（ ）
[A]n^2+n+1
[B]p^2+p+1
[C]n^2+1
[D]p^4+2*p^2+1
解析过程
函数 solve2(n) 计算n所有因子的平方和,则答案为n^2+n+1。
- 当输入为正整数时，第一项减去第二项的差值一定（ ）
[A]>0
[B]>=0&&不一定>0
[C]<0
[D]<=0&&不一定<0
解析过程
差值a−b≤0，且当n=1时等于0，不总是小于0。
填空题
寻找被移除的元素
原有长度为 n+1 公差为 1 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 n 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。
#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right){
int mid = left + (right - left) / 2;
if (nums[mid] == mid + ①) {
left=mid+1;
} else {
right=mid;
}
}
return left+nums[0];
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) cin >> nums[i];
int missing_number = find_missing(nums);
if (missing_number == ⑤) {
cout << "Sequence is consecutive" << endl;
}else{
cout << "Missing number is " << missing_number << endl;
}
return 0;
①:nums[0]
因为等差数列的起始值是nums[0]⑤:nums[n-1]
若序列连续（移除首元素或尾元素），返回值等于数组末位元素 nums[n-1]；否则为缺失元素值。
一个使用二分查找来寻找缺失元素的算法
编辑距离
给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
int m = str1.length();
int n = str2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i-1][j-1]);
}
}
return dp[m][n];
}
int main() {
string str1, str2;
cin >> str1 >> str2;
cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl;
return 0;
}
动态规划
dp[i][j]表示从a[1..i]转换成b[1..j]的编辑距离，dp[n][m]就是答案。
求dp[i][j]考虑两个字符串a[1..i],b[1..j]的尾字符分类讨论: ① a[i] = b[j] dp[i][j] = dp[i-1][j-1]; ② a[i] != b[j] 讨论三种操作情况：插入、删除、修改，取三种情况的最小值。
在a[i]后面插入b[j] a[1..i-1, i] b[1..j-1, j] dp[i][j] = dp[i][j-1] + 1;
删除a[i] a[1..i-1, i] b[1..j-1, j] dp[i][j] = dp[i-1][j] + 1;
修改a[i]为b[j] a[1..i-1, i] b[1..j-1, j] dp[i][j] = dp[i-1][j-1] + 1;
