记一次C++后台开发面试拷打过程

开头简单的自我介绍，面试官和我聊了聊天缓解个人紧张状况，然后就让开屏幕共享开视频做题目，做完以后，问了一些问题，就让等通知了，估计是凉了，不过这里且把当时做的笔试题目复盘一下吧！题目是ai做的题解，唉，AI都比我强，比我面试的时候解释的强多了，未来该何去何从啊...

微*团队c++笔试题

45分钟

【资料图】

一、填空题

1、请计算32位机器上如下代码输出值：

void Func(char str[100]){ cout<

2、请问运行Test函数会有出现结果： 段错误_____

#include using namespace std;void GetMemory(char *p){   p = (char *)malloc(100);}void Test(void) {    char *str = NULL;    GetMemory(str);      strcpy(str, "hello world");    printf("%s\n",str);}int main(){Test();return 0;}

这段代码会出现段错误的原因是在GetMemory函数中，虽然p指针指向了分配的内存空间，但是由于p是传递的指针副本，函数结束后并不会改变原来的指针str，因此在Test函数中使用str指针时，它仍然是NULL指针，所以会出现段错误。

为了解决这个问题，可以将GetMemory函数的参数改为指向指针的指针，这样就可以改变原来的指针了。修改后的代码如下：

#include using namespace std;void GetMemory(char **p){   *p = (char *)malloc(100);}void Test(void) {    char *str = NULL;    GetMemory(&str); // 传递指向指针的指针    strcpy(str, "hello world");    printf("%s\n",str);}int main(){    Test();    return 0;}

3、static局部变量与普通局部变量有什么区别

static局部变量和普通局部变量的主要区别在于它们的生命周期和作用域。

普通局部变量的生命周期只存在于函数调用期间，当函数返回时，它所占用的内存空间会被释放。因此，每次函数调用时，都会重新创建一个新的局部变量。

而static局部变量的生命周期则存在于整个程序运行期间，即使函数返回，它所占用的内存空间也不会被释放。因此，static局部变量在第一次创建后就一直存在于内存中，下次函数调用时可以继续使用之前的值。

另外，static局部变量的作用域仅限于定义它的函数内部，但是它在函数调用期间保持其值不变，因此可以用来实现函数内部的计数器或状态标记等功能。

总之，static局部变量和普通局部变量都是在函数内部定义的局部变量，但是它们的生命周期和作用域有所不同。

4、写出下列代码的输出内容

include int inc(int a){ return (++a);}int multi(int* a, int *b, int* c){ return(*c = *a * *b);}typedef int (*FUNC1 ) (int in);typedef int (*FUNC2)  (int*, int*, int*);void show(FUNC2 fun, int arg1, int* arg2){ FUNC1 p = &inc; int temp = p(arg1); fun(&temp, &arg1, arg2); printf(" %d\n", *arg2);}   main(){ int a; show(multi, 10, &a); return 0;}

110

5、请找出下面代码中的所有错误

说明：以下代码是把一个字符串倒序，如“abcd”倒序后变为“dcba”

#include "string.h"main(){ char* src = "hello , world"; char* dest = NULL; int len = strlen(src); dest = (char*) malloc(len );      char* d = dest; char* s = src[len];     while(len-- != 0 )   d++ = s--;             printf("%s", dest); return 0;}

#include #include  // 需要包含stdlib.h头文件int main() { // main函数需要指定返回值类型int    const char* src = "hello , world"; // src是指向字符串常量的指针，需要加上const关键字    char* dest = NULL;    int len = strlen(src);    dest = (char*) malloc(len + 1); // 分配的内存空间应该是len+1，因为字符串以"\0"结尾    char* d = dest + len - 1; // d指向dest的最后一个字符    const char* s = src; // s指向src的第一个字符    while(len-- != 0) {        *d-- = *s++; // 将s所指向的字符赋值给d所指向的字符，并将d和s分别向前和向后移动一位    }    *d = "\0"; // 需要在dest的末尾添加"\0"，使其成为一个以"\0"结尾的字符串    printf("%s", dest);    free(dest); // 释放动态分配的内存    return 0;}/*忘记包含stdlib.h头文件，导致编译器无法识别malloc和free函数。src是指向字符串常量的指针，需要加上const关键字。分配的内存空间应该是len+1，因为字符串以"\0"结尾。d指向dest的最后一个字符，而不是dest的第一个字符。s指向src的第一个字符，而不是src的最后一个字符。在while循环中，需要将s所指向的字符赋值给d所指向的字符，并将d和s分别向前和向后移动一位。需要在dest的末尾添加"\0"，使其成为一个以"\0"结尾的字符串。在程序结束前需要释放动态分配的内存*/

6.请问下面代码是否合法，为什么？

uint16_t wId = 2;    //合法赋值        uint16_t* p1 = &wId;   //合法，p1指向wld  uint32_t *p2 = p1;   //原因是在将uint16_t类型的指针p1赋值给uint32_t类型的指针p2时，发生了类型不匹配的错误。p1指向的是一个16位的无符号整数，而p2指向的是一个32位的无符号整数，这两种类型的指针所指向的数据的大小不同。因此，将p1赋值给p2会导致指针类型不匹配的错误。    uint32_t dwId = *p2; //程序试图将一个32位的无符号整数赋值给一个16位的无符号整数，这会导致截断错误。具体来说，如果dwId的值大于16位无符号整数的最大值（65535），则只会保留低16位，高16位会被截断。这可能会导致程序逻辑错误或崩溃。    

二、编程题

请编写能直接实现strstr()函数功能的代码(在str1中找到是否包含str2，若包含返回str1中匹配的起始指针)

char* strstr(const char* str1, const char* str2) {    if (*str2 == "\0") {        return (char*) str1;    }    const char* p1 = str1;    while (*p1 != "\0") {        const char* p1_begin = p1;        const char* p2 = str2;        while (*p1 != "\0" && *p2 != "\0" && *p1 == *p2) {            p1++;            p2++;        }        if (*p2 == "\0") {            return (char*) p1_begin;        }        if (*p1 == "\0") {            return nullptr;        }        p1 = p1_begin + 1;    }    return nullptr;}/*该函数首先判断str2是否为空字符串，如果是，则直接返回str1的起始指针。然后在str1中循环查找，每次从当前位置开始，与str2逐个字符比较，如果匹配成功，则继续比较下一个字符，否则从下一个位置开始重新比较。如果str2匹配完了，则返回当前位置的起始指针；如果str1匹配完了，则表示没有找到，返回nullptr。*/

//kmp算法#include #include using namespace std;// 计算next数组void getNext(string pattern, vector& next) {    int n = pattern.size();    next.resize(n);    next[0] = -1;    int j = -1;    for (int i = 1; i < n; i++) {        while (j >= 0 && pattern[i] != pattern[j + 1]) {            j = next[j];        }        if (pattern[i] == pattern[j + 1]) {            j++;        }        next[i] = j;    }}// KMP算法int kmp(string text, string pattern) {    int n = text.size();    int m = pattern.size();    if (m == 0) {        return 0;    }    vector next;    getNext(pattern, next);    int j = -1;    for (int i = 0; i < n; i++) {        while (j >= 0 && text[i] != pattern[j + 1]) {            j = next[j];        }        if (text[i] == pattern[j + 1]) {            j++;        }        if (j == m - 1) {            return i - j;        }    }    return -1;}int main() {    string text = "ababcabcacbab";    string pattern = "abcac";    int pos = kmp(text, pattern);    if (pos == -1) {        cout << "Pattern not found in text" << endl;    } else {        cout << "Pattern found in text at position " << pos << endl;    }    return 0;}

KMP算法的思路是，在匹配字符串的过程中，当发现某个字符不匹配时，不需要从头开始重新匹配，而是利用已经匹配的信息，尽可能地减少比较次数。

具体实现上，首先需要计算出模式串的next数组，next数组表示当匹配失败时，应该将模式串向右移动几位。然后在匹配字符串的过程中，利用next数组进行跳转。如果当前字符匹配成功，则继续比较下一个字符；如果匹配失败，则根据next数组跳转到模式串的某个位置，重新开始比较。

在上面的代码中，getNext函数计算模式串的next数组，kmp函数实现了KMP算法。

三、算法（以下两题，任选一题）

1、用拉链法实现hash，接口：插入，查找，删除

hash函数，可以不实现

要求要用链表实现

#include #include using namespace std;// 哈希表节点struct HashNode {    int key;    int value;    HashNode* next;    HashNode(int k, int v) : key(k), value(v), next(nullptr) {}};// 哈希表class HashTable {private:    vector table;    int capacity;    int size;    // 计算哈希值    int hash(int key) {        return key % capacity;    }public:    // 构造函数    HashTable(int cap) : capacity(cap), size(0) {        table.resize(capacity, nullptr);    }    // 插入元素    void insert(int key, int value) {        int index = hash(key);        HashNode* node = table[index];        while (node != nullptr) {            if (node->key == key) {                node->value = value;                return;            }            node = node->next;        }        node = new HashNode(key, value);        node->next = table[index];        table[index] = node;        size++;    }    // 查找元素    bool find(int key, int& value) {        int index = hash(key);        HashNode* node = table[index];        while (node != nullptr) {            if (node->key == key) {                value = node->value;                return true;            }            node = node->next;        }        return false;    }    // 删除元素    bool remove(int key) {        int index = hash(key);        HashNode* node = table[index];        HashNode* prev = nullptr;        while (node != nullptr) {            if (node->key == key) {                if (prev == nullptr) {                    table[index] = node->next;                } else {                    prev->next = node->next;                }                delete node;                size--;                return true;            }            prev = node;            node = node->next;        }        return false;    }};int main() {    HashTable hashTable(10);    hashTable.insert(1, 10);    hashTable.insert(2, 20);    hashTable.insert(3, 30);    int value;    if (hashTable.find(2, value)) {        cout << "Value of key 2 is " << value << endl;    } else {        cout << "Key 2 not found" << endl;    }    if (hashTable.remove(3)) {        cout << "Key 3 removed" << endl;    } else {        cout << "Key 3 not found" << endl;    }    return 0;}/*哈希表是一种常用的数据结构，它可以实现快速的查找、插入和删除操作。哈希表的核心思想是将键映射到一个存储位置，这个存储位置就是哈希值。为了解决哈希冲突，可以使用拉链法，即将每个哈希值对应的元素放在一个链表中。上面的代码中，HashTable类表示哈希表，HashNode结构体表示哈希表的节点。哈希表使用vector实现，每个元素是一个指向链表头节点的指针。插入、查找、删除操作都需要计算出哈希值，然后在相应的链表中进行操作。*/

2、实现一个大根堆，两个过程：

a、构建堆

b、弹出堆顶数据

#include #include using namespace std;// 构建大根堆void buildMaxHeap(vector& nums) {    int n = nums.size();    for (int i = n / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始调整        int j = i;        while (j * 2 + 1 < n) { // 如果有左孩子            int k = j * 2 + 1; // 左孩子的下标            if (k + 1 < n && nums[k + 1] > nums[k]) { // 如果有右孩子且右孩子比左孩子大                k++; // 右孩子的下标            }            if (nums[k] > nums[j]) { // 如果孩子比父节点大                swap(nums[k], nums[j]); // 交换父节点和孩子                j = k; // 继续向下调整            } else {                break;            }        }    }}// 弹出堆顶元素int popMaxHeap(vector& nums) {    int n = nums.size();    int maxVal = nums[0];    nums[0] = nums[n - 1]; // 把最后一个元素放到堆顶    nums.pop_back(); // 删除最后一个元素    n--;    int i = 0;    while (i * 2 + 1 < n) { // 如果有左孩子        int j = i * 2 + 1; // 左孩子的下标        if (j + 1 < n && nums[j + 1] > nums[j]) { // 如果有右孩子且右孩子比左孩子大            j++; // 右孩子的下标        }        if (nums[j] > nums[i]) { // 如果孩子比父节点大            swap(nums[j], nums[i]); // 交换父节点和孩子            i = j; // 继续向下调整        } else {            break;        }    }    return maxVal;}int main() {    vector nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};    buildMaxHeap(nums);    while (!nums.empty()) {        cout << popMaxHeap(nums) << " ";    }    cout << endl;    return 0;}/*大根堆是一种常用的数据结构，它可以实现快速的查找最大值、插入和删除操作。大根堆的核心思想是将元素按照完全二叉树的形式存储，并且满足每个节点的值都大于等于其左右孩子节点的值。上面的代码中，buildMaxHeap函数用于构建大根堆，popMaxHeap函数用于弹出堆顶元素。构建大根堆的过程是从最后一个非叶子节点开始，依次向上调整每个节点，使得整个堆满足大根堆的性质。弹出堆顶元素的过程是把最后一个元素放到堆顶，然后依次向下调整每个节点，使得整个堆重新满足大根堆的性质。*/