盛算信息-面试经历-笔试部分-完整题目（一）

浅浅的花香味﹌ 2024-02-20 09:39 48阅读 0赞

## 盛算信息-面试经历-完整题目-C++岗 ##

首先是笔试题目，笔试时间一个小时，后面会更新面试部分题目讲解。  
面试题讲解链接：[面试题讲解][Link 1]

## 题目如下 ##

解释c++中static,const的含义与作用。

### static与const的含义和作用 ###

#### **C++中static**:首先他的作用是定义静态变量 ####

1.  在函数内部声明的静态变量具有静态存储持续时间，他们在程序执行期间保持存在，而不是在每次函数调用时创建和销毁，静态变量在函数调用之间保持其值不变，可以用于函数调用之间的共享数据。比如下面这个例子

void foo() {
        
        static int count = 0;
        count++;
        cout << "Count: " << count << endl;
    }
    
    int main() {
        
        foo(); // 输出 Count: 1
        foo(); // 输出 Count: 2
        foo(); // 输出 Count: 3
        return 0;
    }

1.  静态函数：在类中声明的静态函数属于类本身，而不是类的实例，静态函数可以直接通过类名调用，无需创建类的实例，静态函数可以直接通过类名调用，无需创建类的实例。静态函数只能访问静态成员变量和其他静态函数，不能访问静态成员变量和非静态函数，比如下面这个例子。

class MathUtils {
        
    public:
        static int add(int a, int b) {
        
            return a + b;
        }
    };
    
    int main() {
        
        int result = MathUtils::add(5, 3);  // 可以直接通过类名调用
        cout << "Result: " << result << endl; // 输出 Result: 8
        return 0;
    }

1.  静态成员变量：在类中声明静态成员变量属于类本身，而不是类的实例，静态成员变量只有一份拷贝，而不是所有类的实例共享，静态成员可以通过类或实例名访问，比如下面例子。

class MyClass {
        
    public:
        static int count;
    };
    
    int MyClass::count = 0;
    
    int main() {
        
        MyClass obj1;
        MyClass obj2;
        
        obj1.count = 5;
        cout << "obj1.count: " << obj1.count << endl; // 输出 obj1.count: 5
        cout << "obj2.count: " << obj2.count << endl; // 输出 obj2.count: 5
        
        obj2.count = 10;
        cout << "obj1.count: " << obj1.count << endl; // 输出 obj1.count: 10
        cout << "obj2.count: " << obj2.count << endl; // 输出 obj2.count: 10
        
        return 0;
    }

1.  静态类：C++没有直接的关键字来定义静态类，但可以通过将所有成员声明为静态来实现静态类的效果。静态类不能实例化，只能通过类名访问静态成员。

class MathUtils {
        
    public:
        static int add(int a, int b) {
        
            return a + b;
        }
        
        static int multiply(int a, int b) {
        
            return a * b;
        }
    };
    
    int main() {
        
        int result1 = MathUtils::add(5, 3);
        cout << "Result1: " << result1 << endl; // 输出 Result1: 8
        
        int result2 = MathUtils::multiply(5, 3);
        cout << "Result2: " << result2 << endl; // 输出 Result2: 15
        
        return 0;
    }

#### 个人拓展Java中static的作用 ####

在Java中，`static`关键字用于声明静态成员，它可以应用于变量、方法和代码块。

1.  静态变量：使用`static`关键字修饰的变量是静态变量，也称为类变量。静态变量在类加载时被初始化，且只有一份副本，被所有对象共享。

public class Circle {
        
        private static double pi = 3.14;
        private double radius;
        
        // 静态方法可以访问静态变量
        public static double getPi() {
        
            return pi;
        }
        
        public Circle(double r) {
        
            radius = r;
        }
        
        public double getArea() {
        
            return pi * radius * radius;
        }
    }
    
    public static void main(String[] args) {
        
        Circle c1 = new Circle(5.0);
        Circle c2 = new Circle(10.0);
        
        System.out.println(Circle.getPi()); // 输出 3.14
        System.out.println(c1.getArea());   // 输出 78.5
        System.out.println(c2.getArea());   // 输出 314.0
        
        Circle.pi = 3.14159; // 可以通过类名直接访问静态变量并修改其值
        System.out.println(Circle.getPi()); // 输出 3.14159
    }

1.  静态方法：使用`static`关键字修饰的方法是静态方法，也称为类方法。静态方法属于类而不是对象，可以通过类名直接调用，无需创建对象。

public class MathUtils {
        
        public static int add(int a, int b) {
        
            return a + b;
        }
        
        public static int subtract(int a, int b) {
        
            return a - b;
        }
    }
    
    public static void main(String[] args) {
        
        int sum = MathUtils.add(5, 3);       // 直接通过类名调用静态方法
        int difference = MathUtils.subtract(5, 3);
        
        System.out.println(sum);        // 输出 8
        System.out.println(difference);  // 输出 2
    }

1.  静态代码块：使用`static`关键字修饰的代码块是静态代码块，它在类加载时执行，用于初始化静态变量或执行其他静态操作。

public class Circle {
        
        private static double pi;
        
        static {
        
            pi = 3.14;
            System.out.println("Static initializer block executed");
        }
        
        public Circle(double r) {
        
            radius = r;
        }
    }
    
    public static void main(String[] args) {
        
        Circle c = new Circle(5.0); // 输出 "Static initializer block executed"
    }

#### **C++中const**:在C++中，`const`关键字用于声明常量，表示该变量的值在初始化后不能被修改。`const`可以用于变量、函数参数、函数返回值和成员函数。 ####

1.  常量变量：使用`const`关键字声明的变量被称为常量，其值在初始化后不能被修改。常量必须在声明时进行初始化。

const int MAX_VALUE = 100;
    int main() {
        
        MAX_VALUE = 200; // 错误，常量不能被修改
        return 0;
    }

1.  常量函数参数：在函数声明中，使用`const`关键字修饰函数参数，表示该参数在函数内部不会被修改。这样做可以保证函数不会意外修改传入的参数。

void printNumber(const int num) {
        
        num = 10; // 错误，常量参数不能被修改
        cout << num << endl;
    }
    
    int main() {
        
        int value = 5;
        printNumber(value); // 输出 5
        return 0;
    }

1.  常量函数返回值：在函数声明中，使用`const`关键字修饰函数返回值，表示该返回值是一个常量，不能被修改。

const int getNumber() {
        
        return 10;
    }
    
    int main() {
        
        int num = getNumber(); // 错误，常量返回值不能被修改
        return 0;
    }

1.  常量成员函数：在类中声明的成员函数可以使用`const`关键字修饰，表示该函数不会修改类的成员变量。常量成员函数可以在常量对象上调用，但不能修改对象的状态。

// 定义一个圆类
    class Circle {
        
    private:
        double radius; // 圆的半径
    public:
        // 构造函数，用于初始化圆的半径
        Circle(double r) : radius(r) {
        }
        
        // 常量成员函数，用于计算圆的面积
        double getArea() const {
        
            return 3.14 * radius * radius;
        }
    };
    
    // 主函数
    int main() {
        
        // 创建一个常量对象c，半径为5.0
        const Circle c(5.0);
        
        // 调用常量成员函数getArea()，计算圆的面积，并将结果赋值给变量area
        double area = c.getArea();
        
        // 错误，常量对象的成员变量不能被修改
        c.radius = 10.0;
        
        return 0;
    }

#### 个人拓展Java中的常量 ####

在Java中，没有直接的`const`关键字来声明常量。Java使用`final`关键字来声明常量，表示该变量的值在初始化后不能被修改。

1.  常量变量：使用`final`关键字修饰的变量是常量，一旦被赋值后就不能再改变。

final int num = 10;
    num = 20; // 错误，常量不能被修改

1.  常量方法参数：在方法声明中，使用`final`关键字修饰方法参数，表示该参数是一个常量，在方法内部不能修改参数的值。

void printNumber(final int value) {
        
        value = 20; // 错误，常量参数不能被修改
        System.out.println(value);
    }
    
    public static void main(String[] args) {
        
        int num = 10;
        printNumber(num); // 输出 10
    }

1.  常量方法返回值：在方法声明中，使用`final`关键字修饰方法返回值，表示该返回值是一个常量，不能被修改。

final int getNumber() {
        
        return 10;
    }
    
    public static void main(String[] args) {
        
        int num = getNumber(); // 错误，常量返回值不能被修改
    }

1.  常量成员变量：在类中声明的成员变量可以使用`final`关键字修饰，表示该变量是一个常量，一旦被赋值后就不能再改变。

public class Circle {
        
        private final double radius;
        
        public Circle(double r) {
        
            radius = r;
        }
        
        public double getArea() {
        
            return 3.14 * radius * radius;
        }
    }
    
    public static void main(String[] args) {
        
        Circle c = new Circle(5.0);
        double area = c.getArea();
        c.radius = 10.0; // 错误，常量成员变量不能被修改
    }

### c++的注释的演示 ###

这个题比较特殊，演示的是c++中`/**/`多行注释可能遇到的坑，也就是注释嵌套容易遇到的，比如下面的例子

1.  嵌套注释问题：C++中的注释不能嵌套。如果在一个多行注释中使用了另一个多行注释，编译器会将其视为注释的结束，导致编译错误。

/* This is a comment /* with nested comment */ */  // 错误，嵌套注释

1.  注释中的字符串问题：在注释中使用字符串时，需要注意字符串中可能包含的注释结束符`*/`。如果注释结束符出现在字符串中，编译器会将其视为注释的结束，导致编译错误。

/* This is a comment with a string "This is a string */" */  // 错误，字符串中包含注释结束符

1.  注释中的预处理指令问题：在注释中使用预处理指令时，需要注意预处理指令中可能包含的注释结束符`*/`。如果注释结束符出现在预处理指令中，编译器会将其视为注释的结束，导致编译错误。

/* This is a comment with a preprocessor directive #include "header.h" */  // 错误，预处理指令中包含注释结束符

1.  注释中的代码问题：在注释中放置代码是一种常见的错误做法。注释应该用于解释代码的作用和目的，而不是放置实际的代码。如果在注释中放置了代码，编译器会将其视为实际的代码，导致编译错误。

/* This is a comment with code */
    int x = 5;  // 错误，注释中放置了实际的代码

### c++中++运算问题 ###

题目：讲解a+++b的运算过程，通过代码讲解如下

#include <iostream>
    
    int main() {
        
        int a = 5;
        int b = 3;
        int result = a+++b;
    
        std::cout << "Result: " << result << std::endl;
    
        return 0;
    }

1.  首先，将`a`的当前值（5）赋给一个临时变量，然后将`a`的值递增1，此时`a`的值变为6。
2.  然后，将递增后的`a`的值（6）与`b`的值（3）相加，得到最终的结果9。

因此，输出结果为：

Result: 9

### 算法题：求1~100之间的质数 ###

这个太熟了，方法有很多，从慢到快演示。  
最简单方法，这就是根据质数的特性写的。

bool is_prime(int x)
    {
        
        if (x < 2) return false;
        for (int i = 2; i <= x / i; ++ i)
        {
        
            if (x % i == 0) return false;
        }
        return true;
    }

比赛写法，经典算法题，筛法求质数，这个比较讲究了，如果是一般的算法比赛，可以用埃式筛法，如果是ACM这种的话，就要使用线性筛法。

**埃式筛法**：一句话讲解思路就是，如果一个数字他是质数，那么他的倍数一定不是质数，所以只需要把这些不是质数的筛掉就可以了。时间复杂度O(nlogn)

// 埃氏筛法
    
    #include<iostream>
    using namespace std;
    const int N = 1e6 + 10;
    
    int cnt, n;
    bool st[N];
    
    void get_primes(int n)
    {
        
        for (int i = 2; i <= n; ++i)
        {
        
            if (!st[i])
            {
        
                cnt ++;
                for (int j = i + i; j <= n; j += i) st[j] = true;
            }
        }
    }
    int main()
    {
        
        cin >> n;
        get_primes(n);
        cout << cnt << '\n';
        return 0;
    }

**线性筛法**：这个难度就很大了，下面是我以前写一个讲解，以前我也是打过ACM的男人。

// 线性筛法 时间复杂度O(n)
    // 核心思想：一个数只会被它的最小质因子 筛掉 相对于埃氏筛法而言 可以省去很多不必要的操作 每个合数只会被筛一次
    // 数据越大 快的越明显
    
    #include<iostream>
    using namespace std;
    const int N = 1e6 + 10;
    
    int prime[N], cnt, n;
    bool st[N];
    
    void get_primes(int n)
    {
        
        for (int i = 2; i <= n; ++i)
        {
        
            if (!st[i]) prime[cnt ++] = i;
            for (int j = 0; prime[j] <= n / i; ++j)         // 一个个的求出的质数达到枚举 这里的判断条件中是不需要写上 j < cnt的 
                                                            // 因为下面的条件那个break 如果 i是合数 下面那个条件一定会成立 如果i 是质数 下面的那个条件也会成立
                                                            //  prime[]中含有所有合数的质因子 i是质数的话 prime中会有和i相等的一个数
            {
        
                st[prime[j] * i] = true;                    // prime[j] 是合数 prime[j] * i的最小质因子    
                if (i % prime[j] == 0)  break;              // 这里是最能理解的地方
                                                            // 由于prime[j]是按照从小到大的质数进行的 所以 如果这个语句成立的话 那么prime[j] 一定是 i的最小质因子
                                                            // 这个时候就符合算法思想了 每个合数只会被它的最小质因子筛掉 这个时候就要停下来了
                                                            // 如果继续的话会有 prime[j + 1]来筛下一个合数 i * prime[j + 1]
                                                            // 因为prime[j] 是 i的最小质因子 所以i * prime[j + 1] = k * prime[j] * prime[j + 1]
                                                            // 然后这个合数应该是要被 prime[j] 筛掉的 但是此时是被prime[j + 1] 筛掉的 然后违背了 这个算法的核心
            }
        }
    }
    int main()
    {
        
        cin >> n;
        get_primes(n);
        cout << cnt << '\n';
        return 0;
    }

### 讲解C语言里面指针与数组的关系 ###

我当时写的是数组的本质就是指针，指针被分配了内存之后就成了数组，下面是更详细的解释：

1.  数组名作为指针：在C语言中，数组名可以被视为指向数组首元素的指针。例如，对于一个整型数组int arr\[5\]，arr可以被视为指向arr\[0\]的指针。因此，可以通过arr来访问数组的元素，如arr\[0\]、arr\[1\]等。
2.  指针和数组的关系：由于数组名是指向数组首元素的指针，因此可以使用指针的方式来操作数组。例如，可以使用指针算术运算来访问数组的其他元素。比如，可以使用arr + 1来访问数组的第二个元素，使用arr + 2来访问数组的第三个元素，以此类推。
3.  指针与数组的传递：当将数组作为参数传递给函数时，实际上是将数组的首地址（即数组名）传递给函数。在函数内部，可以使用指针的方式来访问数组的元素。这样可以避免在函数调用时复制整个数组，提高了效率。
4.  数组指针：在C语言中，还可以定义指向数组的指针。例如，可以使用int\* ptr来定义一个指向整型数组的指针。通过指针，可以对数组进行遍历和操作。

#### 拓展内容，python,java,golang中指针是如何体现的 ####

**python**：在python中没有指针，但是处处都体现出来了指针，为啥python可以不用定义数据的类型了，正是用了指针的特性，python是万物皆对象，我们也可以说是万物皆指针，所以当然不需要定义具体的类型，因为所有的变量本质都是一个地址，js的设计思路应该也是一样的，不需要定义具体的数据类型。

**java**:java中也是没有指针的概念的，但是有了引用的概念来实现，指针的功能，  
在Java中，尽管没有像C语言那样直接的指针概念，但是通过引用类型和对象引用的方式，可以实现类似于指针的功能，比如下面的例子。

1.  对象引用：在Java中，变量存储的是对象的引用。当我们创建一个对象时，实际上是在堆内存中分配了一块内存空间，并将对象的引用赋给变量。这个引用可以看作是指向对象的指针。

int[] arr = new int[3];  // 创建一个整型数组对象
    int[] arr2 = arr;       // 将arr的引用赋给arr2
    arr2[0] = 1;            // 修改arr2，也会影响到arr
    System.out.println(arr[0]);  // 输出 1

1.  方法参数传递：在Java中，方法参数传递方式是通过对象引用来实现的。当我们将一个对象作为参数传递给方法时，实际上是将对象的引用传递给了方法。这意味着在方法内部对参数的修改会影响到原始对象。

public static void modifyArray(int[] arr) {
        
        arr[0] = 1;   // 修改arr，也会影响到原始数组
    }
    
    int[] arr = new int[3];
    modifyArray(arr);
    System.out.println(arr[0]);  // 输出 1

1.  对象的等价性：在Java中，可以使用`==`运算符来比较两个对象的引用是否相等。如果两个对象的引用指向同一个内存地址，则它们被认为是相等的。

int[] arr1 = new int[3];
    int[] arr2 = arr1;
    System.out.println(arr1 == arr2);  // 输出 true，arr1和arr2引用同一个对象

**golang**:在Go语言中，指针的功能和C语言非常的像，甚至操作符的含义都一样。

1.  声明指针：在Go语言中，可以使用`*`来声明一个指针变量。例如，`var ptr *int`声明了一个指向整型变量的指针。
2.  获取变量的地址：可以使用`&`操作符获取变量的内存地址。例如，`x := 10; ptr := &x`将变量`x`的地址赋给指针变量`ptr`。
3.  解引用指针：可以使用`*`操作符来解引用指针，即获取指针指向的变量的值。例如，`*ptr`表示获取指针`ptr`指向的整型变量的值。
4.  修改变量的值：通过指针，可以直接修改变量的值。例如，`*ptr = 20`表示将指针`ptr`指向的整型变量的值修改为20。
5.  空指针：Go语言中的空指针表示一个指针变量未指向任何有效的内存地址。可以使用`nil`关键字表示空指针。

package main
    
    import "fmt"
    
    func main() {
        
        x := 10
        fmt.Println("x =", x)  // 输出 x = 10
    
        ptr := &x
        fmt.Println("ptr =", ptr)  // 输出 ptr = 0xc0000180b8
        fmt.Println("*ptr =", *ptr)  // 输出 *ptr = 10
    
        *ptr = 20
        fmt.Println("x =", x)  // 输出 x = 20
    
        var nilPtr *int
        fmt.Println("nilPtr =", nilPtr)  // 输出 nilPtr = <nil>
    }

### 讲解你知道的所有排序方法，讲解他们的原理和对应的时间空间复杂度，还有快速排序是哪个排序转换而来的 ###

我整理了一下，如下（默认都是升序排列）：

1.  冒泡排序（Bubble Sort）：
    
     *  原理：通过比较相邻元素的大小，将较大的元素逐步向右移动，从而将最大的元素移动到最右边。重复这个过程，直到整个数组排序完成。
     *  时间复杂度：平均情况和最坏情况下的时间复杂度都为O(n^2)。
     *  空间复杂度：O(1)。

void bubbleSort(vector<int>& arr)
    {
        
        int n = arr.size();
        for (int i = 0; i < n - 1; ++ i)
        {
        
            for (int j = 0; j < n - 1 - i; ++ j)
            {
        
                if (arr[j] > arr[j + i]){
        
                    swap(arr[j], arr[j + 1]);
                } 
            }
        }
    }

1.  选择排序（Selection Sort）：
    
     *  原理：每次从未排序的部分中选择最小（或最大）的元素，然后将其放置在已排序部分的末尾。重复这个过程，直到整个数组排序完成。
     *  时间复杂度：平均情况和最坏情况下的时间复杂度都为O(n^2)。
     *  空间复杂度：O(1)。

void selectionSort(vector<int>& arr) {
        
        int n = arr.size();
        
        // 遍历数组，执行n-1轮选择操作
        for (int i = 0; i < n - 1; i++) {
        
            
            // 假设当前最小元素的索引为i
            int minIndex = i;
            
            // 在未排序部分中找到最小元素的索引
            for (int j = i + 1; j < n; j++) {
        
                if (arr[j] < arr[minIndex]) {
        
                    minIndex = j;
                }
            }
            
            // 将最小元素与未排序部分的第一个元素交换位置
            swap(arr[i], arr[minIndex]);
        }
    }

1.  插入排序（Insertion Sort）：
    
     *  原理：将数组分为已排序和未排序两部分，每次将未排序部分的第一个元素插入到已排序部分的正确位置。重复这个过程，直到整个数组排序完成。
     *  时间复杂度：平均情况和最坏情况下的时间复杂度都为O(n^2)。
     *  空间复杂度：O(1)。

void insertionSort(vector<int>& arr) {
        
      int n = arr.size();
      
      // 从第二个元素开始，依次插入到已排序部分的正确位置
      for (int i = 1; i < n; i++) {
        
          int key = arr[i];
          int j = i - 1;
          
          // 将比key大的元素向后移动
          while (j >= 0 && arr[j] > key) {
        
              arr[j + 1] = arr[j];
              j--;
          }
          
          // 将key插入到正确位置
          arr[j + 1] = key;
      }
    }

1.  快速排序（Quick Sort）：
    
     *  原理：选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素。然后对这两部分分别进行递归排序。通过不断地划分和排序，最终实现整个数组的排序。
     *  时间复杂度：平均情况下的时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)。但是，通过使用随机化的快速排序和优化的分区算法，可以减少最坏情况的出现概率。
     *  空间复杂度：平均情况下的空间复杂度为O(logn)，最坏情况下的空间复杂度为O(n)。
     *  来源：快速排序是由冒泡排序改进而来的，它采用了分治法的思想，通过选择一个基准元素将数组分为两部分，然后对这两部分进行递归排序。

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    int q[N];
    
    void quick_sort(int q[], int l, int r)
    {
        
        if (l >= r) return;
        int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
        while(i < j)
        {
        
            do i ++; while (q[i] < x);
            do j --; while (q[j] > x);
            if (i < j) swap(q[i], q[j]);
        }
        quick_sort(q, l, j); quick_sort(q, j + 1, r);
    }
    
    int main()
    {
        
        int n;
        scanf ("%d", &n);
        for (int i = 0; i < n; ++ i) scanf("%d", &q[i]);
        quick_sort(q, 0, n - 1);
        for (int i = 0; i < n; ++ i) printf("%d ", q[i]);
        return 0;
    }

1.  归并排序（Merge Sort）：
    
     *  原理：将数组分成两个子数组，分别对这两个子数组进行递归排序，然后将排好序的子数组合并成一个有序的数组。通过不断地分割和合并，最终实现整个数组的排序。
     *  时间复杂度：平均情况和最坏情况下的时间复杂度都为O(nlogn)。
     *  空间复杂度：O(n)。

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    int tmp[N], q[N];
    int n;
    
    void merge_sort(int q[], int l, int r)
    {
        
        if (l >= r) return;
        
        int mid = l + r >> 1;
        merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
        
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) 
        {
        
            if (q[i] <= q[j]) tmp[k ++] = q[i ++];
            else tmp[k ++] = q[j ++];
        }
        while (i <= mid) tmp[k ++] = q[i ++];
        while (j <= r) tmp[k ++] = q[j ++];
        
        for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    }
    
    int main()
    {
        
        scanf ("%d", &n);    
        for (int i = 0; i < n; ++i) scanf ("%d", &q[i]);
        
        merge_sort(q, 0, n - 1);
        
        for (int i = 0; i < n; ++i) printf("%d ", q[i]);
        return 0;
    }

1.  堆排序（Heap Sort）：
    
     *  原理：将数组构建成一个最大堆（或最小堆），然后将堆顶元素与堆的最后一个元素交换，并将堆的大小减1。重复这个过程，直到堆为空。通过这种方式，最大（或最小）的元素会被依次放置到数组的末尾，从而实现排序。
     *  时间复杂度：平均情况和最坏情况下的时间复杂度都为O(nlogn)。
     *  空间复杂度：O(1)。

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int N = 100010;
    int h[N], mysize, n, m;
    
    void down(int u)
    {
        
        int t = u;
        if (2 * u <= mysize && h[t] > h[2 * u]) t = 2 * u;
        if (2 * u + 1 <= mysize && h[t] > h[2 * u + 1]) t = 2 * u + 1; 
        if (u != t)
        {
        
            swap(h[u], h[t]);
            down(t);
        }
    }
    
    int main()
    {
        
        cin >> n >> m;
        mysize = n;
        for (int i = 1; i <= n; ++ i)
            cin >> h[i];
        for (int i = n / 2; i; i --)   // 如果i > n / 2 那么上面的 2 * u > size 那么 u = t 会进行很多没有意义的计算
            down(i);
        while (m --)
        {
        
            cout << h[1] << ' ';
            h[1] = h[mysize --];
            down(1);
        }
        return 0;
    }

### 后面就是计算机组成原理的了，选择题记不清了，我计算机组成原理很差，所以就讲解一下简答题 ###

1.  辅存（辅助存储器）：  
    辅存是计算机系统中最慢但容量最大的存储层次。它通常指的是硬盘、固态硬盘（SSD）等外部存储设备。辅存具有较大的存储容量，能够长期保存数据，但是访问速度较慢。辅存主要用于存储操作系统、应用程序、文件和其他数据。
2.  主存（主存储器）：  
    主存是计算机系统中位于辅存和Cache之间的存储层次。它通常指的是随机访问存储器（RAM）或动态随机访问存储器（DRAM）。主存具有较快的访问速度和较大的存储容量，用于存储当前正在运行的程序和数据。CPU通过地址总线和数据总线与主存进行通信，可以读取和写入主存中的数据。
3.  Cache（高速缓存）：  
    Cache是计算机系统中位于CPU和主存之间的存储层次。它是一种速度非常快、容量较小但比主存大的存储器。Cache的作用是通过存储最近使用的数据和指令，提高CPU对数据的访问速度。当CPU需要读取数据时，首先在Cache中查找，如果找到了，则称为“命中”，可以直接从Cache中获取数据，这样可以大大减少访问主存的时间。如果在Cache中没有找到需要的数据，则称为“未命中”，CPU需要从主存中读取数据，并将其存储到Cache中，以供后续访问使用。

Cache-主存-辅存结构的设计是为了在存储层次结构中实现高效的数据访问。Cache作为CPU与主存之间的缓冲区域，可以快速提供数据，减少CPU等待数据的时间。主存作为临时存储区域，存储当前正在运行的程序和数据。辅存作为永久存储区域，用于长期保存数据和程序。通过合理设计和管理这三个层次的存储结构，可以提高计算机系统的性能和效率。

### 二分查找代码实现 ###

这个不难，就是算法导论里面的原题。

int binarySearch(const std::vector<int>& arr, int target) {
        int left = 0;
        int right = arr.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    
        return -1;
    }

### 最长连续不重复子序列 ###

这个也是算法导论上面的题目，算法思路是双指针法.双指针算法最经典的题目  
![在这里插入图片描述][6cc7468a474541b4ac3199eb28bfe0ee.png]

#include<bits/stdc++.h>
    using namespace std;
    const int N = 100010;
    
    int a[N], s[N];
    int n, res;
    
    int main()
    {
        
        cin >> n;
        for (int i = 0; i < n; ++ i) cin >> a[i];
        for (int i = 0, j = 0; i < n; ++ i)
        {
        
            s[a[i]] ++; // 记录下a[i]出现的次数
            while(s[a[i]] > 1)   // 一点碰见两个重复的元素后
            {
          
                s[a[j]] --;  // 这里要主要的一点是这个算法是没有回溯的
                             // 不要被for循环里面的条件误导以为会回溯、
                             // 现在遇到两个相同的元素了
                             // ！！！ 现在是这个算法最厉害的地方 
                             // 这个j代表的是 j可以到达最左的地方 所以在j左边的
                             // 元素的个数就需要都-- 这点很妙
                j ++;        // 然后j++
            }
            res = max(res, i - j + 1);  // 这个res的含义是 在i这个位置、
            // 可以达到的符合题目条件的最大长度
        }
        cout << res;
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_51447496/article/details/134086851?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22134086851%22,%22source%22:%22qq_51447496%22%7D
[6cc7468a474541b4ac3199eb28bfe0ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/34bd3f72bdb64ef6a34ec099b646469b.png