牛客网基础知识强化巩固-周结03

数组强化训练篇

2022-11-21 打卡

知识点总结

1. 什么是渐进时间复杂度
   1. 渐进时间复杂度是指n趋于无穷时的复杂度。
   2. 向有序表中任意一个位置插入元素，插入位置之后的元素依次挪动一个位置，假设元素插入的位置坐标为k，则时间复杂度为O(k)，渐进时间复杂度为O(n)
2. 线性表
   1. 二维数组是每个元素都为线性表的线性表 .
   2. 线性表的顺序存储结构中逻辑顺序与物理顺序总是一致的，但链式存储结构却不是。链式存储的物理顺序地址可以连续也可以不连续
   3. 链式和顺序存储结构没有优劣之分，只是看在什么情况下适合哪种存储结构。对于经常插入或删除的适合选择链式存储，经常查找的适合顺序存储。
3. 矩阵和数组的关系
   1. 数组是一种顺序存储的结构，矩阵是一种逻辑结构，可以使用数组，也可以使用链表。
4. 线性表的长度和存储大小
   1. 线性表长度的定义是它所包含的元素的个数。
   2. 元素的类型决定了元素所占用存储空间的大小，但元素的个数不等价于元素的类型。

2022-11-22 打卡

知识点总结

1. 数组
   1. 二维以上的数组其实是一种特殊的广义表
   2. 数组一旦建立，结构的元素个数和元素间的物理存储关系就不再变化

Java语言强化训练篇

2022-11-21 打卡

知识点总结

1. java容器
   1. Serializable, Cloneable , Iterable , Collection , List , RandomAccess List接口是有序的，通常允许重复；
   2. ArrayList是实现List 接口的大小可变数组（底层为数组）；
   3. Map的特性是Key键唯一；
   4. 查看手册： Note that this implementation is not synchronized. ArrayList的实现是不是线程同步的。
   5. ArrayList的实现是线程非同步的
   6. HashTable Vector的实现是线程同步的
   7. HashMap ArrayList的实现是线程非同步的
   8. 线程同步指的是多个线程同时操作某个对象或者方法或者一段代码块时，必须排队进行操作。保障了共享变量在多个线程之间的同步性。
   9. 线程非同步就是多个线程可以同时操作，是线程不安全的，而ArrayList的实现是线程不安全的，在对ArrayList的对象进行多线程的增删查时，可能会报错。

2022-11-23 打卡

知识点总结

1. java中的字符串

   1. 三者执行速度：StringBuilder > StringBuffer > String ；

   2. StringBuffer是一个线程安全的可修改的字符序列。

   3. StringBuilder是线程不安全的可修改的字符序列。

   4. String的值是不可变的，所以是线程安全的哦。

   5. 用String操作字符串时，实际上是在不断地创建新对象，而原来的对象会作为垃圾被回收；

2022-11-24 打卡

知识点总结

1. Java内存结构包含以下部分：

   1、栈区：由编译器自动分配释放，具体方法执行结束后，系统自动释放JVM内存资源。

   其作用有保存局部变量的值，包括：1.用来保存基本数据类型的值；2.保存类的实例，即堆区对象的引用。也可以用来保存加载方法时的帧。

   2、堆区：一般由程序员分配释放，JVM不定时查看这个对象，如果没有引用指向这个对象就回收。

   其作用为用来存放动态产生的数据，包括new出来的实例，字符数组等。

   同一个类的对象拥有各自的成员变量，存储在各自的堆中，但是他们共享该类的方法。

   3、数据区：用来存放static定义的静态成员。

   4、常量池：JVM为每个已加载的类型维护一个常量池，常量池就是这个类型用到的常量的一个有序集合。包括直接常量(基本类型，String)和对其他类型、方法、字段的符号引用。池中的数据和数组一样通过索引访问。由于常量池包含了一个类型所有的对其他类型、方法、字段的符号引用，所以常量池在Java的动态链接中起了核心作用。常量池存在于堆中。

2. java字符串类型

   1. 

   2. String是一个对象，基本数据类型在java 中只有八种。这八种基本数据类型是基本的值类型，除此以外都是引用类型。

3. String类与StringBuffer类

   1. String的值是不可变的，这就导致每次对String的操作都会生成新的String对象，不仅效率低下，而且浪费大量优先的内存空间；

   2. StringBuffer是可变类，和线程安全的字符串操作类，任何对它指向的字符串的操作都不会产生新的对象。每个StringBuffer对象都有一定的缓冲区容量，当字符串大小没有超过容量时，不会分配新的容量，当字符串大小超过容量时，会自动增加容量。

   3. StringBuilder相比StringBuffer效率更高，但多线程不安全；

      在单线程中字符串的频繁拼接使用StringBuilder效率更高，对于多线程使用StringBuffer则更安全；

   4. 字符串简单操作时没必要使用上述两者，还是用String类型提高速度；

字符串强化训练

2022-11-23 打卡

知识点总结

1. 类型安全不是一种类型，是有关类型操作一种规范。
   如：不让不同类型的数据相互转换
   int Num =3;
   string Str=“3”;
   Num =Str; //错
   Num=int.Parse(Str);//对
2. 类型安全要求可以相互转换的不同类型数据在转换时 显式转换

2022-11-24 打卡

知识点总结

1. 字符串格式化输出

   1. %s：打印字符串时使用的转换说明。
   2. %后加（数字）修饰符：表示打印的最小字段宽度，如%6s。
   3. %后加（.数字）修饰符：对%s转换来说，表示待打印字符的最大数量，如%.3s。
   4. %后加（-）修饰符：表示待打印项左对齐，即从字段的左侧开始打印该项，如%-6s。

   综上，使用%-6.3s转换说明，可成功打印出一个字段宽度为6的左对齐字符串中的前3个字符。

2. 字符串字串计算公式

   1. 字串： n（n+1）/2 + 1
   2. 非空子串：n（n+1）/2
   3. 非空真子串：n（n+1）/2 - 1

链表强化训练

2022-11-25 打卡

知识点总结

1. 什么是存储密度

   1. 存储密度=单链表数据项所占空间/结点所占空间；

   2. 结点所占空间＝数据项所占空间＋存放后继结点地址的链域；

      所以，单链表的存储密度小于1。

2. 什么是广义表？

   1. 广义表，又称列表，也是一种线性存储结构。
   2. 通常，广义表中存储的单个元素称为 “原子”，而存储的广义表称为 “子表”。
   3. 以下是广义表存储数据的一些常用形式：
      • A = ()：A 表示一个广义表，只不过表是空的。
      • B = (e)：广义表 B 中只有一个原子 e。
      • C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
      • D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
      • E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。
   4. 广义表的表头和表尾
      1. 当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。
      2. 强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

   例如在广义表中 LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。

   再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用 {} 表示。

3. 校验结点是否闭合，如必须有与之对应的符号，最适合用什么数据结构来存储？

   1. 栈是解决封闭对应问题的有效方法。
   2. 比如在解析XML中，遇到一个标签（左标签）就入栈，遇到其子标签的左标签（如）同样入栈。遇到右标签(如或)就校验栈顶标签是否与该右标签对应，能对应就出栈，不能对应则说明标签不对称，是无效的XML文件

2022-11-26 打卡

知识点总结

1. 循环链表

   1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（）存储方式最节省运算时间。
   2. 仅有尾指针的单循环链表在最后一个元素之后插入一个元素的复杂度为O(1)、删除第一个元素只需要将尾结点指向下个结点的下个结点即可
   3. 单循环链表的主要优点是：从表中任一结点出发都能扫描到整个链表

2. 设数据结构 B=(D, R) ，其中

   D={ a, b, c, d, e, f }

   R={ (a, b ） , (b, c ） , (c, d ） , (d, e), (e, f), (f, a） }

   该数据结构为（ 非线性结构）。

   1. 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D ；二是 D 上的关系，它反映了 D 中各数据元素之间的前后件关系，通常记为 R 。即一个数据结构可以表示成 B= （ D,R ）。其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系，一般用二元组来表示。
   2. 假设 a 与 b 是 D 中的两个数据，则二元组（ a,b ）表示 a 是 b 的前件， b 是 a 的后件。 如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。 本题数据结构中没有根结点，因此它是非线性结构。

2022-11-27 打卡

知识点总结

1. 注意存储和存取的区别。

   1. 线性表一般有两种存储形式，一种是基于顺序表的存储，一种是基于链表的存储。
   2. 采用顺序表存储，则必须占用一片连续的内存空间，逻辑上相邻的元素，物理存储位置上也相邻。
   3. 采用链表存储，则逻辑上相邻的两个元素，物理位置上不一定相邻。

   采用顺序表的存储，便于随机的存取，但是插入和删除比较耗时。采用链式存储，便于插入和删除，无法随机的存取。

2. 单向链表

   1. 单链表的每个节点都具有唯一的前驱节点和唯一的后继节点，所以当两个单链表存在相交的节点时，这两个链表则同时拥有这个节点，以及这个节点的所有后继节点，当这个公共节点是尾节点时，他们则只含有公共一个节点-------尾节点。
   2. 快慢指针是判断单链表是否有环的一种方法：两个指针，每次移动的步长为2叫做快指针，每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发，当快指针率先到达NULL的时候，则说明此单链表中不存在环，当快指针追上慢指针的时候，说明此单链表中存在环。
   3. 有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点。
   4. 两个单向链表之间相交可以存在环。

sql 语言强化训练

2022-11-21 打卡

知识点总结

1. 关系数据库管理系统的3种基本关系运算

   1. 选择运算

      从关系中找出满足给定条件的那些元组称为选择。其中的条件是以逻辑表达式给出的，值为真的元组将被选取。这种运算是从水平方向抽取元组。　在FOXPRO中的短语FOR和WHILE均相当于选择运算。

      如：LIST　FOR　出版单位=‘高等教育出版社’　AND　单价<=20

   2. 投影运算

      从关系模式中挑选若干属性组成新的关系称为投影。这是从列的角度进行的运算，相当于对关系进行垂直分解。在FOXPRO中短语FIELDS相当于投影运算。

      如：　LIST　FIELDS　单位，姓名

   3. 连接运算

      连接运算是从两个关系的笛卡尔积中选择属性间满足一定条件的元组。

2. 数据库关键字

   1. 候选键(Candidate Key)：一个或者多个属性的集合，可以唯一确定实体的一个实例；
   2. 主键(Primary Key):从候选键中，选中用来作为唯一标识的属性或者属性组被称为主键；
   3. 可选键(Alternative Key):候选键中没有选中的其他键，称为可选键；
   4. 而表的外键是另一表的主键, 外键可以有重复的, 可以是空值。

2022-11-22 打卡

知识点总结

1. MYSQL正则查询

   1. MySQL 中使用REGEXP或NOT REGEXP 运算符(或 RLIKE 和 NOT RLIKE) 来操作正则表达式。

   2. 选项	说明	例子	匹配值示例
      ^	匹配文本的开始字符	‘^b’ 匹配以字母 b 开头 的字符串	book、big、banana、 bike
      [^]	匹配不在括号中的任何字符	'[^abc]’ 匹配任何不包 含 a、b 或 c 的字符串	desk、fox、f8ke

   3. SELECT * FROM Person Address REGEXP '^[^CO]';

      表示筛查出所有匹配[^CO]的项，而[^CO]表示匹配任何不包含C、O的字符串

2. 数据库的封锁机制

   1. 数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时就会产生同时读取和／或修改同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。所以数据库管理系统必须提供并发控制机制。最常用的技术是封锁技术。

3. 数据库视图

   1. 视图（View）是从一个或多个表（或视图）导出的表。视图与表（有时为与视图区别，也称表为基本表——Base Table）不同，视图是一个虚表，即视图所对应的数据不进行实际存储。数据库中只存储视图的定义，在对视图的数据进行操作时，系统根据视图的定义去操作与视图相关联的基本表。

4. 以A、B表为例，主外键为id。简述INNER JOIN、LEFT JOIN和RIGHT JOIN的区别。

   1. A INNER JOIN B：返回A和B中符合on条件式的记录
   2. A LEFT JOIN B: 返回A中的所有记录和B中符合on条件式的记录
   3. A RIGHT JOIN B：返回B中的所有记录和A中符合on条件式的记录

5. 数据库系统的特点

   1. 数据结构化
   2. 数据的共享性高，冗余度低，易扩充
   3. 数据独立性高
   4. 数据由DBMS统一管理和控制
      1. DBMS必须提供以下几方面的数据控制功能：
      2. 数据的安全性保护（security）
      3. 数据的完整性检查（integrity）
      4. 数据库的并发访问控制（concurrency）
      5. 数据库的故障恢复（recovery）

计算机网络强化训练

2022-11-21 打卡

知识点总结

1. 统一资源定位符和统一资源标识符

   1. URI（identifier） 统一资源标识符
   2. URL （locator） 统一资源定位符

2. TCP、UDP、SPX(序列分组交换协议(Sequenced Packet Exchange)，是Novell早期传输层协议。)

   1. 传输层协议的代表包括：TCP、UDP、SPX等。
   2. 传输层是两台计算机经过网络进行数据通信时,第一个端到端的层次，具有缓冲作用。
   3. 当网络层服务质量不能满足要求时，它将服务加以提高，以满足高层的要求；
   4. 当网络层服务质量较好时，它只用很少的工作。传输层还可进行复用，即在一个网络连接上创建多个逻辑连接。

3. 如果进行路由汇聚，能覆盖这几条路由的地址是？答：10.1.192.0/21

   1. 10.1.193.0的二进制：00001010.00000001.11000 001.00000000

      10.1.194.0的二进制：00001010.00000001.11000 010.00000000

      10.1.196.0的二进制：00001010.00000001.11000 100.00000000

      10.1.198.0的二进制：00001010.00000001.11000 110.00000000

      子网掩码为：11111111.11111111.11111 000.00000000 （十进制为255.255.248.0）即可覆盖。

      子网掩码是用来划分主机号和网络号，上面的二进制中只有001， 010， 100， 110这三位以后不同。

      取前面21位相同为网络号，后面11位为主机号。

      故为： 00001010.00000001.11000 000.00000000 (10.1.192.0)

      子网掩码为 11111111.11111111.11111 000.00000000 (255.255.248.0, 缩写为21)

4. 双绞线的连接方式：

   1. 直通线用于连接不同类设备：电脑—交换机, 交换机----路由器
   2. 交叉线用于连接相同类设备：电脑----电脑 , 交换机----交换机
   3. 反转线用于电脑直接连接路由器：电脑----路由器

2022-11-22 打卡

知识点总结

1. PPP协议（点对点协议）
   1. 信息字段的长度是可变的，不超过1500字节，它包含着要传送的数据。
   2. PPP帧的首部和尾部分别为四个字段和两个字段 ；首部：标志字段F、地址字段A、控制字段C、协议字段 尾部：帧校验序列 FCS、标志字段 F；
   3. 首部中的地址字段A规定为0xFF(即11111111)。
      首部中的控制字段C规定为0x03(即00000011)。
      首部中的2字节的协议字段：
      (1)当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。
      (2)当协议字段为0xC021时，PPP帧的信息字段就是PPP链路控制协议LCP的数据。
      (3)当协议字段为0x8021时，PPP帧的信息字段就是网络层的控制数据。