2023真题模拟0807

点我跳转👈🏻

参考答案：

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

错题：

---

第4题

知识点：链表

思路：

1:指向头节点的下一项

2:头节点指向自己

---

第10题

知识点：拓补排序的排序方法是建树和标数来得到数列。

---

第14题

知识点：排列、组合

思路：因为要选3个人，因此可以有三种不同的种类：有一/二/三个女生的，故结果为 C(1,12)*C(2,10)+C(2,12)*C(1,10)+C(3,12)=12*45+66*10+220=1420。

---

阅读程序第二题

代码：

#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;
}

这就是海伦公式。（p=a+b+c,S三角形ABC=sqrt(p(p-a)(p-b)(p-c))）

---

完善程序第一题

代码：

#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 + nums[0]) {
			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 == nums[n-1]) {
		cout << "Sequence is consecutive" << endl;
	}else{
		cout << "Missing number is " << missing_number << endl;
	}
	return 0;
}

（这里的代码已补全）

这个代码是用来找出丢失的数字的。

---

完善程序第二题

代码：

#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]==)
				dp[i][j] = ④;
			else
				dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
		}
	}
	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;
}

（这里的代码已补全）

这个代码是最长不重复子序列。

---

知识小补丁：

等差数列求和公式：（头+尾）*项数/2

等比数列求和公式：(尾(大的数)*比-头(小的数))/(比-1)

THE END