写在前面：
1：本文所有内容均为只作为参考，当年考题不可能重复近三年考过的内容。实验部分完整更新（因为可以自己带电脑且开卷考试），理论部分只更新记忆中的大题。
2：本人真的是一个算法菜鸡，但是个人认为这门课听了也对算法没什么提升，自学占大头。（希望真的能够2024年之前学会算法和数据结构，以及24年dp杯能榜上有名吧...）
3：后续可能会更新一个期末复习整理的大纲，由于csdn改版之后图片复制老是加载不了，所以如果要发出来的话挺耗时间的，之后没发就当我没说过这个事情（嗯）。
实验：
1：
【问题描述】给定一个按值有序（升序）的N元整数数组A，采用折半查找法查找关键值k的位置，并给出查找的过程
【输入形式】
第一行：N
第二行：A[0], A[1], ... , A[N-1]
第三行：k
【输出形式】
第一行：k的位置（索引），若不存在则输出‘no’
第二行：查找的过程，每一次折半的中间（mid）位置的值，以逗号分隔。例如，1 2 3 4 5的中间位置为3，1 2 3 4的中间位置为2。
【样例输入】
样例1
11
2,5,8,11,15,16,22,24,27,35,50
22
样例2
11
2,5,8,11,15,16,22,24,27,35,50
10
【样例输出】
样例1
6
16,27,22
样例2
no
16,8,11
【样例说明】
【评分标准】必须使用折半法，其他方法不能得分。
#include <stdio.h>
#include <stdlib.h>int main(){//input int N;scanf("%d",&N);int *A=(int*)malloc(sizeof(int)*N);int i=0;for(i=0;i<N;i++){//cin>>A[i];scanf("%d",&A[i]);}int k;//cin>>k;scanf("%d",&k);//half searchint left=0,right=N-1,mid;int cnt=0;int flag=0;while(left<=right){mid=(left+right)/2;if(k<A[mid]){right=mid;}else if(k>A[mid]){left=1+mid;}else{//k==midflag=1;break;//found}if(cnt==0) //cout<<A[mid];{printf("%d",A[mid]);}else{printf(",%d",A[mid]);}//else cout<<","<<A[mid];cnt++;}if(flag=1){//cout<<mid;//output the numberprintf("%d",mid);}else{printf("no");}return 0;
}
//2 5 8 11 15 16 22 24 27 35 502：
【问题描述】一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少种跳法，并分析算法的时间复杂度，例如
n 为1 时只有一种跳法
n 为2 时只有两种跳法
【输入形式】输入一个整数n
【输出形式】n级的跳法数，整数m
【样例输入】
6
【样例输出】
13
【样例说明】
输入与输出均为整数
【答题要求】
要求在注释中首先解释求解思路，如果有递推关系，必须说明为什么是这样的关系，递推计算是通过什么道理建立起来的，否则不得分。
需要指出使用了所学过的什么方法，并明确写出算法的时间复杂度。仅使用蛮力法的求解将严重失分。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAX 10000000/*用front、mid、rear存放暂态
类似用三个变量实现dp，使用过程中不断变表 参考斐波那契数
跳上n阶梯子需要前面梯子做基础
若差一阶和f(n-1)相同
若差两阶f(n-2)相同时间复杂度为O（N）
*/
int fun(int n){if(n<2){return 1;}int front=1,mid=1,rear=1;for(int i=2;i<=n;i++){front=mid;mid=rear;rear=(front+mid)%MAX;//max为取余，防止数字过大 }return rear;
}int main(){//input int n;cin>>n;cout<<fun(n);return 0;
}3：
【问题描述】
输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
【输入形式】
一个升序排序的数组以空格隔开，以及一个目标数字，换行输入
【输出形式】
如果存在数组中两个数字和为目标数字，则输出数字对；
如果存在多个满足条件的数字对，输出一对即可；
不存在则不输出；
【样例输入】
1 2 4 7 11 15
15
【样例输出】
4 11
【样例说明】
4+11=15
【评分标准】
时间复杂度必须为 O(n)，否则酌情给分。
注释中要首先说明求解思路。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;int main(){//输入 int n;//元素个数cin>>n;int *a=(int*)malloc(sizeof(int)*n);for(int i=0;i<n;i++){cin>>a[i];} int target;cin>>target;//查找对应的元素 ，cnt可以用于估算时间复杂度 int flag=0,front=0,rear=n-1,cnt=0;//双指针，front指向从头开始的元素，rear指向从尾开始的元素while(front<rear){//序列非负的情况下，如果target始终大于起始值，则两数一定在前面 //但是好像没说非负/* if(a[rear]>target){rear--;cnt++;continue;}*///找到两数 if(a[front]+a[rear]==target){flag=1;cnt++;break;}//如果和偏大，则说明rear取大了 else if(a[front]+a[rear]>target){rear--;cnt++;}//如果和偏小，则说明front取小了 else{front++;cnt++;}}if(flag==1){cout<<a[front]<<" "<<a[rear];}//cout<<cnt;return 0;
}
/*
6
1 2 4 7 11 15
154：
【问题描述】在数组中，数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如
在数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11，是16减去5的结果。
【输入形式】整数数组，空格隔开
【输出形式】数对之差的最大值，一个数字
【样例输入】
2 5 8 19 3 6
【样例输出】
16
【样例说明】题目要求输出数对之差的最大值，即数字减去右边数字的值，不一定为数组中最大值和最小值的差。
【评分标准】要求设计时间和空间复杂度最低、代码最简洁的方法。性能越好得分越高。
如使用蛮力法求解得分最低。注释中要明确解释求解思路与所采用的方法。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;int main(){//input int n;cin>>n;int *a=(int*)malloc(sizeof(int)*n);for(int i=0;i<n;i++){cin>>a[i];}//特殊情况讨论 if(n==0){return 0;}if(n==2){cout<<a[1]-a[0];return 0;}//动态规划，maxD记录差值最大值，max记录从右侧开始的最大值 int maxD=0,max=a[n-1];for(int i=n-2;i>=0;i--){//前面一个数大于当前max if(a[i]>max){max=a[i];//更新max }//当前值小于max，判断差值大小 else{//如果max减去当前值比maxD大 if(max-a[i]>maxD){maxD=max-a[i];//更新maxD }}}//时间复杂度为O（n），空间复杂度O（1） cout<<maxD<<endl;return 0;
}理论：
小题部分（填空+选择）：
1：tsp的英文全称。
2：课件上出现过的概率算法的名字。
3：根据T（n-1）计算大O。
4：回溯法的TSP问题的解空间树采用了什么树。
5：L型骨牌的数目计算公式。
6：给出概率pi和时间ti，分析算法的时间复杂度。
7：大O、大Ω、大Θ哪个给出了上界。
【三】
3.1：给了一堆f（n）和g（n），包括绝对值、log对数、取整等，反正挺复杂的...，求阶相关的大O、大Ω、大Θ，并给出其中对应符号最大和最小的函数。
3.2：KMP的主要思想。
3.3：汉诺塔的伪代码。
3.4：根据问题规模和算法时间T（n），求解计算机在速度性能上翻倍之后且算法不变的情况下，能解决的问题规模为多少？
【四】
4.1：根据T（n-1）计算大Θ。
4.2：快排的伪代码，分析时间复杂度。
4.3：用贪心法算开车加油的最少次数（有n个加油站，初始的时候没油，给出了各加油站距离起始点的位置，油箱容量为m），给出具体的贪心策略，并分析时间复杂度。
