C语言笔试准备

经常要操作的内存分为哪几个类别？

1. 栈区：由编译器自动分配和释放，用于存储函数调用时的参数值、返回地址、局部变量等内容。
2. 堆：一般由程序员分配和释放，存放动态分配的变量。
3. 全局区：全局变量和静态变量存放在这一块，初始化和未初始化的分开放。
4. 文字常量区：常量字符串就放在这里，程序结束后自动释放。
5. 程序代码区：函数体的二进制代码。

下面数据结构中是线性结构的有：

• 链表
• 数组
• 栈

线程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见。

线程间可以直接读写进程数据段（如全局变量）来通信。

线程上下文切换要比进程快。

使用哈夫曼算法编码后，用编码值来存储这段文本将花费最少的存储空间。

使用哈夫曼算法进行编码，编码值可以有多套，但每个字符编码的位是确定的。

哈夫曼树带权路径长度最短的树，路径上全值较大的节点离根较近。

当从一个最小堆删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整到合适位置。

虚函数通常在基类中会提供一个默认实现，虚函数的关键特性是允许在派生类中被重写。

抽象类指针可以指向不同的派生类。

重载函数必须有不同的形参列表。

a[i][j]的实际访问方式为*(*(a+i)+j)

virtual void a()=0;是纯虚函数，纯虚函数的类是抽象类，抽象类不能创建对象，并且抽象类的派生类必须要重写纯虚函数，否则派生类也是抽象类，抽象类不能定义对象。

有m个进程共享同一临界资源，若使用信号量机制实现对该临界资源的互斥访问，则信号量的变化范围是1至n-1。

分段式存储管理有利于程序的动态链接。

执行广度优先搜索时，需要使用队列作为辅助空间。

堆是一颗完全二叉树。

map是用红黑树来实现的。

对包含n个元素的散列表进行检索时，平均检索长度不直接依赖于n，对于散列表（哈希表）的平均检索长度，一般不直接依赖于n，而是取决于散列元素的好坏。

用两趟快排，可以确定2或3个最终位置。如果第一趟确定的位置是最大或者最小的，那么以这个位置为基准只有一边需要递归快排（也就是第二趟的时候只能确定一个），但是如果第一趟的不是最值，是中间某个位置，那么就分为了左边和右边两块，第二次快排的时候就会确定左边一个右边一个的位置（也就是第二趟确定2个位置），那么D选项确定的两个位置都在中间，所以其实应该要确定三个才是正确的

纯虚函数可以做指针和引用。

union all效率更高。

volatile关键字并不能保证线程安全。

HTTP协议的响应码由3个十进制组成，第一个数字为1~5表示5种状态，因此选C。

TCP三次握手建立过程中，所有的标志位至少会有4次被置为1。
SYN置为1.
SYN置为1，ACK=1
ACK=1

C++ String类中没有自带的排序方法，但是可以使用算法库中的sort()方法进行排序。

dirname命令，该命令的作用是返回指定路径的目录名，去掉文件名部分。

inode记录最后一次读取时间，最近修改的时间，该文件的容量，但不记录实际内容。

HTTP协议是一种无状态的协议，因为每个请求都是独立的，服务器不会保存客户端的状态信息。
HTTP协议使用TCP作为传输协议，HTTP协议的默认端口号是80，HTTP协议本身不提供数据加密功能，为了提高传输数据的安全性，可以使用HTTPS协议，它是HTTP协议的安全版本，使用SSL/TLS加密传输协议。

Python不是编译性语言，而是解释性语言。

• 编译型语言：在程序执行之前，将源代码一次编译成机器码，然后直接运行机器码。编译后的程序执行效率较高，但可移植性较差。
• 解释性语言：源代码不是直接编译成机器码，而是由解释器逐行读取并执行。解释性语言执行效率低，但可移植性较好。

string不是C语言的数据类型。

x >> 1表示将x的二进制表示向右移动一位，并在左侧填充0。

结构体声明

struct Mystruct{int a;int b;
};

使用const关键字修饰一个指针变量可以使指针变量所指向的值无法被修改。

？运算符的结合顺序是从右向左？

int a = 1, b = 2, c = 3;
int x = a > b ? a : b > c ? b : c;

先计算b > c ? b:c得3
再计算a > b?a:b得3

指针可以指向任意类型的变量。

指针变量本身占用的内存大小固定。

可以使用指针进行动态内存分配。

结构体可以嵌套定义结构体类型。

可以定义不包含任何成员的结构体类型。

但结构体变量不能直接进行赋值。

关系运算符==、<=、>=、！=

#define FOO(x,y)(x+y)

在C语言的宏定义中，#运算符具有字符串化的功能，会将跟在后面的宏参数转换为一个字符串。

#define STR(x) #x

数组名本身就是地址，因此数组名不能被赋值或用于地址运算

const关键字和#define宏定义虽然都可以定义常量，但它们在很多方面存在区别，不能完全互换使用。
const关键字：

• 类型安全：const定义的常量具有数据类型，编译器可以进行类型检查，提高程序的可靠性。
• 作用域： const定义的常量有明确的作用域，遵循变量的作用域规则。
• 存储： const常量在编译时通常会分配内存空间，可以取地址。
• 调试： const常量可以被调试器跟踪。

#define

• 无类型：宏定义没有数据类型，编译器不能进行类型检查，容易出错。
• 全局替换：宏定义在预编译阶段进行简单的文本替换，没有作用域概念。
• 无存储：宏定义不分配内存空间，不能取地址。
• 调试：宏定义在预编译阶段已经被替换，调试信息较少。

C语言函数的参数不支持默认值

函数指针可以作为另一个函数的参数，这在回调函数等场景中非常常见。

函数指针可以作为函数的返回值。

static限制变量的作用域

常量成员函数是指在成员函数的末尾加上const关键字，这样该函数就不能修改类的成员变量。

unsigned char数据类型表示的数值范围为0-255。

逻辑非的优先级最高，然后是逻辑与，最后是逻辑或。也就是说，在没有括号的情况下，! 会先于 && 和 || 进行运算。

int *p = new int[10]; //p申请的空间里的值是随机值
int *p = new int10; //p申请的空间里的值已经初始化

求最大公约数

int gcd(int a,int b){return b == 0 ? a : gcd(b, a%b);
}

int gcd(int a, int b){while(b != 0){int temp = a%b;a = b;b = temp;}return a;
}

C语言数组作为函数参数

在C语言中，数组作为函数参数传递时，实际上传递的是数组的首地址。也就是说，函数形参接收到的是指向数组第一个元素的指针。

• 传递的是数组的首地址：函数形参接收到的并不是整个数组，而是一个指向数组首元素的指针。
• 数组大小无法在函数内部直接获取：由于只传递了首地址，函数内部无法直接指定数组的长度。
• 修改数组元素会影响原数组：由于传递的是数组的地址，在函数内部对数组元素的修改会直接反映到原数组上。

局部变量空间是从堆分配和栈分配，全局变量和静态局部变量是从静态存储区中划分。

全局变量作用域大于静态局部变量。

1. 类中一旦有virtual修饰的成员函数，编译器会构建虚函数表，在该类的对象中会存放一个指向虚函数表的指针。+4
2. 静态成员变量为所有对象共有，不计算对象的占用空间。

小型机通常采用RISC和Unix操作系统。

tar命令选项

• -c：创建新的归档文件
• -v：创建归档文件时显示详细过程
• -f：指定归档文件名
• z：表示使用gzip算法
• -j：表示使用bzip2算法
• -x表示解压缩

不含回路的有向图，即DAG（有向无环图）一定存在拓扑排序。

m个节点，有m-1个非空指针（除根节点其余节点均有指针指向），其余皆为空指针。

vector作为序列容器删除一个元素会导致后续所有元素迭代器失效，因此必须得接erase的返回值。

数组名是常量指针，所以不能进行赋值操作（不能改变它指向的值）。

-25的源码是10011001，反码是11100110，补码是11100111（符号位不变）

编译器会将inline修饰的函数的函数体直接插入到调用此函数的地方，以此加快程序的运行速度。

堆排序是一种基于比较的排序算法，它的时间复杂度始终是O(n log n)，不受初始数据排列顺序的影响。
堆排序通过构建一个堆的数据结构，然后不断将顶堆最大的元素移出并调整堆，最终得到有序序列。

• 插入排序：时间复杂度与初始数据的有序程度有关。如果数据已经基本有序，插入排序的效率会很高；但如果数据完全无序，则效率较低。
• 冒泡排序：它的时间复杂度是O(n^2)，并且对初始数据的顺序敏感。如果数据已经基本有序，冒泡排序很快结束；但如果无序，需要更多的比较和交换.

加油站

在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。
有一辆容量无限的汽车，从第[i]开到第[i+1]个加油站需要汽油cost[i]升。

给定两个数组gas和cost，如果可以按顺序环绕行驶一周，则返回加油站出发的编号，否则返回-1，保证解唯一。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int currSum = 0, totalSum = 0, start = 0;for(int i=0; i< gas.size(); i++){currSum += (gas[i] - cost[i]);totalSum += (gas[i] - cost[i]);if(currSum < 0){start = i+1;currSum = 0;}}return totalSum < 0 ? -1 : start;}
};

罗马数字转整数

class Solution {
public:int romanToInt(string s) {int sum = 0;int n = s.size();for(int i=0; i<n; i++){if(s[i] == 'I'){if(i+1 < n && s[i+1] == 'V'){sum += 4;i++;}else if(i+1<n && s[i+1] == 'X'){sum += 9;i++;}else{sum += 1;}}else if(s[i] == 'X'){if(i+1 < n && s[i+1] == 'L'){sum += 40;i++;}else if(i+1<n && s[i+1] == 'C'){sum += 90;i++;}else{sum += 10;}}else if(s[i] == 'C'){if(i+1 < n && s[i+1] == 'D'){sum += 400;i++;}else if(i+1<n && s[i+1] == 'M'){sum += 900;i++;}else{sum += 100;}}else if(s[i] == 'V'){sum += 5;}else if(s[i] == 'L'){sum += 50;}else if(s[i] == 'D'){sum += 500;}else if(s[i] == 'M'){sum += 1000;}}return sum;}
};

整数转罗马数字

class Solution {
public:string intToRoman(int num) {string res;vector<int> nums;while (num) {nums.push_back(num % 10);num /= 10;}//int count = nums.size()-1;for (int i = nums.size() - 1; i >= 0; i--) {int tempNum = nums[i] * pow(10, i);if (tempNum == 4) {res += "IV";}else if (tempNum == 9) {res += "IX";}else if (tempNum == 40) {res += "XL";}else if (tempNum == 90) {res += "XC";}else if (tempNum == 400) {res += "CD";}else if (tempNum == 900) {res += "CM";}else {while (tempNum >= 1000) {res += 'M';tempNum -= 1000;}while (tempNum >= 500) {res += 'D';tempNum -= 500;}while (tempNum >= 100) {res += 'C';tempNum -= 100;}while (tempNum >= 50) {res += 'L';tempNum -= 50;}while (tempNum >= 10) {res += 'X';tempNum -= 10;}while (tempNum >= 5) {res += 'V';tempNum -= 5;}while (tempNum >= 1) {res += 'I';tempNum -= 1;}}}return res;}
};

生命游戏

给定一个包含mxn个格子的面板，每一个格子都可以看成是一个细胞。
每个细胞都具有一个初始状态：1为活细胞，0为死细胞。
每个细胞与其八个相邻位置的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数量少于两个，则该位置活细胞死亡。
2. 如果活细胞周围八个位置的活细胞数量有两个或三个活细胞，则该位置活细胞存活。
3. 如果活细胞周围八个位置的活细胞数量超宇三个活细胞，则该位置活细胞死亡。
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活。

下一个状态是指通过将上述规则同时应用于当前状态下的每个细胞所形成的。

C语言格式化输出%u的作用

%u是一个格式化输出控制符，用于将一个无符号整数按十进制形式输出：

• 无符号整数：意味着这个整数不包含负数，其值总是大于等于0。

两数相加

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* prevHead = new ListNode(-1);ListNode* p = prevHead;int flag = 0;while(l1 && l2){int val = l1->val + l2->val + flag;l1->val = val%10;flag = val/10;p->next = l1;p = p->next;l1 = l1->next;l2 = l2->next;}while(l1){int val = l1->val + flag;l1->val = val%10;flag = val/10;p->next = l1;p = p->next;l1 = l1->next;}while(l2){int val = l2->val + flag;l2->val = val%10;flag = val/10;p->next = l2;p = p->next;l2 = l2->next;}if(flag){p->next = new ListNode(1);}return prevHead->next;}
};

课程表二

共有numCourses门课程需要选，[ai,bi]选ai课程之前需要修bi，如果可以完成返回一种顺序，否则返回空。

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> inorder(numCourses, 0); //求每门课程的入度，如果入度为0，表明可以先修vector<vector<int>> nextArray(numCourses); //学完一门课程后，可以学的课程vector<int> res;for(auto &p : prerequisites){inorder[p[0]]++;nextArray[p[1]].push_back(p[0]);}queue<int> que;for(int i=0; i<numCourses; i++){if(inorder[i] == 0){que.push(i);}}while(!que.empty()){int x = que.front();que.pop();res.push_back(x);for(auto p=nextArray[x].begin(); p != nextArray[x].end(); p++){inorder[*p]--;if(inorder[*p] == 0){que.push(*p);}}}if(res.size() == numCourses){return res;}return {};}
};

组合总和

一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。

搜索回溯
定义递归函数dfs(target, combine, idx)
表示当前在candidates第idx位，还剩target要组合，已经组合的列表为combine。
递归的终止条件是target≤0或者candidates数组被全部用完。
那么在当前函数中，我们可以选择跳过不用第idx个数，即执行dfs(target, combine, idx+1)，也可以选择使用第idx个数，即执行dfs(target-candidates[idx], combine, idx)。注意点每个数字可以被重复选取，所以搜索的下标仍然为idx。

class Solution {
public:void dfs(vector<int>& candidates, int target, vector<vector<int>> &res, int index, vector<int>& temp){if(target == 0){res.push_back(temp);return;}if(index == candidates.size() || target < 0){return;}dfs(candidates, target, res, index+1, temp); //跳过当前数temp.push_back(candidates[index]);dfs(candidates, target-candidates[index], res, index, temp);//不跳过当前数temp.pop_back();}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> res;vector<int> temp;dfs(candidates, target, res, 0, temp);return res;}
};