All notes
CppExam

# Linux related

## Fork


int main(){
int pid;
int num=1;
pid=fork();
if(pid>0){
num++;
",num,&num);
}
else if(pid==0){
",num,&num);
}
}

a 父子进程中输出的num相同,num地址不相同
b 父子进程中输出的num不同,num地址相同
c 父子进程中输出的num相同,num地址也相同
d 父子进程中输出的num不同,num地址不相同


Linux中的资源分配都是虚拟机制，也就是说，他们还是会共用一个虚拟的地址，但是映射到物理内存就可能会不一样。答案是b。

## Heap/Stack

a stack由编译器自动分配和释放,存放函数的参数值，局部变量，全局变量的值
b heap一般由程序员分配和释放，若程序员不释放，可能会造成操作系统的内存泄露
c stack由系统自动分配，无需程序员干涉，heap需要手动申请
d heap与stack都会在初始大小空间用满时，系统自动增加其大小


A 错误在全局变量存在.data段和.bss段;


Void foo ( )
{
++a
printf("%d",a);
}


a 3_2_
b 2_3_
c 3_3_
d 2_2_


++不能认为是原子操作，a是全局变量，在内存中，则++a一般被分为从内存取a到寄存器、+、回写到内存三步。

## Linux inter process communication (IPC) facilities include?

TLDP.

• Half-duplex UNIX pipes. Pipes are the eldest of the IPC tools, they provide a method of one-way communications (hence the term half-duplex) between processes.
• FIFOs (named pipes)
• SYSV style message queues
• SYSV style semaphore sets
• SYSV style shared memory segments
• Networking sockets (Berkeley style) (not covered in this paper)
• Full-duplex pipes (STREAMS pipes) (not covered in this paper)

### Pipes

Under Linux, in particular, pipes are actually represented internally with a valid inode. Of course, this inode resides within the kernel itself, and not within the bounds of any physical file system. This particular point will open up some pretty handy I/O doors for us.

To send data to the pipe, we use the write() system call, and to retrieve data from the pipe, we use the read() system call. Remember, low-level file I/O system calls work with file descriptors! However, keep in mind that certain system calls, such as lseek(), do not work with descriptors to pipes.

## Per-, In-, Post-order tree traversal

CSDN. 已知二叉树后序遍历序列是DABEC 中序遍历列是 DEBAC ，它的前序遍历序列是：

----C
---/
--E
-/-\
D---B
-----\
------A


1. 后序遍历得C为根节点。中序得C无右子树。
2. 后序得C下一个根节点为E。
3. 中序DEBA得D为E的左子树。
4. 后序DABE得B为E的下一个根节点，只能为E的右子树了。
5. 中序BA得A为B的右子树。
6. 前序遍历序列：CEDBA。

# C/CPP

## Fibonacci naive recursion's time complexity

Why Fibonacci naive recursion's TC is $O(2^n)$?

The complexity of a naive recursive fibonacci is indeed 2ⁿ.

T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)

Solve this recurrence relation using generating functions:
T(n) =
T(n-1) + T(n-2) + 1 =
T(n-2) + T(n-3) + T(n-3) + T(n-4) + 1 + 2=
T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) +1 +2 +4=
... =

In each step you call T twice, thus will provide eventual asymptotic barrier of:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

Consequently, the tight bound for this function is the Fibonacci sequence itself (~θ(1.6n)).

bonus: The best theoretical implementation to fibonacci is actually a close formula, using the golden ratio:

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(However, it suffers from precision errors in real life due to floating point arithmetics, which are not exact.)

## Assert


void func()
{
char b[2]={0};
strcpy(b,"aaaa");
}


Debug版崩溃，Release版正常？Debug版正常，Release版崩溃？

## Const

What is the output?


#include <iostream>
using namespace std;
int main(void)
{
const int a = 10;
int * p = (int *)(&a);
*p = 20;
cout<<"a = "<<a<<", *p = "<<*p<<endl;
return 0;
}

a = 10, *p = 20


Explanation: Compiler replaces all "a" with 10 in compilation phase. And in the runtime, "p" changes the value. Thus they are different.

## Integer overflow

What is the result? Overflow?


void swap_int(int *a, int *b){
*a=*a+*b;
*b=*a-*b;
*a=*a-*b;
}


Take 32-bit system for example. Assume $a$, $b$ are both positive. If there is an overflow, $a+b=1|rem$, where '1' occupies the sign position, therefore $a$ becomes a negative. Then in $b=a-b$, the $a-b$ is guaranteed to be underflow (why? 2's-complement). Actually when "int" is "unsigned int", the previous deduction still works. See below.

Example. Let's consider "short" instead of "int". a=32767, b=32767. $a_2=b_2=111111111111111$, and $(a+b)_2 = 1111111111111110 = -2$. $-2-32767$ is surely underflow.

Advanced: what if the "short" is changed to "unsigned short"?

The answer is still "correct". Suppose $a=65534$, $b=65535$, then $a+b=65533$, when doing substraction, there is still guaranteed underflow, and a virtual '1' is borrowed beyond the highest bit. In the end $a$ and $b$ are swapped.

 1111111111111110  a
1111111111111111  b
11111111111111101  a+b
a+b truncated to 65533
65535, 65534  a,b are swapped