C++ 2022常见知识点3
C++ 2022常见知识点3
关系型数据库中索引的优点和缺点
参考：https://blog.csdn.net/CodeBlues/article/details/120048111
索引的优点
- 创建索引可以大幅度提高系统性能，帮助用户用户提高查询速度。
- 通过索引的唯一性，可以保证数据库表中每一行数据都是唯一的。
- 可以加速表与表之间的链接。
- 降低查询中分组和排序的时间。即利用索引，就无需进行不必要的分组以及排序操作。
索引的缺点
- 索引的存储需要占用磁盘空间。
- 当数据的量非常巨大时，索引的创建和维护所耗费的时间也是相当大的。
- 当每次执行CRUD中的增删操作时，索引也需要动态维护，降低了数据的维护速度。
HTTP和HTTPS
参考链接：https://www.runoob.com/w3cnote/http-vs-https.html
HTTP（HyperText Transfer Protocol：超文本传输协议）是一种用于分布式、协作式和超媒体信息系统的应用层协议。 简单来说就是一种发布和接收 HTML 页面的方法，被用于在 Web 浏览器和网站服务器之间传递信息。
HTTP 默认工作在 TCP 协议 80 端口，用户访问网站 http:// 打头的都是标准 HTTP 服务。
HTTP 协议以明文方式发送内容，不提供任何方式的数据加密，如果攻击者截取了Web浏览器和网站服务器之间的传输报文，就可以直接读懂其中的信息，因此，HTTP协议不适合传输一些敏感信息，比如：信用卡号、密码等支付信息。
HTTPS（Hypertext Transfer Protocol Secure：超文本传输安全协议）是一种透过计算机网络进行安全通信的传输协议。HTTPS经由HTTP进行通信，但利用SSL/TLS来加密数据包。HTTPS开发的主要目的，是提供对网站服务器的身份认证，保护交互数据的隐私与完整性。
HTTPS默认工作在TCP协议443端口，它的工作流程一般如下方式：
- TCP三次同步握手
- 客户端验证服务器数字证书
- DH算法协商对称加密算法的密钥、hash算法的密钥
- SSL安全加密隧道协商完成
- 网页以加密的方式传输，用协商的对称加密算法和密钥加密，保证数据机密性；用协商的hash算法进行数据完整性保护，保证数据不被篡改
截至 2018 年 6 月，Alexa 排名前 100 万的网站中有 34.6% 使用 HTTPS 作为默认值，互联网 141387 个最受欢迎网站的 43.1% 具有安全实施的 HTTPS，以及 45% 的页面加载（透过Firefox纪录）使用HTTPS。2017 年3 月，中国注册域名总数的 0.11％使用 HTTPS。
根据 Mozilla 统计，自 2017 年 1 月以来，超过一半的网站流量被加密。
HTTP和HTTPS之间的区别
- HTTP明文传输，数据都是未加密的，安全性较差，HTTPS（SSL + HTTP）数据传输过程是加密的，安全性较好。
- 使用HTTPS协议需要到CA（Certificate Authority，数字证书认证机构）申请证书，免费证书一次性只有一年的有效期。证书颁发机构如：Symantec、Comodo、GoDaddy 和 GlobalSign 等。
- HTTP页面响应速度比HTTPS快，主要是因为HTTP使用TCP三次握手建立连接，客户端和服务器需要交换三个包，而HTTPS除了TCP的三个包，还要加上SSL握手需要的九个包，所以一共是12个包，不管是解析还是加密都需要消耗时间。
- HTTP和HTTPS使用的是完全不同的连接方式，用的端口也不一样，前者是80端口，后者是443。
- HTTPS其实就是建构在SSL/TLS之上的HTTP协议，所以HTTPS要比HTTP消耗更多的服务器资源。
HTTPS的工作原理
关于TCP的三次握手以及四次挥手可参考链接：https://blog.csdn.net/qq135595696/article/details/123978933
我们都知道HTTPS能够加密信息，以免铭感信息被第三方获取，所以很多银行网站或电子邮箱等安全级别较高的服务都会采用HTTPS协议。
-
客户端发起HTTPS请求
就是用户在浏览器（客户端）里输入一个HTTPS网址，然后连接到服务器的443端口。
-
服务端配置
采用HTTPS协议的服务器必须要有一套数字证书，可以自己制作，也可以向组织申请，区别是自己颁发的证书需要客户端验证通过，才可以继续访问，而使用受信任的公司申请的证书则不会弹出提示页面（StartSSL就是一个不错的选择，有1年的免费服务）。
-
传输证书
这个证书其实是公钥，只是包含很多信息，如证书的颁发机构，过期时间等。
-
客户端解析证书
这部分工作是客户端的TLS完成的，首先会验证公钥是否有效，比如颁发机构，过期时间等，如果发现异常，则会弹出一个警告框，提示证书存在问题。如果证书没有问题，则会生成一个随机值，然后用证书对该随机值进行加密，把随机值当作锁头锁起来，这样除非有钥匙，不然是看不到所背后的内容的。
-
传输加密信息
这部分传输的信息是用证书进行加密后的随机值，目的就是让服务端得到这个随机值，以后客户端和服务端的通信就可以通过这个随机值来进行加密解密。
-
服务端解密信息
服务端用私钥解密后，得到了客户端传过来的随机值(私钥)，然后把内容通过该值进行对称加密，所谓对称加密就是，将信息和私钥通过某种算法混合在一起，这样除非知道私钥，不然无法获取内容，而正好客户端和服务端都知道这个私钥，所以只要加密算法够彪悍，私钥够复杂，数据就够安全。
-
客户端解密信息
客户端用之前生成的私钥解密服务端传过来的信息，于是获取了解密后的内容，整个过程第三方即使监听到了数据，也束手无策。
将14拆成几个自然数的和，再求出这些数的乘积，可以求出的最大乘积是多少？
乘积最大是3*3*3*3*2=162，当分成的数尽可能接近e时，其乘积最大。
两个圆，半径分别为1cm、3cm，小圆在大圆外，绕大圆圆周滚动一周，请问小圆一共旋转了几圈？
路程上虽说小圆的周长是大圆三分之一，但是小圆绕大圆圆周滚动一周这一圈也要算进去，所以3+1=4。
一个单核多道批处理系统中仅有 P1 和 P2 两个作业， P2 比 P1 晚10ms到达，它们的计算和 I/O 操作顺序如下：
- P1 ：计算 40ms ， I/O 120ms ，计算 20ms；
- P2 ：计算 30ms ， I/O 60ms ，计算 40ms；
若不考虑调度和切换时间，则完成两个作业需要的时间最少是？
注意：这道题中，P1和P2是不能同时进行 IO 的，正确的流程为：
- P1 计算40ms；
- P1 进行 120ms IO（同时P2进行30ms计算）；
- P2进行 60ms IO（同时 P1进行20ms计算）；
- P2 进行 40ms 计算。
- 总计：40+120+60+40=260ms。
已知公式：DONALD + GERALD = ROBERT
以上共有10个字母，每一个字母都代表阿拉伯数字中 0-9 中的一个，已知D = 5，请计算出 N字母代表的数字。
- D=5，所以T=0，且个位有一个进位，所以R是奇数；
- 万位O+E的是O，考虑到进位只能是1，所以E=9；
- 十万位D+G+1=R，所以R>6，所以R=7；所以G=1；
- 再看十位L+L+1的是R,所以L=3或8；考虑到百位A+A的结果为E=9是奇数 ，所以十位有个进位，因此L=8，A=4；
- 剩下的三个数只能是N=6，B=3，O=2。
二分查找要求查找的数组必须已排序
已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项u的运算是？
TIPS：广义表除了头之外其它全为尾，只能取头（head）或除头以外的所有元素（tail）。
- 广义表L=((x,y,z),a,(u,t,w))
- 第一次tail(L)取出(a,(u,t,w))
- 第二次tail()取出((u,t,w))
- 第三次head()取出(u,t,w)
- 第四次head()取出u
给定n个权值，其对应哈夫曼树的结点总数为？
哈夫曼树没有度为1的结点，且权值所在结点都是叶子结点。二叉树中度为2的结点数比叶结点少1，即由权值总数为n，知道叶子结点数为n，又度为2的结点为n-1个，故共有n+n-1=2n-1个。
n 个顶点，m 条边的全连通图，至少去掉几条边才能构成一棵树？
n个顶点的树一定有n-1条边，所以需要发去掉m - (n - 1) = m - n + 1条边。
先序遍历序列为a,b,c,d的不同二叉树的个数为？
可参考：https://blog.csdn.net/rosefun96/article/details/96974507
卡特兰数：C(2n,n)/(n+1) = 70 / 5 = 14
给定一个m行n列的整数矩阵（如图），每行从左到右和每列从上到下都是有序的。判断一个整数k是否在矩阵中出现的最优算法，在最坏情况下的时间复杂度是？
杨氏矩阵查找算法。
bool stepWise(int mat[][N_MAX], int N, int target,
int &row, int &col)
{
if (target < mat[0][0] || target > mat[N-1][N-1])
return false;
row = 0;
col = N-1;
while (row <= N-1 && col >= 0)
{
if (mat[row][col] < target)
row++;
else if (mat[row][col] > target)
col--;
else
return true;
}
return false;
}
有一个小白程序员，写了一个只能对5个数字进行排序的函数。现在有25个不重复的数字，请问小白同学最少需要调几次该函数，才可以找出其中最大的三个数？
- 第一步：25人分为5组调用，分别排序，调用5次
- 第二步：取出5组中的最大数，排序，调用1次
- 第三步：将第二步排序中最大的三组取出，假设为A,B,C,从第二步已知A[1]>B[1]>C[1]，不需要再比较，选A[2]、A[3]、B[1]、B[2]、C[1]比较。不需要比较B[3]是因为A[1]已经最大了，若剩下两个数在B中，A[1]占一个，只剩两个位置，C[1]同理。调用1次
- 总计7次。
直线上的点
参考链接：https://blog.csdn.net/sinat_38972110/article/details/82221517
题目一：给定N个二维坐标点(包含整形x,y)，找到位于同一条直线上点的最大个数。
int Gcd(int a, int b)
{
if (0 == b)
{
return a;
}
else
{
return Gcd(b, a % b);
}
}
int max(int a, int b) { return a > b ? a : b; }
int maxPoints(vector<Point>& points)
{
int ans = 0;
int cnt = 0;
int overLap = 0;
int dx = 0;
int dy = 0;
int g = 0;
for (int i = 0; i < points.size(); i++)
{
cnt = 0;
overLap = 0;
map<pair<int, int>, int> line;
for (int j = i + 1; j < points.size(); j++)
{
dx = points[i].x - points[j].x;
dy = points[i].y - points[j].y;
if (0 == dy && 0 == dx)
{
overLap++;
continue;
}
g = Gcd(dx, dy);
dx /= g;
dy /= g;
cnt = max(cnt, ++line[make_pair(dx, dy)]);
}
ans = max(ans, cnt + overLap + 1);
}
return ans;
}
题目二：给定N个三维坐标点(包含整形x,y,z)，找到位于同一条直线上点的最大个数
3D的情况是类似的，唯一不同是多个维度，所以斜率(准确得说是方向向量)用(dx,dy,dz)表示。
struct Point
{
int x;
int y;
int z;
Point() : x(0), y(0), z(0) {}
Point(int a, int b, int c) : x(a), y(b), z(c) {}
};
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
int max(int a, int b) { return a > b ? a : b; }
int maxPoints(vector<Point>& points)
{
int ans = 0;
for (int i = 0; i < points.size(); i++)
{
int cnt = 0, overLap = 0;
map<pair<pair<int, int>, int>, int> line;
for (int j = i + 1; j < points.size(); j++)
{
int dx = points[i].x - points[j].x;
int dy = points[i].y - points[j].y;
int dz = points[i].z - points[j].z;
//判断两点是否重合
if (dx == 0 && dy == 0 && dz == 0)
{
++overLap;
continue;
}
//计算最简方向向量并存入map容器中,同时更新cnt
int g = gcd(dx, dy, dz);
dx /= g;
dy /= g;
dz /= g;
cnt = max(cnt, ++line[pair<pair<int, int>, int>(pair<int, int>(dx, dy), dz)]);
}
//统计该基准点下的最大共线点数量
//cnt+重合点+基准点自身
ans = max(ans, cnt + overLap + 1);
}
return ans;
}