首页 > 编程学习 > C++ 2022常见知识点3

C++ 2022常见知识点3

发布时间:2022/10/1 5:16:12

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;
	}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号