C++ 2022常见知识点3

C++ 2022常见知识点3

关系型数据库中索引的优点和缺点

参考：https://blog.csdn.net/CodeBlues/article/details/120048111

索引的优点

1. 创建索引可以大幅度提高系统性能，帮助用户用户提高查询速度。
2. 通过索引的唯一性，可以保证数据库表中每一行数据都是唯一的。
3. 可以加速表与表之间的链接。
4. 降低查询中分组和排序的时间。即利用索引，就无需进行不必要的分组以及排序操作。

索引的缺点

1. 索引的存储需要占用磁盘空间。
2. 当数据的量非常巨大时，索引的创建和维护所耗费的时间也是相当大的。
3. 当每次执行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端口，它的工作流程一般如下方式：

1. TCP三次同步握手
2. 客户端验证服务器数字证书
3. DH算法协商对称加密算法的密钥、hash算法的密钥
4. SSL安全加密隧道协商完成
5. 网页以加密的方式传输，用协商的对称加密算法和密钥加密，保证数据机密性；用协商的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协议。

1. 客户端发起HTTPS请求

   就是用户在浏览器（客户端）里输入一个HTTPS网址，然后连接到服务器的443端口。

2. 服务端配置

   采用HTTPS协议的服务器必须要有一套数字证书，可以自己制作，也可以向组织申请，区别是自己颁发的证书需要客户端验证通过，才可以继续访问，而使用受信任的公司申请的证书则不会弹出提示页面（StartSSL就是一个不错的选择，有1年的免费服务）。

3. 传输证书

   这个证书其实是公钥，只是包含很多信息，如证书的颁发机构，过期时间等。

4. 客户端解析证书

   这部分工作是客户端的TLS完成的，首先会验证公钥是否有效，比如颁发机构，过期时间等，如果发现异常，则会弹出一个警告框，提示证书存在问题。如果证书没有问题，则会生成一个随机值，然后用证书对该随机值进行加密，把随机值当作锁头锁起来，这样除非有钥匙，不然是看不到所背后的内容的。

5. 传输加密信息

   这部分传输的信息是用证书进行加密后的随机值，目的就是让服务端得到这个随机值，以后客户端和服务端的通信就可以通过这个随机值来进行加密解密。

6. 服务端解密信息

   服务端用私钥解密后，得到了客户端传过来的随机值(私钥)，然后把内容通过该值进行对称加密，所谓对称加密就是，将信息和私钥通过某种算法混合在一起，这样除非知道私钥，不然无法获取内容，而正好客户端和服务端都知道这个私钥，所以只要加密算法够彪悍，私钥够复杂，数据就够安全。

7. 客户端解密信息

   客户端用之前生成的私钥解密服务端传过来的信息，于是获取了解密后的内容，整个过程第三方即使监听到了数据，也束手无策。

将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 的，正确的流程为：

1. P1 计算40ms；
2. P1 进行 120ms IO（同时P2进行30ms计算）；
3. P2进行 60ms IO（同时 P1进行20ms计算）；
4. P2 进行 40ms 计算。
5. 总计：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;
	}