C++笔试总结

今天药忘吃喽~ 2022-09-25 05:11 293阅读 0赞

有多套完整python，人工智能，机器学习，马哥最新Linux运维，老男孩Linux运维，老男孩python全栈，老男孩python14期，传智播客C++，传智播客java教程，黑马安卓视频教程，得到音频所有专栏打包出售，有需要的加微信Wonder–G联系。（Wonder–G中的–是两个减号）

### 1.计算机操作系统 ###

#### 1.1shell执行机制 ####

shell内置命令exec有两个主要目的:(1)使用它可以不用创建新进程来执行一个命令，这样执行的速度非常的快。(2)使用它可以重定向来自shell脚本内部的文件描述符。 要注意的是exec命令不会返回控制状态的，所以通常他把安排在最后一行执行。

#### 1.2缺页中断 ####

缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。  
例题：在虚拟存储系统中，若进程在内存中占三块(开始时为空，采用先进先出页面淘汰算法，当执行访问页号序列为1、2、3、4、1、2、5、1、2、3、4、5、6时，将产生（ ）次缺页中断。  
答案10次，解析如下：![这里写图片描述][20160815104806287]

#### 1.3I/O控制方式 ####

循环测试 I/O方式（轮询方式）:  
利用I/O测试指令测试设备的闲忙。若设备不忙，则执行输入或输出指令；若设备忙，则I/O测试指令不断对该设备进行测试，直到设备空闲为止。这种方式使CPU花费很多时间在I/O是否完成的循环测试中，造成极大的浪费！\[1\]

中断处理方式:  
引入中断之后，每当设备完成I/O操作，便以中断请求方式通知CPU，然后进行相应处理。但由于CPU直接控制输入输出操作，每传达一个单位信息，都要发生一次中断，因而仍然消耗大量CPU时间。

直接内存存取（DMA）方式:  
DMA（Direct Memory Access，直接内存存取）方式用于高速外部设备与内存之间批量数据的传输。它使用专门的DMA控制器，采用窃取总线程控制权的方法，由DMA控制器送出内存地址和发出内存读、设备写或者设备读、内存写的控制信号完成内存与设备之间的直接数据传送，而不用CPU干预。当本次DMA传送的数据全部完成时才产生中断，请求CPU进行结束处理。

笔试题：采用DMA方式传送数据时，每传送一个数据要占用*\_*的时间。  
A.一个指令周期 B.一个机器周期 C.一个时钟周期 D.一个存储周期  
答案：D 一个存储周期。DMA获得内存总线的控制权，单纯的是为了做内存访问，所以仅需要一个存取周期，这事和时钟周期没关系。

通道方式:  
通道是一个用来控制外部设备工作的硬件机制，相当于一个功能简单的处理机。通道是独立于CPU的、专门负责数据的输入输出传输工作的处理器，它对外部设备实统一管理，代替CPU对I/O操作进行控制，从而使I/O操作可以与CPU并行工作。通道是实现计算机和传输并行的基础，以提高整个系统的效率。

#### 1.4静态库与动态库 ####

1.静态链接库的优点  
(1)代码装载速度快，执行速度略比动态链接库快；  
(2)只需保证在开发者的计算机中有正确的.LIB文件，在以二进制形式发布程序时不需考虑在用户的计算机上.LIB文件是否存在及版本问题，可避免DLL地狱等问题。  
2.动态链接库的优点  
(1)更加节省内存并减少页面交换；  
(2)DLL文件与EXE文件独立，只要输出接口不变（即名称、参数、返回值类型和调用约定不变），更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性；  
(3)不同编程语言编写的程序只要按照函数调用约定就可以调用同一个DLL函数；  
(4)适用于大规模的软件开发，使开发过程独立、耦合度小，便于不同开发者和开发组织之间进行开发和测试。  
3.不足之处  
(1)使用静态链接生成的可执行文件体积较大，包含相同的公共代码，造成浪费

#### 1.5计算机引入缓存的原因 ####

引入缓冲的主要原因包括：缓和CPU与I/O设备间速度不匹配的矛盾；减少对CPU的中断频率，放宽对中断响应时间的限制；提高CPU和I/O设备之间的并行性。所以采用缓冲技术，可减少对CPU的中断次数，从而提高系统效率。

#### 1.6多道程序 ####

多道程序设计是指在主存中同时存放多道用户作业，使它们都处于执行的开始点和开始点之间，这些程序共享计算机系统资源。  
多道程序设计的主要优点有：  
(1)提高CPU的利用率。在多道程序环境下，多个程序共享计算机资源当某个程序等待I/O操作时，CPU可以执行其他程序，大大提高CPU的利用率。  
(2)提高设备的利用率。在多道程序环境下，多个程序共享系统的设备，大大提高系统设备的利用率。  
(3)提高系统的吞吐量。在多道程序环境下，减少了程序的等待时间，提高了系统的吞吐量。

#### 1.7时间片轮询调度算法 ####

时间片轮询调度中有趣的一点是如何确定时间片的长度。从一个进程切换到另一个进程是需要一定时间的，因为要保存和装入寄存器值及内存映像等保护现场的工作，更新各种表格和队列等。假如进程切换，有时称为上下文切换，需要的时间为 5 毫秒，再假设时间片长度设定为 20 毫秒，则在做完 20 毫秒有用的工作之后， CPU 将花费 5 毫秒来进行进程切换。 CPU 时间的 20% 被浪费在了管理开销上。进程切换时间一定的情 况下，如果时间片长度设定的越小时，这种浪费更明显。所以，时间片长度与 CPU 利用率是一对不可调和的矛盾，必须处理好它们之间的关系。  
为了提高 CPU 效率，我们可以将时间片长度设得大一些，这时浪费的时间只有就会相对减小。但在一个分时系统中，各个任务对时间片长度的要求是不一致的。例如在一个系统中，可能要求每秒钟更新一下显示内容，每几十毫秒要扫描一下按键，每几毫秒要检测一下串口缓冲区等……可见，各个任务对时间的依赖程度是不一样的。如果时间片设得太长，某些对实时性要求高的任务可能得不到执行，使得系统的实时性变差。  
总之，时间片的设定应满足对实时性要求最高的那个任务，这样才能确保每个任务都可以及时得到执行而不被错过。

#### 1.8线程和进程的区别与联系 ####

1、进程：子进程是父进程的复制品。子进程获得父进程数据空间、堆和栈的复制品。  
2、线程：相对与进程而言，线程是一个更加接近与执行体的概念，它可以与同进程的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。  
两者都可以提高程序的并发度，提高程序运行效率和响应时间。  
线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源管理和保护；而进程正相反。同时，线程适合于在SMP机器上运行，而进程则可以跨机器迁移。  
根本区别就一点：用多进程每个进程有自己的地址空间(address space)，线程则共享地址空间。所有其它区别都是由此而来的：  
（1）速度：线程产生的速度快，线程间的通讯快、切换快等，因为他们在同一个地址空间内。  
（2）资源利用率：线程的资源利用率比较好也是因为他们在同一个地址空间内。  
（3）同步问题：线程使用公共变量/内存时需要使用同步机制还是因为他们在同一个地址空间内

#### 1.9进程死锁 ####

某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台，当N的取值不超过（）时系统不会发生死锁。  
答案：5个，设有m个资源，n个进程，每个进程要调用k个资源，一次只能调用一个，则：m>n(k-1) 对应找满足条件的值即可。  
或者可以用哲学家就餐问题的思想解决此类问题，每个进程要求3台，所以先给每个进程2台，再如果多出一台，分给某一个进程，等这个进程执行完了，释放自己的资源给其他进程用，这样就不会发生死锁。即2N+1=11，得N=5。

#### 1.10操作系统临界区 ####

每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源），每次只准许一个进程进入临界区，进入后不允许其他进程进入。

进程进入临界区的调度原则是：  
①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。  
②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。  
③进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。④如果进程不能进入自己的临界区，则应让出CPU，  
避免进程出现“忙等”现象。

#### 1.11虚拟内存 ####

虚拟内存也称虚拟存储器（Virtual Memory）。电脑中所运行的程序均需经由内存执行，若执行的程序占用内存很大或很多，则会导致内存消耗殆尽。为解决该问题，Windows中运用了虚拟内存技术，即匀出一部分硬盘空间来充当内存使用。当内存耗尽时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。若计算机运行程序或操作所需的随机存储器(RAM)不足时，则 Windows 会用虚拟存储器进行补偿。它将计算机的RAM和硬盘上的临时空间组合。当RAM运行速率缓慢时，它便将数据从RAM移动到称为“分页文件”的空间中。将数据移入分页文件可释放RAM，以便完成工作。

#### 1.12LRU算法 ####

LRU（least recently used）最近最少使用:  
假设 序列为 4 3 4 2 3 1 4 2  
物理块有3个 则  
首轮 4调入内存 4  
次轮 3调入内存 3 4  
之后 4调入内存 4 3  
之后 2调入内存 2 4 3  
之后 3调入内存 3 2 4  
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）  
之后 4调入内存 4 1 3（原理同上）  
最后 2调入内存 2 4 1

#### 1.3Linux挂载与卸载 ####

将光盘/dev/hdc卸载的命令是?  
A、umount /mnt/cdrom /dev/hdc  
B、unmount /dev/hdc  
C、umount /dev/hdc  
D、unmount /mnt/cdrom /dev/hdc  
答案：AC  
解释：挂载设备使用mount，卸载设备使用umount，有三种方式，通过设备名，挂载点或者设备名和挂载点  
如题目所示：  
umount /dev/hdc  
umount /mnt/cdrom  
umount /mnt/cdrom /dev/hdc

### 2.Cplusplus ###

#### 2.1内联函数 ####

C++有三种方式实现内联函数：  
（1）将函数的定义写在类定义的内部；定义在类声明之中的成员函数将自动地成为内联函数。  
（2） 在类定义内部的函数声明上用inline显式指定；  
（3）在类定义体外部的函数实现上用inline显式指定；

内联函数可能在程序中定义不止一次，只要内联函数的定义在某个源文件中只出现一次，而且在所有的源文件中，其定义必须是相同的。如果inline函数的定义和声明是分开的，而在另外一个文件中需要调用这些inline函数得时候，内联是无法在这些调用函数内展开的。这样内联函数在全局范围内就失去了作用。解决的办法就是把内联函数得定义放在头文件中，当其它文件要调用这些内联函数的时候，只要包含这个头文件就可以了。把内联函数的定义放在头文件中，可以确保在调用函数时所使用的定义是相同的，并保证在调用点该函数的定义对调用点可见。

内联函数(inline function与一般的函数不同，不是在调用时发生控制转移，而是在编译阶段将函数体嵌入到每一个调用语句中。

林锐还建议，只在定义前加上inline，而不是在声明和定义前都加，因为这能体现高质量C++/C 程序设计风格的一个基本原则：声明与定义不可混为一谈。

内联函数(inline function)与编译器的工作息息相关。编译器会将程序中出现内联函数的调用表达式用内联函数的函数体来替换。

调用函数要比使用等价的表达式要慢很多。在大多数机器上，调用函数都要做很多事情：调用前要先保存寄存器，并在返回是回复；复制实参；程序还必须转到一个新的位置。省去了参数压栈，生成汇编的call调用，返回参数等操作。

内联函数的缺点：  
如果调用内联函数的地方过多，也可能造成代码膨胀。毕竟，编译器会把内联函数的函数体嵌入到每一个调用了它的地方，重复地嵌入。

#### 2.2设计模式 ####

简单工厂模式：增加新的功能时，需要修改工厂类。  
工厂方法模式：工厂A生产A零件，工厂B生产B零件，每增加一种产品， 就需要增加一个对象的工厂。  
抽象工厂模式：工厂A，专门用来生产A型号的处理器（包括单核和多核），工厂B，专门用来生产B型号的处理器 （包括单核和多核）。  
![抽象工厂的UML类图][UML]  
单例模式：  
![单例模式UML图][UML 1]  
构造函数是private的，不能通过构造函数创建对象，只能调用类的静态函数，但是静态函数中有if(singleton == NULL)\{\}来判断是不是第一次执行，所以单例模式只能实例化一次。  
桥接模式：将抽象部分与它的实现部分分离，使它们都可以独立地变化。如何运用桥接模式呢？可以将操作系统和计算机分别抽象出来，让它们各自发展，减少它们的耦合度。![这里写图片描述][0_13128077403rl3.gif]  
策略模式：定义一系列的算法，把它们一个个封装起来，传递不同参数可以实现不同功能。

//抽象接口 
    class ReplaceAlgorithm  
    {  
    public:  
        virtual void Replace() = 0;  
    };  
    //三种具体的替换算法 
    class LRU_ReplaceAlgorithm : public ReplaceAlgorithm  
    {  
    public:  
        void Replace() { cout<<"Least Recently Used replace algorithm"<<endl; }  
    };  
    
    class FIFO_ReplaceAlgorithm : public ReplaceAlgorithm  
    {  
    public:  
        void Replace() { cout<<"First in First out replace algorithm"<<endl; }  
    };  
    class Random_ReplaceAlgorithm: public ReplaceAlgorithm  
    {  
    public:  
        void Replace() { cout<<"Random replace algorithm"<<endl; }  
    };  
    
    //Cache需要用到替换算法 
    class Cache
    {
    private:
        ReplaceAlgorithm *m_ra;
    public:
        Cache(ReplaceAlgorithm *ra) { m_ra = ra; }
        ~Cache() { delete m_ra; }
        void Replace() { m_ra->Replace(); }
    };

原型模式： 原型模式实现的关键就是实现Clone函数，对于C++来说，其实就是拷贝构造函数，需实现深拷贝。  
![0_13127061145Pzq.gif][]  
模板方法模式：以public non-virtual成员函数调用低访问性的（private或protected）的virtual函数。  
观察者模式：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。

//可以看到博客类中有一个观察者链表（即订阅者），当博客的状态发生变化时，通过Notify成员函数通知所有的观察者，告诉他们博客的状态更新了。而观察者通过Update成员函数获取博客的状态信息。代码实现不难，下面给出C++的一种实现。
    
    //观察者
    class Observer  
    {
    public:
        Observer() {}
        virtual ~Observer() {}
        virtual void Update() {} 
    };
    //博客
    class Blog  
    {
    public:
        Blog() {}
        virtual ~Blog() {}
        void Attach(Observer *observer) { m_observers.push_back(observer); }     //添加观察者
        void Remove(Observer *observer) { m_observers.remove(observer); }        //移除观察者
        void Notify() //通知观察者
        {
            list<Observer*>::iterator iter = m_observers.begin();
            for(; iter != m_observers.end(); iter++)
                (*iter)->Update();
        }
        virtual void SetStatus(string s) { m_status = s; } //设置状态
        virtual string GetStatus() { return m_status; }    //获得状态
    private:
        list<Observer* > m_observers; //观察者链表
    protected:
        string m_status; //状态
    };
    //以上是观察者和博客的基类，定义了通用接口。博客类主要完成观察者的添加、移除、通知操作，设置和获得状态仅仅是一个默认实现。下面给出它们相应的子类实现。 
    
    //具体博客类
    class BlogCSDN : public Blog
    {
    private:
        string m_name; //博主名称
    public:
        BlogCSDN(string name): m_name(name) {}
        ~BlogCSDN() {}
        void SetStatus(string s) { m_status = "CSDN通知 : " + m_name + s; } //具体设置状态信息
        string GetStatus() { return m_status; }
    };
    //具体观察者
    class ObserverBlog : public Observer   
    {
    private:
        string m_name;  //观察者名称
        Blog *m_blog;   //观察的博客，当然以链表形式更好，就可以观察多个博客
    public: 
        ObserverBlog(string name,Blog *blog): m_name(name), m_blog(blog) {}
        ~ObserverBlog() {}
        void Update()  //获得更新状态
        { 
            string status = m_blog->GetStatus();
            cout<<m_name<<"-------"<<status<<endl;
        }
    };
    //客户的使用方式：
    
    //测试案例
    int main()
    {
        Blog *blog = new BlogCSDN("wuzhekai1985");
        Observer *observer1 = new ObserverBlog("tutupig", blog);
        blog->Attach(observer1);
        blog->SetStatus("发表设计模式C++实现（15）——观察者模式");
        blog->Notify();
        delete blog; delete observer1;
        return 0;
    }

原型模式：举个现实中的例子来介绍原型模式。找工作的时候，我们需要准备简历。假设没有打印设备，因此需手写简历，这些简历的内容都是一样的。这样有个缺陷，如果要修改简历中的某项，那么所有已写好的简历都要修改，工作量很大。随着科技的进步，出现了打印设备。我们只需手写一份，然后利用打印设备复印多份即可。如果要修改简历中的某项，那么修改原始的版本就可以了，然后再复印。原始的那份手写稿相当于是一个原型，有了它，就可以通过复印（拷贝）创造出更多的新简历。这就是原型模式的基本思想。下面是原型模式的UML图：  
![这里写图片描述][0_13127061145Pzq.gif]  
在ResumeA和中ResumeB中实现Clone()深拷贝函数。

#### 2.3 cin的返回值 ####

int N = 0, M = 0;
    while (cin >> N >> M)
        cout << "hello" << endl;

以上代码，当输入的N或者M不合法的时候会退出，或者输入Ctrl+z的时候退出。

#### 2.4继承与组合的区别和应用场景 ####

继承（is-a）提高了代码的复用性。组合（has-a）显然不具备这种特性。

当前对象与组合的对象是一个低耦合关系，如果修改包含对象的类中代码不需要修改当前对象类的代码。  
如果对父类的方法做了修改的话（比如增加了一个参数），则子类的方法必须做出相应的修改。所以说子类与父类是一种高耦合，违背了面向对象思想。设计模式中认为这是一种破坏了父类的封装性的表现。

继承是在编译时刻静态定义的，即是静态复用，在编译后子类和父类的关系就已经确定了。而组合这是运用于复杂的设计，它们之间的关系是在运行时候才确定的，即在对对象没有创建运行前，整体类是不会知道自己将持有特定接口下的那个实现类。在扩展方面组合比集成更具有广泛性。

组合比继承更具灵活性和稳定性，所以在设计的时候优先使用组合。

<table> 
 <thead> 
  <tr> 
   <th>组 合 关 系</th> 
   <th>继 承 关 系</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>优点：不破坏封装，整体类与局部类之间松耦合，彼此相对独立</td> 
   <td>缺点：破坏封装，子类与父类之间紧密耦合，子类依赖于父类的实现，子类缺乏独立性</td> 
  </tr> 
  <tr> 
   <td>优点：具有较好的可扩展性</td> 
   <td>缺点：支持扩展，但是往往以增加系统结构的复杂度为代价</td> 
  </tr> 
  <tr> 
   <td>优点：支持动态组合。在运行时，整体对象可以选择不同类型的局部对象</td> 
   <td>缺点：不支持动态继承。在运行时，子类无法选择不同的父类</td> 
  </tr> 
  <tr> 
   <td>优点：整体类可以对局部类进行包装，封装局部类的接口，提供新的接口</td> 
   <td>缺点：子类不能改变父类的接口</td> 
  </tr> 
  <tr> 
   <td>缺点：整体类不能自动获得和局部类同样的接口</td> 
   <td>优点：子类能自动继承父类的接口</td> 
  </tr> 
  <tr> 
   <td>缺点：创建整体类的对象时，需要创建所有局部类的对象</td> 
   <td>优点：创建子类的对象时，无须创建父类的对象</td> 
  </tr> 
 </tbody> 
</table>

#### 2.5面向对象和面向过程的区别 ####

面向对象的三大基本特征：封装、继承、多态。  
面向过程：  
优点：性能比面向对象高，因为类调用时需要实例化，开销比较大，比较消耗资源;比如单片机、嵌入式开发、Linux/Unix等一般采用面向过程开发，性能是最重要的因素。  
缺点：没有面向对象易维护、易复用、易扩展。  
面向对象：  
优点：易维护、易复用、易扩展，由于面向对象有封装、继承、多态性的特性，可以设计出低耦合的系统，使系统更加灵活、更加易于维护。  
缺点：性能比面向过程低

#### 2.7封装 ####

把数据和函数包装在一个单独的单元（称为类）的行为称为封装。数据封装是类的最典型特点。数据不能被外界访问，只能被封装在同一个类中的函数访问。这些函数提供了对象数据和程序之间的接口。避免数据被程序直接访问的概念被称为”数据隐藏”。

封装机制将数据和代码捆绑到一起，避免了外界的干扰和不确定性。它同样允许创建对象。简单的说，一个对象就是一个封装了数据和操作这些数据的代码的逻辑实体。

在一个对象内部，某些代码和（或）某些数据可以是私有的，不能被外界访问。通过这种方式，对象对内部数据提供了不同级别的保护，以防止程序中无关的部分意外的改变或错误的使用了对象的私有部分。

#### 2.8知识点总结 ####

模板的调用，会根据调用的参数，生成模板对应的实际调用的函数体，如果调用的参数不同，会生成不同的代码，所以会导致代码膨胀。

#### 2.9C++中指针和引用有什么区别？ ####

1、引用访问一个变量是直接访问，而指针是间接访问。  
2、引用是一个变量的别名，本身不单独分配自己的内存空间，而指针有自己的内存空间。  
3、引用在开始的时候就绑定到了一个内存空间(开始必须赋初值),所以他只能是这个内存空间的名字,而不能改成其他的,当然可以改变这个内存空间的值.

#### 2.10STL ####

(1)unordered\_map hash\_map map  
运行效率方面：unordered\_map最高，hash\_map其次，而map效率最低单提供了有序的序列。  
占用内存方面：hash\_map内存占用最低，unordered\_map其次(数量少时优于hash\_map），而map占用最高。  
需要无序容器时候用unordered\_map，有序容器时候用map。

性能比较：  
若考虑有序，查询速度稳定，容器元素量少于1000,非频繁查询那么考虑使用map。  
若非常高频查询(100个元素以上，unordered\_map都会比map快)，内部元素可非有序，数据大超过1k甚至几十万上百万时候就要考虑使用unordered\_map(元素上千万上亿时4GB的内存就要担心内存不足了,需要数据库存储过程挪动到磁盘中)。  
hash\_map相比unordered\_map就是千万级别以上内存占用少15MB,上亿时候内存占用少300MB，百万以下都是unordered\_map占用内存少，  
且unordered\_map插入删除相比hash\_map都快一倍，查找效率相比hash\_map差不多，或者只快了一点约1/50到1/100。  
综合非有序或者要求稳定用map，都应该使用unordered\_map,set类型也是类似的。  
unordered\_map 查找效率快五倍，插入更快，节省一定内存。如果没有必要排序的话，尽量使用 hash\_map(unordered\_map 就是 boost 里面的 hash\_map 实现)。

### 3.逻辑题 ###

#### 3.1水桶问题 ####

![这里写图片描述][20160813134456094]  
遇到这种题要在纸上明确罗列出几种情况，要不然算完一会儿就忘了。计算能否获得8L时，这样计算：8=7+1，8=6+2，8=5+3, 8=4+4，然后再看能否获得7,1,6,2,5,3,4等。

### 4.数据结构与算法 ###

#### 4.1排序算法 ####

桶排序：要对大小为\[1..1000\]范围内的n个整数A\[1..n\]排序，可以把桶设为大小为10的范围，具体而言，设集合B\[1\]存储\[1..10\]的整数，集合B\[2\]存储(10..20\]的整数，……集合B\[i\]存储((i-1)\*10, i\*10\]的整数，i = 1,2,..100。总共有100个桶。然后对A\[1..n\]从头到尾扫描一遍，把每个A\[i\]放入对应的桶B\[j\]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。

其中最好、最坏、平均三项复杂度全是一样的就是与初始排序无关的排序方法。

直接插入：当序列已经有序的情况下，使用直接插入排序的时间复杂度为O(n)

#### 4.2字符串算法 ####

n是主串长度，m是字串长度  
朴素模式匹配算法时间复杂度是O((n-m+1)\*m)，KMP算法的时间复杂度是O(n+m)

#### 4.3关联数组 ####

关联数组是一种具有特殊索引方式的数组。不仅可以通过整数来索引它，还可以使用字符串或者其他类型的值（除了NULL）来索引它。  
关联数组的元素没有特定的顺序，你可以把它们想象为一组卡片。每张卡片上半部分是索引而下半部分是数值。

#### 4.4哈夫曼树 ####

带权路径最小的二叉树叫做哈夫曼树。

#### 4.5循环队列 ####

头指针F总是指向队头元素的前一位置.尾指针R总是指向队尾元素的当前位置.则该循环队列中的元素个数为（R-F+M)%M

#### 4.6图的邻接表 ####

![这里写图片描述][20160818002623835]  
注意，图的邻接表中结点是有顺序的，3在左，2在中，1在右。

#### 4.7二分法查找 ####

22 34 55 77 89 93 99 102 120 140  
假设低下标用low表示，高下标用high表示。  
查找77：  
开始low = 0, high = 9  
第一次查找，找到中心的下标为(0+9)/2 = 4，即89，由于89大于77，所以，调整low = 0，high = 3（注意：由于知道下标为4的元素比77大，所以不会让high等于4）  
第二次查找，找到中心的下标为(0+3)/2 = 1，即34，由于34小于77，所以，调整low = 2，high = 3  
第三次查找，找到中心的下标为(2+3)/2 = 2，即55，由于55小于77，所以，调整low = 3，high = 3  
第四次查找，找到中心的下标为(3+3)/2 = 3，即77，找到所要找的元素

#### 4.8格雷码生成法 ####

假设原始的值从0开始，格雷码产生的规律是：第一步，改变最右边的位元值；第二步，改变右起第一个为1的位元的左边位元；第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) - 1 步）。  
用一个例子来说明：  
假设产生3位元的格雷码，原始值位 000  
第一步：改变最右边的位元值： 001  
第二步：改变右起第一个为1的位元的左边位元： 011  
第三步：改变最右边的位元值： 010  
第四步：改变右起第一个为1的位元的左边位元： 110  
第五步：改变最右边的位元值： 111  
第六步：改变右起第一个为1的位元的左边位元： 101  
第七步：改变最右边的位元值： 100

自然二进制码转换成二进制格雷码，其法则是保留自然二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法相类似。

二进制格雷码转换成自然二进制码,其法则是保留格雷码的最高位作为自然二进制码的最高位，而次高位自然二进制码为高位自然二进制码与次高位格雷码相异或，而自然二进制码的其余各位与次高位自然二进制码的求法相类似。

#### 4.9 B-B+B\*树 ####

B-树（B树）：多路搜索树（M阶），每个结点存储M/2-1（向上取整）到M-1个关键字，每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；所有关键字在整颗树中出现，且只出现一次，可以在非叶子结点中查找到目标数据。

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引，B+树总是到叶子结点才能查找到目标数据。

B\*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。

#### 4.10最小公倍数和最大公约数 ####

最小公倍数的公式是 a\*b/m，m为最大公约数。  
因为a=m\*i; b=m\*j; 最小公倍数为 m\*i\*j  
最大公约数的计算方法：  
a ÷ b，令r为所得余数（0≤r＜b）  
若 r = 0，演算法结束；b 即为答案。  
互换：置 a←b，b←r，并返回第一步。  
代码如下：

int gcd(int a, int b)
    {
        int r = a%b;
    
        if (r == 0)
            return b;
        else
            return gcd(b, r);
    }

#### 4.11AVL树和红黑树 ####

AVL树：平衡二叉树，是一种二叉排序树，没有一个结点的左子树和右子树的高度差大于1。左子树深度减去右子树的深度称为平衡因子，平衡因子只可能是-1、0、1.  
红黑树：是一种自平衡二叉查找树，其操作时间复杂度最糟糕是O(log2(n+1))  
红黑树并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以 O(log2 n)（2是下标） 的时间复杂度进行搜索、插入、删除操作。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。红黑树典型的用途是实现关联数组.

符合以下几条规则：  
1.每个结点要么是红的要么是黑的。  
2.根结点是黑的。  
3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。  
4.如果一个结点是红的，那么它的两个儿子都是黑的。  
5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。  
一棵n个内结点的红黑树的高度至多为2lg(n+1)，最少为 O(log(n))

性质:  
1>一棵n个结点的AVL树的平均搜索长度保持在O(log2(n)).  
2>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为O(log2(n)).

#### 4.12二叉树 ####

某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是高度等于其结点数。

#### 4.13动态规划 ####

那么遇到问题如何用动态规划去解决呢？按照下面的步骤去考虑：  
1、构造问题所对应的过程。  
2、思考过程的最后一个步骤，看看有哪些选择情况。  
3、找到最后一步的子问题，确保符合“子问题重叠”，把子问题中不相同的地方设置为参数。  
4、使得子问题符合“最优子结构”。  
5、找到边界，考虑边界的各种处理方式。  
6、确保满足“子问题独立”，一般而言，如果我们是在多个子问题中选择一个作为实施方案，而不会同时实施多个方案，那么子问题就是独立的。  
7、考虑如何做备忘录。  
8、分析所需时间是否满足要求。  
9、写出转移方程式。  
举例：01背包问题  
这题非常有名，只要是计算机专业的应该都有听说过。有N件物品和一个容量为V的背包。第i件物品的体积是c\[i\]，价值是v\[i\]。求解将哪些物品装入背包可使价值总和最大。

我们把题目具体下， 有5个商品，背包的体积为10，他们的体积为 c\[5\] = \{3,5,2,7,4\}; 价值为 v\[5\] = \{2,4,1,6,5\};

问题分析：  
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。可以将背包问题的求解看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些不放入背包。

如果一个问题的最优解包含了物品n，即Xn = 1（把第n个放入），那么其余X1, X2, …..,Xn-1 一定构成子问题1,2,…..,n-1在容量C - cn时的最优解。如果这个最优解不包含物品n,即Xn = 0;那么其余 X1, X2…..Xn-1一定构成了子问题 1,2,….n-1在容量C时的最优解。

假设有N件物品和一个容量为V的背包。第i件物品的体积是v\[i\]，价值是c\[i\]，将哪些物品装入背包可使价值总和最大？  
每一种物品都有两种可能即放入背包或者不放入背包。可以用dp\[i\]\[j\]表示第i件物品放入容量为j的背包所得的最大价值，则状态转移方程可以推出如下：  
dp\[i\]\[j\]=max\{dp\[i-1\]\[j-v\[i\]\]+c\[i\],dp\[i-1\]\[j\]\};  
代码如下：

for (int i = 1;i <= N;i++) //枚举物品 
    {  
        for (int j = 0;j <= V;j++) //枚举背包容量 
        {  
            f[i][j] = f[i - 1][j];  
            if (j >= v[i])  
            {  
                f[i][j] = Max(f[i - 1][j],f[i - 1][j - v[i]] + c[i]);  
            }  
        }  
    }

#### 4.14算法时间复杂度 ####

算法时间复杂度取决于：待处理数据的状态和问题的规模。

#### 4.15mt19937 HAKMEM169 popcnt ####

mt19937是一种随机数生成算法，HAKMEM169可用于计算二进制数中1的个数。  
popcnt是“population count”的缩写，该操作一般翻译为“位1计数”，即统计有多少个“为1的位”。

### 5.计算机网络 ###

#### 5.1TCP协议 ####

服务器在收到syn包时将加入半连接队列，服务器接受到客户端的ack包后将从半连接队列删除。

TCP链接中主动断开链接netstat观察可能出现的状态流转是：  
ESTABLISHED->FIN\_WAIT\_1->FIN\_WAIT\_2->TIME\_WAIT->CLOSED或者  
ESTABLISHED->FIN\_WAIT\_1->TIME\_WAIT->CLOSED

#### 5.2IP地址 ####

网络地址为172.16.0.0，采用子网掩码255.255.224.0，广播地址：最后13位的主机号全为1。共划分了8个子网。

#### 5.3IP地址汇总的计算方法 ####

（1）确定需要汇总的网段的子网地址。  
（2）将各网段的子网地址以二进制写出。  
（3）比较各网段二进制表示的网络地址，从第1位比特开始进行比较记录连续的相同的比特，从不相同的比特位到地32个比特为填充0。由此得到的地址为汇总后的网段的网络地址，其网络位为连续的相同的比特的位数。

#### 5.4交换机 ####

交换机为独占带宽，例如有某一速率为100M的交换机，有20个接口，那么它的每一个接口的速率为100M，注意这里的100M是100Mb/s

#### 5.5拥塞控制 ####

慢开始算法：慢慢改变拥塞窗口的大小，每经过一个传输轮次，拥塞窗口cwnd就加倍。  
拥塞避免算法：每经过一个传输轮次，拥塞窗口cwnd就加1。  
先执行慢开始算法，当cwnd等于ssthresh时（阻塞拥塞窗口的一半），开始执行拥塞避免算法。如果下次再出现拥塞，ssthresh再次变为cwnd的一半，重复上述过程。

#### 5.6TCP和UDP协议的区别 ####

1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接。  
2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付。  
3、TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的。  
UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）  
4、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信。  
5、TCP首部开销20字节;UDP的首部开销小，只有8个字节。  
6、TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道。

#### 5.7RTT ####

RTT(Round-Trip Time): 往返时延。在计算机网络中它是一个重要的性能指标，表示从发送端发送数据开始，到发送端收到来自接收端的确认（接收端收到数据后便立即发送确认），总共经历的时延。

#### 5.8URL ####

url的格式：<scheme>://user:password@host:<port>/<path>;<param>?query

### 6.Linux编程 ###

#### 6.1socket编程 ####

select 和 epoll效率差异的原因：select采用轮询方式处理连接，epoll是触发式处理连接。  
select:  
1.Socket数量限制：该限制可操作的Socket数由FD\_SETSIZE决定，内核默认32\*32=1024.  
2.操作限制：通过遍历FD\_SETSIZE(1024)个Socket来完成调度，不管哪个Socket是活跃的，都遍历一遍。  
epoll：  
1.Socket数量无限制：该模式下的Socket对应的fd列表由一个数组来保存，大小不限制（默认4k）。  
2.操作无限制：基于内核提供的反射模式，有活跃Socket时，内核访问该Socket的callback，不需要遍历轮询。  
但当所有的Socket都活跃的时候，所有的callback都被唤醒，会导致资源的竞争。既然都是要处理所有的Socket，那么遍历是最简单最有效的实现方式。

#### 6.2线程互斥与同步 ####

线程同步是指线程之间所具有的一种制约关系，一个线程的执行依赖另一个线程的消息，当它没有得到另一个线程的消息时应等待，直到消息到达时才被唤醒。经典的例子如生产者消费者模型。

线程互斥是指对于共享的进程系统资源，在各单个线程访问时的排它性。当有若干个线程都要使用某一共享资源时，任何时刻最多只允许一个线程去使用，其它要使用该资源的线程必须等待，直到占用资源者释放该资源。线程互斥可以看成是一种特殊的线程同步。

### 7.数据库 ###

#### 7.1MySQL日志 ####

慢查询日志：是用来记录执行时间超过指定时间的查询语句。通过慢查询日志，可以查找出哪些查询语句的执行效率很低，以便进行优化。一般建议开启，它对服务器性能的影响微乎其微，但是可以记录mysql服务器上执行了很长时间的查询语句。可以帮助我们定位性能问题的。

redo log： 如果在dirty page还未刷入磁盘时，server非正常关闭，这些修改操作将会丢失，如果写入操作正在进行，甚至会由于损坏数据文件导致数据库不可用。为了避免上述问题的发生，Innodb将所有对页面的修改操作写入一个专门的文件，并在数据库启动时从此文件进行恢复操作，这个文件就是redo log file。

中继日志： MySQL在从节点上使用了一组编了号的文件，这组文件被称为中继日志。当SQL线程把那些数据复制发生的变更应用到从节点时，中继日志将会负责保存这些变更。中继日志文件是按照编码顺序排列的，从000001开始，包含所有当前可用的中继文件的名称。中继日志的格式和MySQL二进制日志的格式一样，从而更容易被mysqlbinlog客户端实用程序读取。

二进制日志记录的是主库的修改行为，而中继日志记录的是接收自主库的二进制日志。

#### 7.2 数据库事务正确执行的四个基本要素 ####

ACID，指数据库事务正确执行的四个基本要素的缩写。包含：原子性(Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。

#### 7.3数据库范式 ####

设计关系数据库时，遵从不同的规范要求，设计出合理的关系型数据库，这些不同的规范要求被称为不同的范式，各种范式呈递次规范，越高的范式数据库冗余越小。  
第一范式：数据库表的每一列都是不可分割的原子数据项。  
第二范式：第二范式就是在第一范式的基础上属性完全依赖于主键。  
第三范式：满足第三范式（3NF）必须满足第二范式（2NF）。第三范式要求一个关系中不包含已在其它关系已包含的非主关键字信息（只能包含主键）。第三范式就是属性不依赖于其它非主属性

第一范式： 对于表中的每一行，必须且仅仅有唯一的行值.在一行中的每一列仅有唯一的值并且具有原子性.  
第二范式： 要求非主键列是主键的子集，非主键列活动必须完全依赖整个主键。主键必须有唯一性的元素,一个主键可以由一个或更多的组成唯一值的列组成。一旦创建，主键无法改变，外键关联一个表的主键。主外键关联意味着一对多的关系.  
第三范式： 前提必须遵循2NF，要求非主键列互不依赖，消除传递依赖。  
BCNF范式： 前提必须遵循3NF，要求主键列互不依赖。  
第四范式： 禁止多值依赖。  
第五范式： 第五范式将表分割成尽可能小的块，为了排除在表中所有的冗余.  
第一范式用来消除某个表列存储多个值的冗余现象。  
第二范式用来处理冗余数据的删除问题。  
第三范式用来消除没有直接依赖于第一范式和第二范式形成的非主键列。  
BCNF范式用来消除没有直接依赖于第一范式和第二范式形成的主键列。  
第四范式用来消除多值依赖。  
第五范式用来处理消除所有的业务冗余，以独立的表来表达每一个业务需求。

#### 7.4 Oracle表空间 ####

由于区间（Extent）是Oracle创建对象时的最小分配单元，所以表空间的管理实际上就是针对于区间的管理。

字典管理表空间：面临的一个严重问题是空间碎片。 在字典管理表空间中，我们经常会遇到这样的悖论，一个表空间中的自由空间（可以通过dba\_free\_space视图来计算）还有几百MB，但是一个请求几百KB空间的表可能都已经无法扩展。这是因为表空间中的自由空间并不连续，每块自由空间都很小，已经不能满足一个表的扩展需要。EXTENT\_MANAGEMENT显示为DICTIONARY的就是字典管理表空间。

本地化管理表空间（Local Management Tablespace，简称LMT）。所谓本地化管理，就是指Oracle不再利用数据字典表来记录Oracle表空间里面的区间的使用状况，而是在每个表空间的数据文件的头部加入了一个位图区域，在其中记录每个Extent的使用状况。每当一个Extent被使用，或者被释放以供重新使用时，Oracle都会更新数据文件头部的这个记录，反映这个变化。其中关键字EXTENT MANAGEMENT LOCAL指定这是一个本地化管理的表空间。

#### 7.5索引 ####

1、复合索引：索引可以包含一个、两个或更多个列。两个或更多个列上的索引被称作复合索引。  
利用索引中的附加列，您可以缩小搜索的范围，但使用一个具有两列的索引不同于使用两个单独的索引。复合索引的结构与电话簿类似，人名由姓和名构成，电话簿首先按姓氏对进行排序，然后按名字对有相同姓氏的人进行排序。如果您知道姓，电话簿将非常有用；如果您知道姓和名，电话簿则更为有用，但如果您只知道名不姓，电话簿将没有用处。  
所以说创建复合索引时，应该仔细考虑列的顺序。对索引中的所有列执行搜索或仅对前几列执行搜索时，复合索引非常有用；仅对后面的任意列执行搜索时，复合索引则没有用处。  
2、普通索引  
普通索引（由关键字KEY或INDEX定义的索引）的唯一任务是加快对数据的访问速度。因此，应该只为那些最经常出现在查询条件（WHEREcolumn=）或排序条件（ORDERBYcolumn）中的数据列创建索引。只要有可能，就应该选择一个数据最整齐、最紧凑的数据列（如一个整数类型的数据列）来创建索引。  
3、唯一索引  
普通索引允许被索引的数据列包含重复的值。比如说，因为人有可能同名，所以同一个姓名在同一个“员工个人资料”数据表里可能出现两次或更多次。  
如果能确定某个数据列将只包含彼此各不相同的值，在为这个数据列创建索引的时候就应该用关键字UNIQUE把它定义为一个唯一索引。这么做的好处：一是简化了MySQL对这个索引的管理工作，这个索引也因此而变得更有效率；二是MySQL会在有新记录插入数据表时，自动检查新记录的这个字段的值是否已经在某个记录的这个字段里出现过了；如果是，MySQL将拒绝插入那条新记录。也就是说，唯一索引可以保证数据记录的唯一性。事实上，在许多场合，人们创建唯一索引的目的往往不是为了提高访问速度，而只是为了避免数据出现重复。  
4、主索引  
在前面已经反复多次强调过：必须为主键字段创建一个索引，这个索引就是所谓的”主索引”。主索引与唯一索引的唯一区别是：前者在定义时使用的关键字是PRIMARY而不是UNIQUE。  
5、外键索引  
如果为某个外键字段定义了一个外键约束条件，MySQL就会定义一个内部索引来帮助自己以最有效率的方式去管理和使用外键约束条件。  
6、全文索引  
　　文本字段上的普通索引只能加快对出现在字段内容最前面的字符串(也就是字段内容开头的字符)进行检索操作。如果字段里存放的是由几个、甚至是多个单词构成的较大段文字，普通索引就没什么作用了。这种检索往往以LIKE %word%的形式出现，这对MySQL来说很复杂，如果需要处理的数据量很大，响应时间就会很长。  
　　这类场合正是全文索引(full-text index)可以大显身手的地方。在生成这种类型的索引时，MySQL将把在文本中出现的所有单词创建为一份清单，查询操作将根据这份清单去检索有关的数据记录。全文索引即可以随数据表一同创建，也可以等日后有必要时再使用下面这条命令添加：  
ALTER TABLE tablename ADD FULLTEXT(column1, column2)  
有了全文索引，就可以用SELECT查询命令去检索那些包含着一个或多个给定单词的数据记录了。下面是这类查询命令的基本语法：  
SELECT \* FROM tablename  
WHERE MATCH(column1, column2) AGAINST(‘word1’, ‘word2’, ‘word3’)  
上面这条命令将把column1和column2字段里有word1、word2和word3的数据记录全部查询出来。  
注解：InnoDB数据表不支持全文索引。

#### 7.6超码候选码 ####

如果一个超关键字去掉其中任何一个字段后不再能唯一地确定记录，则称它为“候选关键字”（Candidate Key）。候选关键字既能唯一地确定记录，它包含的字段又是最精炼的。也就是说候选关键字是最简单的超关键字。

若一个关系有多个候选码，选择其中一个作为主码。  
外码可以取空值。

#### 7.7事务的四大特性 ####

事务应该具有4个属性：原子性、一致性、隔离性、持续性。这四个属性通常称为ACID特性。  
　　原子性（atomicity）。一个事务是一个不可分割的工作单位，事务中包括的诸操作要么都做，要么都不做。  
　　一致性（consistency）。事务必须是使数据库从一个一致性状态变到另一个一致性状态。一致性与原子性是密切相关的。  
　　隔离性（isolation）。一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对并发的其他事务是隔离的，并发执行的各个事务之间不能互相干扰。  
　　持久性（durability）。持续性也称永久性（permanence），指一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其有任何影响。

#### 7.8SQL语句优化 ####

如果要优化SQL语句，就先where过滤，再分组。  
多表查询优于子查询。  
在oracle 中delete操作快，在mysql中truncate快.  
使用索引。

### 8.其他知识点 ###

#### MVC: ####

mvc框架是指的是模型(model)-视图(view)-控制器(controller)  
视图是用户看到并与之交互的界面。  
模型表示企业数据和业务规则。  
控制器接受用户的输入并调用模型和视图去完成用户的需求。

#### XML: ####

XML可扩展标记语言，它被设计用来传输和存储数据，其焦点是数据的内容。它的设计宗旨是传输数据，而不是显示数据。它不是超文本标记语言的替代，它是对超文本标记语言的补充，它和超文本标记语言为不同的目的而设计。超文本标记语言被设计用来显示数据，其焦点是数据的外观。  
对它最好的描述是：它是独立于软件和硬件的信息传输工具。XML是各种应用程序之间进行数据传输的最常用的工具。

#### 随机访问： ####

随机访问是说你可以随意访问该数据结构中的任意一个节点.

计算机使用总线结构的好处是实现积木化。

[20160815104806287]: /images/20220718/9e86a10a264847ba97f08bb5ac1d1ef0.png
[UML]: https://img-my.csdn.net/uploads/201108/6/0_1312616458PVae.gif
[UML 1]: /images/20220718/271406b922f746d196fe011ec4d5f786.png
[0_13128077403rl3.gif]: /images/20220718/bce6931bb59f4b76afebcfbc963bcb34.png
[0_13127061145Pzq.gif]: /images/20220718/90db55ee80a64fbaa760278d8a76ffd7.png
[20160813134456094]: /images/20220718/9e0bda23bf4e4111aefde2302cca3523.png
[20160818002623835]: /images/20220718/0d0d7fdd1b4d46e0b5a5dacc09659ef9.png