All notes

Linux related


int main(){
   int pid;
   int num=1;
   printf("in parent:num:%d addr:%x
   else if(pid==0){
   printf("in child:num:%d addr:%x

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




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

正确答案: B C 你的答案: A B C D (错误)

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



Void foo ( )

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


Linux inter process communication (IPC) facilities include?



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 ,它的前序遍历序列是:


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


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.)


void func()
   char b[2]={0};




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){

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