All notes
CppExam

Linux related

Fork


int main(){
   int pid;
   int num=1;
   pid=fork();
   if(pid>0){
   num++;
   printf("in parent:num:%d addr:%x
",num,&num);
   }
   else if(pid==0){
   printf("in child:num:%d addr:%x
",num,&num);
   }
}

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

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

Heap/Stack

关于操作系统heap与stack说法中,正确的是()。

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

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

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

Multi-thread

多选题:两个线程并发执行以下代码,假设a是全局变量,初始值是1,那么以下输出中()是可能的:


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.

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版崩溃?

因为在Debug中有ASSERT断言保护,所以要崩溃,而在Release优化中就会删掉ASSERT,所以会出现正常运行。

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