What's the Highlight

####

資料結構

• Linked List:
  連結串列(Linked List)是串列(List)的一種，是一種常見的資料結構，利用這個資料結構也能進一步實作出其他的資料結構，例如堆疊(Stack)和佇列(Queue)等。
  特性是能夠不使用連續的記憶體空間的情況下，能夠保有並使用一份連續的資料；相對來看，陣列則需要使用連續的記憶體空間。
• stack:
  是一種後進先出(Last-In-First-Out, LIFO)的排程，而在此資料結構中至少會實作兩個操作：
  push：將資料放入堆疊頂端 / pop：取出堆疊頂端之資料
  在實作上一般可以使用陣列或連結串列(LinkedList)兩種方式來實作
• Queue:
  佇列(Queue) 是一種先進先出(First-In-First-Out, FIFO)的排程，而在此資料結構中至少會實作兩個操作：
  enqueue：將資料放入佇列尾端。(註：C++中用push、Java用offer、也有add等不同的用字)
  dequeue：取出佇列前端之資料。(註：C++中用pop、Java用poll、也有remove等不同的用字)
  在實作上一般使用連結串列(LinkedList)來實作，使用陣列同樣可以達成，但較為複雜
• Tree:
  樹(Tree)是一種常見的資料結構，他是一種階層式(Hierarchical)的資料集合, 實作上可以用連結串列完成

####

關於變數儲存與記憶體:

變數使用:

• Local 變數
  一般區域變數均被宣告在某區段之內，事實上區域變數是用 stack 或 heap 方式 佔用記憶體空間, what's different stack and heap using in local ?
• static 變數 
  static變數的宣告方式，也是一種區域變數的宣告方式它和區域變數最大的不同在於存在 global區，static變數不會在程式執行完這個區段後，將記憶體回收。
• Global 外在變數
  外在變數是指定義於程式外部的變數存在 global區，當一個變數被定義為外在變數後，其他所有的函式或區段皆可使用此變數。

####

記憶體儲存變數分區:

變數會佔用記憶體，記憶體分為三個部份來存這些變數，分別是global、stack與heap。stack與heap在記憶體中的配置狀況可以參考這張圖(http://www.geeksforgeeks.org/archives/14268):

• global:
  用來放全域變數、靜態變數(static)等等。
• stack: (參考)
  台灣正體中文稱為堆疊，大陸叫做棧。
  Stack中常見的存放資訊如下：區域變數(local variable)、函式參數(function/method parameter)、函數的返回位址(function/method return address)等資訊。
  可預測性外加後進先出(LIFO)的生存模式，令stack無疑是最佳的存放策略。
  所以必須在編譯時期為已知。
  這些變數的回收會發生在它從堆疊pop出去的時候，因為個數、大小什麼的都是已知，所以系統知道怎麼進行配置與回收。
  stack中的資料之存活週期規律故由系統自行產生與回收其空間即可，就不勞工程師們費心啦！
• heap:
  台灣正體中文稱為堆積，大陸叫做堆。
  不可預測的因素造成上述的stack區塊不適合運用。所以當資訊為動態配置產生，系統會存放在另外一塊空間，稱之為『Heap』(注意這裡的Heap跟資料結構中的Heap不相關，可別會錯意！)。
  這裡的記憶體由使用者負責進行回收，配置則是由malloc或是new來負責。
  所以使用Heap記憶體主要是編譯時期還不知道 大小或個數的變數。
  例如說，你需要用一個陣列，這個陣列的大小要在執行的時候由使用者的輸入來決定，那你就只能使用動態配置，也就是把這個陣列配置在heap中。
  Heap中的資料如果沒有正常的回收，將會逐步成長到將記憶體消耗殆盡，下次發生上述問題的實後，切記自己檢查一下heap空間的資料有無正常回收。

stack與heap在記憶體中的配置狀況可以參考這張圖:

refer from (http://wp.mlab.tw/?p=312)

For example,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<iostream> using namespace std; int main(){     int a1,a2,a3,a4,a5;     int *b1=new int;     int *b2=new int;     int *b3=new int;     int *b4=new int;     cout << "address of a1 is " << &a1 << endl;     cout << "address of a2 is " << &a2 << endl;     cout << "address of a3 is " << &a3 << endl;     cout << "address of a4 is " << &a4 << endl;     cout << "address of a5 is " << &a5 << endl;     cout << "address of b1 is " << &b1 << endl;     cout << "  value of b1 is " << b1 << endl;     cout << "address of b2 is " << &b2 << endl;     cout << "  value of b2 is " << b2 << endl;     cout << "address of b3 is " << &b3 << endl;     cout << "  value of b3 is " << b3 << endl;     cout << "address of b4 is " << &b4 << endl;     cout << "  value of b4 is " << b4 << endl;     delete b1,b2,b3,b4; }

address of a1 is 0x7fff4e62c554
address of a2 is 0x7fff4e62c550
address of a3 is 0x7fff4e62c54c
address of a4 is 0x7fff4e62c548
address of a5 is 0x7fff4e62c544
address of b1 is 0x7fff4e62c538
value of b1 is 0x417a010
address of b2 is 0x7fff4e62c530
value of b2 is 0x417a030
address of b3 is 0x7fff4e62c528
value of b3 is 0x417a050
address of b4 is 0x7fff4e62c520
value of b4 is 0x417a070

可以發現，a1到a5的記憶體位址是由大而小，也就是由高而低。
而b1到b4的所指的位址(在heap)是由小而大，也就是由低而高，b1到b4本身的位址(在stack)則是由高而低。Hint: 指標 is 8-bytes (if OS is 64-bytes system)

####

關於 multi-thread 執行緒 在Linux/Windows

(還是看不懂, 需要再充實內容)

Linux thread

產生child process (參考)

#include
int clone(int (*fn)(void *), void *child_stack, int flags, void *arg);
clone()與fork()不同，clone()允許child process 與parent process 共用部分execution context,
— 例如: memory space, the table of file descriptors, and the table of signal handlers.
– clone()主要用途: 製作threads (例如: POSIX threads)
— When the child process is created with clone, it executes the function application fn(arg). (This differs from fork(2).)
— The fn argument is a pointer to a function that is called by the child process at the beginning of its execution.
— The arg argument is passed to the fn function.
— The child_stack argument specifies the location of the stack used by the child process.
— 不相容於其他Unix系統，clone()為Linux特有
— Linux沒有另外定義thread: Linux的threads (例如: POSIX threads)，其實是利用clone()產生的child processes。
–sleep()系統呼叫: 會使得該process睡覺，所有thread因此全部睡覺。
–若只是要讓某一thread睡覺，必須設計另一系統呼叫，例如: pthread_delay()

Linux thread特點:
— 可直接執行sleep()等系統呼叫，而不會影響其他threads
— threads其實是共用記憶體空間等資源的processes，因此可以使用kill命令，送訊號或殺掉thread

POSIX Threads (pthread)

#include
#include #include
#include
#include
int a=1;
int b=1;
pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;
#define NTIMES 20

void* do_p1(void* z)  //start function of thread1
{
   int i;
   for(i=0; i<NTIMES; i++)
   {
      pthread_mutex_lock(&mutex);
      a += 1;
      b += 1;
      printf("P1: a=%d, b=%d\n", a, b);
      fflush(stdout);
      pthread_mutex_unlock(&mutex);
      sleep(random() % 2);
   }
   return 0;
}

void* do_p2(void* z) //start function of thread2
{
int i;
for(i=0; i<NTIMES; i++)
{
pthread_mutex_lock(&mutex);
a *= 2;
b *= 2;
printf(“P2: a=%d, b=%d\n", a, b);
fflush(stdout);
pthread_mutex_unlock(&mutex);
sleep(random() % 2);
}
return 0;
}

int main()
{
pthread_t thread1, thread2;
int seed;

printf(“seed: “);
scanf(“%d", &seed);
srandom(seed);
pthread_create(&thread1, 0, &do_p1, 0);
pthread_create(&thread2, 0, &do_p2, 0);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
}

執行thread.c
>> gcc –o thread thread.c –lpthread
>> ./thread
seed: 91821

[C++ 範例代碼] 在Windows 下撰寫簡單 Thread 程式

refer from (http://puremonkey2010.blogspot.tw/2012/03/c-windows-thread.html)

基本演算法 (可以參考"數值分析")

Divide and conquer作法:

將問題先切分成小問題後再解決，再將結果合併求出原始問題的答案。
優點:
– 將困難的問題簡化為容易實作的方式，例如河內塔(Tower of Hanoii)問題。
– 提升程式效率，例如歸併排序(Merge Sort)讓排序速度提升。
– 能夠平行處理，例如MapReduce也是Divide and conquer的一種。
不適合的情況:
– Divide and conquer是利用遞迴的方式來實作，所以當不適合使用遞迴的時候也就不適合使用Divide and conquer

-> 二元搜索法(Binary Search):

又稱折半搜索，搜索演算法的一種，可使用Divide and Conquer或直接使用迴圈來實作，搜索的目標資料必須是已經排序過的(以小到大排序為例)。其概念是每次挑選中間位置的資料來比對，若該資料小於目標值，則縮小範圍為左半部，反之亦然；因此使用這個方法每次比對後都可以濾掉一半的資料，以增快搜索速度。

function search(list, target)
{
    var left = 0, right = list.length - 1
    while (left <= right) {   
        var middle = 取出list中點
        if (list[middle] == target)
            return middle;   // 比目標大，再搜索左半邊   
        else if (list[middle] > target)
            right = middle - 1; // 比目標小，再搜索右半邊
        else if (list[middle] < target)
            left = middle + 1;
        endif
    }
    return -1;
}

Divide and Conquer方法:

function search(list, target, left, right) {
    if (left > right)
        return -1;
  
    var middle = /* 取出list中點 */
    if (list[middle] == target)
        return middle;
        // 比目標大，再搜索左半邊
    else if (list[middle] > target)
        return search(list, target, left, middle - 1);
        // 比目標小，再搜索右半邊
    else if (list[middle] < target)
         return search(list, target, middle + 1, right);
    endif
    return 0;
}

####

Dynamic Programming

中文譯作動態規劃，動態規劃類似Divide and Conquer，一個問題的答案來相依於子問題，常用來解決最佳解的問題。與Divide and Conquer不同的地方在於，動態規劃多使用了memorization的機制，將處理過的子問題答案記錄下來，避免重複計算，因此在子問題重疊的時候應該使用動態規劃；Divide and Conquer通常使用遞迴(Top-Down)來處理，轉成迭代法(Bottom-up)來解並不容易，故使用動態規劃則可以解決重覆計算並保留遞迴思考的優點。

-> 費波那西數列(Fibonacci)

費波那西數列(Fibonacci)，又稱費氏數列、黃金分割數列等很多譯名，由西方的數學家費波那西使用兔子問題來描述這個數列
使用數學式來表達的話如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

使用Divide and Conquer的寫法如下： O(2^n)
每次都必須recursive計算出數值

function Fibonacci(n)
 if (n == 0)
  return 0;
 if (n == 1)
  return 1;
 return Fibonacci(n - 1) + Fibonacci(n - 2);

動態規劃寫法
如下： O(n)
透過array方式將計算過的數值儲存起來, 避免重複計算!

var map // cache of fibonacci
function Fibonacci(n)
 var value = map[n]
 if (value == null) {
  if (n == 0)
   value = 0;
  else if (n == 1)
   value = 1;
  else value = Fibonacci(n - 1) + Fibonacci(n - 2);
  map[n] = value; 
 }
return value;

最大子序列(Maximum Subarray)

(不了解目的是什麼?)

最大子序列(Maximum Subarray或稱作Maximum Subsequence)為在一個具有正負數陣列當中，找出一段連續的元素總和最大，這個問題又分為一定要取值或可不取。實作方法有很多種，這裡說明四種實作方法，分別為暴力法、改良式暴力法、Divide and Conquer和Kadane’s演算法(Dynamic Programming)，其中Kadane’s實作取值和可不取值兩種版本，其他為一定要取值版本。 refer from (http://emn178.pixnet.net/blog/post/88907691)

暴力法 O(n^3)
最簡單直覺的想就是將所有可能的開始和結束範圍都算過一遍即可，[0] ~ [0]、[0] ~ [1] … [0] ~ [N] … [N] ~ [N]的總和找出最大。

改良式暴力法 O(n^2)
然而在上面暴力法計算，[0] ~ [N]的總和時，其實過程中[0] ~ [0]、[0] ~ [1] … [0] ~ [N]的總和也已經同時計算了，所以只需計算[0] ~ [N]、[1] ~ [N] … [N] ~ [N]即可。

Divide and Conquer O(nlog n)
如下圖所示，Divide and Conquer的基本概念是，將數列分成兩塊，各自回報最大的值，如藍色部分；然而這是最大子序列不只會出現在左邊或右邊，也有可能出現橫跨兩邊的紅色區域，所以還要再找出紅色區域的最大值。由於紅色區域表示的是橫跨兩邊，所以只要考慮包含中點的情況，如圖紅色元素與綠色區域，最後最大子序列的值即為紅色區域或藍色區域的最大值。

Kadane’s演算法 O(n)
Kadane’s演算法為Dynamic Programming(動態規劃)方式，概念上其實是很直覺的思考，如下圖所示，當計算前四個元素的時候，前面總和是1、3和6，很明顯列入計算是有幫助的，故我們會納入計算，但是到了第五個元素的時候，前面總和變成-1，若列入計算會拉低分數，故我們不列入計算；由以上簡單的範例可知，當連續總和是正的時候，可以繼續列入計算，當為負的時候，則不列入計算，也就是重新重0開始。不過也因為這樣的演算法特性，原始版本無法是一定要取值的版本，必須做額外的處理。

####

直接列出考古題

1. 物件導向的三大特性

封裝
將程式碼包裝成為Class以提供特定功能的一種過程。好處：程式碼共用。
繼承
Class可透過Inheritance(繼承)來擴充(或修改)內容。
多型
在執行階段，定義可供用戶端程式碼交換使用，具有不同功能但名稱完全相同之方法或屬性的Class。

2.Overload 和 Override 的區別。Overloaded的方法是否可以改變返回值的類型?

(不懂)

Overload 發生在同一類別裡，Override發生在繼承關係間。 
Overload 為靜態連結，Override為動態連結。 
可改變返回值的型態，前提是參數也要變，參數相同傳回值不同是不被允許的。 

3.write your own strcmp

如果字串比較結果一樣，便會傳回 0
若字串不同則：
字串1 > 字串2的話，會傳回大於 0 的值 1
字串1 < 字串2的話，會傳回小於 0 的值 -1
int ownstrcmp(char a[], char b[])
{
   int i = 0;
   while( a[i] == b[i] )  
   {
      if( a[i] == '\0' ) 
        return 0;
      ++i;
   }
   return  ( a[i] < b[i]) ? -1 : 1;
}

4. what is different between mutex and semaphore?

Mutex是一把鑰匙，一個人拿了就可進入一個房間，
出來的時候把鑰匙交給隊列的第一個。
一般的用法是用於串行化對critical section代碼的訪問，
保證這段代碼不會被並行的運行。 
(A mutex is really a semaphore with value 1.)

Semaphore是一件可以容納N人的房間，如果人不滿就可以進去，
如果人滿了，就要等待有人出來。
對於N=1的情況，稱為binary semaphore。
一般的用法是，用於限制對於某一資源的同時訪問。

5. Compare array and list

std::array is just a class version of the classic C array. 
That means its size is fixed at compile time 
and it will be allocated as a single chunk 
(e.g. taking space on the stack). 
The advantage it has is slightly better performance 
because there is no indirection between the object 
and the arrayed data.

std::vector is a small class containing pointers into 
the heap.
(So when you allocate astd::vector, it always calls new.)
They are slightly slower to access 
because those pointers have to be chased 
to get to the arrayed data...
But in exchange for that, they can be resized 
and they only take a trivial amount of stack space 
no matter how large they are.

6.Compare stack and queue (怎麼用link list 呈現?)

佇列(Queue)是用先進先出的方式處理物件的集合，
例如到銀行排隊，先排的人先處理；
而堆疊(Stack )是後進先出的集合，
例如玩撲克牌排遊戲時，發牌時是從整疊的最上一張拿取。

7.write a function that can calculate 1*2+2*3+…..+(n-1)*n

int nc(int n)
{
    int sum = 0;
    for(int i = 2; i <= n; i++){
        sum = sum + i*(i-1);
    }
    return sum;
}

類似的, 改成乘法 (遞回)
寫一個 function 可傳入正整數參數 N，回傳 1 + 2 + 3 + … + N 的和

int Fab (int n) {
   if (n <= 0)
      printf("N should larger than 0 ! \n");
   else if( n == 1)
      return 1;
   else
      return n + Fab(n-1);
}

8. Explain Static and volatile

Static:
(1) 修飾檔案中的global variable：
使這個變數只有在本檔案中才可以被使用，
相同專案中的其他檔案看不到它的存在。 
(補：放在function前也有一樣的作用。)

(2) 修飾function中的local variable：
此變數一旦經過初始化就會一直存在直到程式結束，
跳出function時它也會保持當下的值，
(ex. 可用來計算同一個function被呼叫的次數。) 
只會被初始化一次，並且只有進入function中才看得到這個變數 !!

(3) 修飾class中的member variable和 function：
variable：會使同一個class的所有實體共用同一個member variable，
或者說這個member variable在同一個class的所有實體擁有相同的值。 
一樣只會初始化一次，甚至不需要實體就可呼叫。
function：static member function不屬於任何一個實體，
也是不需要實體就可呼叫，但它只能操作static member variables而已。

他們都透過 :: 運算子來呼叫，表示屬於某一個class但不屬於任何實體。 
ex. A::x
也可以透過實體用 . 運算子呼叫，但觀念上比較不好！

Volatile:
被volatile修飾的變數代表它的值有可能因為編譯器不知道的因素修改，
所以告訴編譯器不要對它涉及的地方做最佳化，
並在每次操作它的時候都去讀取該變數實體位址上最新的值，
而不是讀取CPU暫存器上的值，
一般的變數可能因為剛剛讀取過而放在CPU暫存器上使動作變快。

例子：
(1) 硬體暫存器，如狀態暫存器。
(2) 多執行緒所共用的全域變數。
(3) 中斷服務函式 (Interrupt Service Rountie，ISR)所使用的全域變數。
 
Volatile陷阱, 想想底下範例是否有問題?  
(http://adrianhuang.blogspot.tw/2011/08/cvolatile.html)
假設有個函數
int square(volatile int *ptr) {
   return *ptr * *ptr;
}

則編譯器可能會把它解讀成下列code
int square(volatile int *ptr) {
   int a,b;
   a = *ptr;
   b = *ptr;
   return a * b;
}

實際上產生的可能不是平方值，所以改成下列方式才不會出錯
int square(volatile int *ptr) {
   int a;
   a = *ptr;
   return a * a;
}

C/C++中的volatile使用時機?
. 不知各位對volatile(揮發性的)這個字陌不陌生? 
  我相信大家在一些程式或多或少都看過這個字眼, 
  但是究竟要在何種場合用它呢?
. 當然一定是有需要, C/C++才會有這個保留字, 
  否則只是增加programmer的困擾而已
. 有2兩個場合(I/O & multithread program), 
  供各位參考!
. 請大家check自己的程式中(尤其是第2個場合), 
  若有的話請記得加上volatile

1. I/O, 假設有一程式片斷如下

U8 *pPort;
U8 i, j, k;

pPort = (U8 *)0x800000;

i = *pPort; 
j = *pPort; 
k = *pPort; 

以上的i, j, k很有可能被compiler最佳化而導致產生
i = j = k = *pPort;  
的code, 也就是說只從pPort讀取一次, 而產生 i = j = k 的結果, 
但是原本的程式的目的是要從同一個I/O port讀取3次的值給不同的變數
i, j, k的值很可能不同(例如從此 I/O port 讀取溫度), 
因此i = j = k的結果不是我們所要的, 那怎麼辦? 
=> 用volatile, 將
U8 *pPort;
改為
volatile U8 *pPort;

告訴compiler, pPort變數具有揮發性的特性, 
所以與它有關的程式碼請不要作最佳化動作. 因而 
i = *pPort; 
j = *pPort; 
k = *pPort; 
此三列程式所產生的code, 會真正地從pPort讀取三次, 從而產生正確的結果

2. Global variables in Multithread program 
=> 這是在撰寫multithread program時最容易被忽略的一部份
=> 此原因所造成的bug通常相當難解決(因為不穩定)

假設有以下程式片斷, thread 1 & thread 2 共用一個global var: gData 

thread 1: thread 2: 

... .... 
int gData; 
extern int gData; 

while (1) 
int i, j, k; 
{ 
    .... 
    for (i = 0; i < 1000; i++)
        gData = rand(); 
    { 
        ..... 
        /* A */
    } 
    j = gData; 
    .... 
    .... 
} 

在thread 2的for loop中, 聰明的compiler看到gData的值, 
每次都重新從memory load 到register, 
實在沒效率, 因此會產生如下的code
(注意,tmp也可以更進一步的用register取代):
 
tmp = gData;
for (i = 0; i < 1000; i++)  
{     /* A */    j = tmp;    ....  }    
也就是gData只讀取一次, 這下子問題來了, 
說明如下:thread 2在執行for loop到
j = gData 的前一列(A)的時候(假設此時gData=tmp=5), 
被切換到thread 1執行. 在thread 1的while loop
中透過gData = rand(), 對gData做了修改(假設改為1), 
再切換回thread 2執行. 繼續執行 j = gData, 產生j = 5的結果. 
但是正確的結果應該是 j = 1 怎麼辦 => 也是用volatile,

在thread 1中, 將
int gData; 
改為
volatile int gData; 

在thread 2中, 將
extern int gData; 
改為
extern volatile int gData; 
 

類似有:
Q: C語言的volatile的含義是什麼。使用時會對編譯器有什麼暗示。
A:
那麼這道題非常重要！！嵌入式系統程式師經常同硬體、中斷、RTOS等等打交道，所用這些都要求volatile變數。
從詞面上講，volatile的意思是易變的，也就是說，在程式運行過程中，有一些變數可能會被莫名其妙的改變，而優化器為了節約時間，有時候不會重讀這個變數的真實值，而是去讀在寄存器的備份，這樣的話，這個變數的真實值反而被優化器給“優 化”掉了，用時髦的詞說就是被“和諧”了。

如果使用了這個修飾詞，就是通知編譯器別犯懶，老老實實去重新讀一遍！可能我說的太“通俗”了，那麼我引用一下 “大師”的標準解釋：
volatile的本意是“易變的” 。
由於訪問寄存器的速度要快過RAM,所以編譯器一般都會作減少存取外部RAM的優化，但有可能會讀髒資料。當要求使用volatile 聲明的變數的值的時候，系統總是重新從它所在的記憶體讀取資料，即使它前面的指令剛剛從該處讀取過資料。而且讀取的資料立刻被保存。

精確地說就是，優化器在用到這個變數時必須每次都小心地重新讀取這個變數的值，而不是使用保存在寄存器裏的備份。
下面是volatile變數的幾個例子：
1). 並行設備的硬體寄存器（如：狀態寄存器）
2). 一個中斷服務副程式中會訪問到的非自動變數(Non-automatic variables)
3). 多執行緒(Thread)應用中被幾個任務共用的變數

9. Explain process and thread

Program：
放在二次儲存裝置中，尚沒有被Load到記憶體的一堆Code稱之為「程式」。
(也就是還是死的)

Process：
已經被Load到記憶體中，任何一行Code隨時會被CPU執行，
且其宣告的在記憶體的變數的值會隨著需求而不斷變動。
稱之為「程序」。(也就是活的Program) => 恐龍本第三章
一個多工作業系統(Multitasking Operating System)
可以同時運行多個Process, 然而一個CPU一次只能做一件事情，
但CPU的數量永遠少於運行中的Process數，
因此每個Process使用的時間需要被排程(Scheduling) => 恐龍本第五章
又每個Process間在記憶體中，如果擺放的方式不當，
就會在記憶體中產生很多沒辦法用到的碎片，
因此MemoryManagement是一個問題 => 恐龍本第八章
另外，每個Process所需要的記憶體總合，
也可能大於實體記憶體，
因此需要另外用二次儲存裝置充當虛擬記憶體(Virtual Memory)，
但是二次儲存裝置的速度肯定很慢，因此如何做到對虛擬記憶體最小的依賴，
盡量避免Page Fault(電腦在主記憶體中找不到資料，而要去二次記憶體找，
就稱為Page Fault),
防止Thrashing的發生(因為Virtual Memory演算法不當，
造成幾乎每次存取都要依賴二次記憶體，就是Thrashing)，
以達到效能最佳化，也是個學問 => 第九章

Thread ：
在同一個Process底下，有許多自己的分身，就是Thread，中文又翻成執行緒。
以往一個Process一次只能做一件事情，因此要一面輸入文字，一面計算字數，
這種事情是不可能的。但是有了Thread之後，可以在同一個Process底下，
讓輸入文字是一個Thread，計算文字又是另外一個Thread，
對CPU來說兩個都是類似一個Process，因此兩個可以同時做。
又一個Process底下有數個Thread，
而一個Process的Global Variable可以讓它的所有Thread共享，
也就是所有Thread都可以存取同一個Process的Global Variable。
而每個Thread自己也有自己的專屬Variable。 => 恐龍本第四章
但是，如果有兩個Thread要存取同一個Global Variable，有可能發生問題，
也就是說可能會存取到錯的值(例如兩個Thread同時要對一個Variable做加減，
最後那個答案可能會是錯的)，這就是Synchronization問題 =>恐龍本第六章
又，每一個Thread之間可能會互搶資源，而造成死結(Deadlock)，
只要以下四個條件都滿足就有死結。
(1)這個資源不能同時給兩個人用 
(2)有一個人拿了一個資源，又想拿別人的資源 
(3)如果一個人占了茅坑不拉屎，占用資源很久，仍不能趕他走 
(4)A等B，B等C，C等D，D又等A 等成一圈。 
要解決這種狀況有 Avoid(預防) 或 避免(Prevent)兩種方式，
破除以上四種其中一種即可。=> 恐龍本第七章

10. 以下程式碼印出來為何?

printf(“size of BYTE = %d\n \
size of float = %d\n \
size of unsigned int = %d\n \
size of int = %d\n \
size of double = %d\n \
size of unsigned char = %d\n \
size of char = %d\n"
,sizeof(BYTE)
,sizeof(float)
,sizeof(unsigned int)
,sizeof(int)
,sizeof(double)
,sizeof(unsigned char)
,sizeof(char));

size of BYTE = 1
size of float = 4
size of unsigned int = 4
size of int = 4
size of double = 8
size of unsigned char = 1
size of char = 1

補充: C語言所定義的資料型別如下

型別	符號位元	位元長度	表示方法	數值範圍
整數	有	16或32	int	-2147483648 ~ 2147483647
		8	char	-128 ~ 127
		16	short	-32768 ~ 32767
		32	long	-2147483648 ~ 2147483647
		64	long long
	無	16或32	unsigned int	0 ~ 4294967295
		8	unsigned char	0 ~ 256
		16	unsigned short	0 ~ 65535
		32	unsigned long	0 ~ 4294967295
		64	unsigned long long
浮點數	有	32	float	10^-38~10^38
		64	double	10^-308~10^308
字元	有	8	char	-128 ~ 127

11.請試著寫出下面代碼的輸出:

view plaincopy to clipboardprint?
#include
#include

int main()
{
char strAry[] = “This is string";
char *aryPtr = strAry;
int *intPtr = (int*)strAry;

printf(“\t[Line01] strAry=%s\n", strAry);
printf(“\t[Line02] aryPtr=%s\n", aryPtr);
//printf(“\t[LineX] *aryPtr=%s\n", *aryPtr); // Segment fault
printf(“\t[Line03] sizeof(aryPtr)=%d\n", sizeof(aryPtr));
printf(“\t[Line04] sizeof(*aryPtr)=%d\n", sizeof(*aryPtr));
printf(“\t[Line05] *aryPtr=’%c’\n", *aryPtr);
printf(“\t[Line06] *aryPtr+1=’%c’\n", *aryPtr+1);
printf(“\t[Line07] *(aryPtr+1)=’%c’\n", *(aryPtr+1));
printf(“\t[Line08] sizeof(intPtr)=%d\n", sizeof(intPtr));
printf(“\t[Line09] sizeof(*intPtr)=%d\n", sizeof(*intPtr));
printf(“\t[Line10] intPtr=%s\n", intPtr);
//printf(“\t[LineX] *intPtr=%s\n", *intPtr); // Segment fault
printf(“\t[Line11] *intPtr=’%c’\n", *intPtr);
printf(“\t[Line12] *intPtr+1=’%c’\n", *intPtr+1);
printf(“\t[Line13] *(intPtr+1)=’%c’\n", *(intPtr+1));
return 0;
}

Sol:

[Line01] strAry=This is string  
### 字串陣列 char[] ="..." 會自動加上 NULL 到結尾.

[Line02] aryPtr=This is string  
### 同上, 只是把 aryPtr 指標指向 strAry 的位置. 
strAry 本身也是個指標.

[Line03] sizeof(aryPtr)=4       
### 指標的大小根據系統是 32bit (4byte) 
或是 64bit(8bypte) 有所不同.

[Line04] sizeof(*aryPtr)=1      
### char 的大小為 1 byte.

[Line05] *aryPtr='T'            
### 指向字串中第一個字元 'T'

[Line06] *aryPtr+1='U'          
### char 'T' + 1=char 'U'. 
-> ASCII 'T'=84. 84+1=85=ASCII 'U'.

[Line07] *(aryPtr+1)='h'        
### 將 aryPtr 指標移動一個 char 的位置 (1 個 byte 的距離), 
即是字串的第二個字元 'h'.

[Line08] sizeof(intPtr)=4       
### 同 Line03

[Line09] sizeof(*intPtr)=4      
### int 類型的大小為 4 byte.

[Line10] intPtr=This is string  
### 雖然用 int* 指定 pointer 類型, 但是在 printf 使用 '%s', 
故還是打印出字串出來.

[Line11] *intPtr='T'            
### 指向字串中第一個字元 'T'.

[Line12] *intPtr+1='U'          
### 同 Line6

[Line13] *(intPtr+1)=' '        
### 因為 指標類型為 int, 故移動一個位置為 4 byte, 
所以指向第 0+4 =4 位置上的字元, 即字串的第五個字元 (從 0 開始).

同樣類型題目, 程式碼輸出為何?
int a[5] ={1,2,3,4,5};
int *p = (int *)(&a+1);
ask: the value of *(a+1), (*p-1)?

*(a+1) : 2
(*p-1) : ????????? (undefined behavior)

這題要考你 a+1 和 &a+1 的區別,
第一種的+1一次是跳一個int的大小(i.e., 4bytes in 32-bits cpu)
第二種的+1一次是跳一整個array的大小 (i.e., 4*5=20 bytes)

更清楚的說明在這 可以看到: a 和 &a 的type不同, 而當要 +1 時，要加的是 type的大小
所以*(a+1)是2，(*p-1)是garbage (unknown value)

同樣類型題目, 請用變數 a 給出下面的定義: (nice)
a)一個整型數 (An integer)
b)一個指向整數的指標 (A pointer to an integer)
c)一個指向指標的指標，它指向的指標是指向一個整型數 (A pointer to a pointer to an integer)
d)一個有10個整數型的陣列 (An array of 10 integers)
e)一個有10個指標的陣列，該指標是指向一個整數型的 (An array of 10 pointers to integers)
f)一個指向有10個整數型陣列的指標 (A pointer to an array of 10 integers)
g)一個指向函數的指標，該函數有一個整數型參數並返回一個整數 (A pointer to a function that takes an integer as an argument and returns an integer)
h)一個有10個指標的陣列，該指標指向一個函數，該函數有一個整數型參數並返回一個整數 (An array of ten pointers to functions that take an integer argument and return an integer)

答案是︰
a) int a;             // An integer
b) int *a;            // A pointer to an integer
c) int **a;           // A pointer to a pointer to an integer
d) int a[10];         // An array of 10 integers
e) int *a[10];        // An array of 10 pointers to integers
f) int (*a)[10];      // A pointer to an array of 10 integers
g) int (*a)(int);     // A pointer to a function a that takes an integer argument and returns an integer
h) int (*a[10])(int); // An array of 10 pointers to functions that take an integer argument and return an integer

12. Write a function which can return the bit content form

嵌入式系統總是要用戶對變量或暫存器進行位操作。
給定一個整型變量a，寫兩段程式碼，
第一個設置a 的bit 3，
第二個清除a 的bit 3。在以上兩個操作中，要保持其它位不變。

#define BIT3 (0x1 << 3)
static int a;

void set_bit3(void) 
{
    a |= BIT3;
}

void clear_bit3(void) 
{
    a &= ~BIT3;
}

void get_bit3(void)
{
   int mask = 1 << 3;    
   int masked_n = a & mask;    
   int a = masked_n >>3;
}

若是題目要求寫成#define, 則方式如下:

#define SET_BIT(x, n) ( (x) |= (1<< (n)) )
#define CLR_BIT(x, n) ( (x) &= (~(1<< (n))))
#define CHK_BIT(x, n) ( ((x) & (1<< (n)))!=0 )  ==> 檢查是否為 1
#define FLIP_BIT(x, n) ( (x) ^= (1<< (n)) )     ==> 指的是原先某個位元，從1變成0，從0變成1

類似的還有,(不懂)
存取固定的記憶體位置 (Accessing fixed memory locations) 嵌入式系統經常具有要求程式員去存取某特定的記憶體位置的特點。
在某工程中，要求設定一個絕對位址為 0x67a9 的整數型變數的值 為0xaa55。
編譯器是一個純粹的ANSI編譯器。寫程式碼去完成這一任務。這一問題測試你是否知道為了存取一絕對位址把一個整數型強製轉型 (typecast) 為一指標是合法的。
典型的類似程式碼如下︰

int *ptr;

ptr = (int *)0x67a9;
*ptr = 0xaa55;

一個較艱澀的方法是︰
*(int * const)(0x67a9) = 0xaa55;
即使你的品味更接近第二種方案，但我建議你在面試時使用第一種方案。

13. Explain Const

C 語言中const用來定義常量。

const定義的變量在定義時要初始化，否則將會是一個隨機值，而且在定義後其值不能被改變。

const在指標(pointer)使用中可以表明指標指到data是const or 指標本身是const or 兩者都是:

1. int *a ;                             /* non-const pointer, non-const data */
2. const int a;                  /* const data，a是一個常整型數*/
3. int const a;                  /* const data ，a是一個常整型數*/
4. const int *a;                 /* non-const pointer, const data ,  a 是一個指向常整型數的指針（也就是，整型數是不可修改的，但指針可以） */
5. int * const a;                /* const pointer, non-const data, a 是一個指向整型數的常指針（也就是說，指針指向的整型數是可以修改的，但指針是不可修改的） */
6. int const * a const;    /* const pointer, const data, a 是一個指向常整型數的常指針（也就是說，指針指向的整型數是不可修改的，同時指針也是不可修改的） */???
7. const int * const a ;    /* const pointer, const data, a 是一個指向常整型數的常指針（也就是說，指針指向的整型數是不可修改的，同時指針也是不可修改的） */

相同類型:
Q: C語言的const的含義是什麼。在定義常量時，為什麼推薦使用const，而不是#define。
A:
const修飾詞可以將一個變數修飾為“唯讀”，這個就能稱 為常量麼？姑且認為可以。
回到題目中，const是唯讀的意思，它限定一個變數不允許被改變，誰都不能改！
既然是修飾變數，那麼變數的類型就可以豐富多彩，int 啊，char啊，只要C認識的都可以；
但是#define就不可以了，在預處理階段缺乏類型檢測機制，有可能會出錯。
還有就是變數可以 extern，但是#define就不可以。

14. 下面的代碼輸出是什麽，為什麽？

void foo(void)
{
    unsigned int a = 6;
    int b = -20;
    (a+b > 6) ? puts(“> 6″) : puts(“<= 6″);
}

這無符號整型問題的答案是輸出是 "> 6"。

原因是當表達式中存在有符號類型和無符號類型時, 
所有的操作數都自動轉換為無符號類型。
因此-20變成了一個非常大的正整數，所以該表達式計算出的結果大於6。

另一個奇怪確合法的語法
C語言允許一些令人震驚的結構，下面的結構是合法的嗎，如果是，它做些什麼 ?

int a = 5, b = 7, c;
c = a+++b;

不管你相不相信，上面的例子是完全合法的。
問題是編譯器如何處理它 ? 根據最處理原則，
編譯器應當能處理儘可能所有合法的用法。
因此，上面的程式碼被處理成︰
c = a++ + b;

因此，這段程式碼持行後
a = 6, b = 7, c = 12

15.String 跟 StringBuffer差別。

String 類型和StringBuffer的主要性能區別：
String是不可變的對象, 因此在每次對 String 類型進行改變的時候，
都會生成一個新的 String 對象，然後將指針指向新的 String 對象，
所以經常改變內容的字符串最好不要用 String ，
因?每次生成對象都會對系統性能產生影響，
特別當內存中無引用對象多了以後， JVM 的 GC 就會開始工作，性能就會降低。

使用 StringBuffer 類時，每次都會對 StringBuffer 對象本身進行操作，
而不是生成新的對象並改變對象引用。
所以多數情況下推薦使用 StringBuffer ，
特別是字符串對象經常改變的情況下。
在某些特別情況下， 
String 對象的字符串拼接其實是被 JVM 解釋成了
StringBuffer 對象的拼接，
所以這些時候 String 對象的速度並不會比 StringBuffer 對象慢，例如：
String S1 = “This is only a” + “ simple” + “ test”;
StringBuffer Sb = 
new StringBuilder(“This is only a”).append(“ simple”)
.append(“ test”);

生成 String S1 對象的速度並不比 StringBuffer慢。
其實在 JVM 裏，自動做了如下轉換：
String S1 = “This is only a” + “ simple” + “test”; 
JVM直接把上述語句當作：
String S1 = “This is only a simple test”;
所以速度很快。但要注意的是，
如果拼接的字符串來自另外的String對象的話，
JVM就不會自動轉換了，速度也就沒那麼快了，例如：

String S2 = “This is only a”;
String S3 = “ simple”;
String S4 = “ test”;
String S1 = S2 +S3 + S4;

這時候，JVM 會規規矩矩的按照原來的方式去做。
在大部分情況下，StringBuffer > String。

16. 解釋並舉例多型、封裝、繼承。

多型: 名稱同樣的參數可以因為類別不同而有不同功能
封裝: 將程式碼包裝，以便重複利用，程式碼共用
繼承: 透過繼承來擴充內容

17. 作業系統名詞解釋

Context switch:
A context switch (also sometimes referred to as 
a process switch or a task switch) is 
the switching of the CPU  
from one process or thread to another.

中斷（Interrupt）：
屬於非同步發生的事件（event），
在任何時間都可能發生且與處理器（processer）在執行的東西毫無關連，
通常它由輸出入裝置（I/O devices），
處理計時器，或時序（timers）產生

陷阱（EXception or Trap）：
屬於同步狀態，通常由執行某一特別的指令。
陷阱（Trap或exception）可以藉由執行相同資料及狀態下的程式而重複產生。
其例有無效記憶體存取或除以零。

輪詢（polling）：
中斷發生時，CPU做輪詢的動作，去查詢所有I/O裝置看誰需要服務。

interrupt發生後，OS的處理程序
(在monitor area內會存放interrupt vector及各種ISR):
-- Step：
--1 暫停目前process的執行，並保存當時執行狀況
--2 根據interrupt ID查詢interrupt vector，
    取出對應的Interrupt Service Routine(ISR)起始位址
--3 Jump to ISR的initial address，執行該ISR
--4 ISR complete
--5 OS恢復原先中斷前的process執行

Interrupt的種類：
--1. External interrupt(HW) : CPU以外的周邊元件所發出的, 
     eg. I/O complete、I/O error、machine check
--2. Internal interrupt(HW) : CPU本身所引發的, 
     eg. stack overflow、illegal command(非法指令執行)、
         divided by zero(除以0)...
--3. Software interrupt : 當user program執行時，
     若需要OS提供服務，
     則發出此類中斷通知OS執行對應的service routine, 
     eg. system call、trap

Interrupt與Trap之比較:
Interrupt：Hardware generated interrupt, 
eg. I/O device發出"I/O complete"中斷
Trap：Software generated interrupt 
用途：user program需要OS提供Service時發出, 
Catch up arithematic error, eg. Divide-by-Zero

 
DMA（Direct Memory Access）:
高速地將 I/O 資料傳送到記憶體，而不被CPU干涉。
-- Used for high-speed I/O devices 
   able to transmit information at close to memory speeds.
-- Device controller transfers blocks of data 
   from buffer storage directly to main memory 
   without CPU intervention.
-- Only on interrupt is generated per block 
   rather than the one interrupt per byte.


Call Back Function :
簡單的說，如果你使用了某個function，
那麼你就是『call』了一個function。
如果系統或是函式是要求你給一個function pointer，
這個function pointer指到一個實際的函式
(多半這個函式是你自己寫的)。
然後它會在適當的時間呼叫此function，
則此function就是所謂的 callback function。
因為這個function是被『callback』了。

18. 請說明 C/C++ 字串格式化內容與指標使用:

scanf ( " %d,%f" ,&a ,&b)
=====================================================
%c   字元          輸入一字元到指定位址
%s   字串指標      輸入一字串到指定位址內
%d   整數          輸入一整數值到指定變數位址內
%i   整數          輸入十進位,八進位,十六進位整數值到指定變數位址內
%o   整數          輸入八進位值到指定變數位址內
%u   整數          輸入一無正負號十進位整數到指定變數位址
%x   整數          輸入十六進位值到指定變數位址內
%e   浮點數        輸入一浮點數到指定變數位址內,可用指示
%f   浮點數        輸入一浮點數到指定變數位址內
=====================================================

指標:
& : 用來取得變數位址
* :用來取得指表所指變數的內含值及定義指標
int  a, *p;
p = &a;

19. 預處理器 (Preprocessor)

用預處理指令#define 聲明一個常數，用以表示1年中有多少秒 (忽略閏年問題):

#define SECONDS_PER_YEAR (60 * 60 * 24 * 365)UL
- 懂得預處理器將為你計算常數表達式的值，
因此，直接寫出你是如何計算一年中有多少秒會比直接計算出實際的值更清晰。
- 意識到這個表達式將使一個16位元的機器產生整數型溢位 
- 因此要用到長整型符號L，告訴編譯器這個常數是的長整型數。
- 如果你在你的表達式中用到UL (表示無符號長整型)，
  那麼你有了一個好的起點。記住，第一印象很重要。

寫一個“標準”巨集MIN ，這個巨集輸入兩個參數並返回較小的一個:

#define MIN(A，B)  ( (A)  <= (B) ? (A) : (B))

這個測試是為下面的目的而設的︰
∙ 標識#define在巨集中應用的基本知識。這是很重要的，
因為在行內(inline)運算子變為標準C的一部分之前，
巨集是方便產生行內程式碼的唯一方法，
對於嵌入式系統來說，為了能達到要求的性能，行內程式碼經常是必須的方法。
∙ 三元運算子的知識。
這個運算子存在C語言中的原因是它使得編譯器能產生比
if-then-else更優化的程式碼，了解這個用法是很重要的。
∙ 懂得在巨集中小心地把參數用括號括起來

預處理器許多標識的意義?

__FILE__ ：此標誌會在预编译时会替换成当前的源文件名
__LINE__ ：此標誌會在预编译时会替换成当前的行号
__FUNCTION__：此標誌會在预编译时会替换成当前的函数名称
defined() : 檢查某的巨集定義是否被定義了，通常與 #if 合用，
像是 #if defined(OS) …
#error    : 在編譯時，輸出錯誤訊息，警告使用者某些錯誤，
並且不會真的進行編譯，在巨集處理階段就會停止。 
            就是在編譯前程式設計師就預測在某種情況下會發生錯誤, 
所以compiler看到它就會停掉啦, 舉例如下: (參考)
            #if defined(BUILD_TYPE_NORMAL)
            # define DEBUG(x) do {;} while (0) 
/* paranoid-style null code */
            #elif defined(BUILD_TYPE_DEBUG)
            # define DEBUG(x) _debug_trace x 
/* e.g. DEBUG((_debug_trace args)) */
            #else
            # error "Please specify build type in the Makefile"
            #endif
            當預處理打#error指令，
它會報告字符串作為錯誤信息，並停止編譯;
究竟該錯誤信息是這樣依賴於編譯器。

#warning  : 在編譯時，輸出警告訊息，
警告使用者某些注意事項，但是不會中止編譯，
仍然會繼續編譯出目的檔。
ex: #warning "Do not use ABC, which is deprecated.
Use XYZ instead."
#pragma   : 用來告知編譯器某些特殊指示，
例如不要輸出錯誤訊息，抑制警告訊息，或者加上記憶體漏洞檢查機制等。

預處理器標識#error的目的是什麼 ?

如果你不知道答案，請看參考文獻1。
這問題對區分一個正常的伙計和一個書呆子是很有用的。
只有書呆子才會讀C語言課本的附錄去找出象這種問題的答案。
當然如果你不是在找一個書呆子，那麼應試者最好希望自己不要知道答案。

想要預處理器處理成字符串, 怎麼做?

1. 固定參數, 可以使用#號 ：
#define MONCK(ARGTERM) 
printf("The term " #ARGTERM " is a string/n")
若使用 MONCK(A to B); 
則输出：The term A to B is a string

2. 可變參數, 用三個點（...）來表示，且配合用__VA_ARGS__來展開：
#define err(...) fprintf(stderr,__VA_ARGS__)
若使用 err("%s %d/n","The error code: ",48);
=> 就是 fprintf(stderr,"%s %d/n","The error code ",48);
或是另一種與法如:
#define ABC(format, arg…)   printf(format, ##arg);

20. 找出程式錯誤:

(1) 一個中斷服務次程序(ISR)的程式碼
中斷是嵌入式系統中重要的組成部分，這導致了很多編譯開發商提供一種擴展 –
讓標準C支持中斷。具代表的事實是，產生了一個新的關鍵字 __interrupt。
下面的程式碼就使用了__interrupt關鍵字去定義了一個中斷服務次程序(ISR)，
請評論一下這段程式碼的。

__interrupt double compute_area(double radius)
{
    double area = PI * radius * radius;
    printf(“\nArea = %f"， area);
    return area;
}

這個函數有太多的錯誤了︰
∙ ISR 不能返回一個值。如果你不懂這個，那麼你不會被雇用的。
∙ ISR 不能傳遞參數。如果你沒有看到這一點，你被雇用的機會等同第一項。
∙ 在許多的處理器/編譯器中，浮點一般都是不可重入的。
有些處理器/編譯器需要讓多餘的暫存器入棧(PUSH入堆疊)，
有些處理器/編譯器就是不允許在ISR中做浮點運算。
此外，ISR應該是短而有效率的，在ISR中做浮點運算是不明智的。
∙ 與第三點一脈相承，printf()經常有重入和性能上的問題。

(什麼叫做重入?reentrant?)
如果你丟掉了第三和第四點，我不會太為難你的。
但如果你能得到後兩點，那麼你的被雇用前景越來越光明了。

(2) 程式碼片斷
unsigned int zero = 0;
unsigned int compzero = 0xFFFF;
/*1’s complement of zero */

對于一個int型不是16位的處理器為說，上面的程式碼是不正確的。
應編寫如下︰
unsigned int compzero = ~0;

21. 如何在C中初始化一個字元陣列。

最簡單的方法是
char array[];
但是在初始化上好像還欠缺點什麼，以下：
char array[5]={‘1′,’2′,’3′,’4′,’5’};
或者
char array[5]={“12345″};
或者
char array[2][10]={“China","Beijing"};
也許更符合“初始化”的意思。

22. 如何在 C 中為一個陣列分配空間。

一種是棧(stack)的形式：
char array[5]； 意思是分配給陣列array一個5個位元組的空間。

一種是堆(heap)的形式：
char *array;
array=(char *)malloc(5);
//C++: array=new char[5];

23. 如何初始化一個指標陣列。(不懂)

指向陣列的指標：
char (*array)[5];含義是一個指向存放5個字元的陣列的指標。
存放指標的陣列：
char *array[5];含義是一個陣列中存放了5個指向字元型資料的指標。
按照題意，我理解為初始化一個存放指標的陣列，char *array[2]={“China","Beijing"}；
其含義是初始化了一個有兩個指向字元型資料的指標的陣列，這兩個指標分別指向字串"China"和"Beijing"。

24. 如何定義一個有10個元素的整數型指標陣列。

int *array[10];

25. s[10]的另外一種表達方式是什麼。

前面說過了，陣列和指標其實是資料存在形態的兩種表現形式，如果說對於陣列s[]，我們知道*s=s[0]，那麼s[10]的另一種表達方式就是：
*(s+10)

26. GCC3.2.2版本中支援哪幾種編程語言

支援 C, C++, Java, Obj-C, Ada, Fortran, Pascal, Modula-3等語言

27. 要使用CHAR_BIT需要包含哪個頭檔

limits.h

28. 對(-1.2345)取整是多少？

其實不同的取整函數可能有不同的結果，不過這個數沒有太大的爭議，答案是-1。

29. 如何讓局部變數具有全局生命期。

即用static修飾就可以了，但是只是生命期延長，範圍並沒有擴大，除非把這個變數定義在函數體外的靜態區，不過那樣就變成Global變數了

30. C 中的常量字串應在何時定義？

據我理解，有兩種情況，一種是預處理階段，用#define定義；還有就是使用const修飾詞，不過const修飾的是一個變數，其含義是“唯讀”，稱之為常量並不準確，但是確實可以用操作變數的方法當常量用。所以還是第一種比較靠譜。

31. 如何在兩個.c檔中引用對方的變數

最簡單最直接的方法是為變數添加extern修飾詞，當然這個變數必須是Global變數

(還有一種就是利用函數調用來進行變量的間接引用，比如這個C檔中的一個函數引用另外一個C中的函數，將變數通過實參的形式傳遞過去。
不過題目既然說是引用，那麼還是用第一個答案好了。)

32. 使用malloc之前需要做什麼準備工作 (Heap)

首先要知道malloc的用途，簡單的說就是動態的分配一段空間，返回這段空間的頭指針。
實際的準備工作可以這麼分：需要這段空間的指標是否存在，若不存在，則定義一個指標用來被賦值，還要清楚要返回一個什麼類型的指標，分配的空間是否合理；如果指標已經存在，那麼在重新將新的空間頭位址賦值給這個指標之前，要先判斷指標是否為NULL，如果不是要free一下，否則原來的空間就會被浪費，或者出錯，free之後就按照前一種情形考慮就可以了。

33. realloc函數在使用上要注意什麼問題。

據我的初步理解，這個函數的作用是重新分配空間大小，返回的頭指標不變，只是改變空間大小。
既然是改變，就有變大、變小和為什麼改變的問題。變大，要注意不能大到記憶體溢出；變小，那變小的那部分空間會被徵用，原有資料不再存在；為什麼改變，如果是想重新挪作他用，還是先free 了吧。

34. strtok 函數在使用上要注意什麼問題。

這個函數的作用是分割字串，但是要分割的字串不能是常量，這是要注意的。strtok的原形是char *strtok(char *string, char *delim);
比如先定義一個字串：char array[]="part1,part2″;
我們將","作為分隔符號，先用pt=strtok(array,",");，得到的結果print出來就是"part1″，

那後面的呢，要寫成pt=strtok(NULL,",");
注意，要用NULL，如果被分割的字串會被分成N段，那從第二次開始就一直要用NULL。(那怎麼取用第三次的呢?第四次呢?)
總結起 來，需要注意的是：被分割的字串和分隔符號都要使用變數；除第一次使用指向字串的指標外，之後的都要使用NULL；

35. gets函數在使用上要注意什麼問題。

這是一個鍵盤輸入函數，將輸入字串的頭位址返回。
輸入完一個字串後，這個字串可能依然存在於這個標準輸入流之中，當再次使用gets的時候，也許會把上次輸入的東西讀出來，所以應該在使用之後用 fflush(stdin);處理一下，將輸入流清空。
最後也還是要注意溢出的問題。

36. a+++++b 所表示的是什麼意思？有什麼問題？

這個其實並沒有語法錯誤，按照C對運算符等級的劃分，++的優先順序大於+，那麼這句話會被編譯器看做：(a++)+ (++b)，這回明白了吧。有什麼問題，語法上沒有問題，有的是道德上的問題！作為一個優秀的程式師，我們要力求語句的合法性和可讀性，如果寫這句的人是 在一個team裏，那麼他基本會被打的半死……最後討論一下結果：假設a之前的值是3，b是4，那麼運行完這個變態語句後，a的值是4，b是5，語句的結 果是8。

37. 如何定義Bool變數的TRUE和FALSE的值

把TURE和FALSE給定義了，使用#define就可以：
#define TURE 1
#define FALSE 0
如果有一個變數需要定義成bool型的，舉個例子：bool a=TURE;就可以了。

38. explain “struct" and “union" (參考: MTK考題, 解答)

struct → 所佔記憶體空間為 member 相加
union → 所佔記憶體空間由最大size member決定

note: 所以union的member同一時間只會最多出現一個

39. explain lvalue and rvalue (參考)

我們要先知道lvalue和rvalue，指的是一個表達式(expression)而非物件(object)。兩者的差別在於，lvalue指明了一個續存物件(persistent object)或function，例如++a,obj, *ptr, arr[index]等都是lvalue；而rvalue是沒有名字的，可能是暫時物件(temporary object)，函數傳回的non-reference value，或者就只是一個字面常數值，例如a++,42,int(3.14)。重要的差別在於，lvalue所指的東西是有名字的、能續存下去的物件或函數，而rvalue所指的東西是沒有名字的、暫時性的、在表達式之後就會消失的東西。

一個判斷表達式是lvalue或rvalue的方法是：能不能對該表達式取址(address of, &運算子)?如果可以，則是lvaule，反之則是rvalue。因為，lvalue指的東西是有名字的，在表達式結束後不會消失，取其位址是安全的；而rvalue指的東西在表達式結束後就會消失，如果我們取它的位址，在表達式結束後，rvalue所指的東西就會蒸發，該位址上會有什麼值就不得而知了，這是非常危險的動作，所以編譯器是不給過的。

40. write a code that check the input is a multiple of 3 or not without using division or mod

參考解答

while n > 0:
    n -= 3
while n < 0:
    n += 3
return n == 0

41. 不使用暫存變數交換兩個變數 ( Swap two variables without using a temporary variable )

第一種方式是使用 XOR 運算： (參考)
a = a ^ b
b = a ^ b
a = a ^ b
第二種是使用加法與減法：
a = a + b
b = a - b
a = a - b

第三種是使用乘法與除法：
a = a * b
b = a / b
a = a / b

這三種方式作用都相同，
但是第二種與第三種都可能會有溢位（overflow）的問題，
所以最佳的解法是使用第一種 XOR 運算。

42. 寫出一個簡單 makefile 編譯 main.c 與 foo.c, 也可清除main.o foo.o 檔

main: main.o foo.o        
    gcc main.o foo.o -o main  
main.o: main.c             
    gcc main.c -c          
foo.o: foo.c             
    gcc foo.c -c          
clean:                 
    rm -rf main.o foo.o  

43. 用 C 實作 Stack的 pop()與 push() :

在程式語言中，要實現堆疊有許多種方法，最簡單的方式就是使用陣列模擬。 (參考)
即定義一個大小為 MAX_SIZE 的陣列，並使用一個變數 top 來表示堆疊的頂端。
以下是 C 以陣列實現的堆疊原始碼，可以參考看看：

#include 
#include 
#define MAX_SIZE 10
void push(int);
void pop(void);

int stack[MAX_SIZE], top = 0;
int main(void)
{
    push(0);
    push(1);
    push(2);
    pop();
    pop();
    push(3);
    push(4);
    pop();
    pop();
    pop();
    push(5);
    push(6);
    push(7);
    pop();
    pop();
    pop();

    system("pause");
}

void push(int data)
{
    if (top == MAX_SIZE)
    {
        printf("The stack is full!\n");
    }
    else
    {
        stack[top++] = data;
    }
}
void pop(void)
{
    if (top == 0)
    {
        printf("The stack is empty!\n");
    }
    else
    {
        printf("%d\n", stack[--top]);
    }
}

44. 什麼是 extern C 與 extern ?

extern “C" 是C++特有的組合關鍵字，在C裡並沒有這個的組合，僅有extern這個關鍵字! (出處)

extern “C" :

為什麼C++會需要這樣的關鍵字組呢? 原因是C++它有一個複載(overloading)的功能，也就是說同樣的函式名稱可以有多個定義只要參數簽名不同即可。比如說C++裡可以有以下的二個宣告
bar(int i, int j);
bar(double i, double j);
這二個函式都是同樣的名字叫bar，僅參數型式不同。然而在C語言裡是不被允許的! C++是如何處理這同名的函式呢? 其實他在編譯時會偷偷的把這二個函式名變成不同的名字，舉例來說bar(int i, int j)可能會被改成_bar_int_int(每種compiler產生不太一樣)，而另一個則被改成_bar_double_double。這技術稱Mangling。

問題來了! 當我們希望C++不要偷換函式名時該怎麼辦? 於是就有了extern “C" 這個關鍵字組出現了。這個字組就是請C++不要自己又偷天換日，請它保留原名。所以當我們宣告一個函式如下時:
extern “C" bar(int i, int j);

編譯器就不會把bar變成_bar_double_double。

實際使用的注意事項:
1. 當C++使用C的函式庫(library)時，C++不能直接套用C的header檔。因為他會把header裡的宣告給mangleing了。所以他必須使用如下:

extern “C"
{
#include “C_LIB.h" //C_LIB 是C語言所製告出來的。
}

2. 相反的，在C語言的編譯器裡若要使用由C++所製告出來的C函式庫，那麼也不能直接的使用C++的header檔。因為此header檔必然存在extern “C" 這個關鍵字組，而這字組C語言是不認識的。所以必需要把C++的header檔裡的extern “C" { } 移除後才可以讓C編譯器使用。

extern :

一般是用在外部變數(或稱為全域變數)上的
* 宣告在函數內部的變數為內部變數，又稱為自動變數

主要功能是可以讓不同檔案間可以共用同一個變數
* 變數宣告可以多次，宣告其存在
* 變數定義只可以一次，讓程式為其配置空間

file1.cpp
———
int a; /* 變數a的定義兼宣告 */

file2.cpp
———
extern int a;
/* 變數a的外部宣告 */
/* 表示a在別的檔案被定義了 */

45. 什麼是 inline ?

在函式前面加入關鍵字 inline , 此函式就可以「建議」編譯器將之設定為 「行內函式」(Inline function)
有什麼優點呢?
如果編譯器評估效能有改善而建議被採納，則該函式會自動在呼叫點展開為程式碼，行內函式建議可以直接定義於表頭檔案中

inline int pow2(int num) {
   return num*num;
}

46. 請說明 call by value, call by address, call by reference

在C語言裡裡，傳遞參數的2種方式，分別是Call by value、Call by pointer。而在C++裡多了一個Call by reference的方法。Call by reference的作用和目的和Call by pointer是一樣的，都是想要指回原本的變數並且可以修改。不過Call by reference寫起來更簡單。 (或看另一文章介紹)

以下為程式碼:

//call by value 
傳值call by value，傳值的意思顧名思義就是只把『值』複製給對方
對方拿到了你的值以後做任何改變都不會影響到原本的值
int main(){ 
   int a = 10; 
   plus(a); 
} 
int plus(int a){ 
   //兩個a位於不同記憶體空間 
   return a++; 
}
 
//call by address
傳指標就是傳address過去，說到底仍然也是call by value，
只是那個value是指標本身，複製的內容也是指標本身，
只不過那個值Value剛好就是位址address
也稱作call by value of pointer,
 所以對方修改address裡的數值也從時修改了傳送方原本的值 (參考)
int main(){
   int a = 10;
   plus(&a); // a = 11
}
void plus(int* a){ 
   //傳入a的記憶體位置，function中的a pointer指向main中的a變數
   (*a)++; 
}

 
//call by reference 
傳參考是C++才有的東西，C語言是沒有的唷，
可以說call by reference是call by address的進化版，
因為傳址的指標它的內容為指向的位址，
但他本身仍然有記憶體位址，但是傳參考是不會有的
int main(){ 
   int a = 10; 
   plus(a); // a = 11; 
} 
void plus(int &a){ 
   //作用與call by address相同，寫法更簡潔 但僅限C++ only 
   a++; 
}

47. 請寫一段程式碼來宣告一個函式指標 (pointer to function)

宣告方式： return_type (*func_pointer)( parameter list ); (參考)
如下

#include
 
int add(int n1, int n2){ 
 return n1 + n2;
}
 
int main(){ 
 int (*fptr)(int, int);
 fptr = add;
 
 int num1 = 10, num2 = 30;
 printf("num1 + num2 is : %d\n", fptr(num1, num2));
 
 return 0;
}

第8行宣告一個指標名為 fptr ，指向 int (int, int)
換句話說，fptr的type : int (*)(int, int)

我們可以用以下兩種方式將已知的function, assign 給 function pointer：

1. fptr = &func_name;
2. fptr = func_name;(???為什麼這種可以)

使用的時候也有兩種方法可以使用：

1. (*fptr)(num1, num2);
2. fptr(num1, num2);

每次讀到這一段的時候，總是有個疑惑：為什麼兩種方法都可以？
甚至，你編譯下面這一段 code 也可以執行：

#include
 
void print_hello(){ 
 printf("Hello world\n");
 return;
}
 
int main(){ 
 print_hello();
 (&*print_hello)();
 (*&*print_hello)();
 (**&print_hello)();
 (&**&print_hello)();
 (&*&*print_hello)();
 return 0;
}

Why?

要確保初值化(initialization)或是assignment的正確性，取決於 1.數值 2.型別
舉例來說：
int func(int, int);
int (*fptr)(int, int);

type of fptr is : int (*)(int, int);
type of func is : int (int, int);
type if &func is : int (*)(int , int);

所以 fptr = &func 很合理，型別正確並且數值也正確（&func數值和func一樣）
可是 fptr = func 型別不一樣。 所以在這裡其實做了implicit conversion 將function name ( i.e. function designator ) 轉成函式指標使用

至於，使用的方式有兩種一種用deference(i.e use * operator)，一種不用
我曾經在一本書上看到這樣的解釋：

在使用function的時候，fun()，其中()稱作 function-call operator
function-call operator 只允許 pointer to function使用。

所以一般我們在使用func_name(); 其實會做implicit conversion將func_name轉型, 所以我們這樣寫其實也可以執行(&func_name)();

以上就是 function pointer 的基本操作。

轉自ptt: [重要] 發文前務必閱讀：C/C++常見問題十三誡

1. 不可以提取不知指向何方的指標(指標變數必需先指向某個可以合法操作的空間，才能進行操作)：
2. 不能存取超過陣列既定範圍的空間

    錯誤例子：char *pc1;      /* 未給予初值，不知指向何方 */
            char *pc2 = 0;  /* pc2 起始化為 null pointer */
            *pc1 = 'a';     /* 將 'a' 寫到不知何方，錯誤 */
            *pc2 = 'b';     /* 將 'b' 寫到「位址0」，錯誤 */
    正確例子：char c;          
            char *pc1 = &c;  
            *pc1 = 'a';      /* c 的內容變為 'a' */
    錯誤例子：char *name;   /* name 尚未指向有效的空間 */
            printf("Your name, please: ");
            gets(name);   /* 您確定要寫入的那塊空間合法嗎??? */
            printf("Hello, %s\n", name);
    正確例子(如果編譯期就能決定字串的最大空間用char[])：
    char name[21];  
/* 讀入字串最長 20 個字元，保留一格空間放 '\0' */
    printf("Your name, please: ");
    gets(name);
    printf("Hello, %s\n", name);
    (若是在執行時期才能決定字串的最大空間，則需利用動態分配空間) 
    size_t length;
    char *name;
    printf("請輸入字串的最大長度(含null字元): ");
    scanf("%u", &length);
    name = (char *)malloc(length);
    printf("Your name, please: ");
    scanf("%s", name);
    printf("Hello, %s\n", name);
    free(name);

4. 不要試圖用 char* 去更改一個"字串常數"：

    char* pc = "john";   /* pc 現在指著一個字串常數 */
    *pc = 'J';   /* 但是 pc 沒有權利去更改這個常數! */
    說明：字串常數的內容是"唯讀"的，有使用權但沒有更改的權利，若希望使    
    用可以更改的字串，需將其放在合法空間。
    
    錯誤例子(strcat()不會另行配置空間，
只將資料附加到 s1 所指唯讀字串的後面，
會寫入到程式無權碰觸的記憶體空間)：
    char *s1 = "Hello, ";
    char *s2 = "world!";
    strcat(s1, s2);
   正確例子：
    char s1[20] = "Hello, ";
    char *s2 = "world!";
    strcat(s1, s2);

5. 不能在函式中回傳一個指向區域性自動變數的指標
(區域變數在離開該區域時被消滅，因此呼叫端得到的指標所指的字串內容失效了，但如果指標內容是用動態的方式配置，這塊空間是在heap而非stack上，heap空間不會自動回收，因此這塊空間在離開函式後依然有效，但要記得free掉記憶體)：

   錯誤例子：char *getstr(char *name){
                     char buf[30] = "hello"; 
                     strcat(buf, name);
                     return buf;
                 }
   正確例子：void getstr(char buf[], int buflen, char *name){
                   char s[] = "hello";
                   strcpy(buf, s);
                   strcat(buf, name);
                   }
    正確例子：int* foo(){
                   int* pInteger = 
(int*) malloc( 10*sizeof(int) );
                   return pInteger;
                   }

6. 不可以只做 malloc(), 而不做相應的 free()

但若不是用 malloc() 所得到的記憶體，則不可以 free()。
已經 free()了所指記憶體的指標，
在它指向另一塊有效的動態分配得來的空間之前，
不可以再被 free()，也不可以提取(dereference)這個指標。
[C++] 你不可以只做 new, 而不做相應的 delete.

7. 在數值運算、賦值或比較中不可以隨意混用不同型別的數值

錯誤例子(1)：
unsigned int sum = 2000000000 + 2000000000; /* 20 億 */
double f = 10 / 3;

正確例子(1)：
/* 全部都用 unsigned int, 注意數字後面的 u, 大寫 U 也成 */
unsigned int sum = 2000000000u + 2000000000u;
/* 或是用顯式的轉型 */
unsigned int sum = (unsigned int)2000000000 + 2000000000;
double f = 10.0 / 3.0;

說明：在目前最普遍的32位元PC作業平台上，
整數常數2000000000的型別為 signed int(簡寫為 int)，
相加後，其結果仍為 int, 但是 signed int 放不下 4000000000, 
造成算術溢位(arithmetic overflow)，
很可能無法將正確的值指派給 unsigned int sum，
縱使 unsigned int 放得下4000000000的數值。

注意：寫成unsigned int sum = (unsigned int)
(2000000000 + 2000000000);也是不對的。

例子(2)：（感謝 sekya 網友提供）
unsigned char a = 0x80;
char b = 0x80; /* implementation-defined result */
if( a == 0x80 ) { /* 恒真 */
  printf( “a ok\n" );

if( b == 0x80 ) { /* 不一定恒真 */
  printf( “b ok\n" );
}
說明：在將 char 型別定義為範圍從 -128 至 +127 的系統上，
int 0x80（其值等於 +128）要轉成 char 會放不下，
會產生編譯器自行定義的值。這樣的程式就不具可移植性了。

8. 在一個運算式中，不能對一個基本型態的變數修改其值超過一次以上
(C/C++並沒有強制規定參數會由哪個方向開始處理(不像Java是由左到右)，因此可能會造成與預期不符的情況)：

    錯誤例子：int i = 7;
             int j = ++i + i++;
    正確例子：int i = 7;
             int j = ++i;
             j += i++;

    錯誤例子：x = x++;
    錯誤例子：int arr[5];
             int i = 0;
             arr[i] = i++;

    正確例子：int arr[5];
             int i = 0;
             arr[i] = i;
             i++;
    錯誤例子：int Integer=10;
             printf("%d %d %d", Integer++, Integer++, Integer++);
    錯誤例子：void foo(int a, int b) { ... }
             int main() {
               int i=0;
               foo(i++, i++);
             }

9. 在 Macro 定義中, 務必為它的參數個別加上括號()：

   錯誤例子：#define SQUARE(x)    (x * x)
   正確例子：#define SQUARE(x)    ((x) * (x))
   如果是用 C++,可利用inline function來取代上述的 
macro,以免除 macro 定義的種種危險性。
   如：inline int square(int x) { return x * x; }
    macro 定義出的「偽函式」至少缺乏下列幾項函式本有的能力：
    (1) 無法進行參數型別的檢查。
    (2) 無法遞迴呼叫。
    (3) 無法用 & 加在 macro name 之前，取得函式位址。

10. 不可以在 stack 設置過大的變數
(編譯器會自行決定 stack 的上限，可能是數KB 或數十 KB，當變數所需的空間過大時，很容易造成 stack overflow，程式亦隨之當掉，若真正需要如此大的空間，那麼建議配置在 heap 上，或是採用static / globla variabl)：

    錯誤例子：int array[10000000];       
    正確例子：int *array = (int*) 
malloc(10000000*sizeof(int));

11. 使用浮點數精確度造成的誤差問題
根據 IEEE 754 的規範，又電腦中是用有限的二進位儲存數字，因此常有可能因為精確度而造成誤差，例如加減乘除，等號大小判斷，分配律等數學上常用到的操作，很有可能因此而出錯(不成立)

12. 不要猜想二維陣列可以用 pointer to pointer 來傳遞：

    void pass1DArray( int array[] );
    int a[10];
    pass1DArray( a );   
/* 可以合法編譯，而且執行結果正確!! */
    事實上，編譯器會這麼看待
    void pass1DArray( int *array );
    int a[10];
    pass1DArray( &a[0] );
    二維陣列不能直接改成 int **
    錯誤例子：void pass2DArray( int **array );
             int a[5][10];
             pass2DArray( a );  /* 這時候編譯器會報錯 */
    在一維陣列中，宣告了一個 a[10]，那我可以把 a 當成指標來操作 *a 
    *(a+9)，但是多維陣列無法如此使用。
    void pass2DArray(int (*array) [10]); 
    // array 是個指標，指向 int [10]
    int a[5][10];
    pass2DArray( a );

13. 函式內 new 出來的空間記得要讓主程式的指標接住：

    錯誤例子：void newArray(int* local, int size) {
                 local = (int*) malloc( size * sizeof(int) );
             }
             int main() {
                 int* ptr;
                 newArray(ptr, 10);
             }
    原因如下：                                          
    1. int* ptr;        ptr -> |__未知的空間__|
                        
    2. 呼叫函式 newArray ptr -> |__未知的空間__|  |__未知的空間__| 
                               |___合法空間___|  |__未知的空間__|
    local接到了ptr指向的那個位置，
    接著函式內local要到了新的位置但是ptr指向的位置還是沒變的，
    因此離開函式後就好像事什麼都沒發生，
    嚴格說起來還發生了 memory leak。
    以下是一種解決辦法：int* createNewArray(int size) {
                           return (int*) malloc( size * sizeof(int) );
                      }
                      int main() {
                           int* ptr;
                           ptr = createNewArray(10);
                      }
    如果是 C++可用 Reference：void 
    newArray(int*& local, int size) {
        local = new int[size];
    }

###

擬真試題1

• 1. C/C++ 類：
  • 1.1   const int* p 和 int* const q 兩者之差別？

    前者: 指到的資料型態為const
    後者: 指標本身為const
    

  • 1.2   32-bit machine用C語言對位址 0x00005000 的第三個bit設成0，第五個bit設成1。

    #define BIT3 (0x0008)
    #define BIT5 (0x0010)
    
    unsigned int a=0x00005000;
    void set_bit3(void) { a |= BIT3;} 
    void clear_bit5(void) { a &= ~BIT5;}
    

  • 1.3 指標與陣列的差別？

    宣告陣列的時候，會同時宣告記憶體位址供陣列使用；
    宣告指標時，則不會。
    

  • 1.4 試寫出一個Macro求出兩數之最大值。

    #define MAX(A,B) ( (A) >= (B) )? (A) :(B) )
    

  • 1.5 #define SUM(a,b) a+b ,  若是 SUM(2,5)*10 的答案是什麼？

     SUM(2,5)*10 = 2+5*10 = 52
    

  • 1.6 給予10個任意整數，輸出其最小值、最大值、平均值。

    int Max = a[0], Min = a[0], Avg = 0; 
        for(int i = 0 ; i < 10 ; i++)     {         if(Min > a[i])
                Min = a[i];
            if(Max < a[i])
                Max = a[i];
            Avg += a[i];
        }
       cout << Min << Max << static_cast(Avg)/10 << endl;
    

  • 1.7 說明並解釋下列之interrupt service routine 之錯誤處？

    __interrupt double isr(double r) {
     double area = PI*r*r ;
     printf("%f\n",area) ;
     return area ;
         }
    

    Ans:
    ISR不能有返回值(不知道給誰)
    ISR不能傳遞參數(不知道誰呼叫)
    浮點運算和pintf有重入問題
    ISR應短而高效
  • 1.8 寫出一個字串拷貝程式： void StrCpy(char* dst , char* src) ;

  for(; *src != '\0', *dst = *src; dst++, src++)
  

  • 1.9 寫出整數轉換字串程式

    char* s;
    sprintf(s, "%d", i);
    

  • 1.10 寫出一個程式若輸入為 12345678 , 則返回值為 56781234    DWORD fun(DWORD num)

    typedef unsigned long DWORD;
    DWORD fun(DWORD num)
    {
        DWORD h, l;
        h = num << 16;     l = num >> 16;
        return h ^ l;
    }
    
    備註: DWORD 就是 Double Word， 每個word为2個Byte的長度，DWORD 即為4個Byte，每個Byte是8位bits，共32位bits
    

  • 1.11 若x=456;則return值為多少

    int fun(int x)
    {
       int count = 0 ; 
       while(x){ 
          count++ ; 
          x = x & (x-1) ; 
       } 
       return count ; 
    }   
    

    Ans: 4
  • 1.12 連續呼叫 func 10 次，印出的值為何？

    void func(void){
       static int i = 0 ; 
       i++ ; 
       printf("%d " , i ) ; 
       } 
    

    ans: 1 2 3 4 5 6 7 8 9 10
  • 1.13 何謂this指標？何謂template? 何謂virtual function?

    - this是一個被C++保留的詞彙，在某個class裡面指向自己這個物件的指標，儲存自己的記憶體位置
    
    - C++ 的 Template 是種將資料型態參數化的功能。將資料型態資訊自程式碼中抽離，代之以簡化的符號 (T, T1, T2, ...)。再由編譯器透過類似巨集代換的方式，根據樣板內容產生實際的程式碼。(參考)
    
    - 虛擬函數就是指一個函數的行為可以在其所屬類別之衍生類別中被另一個和該函數具有相同簽章(signature) 之同名函數所重新設計和替換掉. 換句話說, 虛擬函數存在的目的就是讓衍生類別可以自行設計修改原有之函數行為. 如. Function Template (函數樣板) 與 Class Template (類別樣板)。 (參考)
    
     
    

  • 1.14 寫出一個程式輸入幾點幾分，return 值為時針與分針的角度 (需注意若為9:00則其角度為90度，非270度)

    這個題目的輸入格式是 HH:MM 的格式，我們還是可以直接用 scanf("%d:%d", &h, &m) 的方式還讀取輸入的資料。接下來計算完時針與分針各別的角度求兩者的差，並用下面的規則處理：
    
    如果這個值小於 0，則將它的負號拿掉。
    如果這個值大於 360，則將它減去 360。
    如果這個值大於 180，則以 360 減去該值。(由於取的是小的角度)
    我們把這些想法寫成程式： (參考)
    
    #include 
    void main()
    {
       int h, m;
       float dh, dm, d;
     
       scanf("%d:%d", &h, &m);
       dm = m*6;
       dh = h*30 + m*0.5;
       d = dh-dm;
       if(d<0) d = -d;    if(d>=360) d=d-360;
       if(d>=180) d=360-d;
       printf("%.3f\n", d);
    }
    

2. OS類：

• 2.1 何謂reentrant程式，設計reentrant需注意什麼？

  Reentrant function 就是可以被重疊執行的 function，講白話就是一個動作還沒做完之前，又重新做了同樣的動作，重疊執行的狀況發生卻不會影響到結果的正確性，符合這種特性即稱為 Reentrant
  
  有些情況就要把 function 設計為 Reentrant，例如多個 Thread 執行同一個 function，或是在 Thread 中在做了某些事後又呼叫自己，整數比大小就是個 Reentrant function 的例子
  
  int Max(int a, int b)
  {
    if(a > b)
    {
      return a;
    }
    return b;
  }
  
  注意這種 function 的條件為  (參考)
  1. 非 const 的區域或全域變數不可使用 (以免之後的 Thread 改變了值)
  2. return 值不可為非 const 的區域或全域變數(理由同上)
  3. 僅依賴呼叫者提供的參數(安全又衛生)
  4. 可重疊執行，所以沒有 Lock 的機制(很直觀)
  5. function 內部呼叫的 function 也必須為 Reentrant (不然呢？)
  

• 2.2 解釋stack與heap
• 2.3 何謂deadlock?

  一組processes陷入互相等待的情況(Circular waiting)
  造成processes接無法往下執行，使得CPU utilization及Throughput大幅降低
  
  Deadlock成立的四個必要條件:
  1. Mutual exclusion(互斥)
  2. Hold & wait(持有並等待) (Partial Allocation)
  3. No preemption(不可強取豪奪)
  4. Circular waiting(循環等待)
  

• 2.4 說明 mutex 與 semaphore

  Mutex是一把鑰匙，一個人拿了就可進入一個房間，出來的時候把鑰匙交給隊列的第一個。一般的用法是用於串行化對critical section代碼的訪問，保證這段代碼不會被並行的運行。
  (A mutex is really a semaphore with value 1.)
  
  Semaphore是一件可以容納N人的房間，如果人不滿就可以進去，如果人滿了，就要等待有人出來。對於N=1的情況，稱為binary semaphore。一般的用法是，用於限制對於某一資源的同時訪問。
  
  
  Binary semaphore與Mutex的差異：
  
  在有的系統中Binary semaphore與Mutex是沒有差異的。在有的系統上，主要的差異是mutex一定要由獲得鎖的進程來釋放。而semaphore可以由其它進程釋放（這時的semaphore實際就是個原子的變量，大家可以加或減），因此semaphore可以用於進程間同步。 Semaphore的同步功能是所有系統都支持的，而Mutex能否由其他進程釋放則未定，因此建議mutex只用於保護critical section。而semaphore則用於保護某變量，或者同步。
  
  
  另一個概念是spin lock，這是一個內核態概念。 
  spin lock與semaphore的主要區別是spin lock是busy waiting，而semaphore是sleep。對於可以sleep的進程來說，busy waiting當然沒有意義。對於單CPU的系統，busy waiting當然更沒意義（沒有CPU可以釋放鎖）。因此，只有多CPU的內核態非進程空間，才會用到spin lock。 Linux kernel的spin lock在非SMP的情況下，只是關irq，沒有別的操作，用於確保該段程序的運行不會被打斷。其實也就是類似mutex的作用，串行化對critical section的訪問。但是mutex不能保護中斷的打斷，也不能在中斷處理程序中被調用。而spin lock也一般沒有必要用於可以sleep的進程空間。
  
  

• 2.5 設計OS的重點在哪些？
• 2.6 如何 Linux 與 windows 互相傳送檔案？

  samba
  

• 2.7 何謂DLL?

  Dynamic Link Library(動態連結檔) 
  就是將一些function封裝起來,以達到資源共用、程式共用的目的, 一方面也能節省記憶體空間...
  

• 2.8 uClinux 與 Linux 最大差異在哪？

  uClinux 就是Micro-Control-Linux，字面上的理解就是"針對微控制領域而設計的Linux 系統.
  
  沒有MMU支持是uClinux與主流Linux的基本差異。
  　　標準Linux是針對有MMU的處理器設計的。在這種處理器上，虛擬地址被送到MMU，把虛擬地址映射為物理地址。通過賦予每個任務不同的虛擬-物理地址轉換映射，支持不同任務之間的保護。
  　　對uCLinux 來說，其設計針對沒有MMU的處理器，不能使用處理器的虛擬內存管理技術。uCLinux仍然采用存儲器的分頁管理，係統在啟動時把實際存儲器進行分頁。在加載應用程序時程序分頁加載。但是由於沒有MMU管理，所以實際上uCLinux采用實存儲器管理策略。uCLinux係統對於內存的訪問是直接的，所有程序中訪問的地址都是實際的物理地址。操作係統對內存空間沒有保護，各個進程實際上共享一個運行空間。一個進程在執行前，係統必須為進程分配足夠的連續地址空間，然後全部載入主存儲器的連續空間中。
  

• 2.9 何謂即時多工系統？

3. 計組、硬體類：

• 3.1 何謂DMA，有何好處？
• 3.2 何謂Little endian / Big endian

  endian指的是當物理上的最小單元比邏輯上的最小單元小時，邏輯單元對映到物理單元的排布關係。
  
  如果你在文件上看到一個雙字組的data，
  Ex: long MyData = 0x12345678，要寫到從0x0000開始的記憶體位址時。
  
  如果是Big Endian的系統，
  存到記憶體會變成 0x12 0x34 0x56 0x78，最高位元組在位址最低位元，最低位元組在位址最高位元，依次排列。
  如果是Little Endian的系統，
  存到記憶體會變成 0x78 0x56 0x34 0x12，最低位元組在最低位元，最高位元組在最高位元，反序排列。
  
  比較的結果就是這樣：
          big-endian little-endian
  0x0000 0x12         0x78
  0x0001 0x34         0x56
  0x0002 0x56         0x34
  0x0003 0x78         0x12
  

• 3.3 何謂 JTAG? 何謂ICE？

  JTAG是聯合測試工作群組（Joint Test Action Group）,
  何謂JTAG測試，
  簡言之，係順序掃描積體電路元件之全部外界輸入輸出腳端，
  擷取輸入輸出端之測試數據，藉以測試元件內部之功能，
  或進行被安裝在印刷電路基板上之測試方法。
  ICE是在線模擬器 (In-Circuit Emulator, ICE) 
  是用來除錯嵌入式系統軟體的硬體設備
  

• 3.4 解釋 write back 與 write through

  (參考)
  
  write-through cache
  使用 write-through 的 cache,
  資料寫入cache時也會同步寫入儲存裝置
  
  write-back
  而 write-back 是將資料量儲存到一定的量之後,
  會依據同區塊的資料一次整批寫回去.裡面有提到 dirty ,
  他是在記憶體裡面 cache 的一個 bit 
  用來指示這筆資料已經被 CPU 修改過但是尚未回寫到儲存裝置中.
  

• 3.5 列舉幾個serial port, parallel port

  serial port :
  終端（Computer terminal）/ 數據機/舊式串列埠滑鼠
  
  parallel port:
  印表機 / 影像掃描器 / 並列裝置，如EPROM編程器
  

• 3.6 說明 Watchdog 之運作機制

  Watch Dog, 就是一隻程式或一個系統, 
  去到一個或各個系統去巡邏, 看是否出問題, 
  而當出問題時, 將會啟動一些備援機制, 
  或者是被一些系統的 Disable, 或相對應的行為, 
  這就是 Watch Dog 系統
  

4. 網路類：

• 4.1 分別說明switch、hub、router、gateway

  Hub集線器  (參考)
  將所有線路全部連結起來，除了廣播電子訊號之外，並不做任何處理。
  OSI模型層級:L1實體層
  
  Switch交換器 
  藉由MAC位址判斷訊框應該往哪裡送。
  OSI模型層級 L2資料連結層
  
  Router路由器 
  藉由IP位址判斷封包應該往哪裡送。
  OSI模型層級 L3網路層
  
  Gateway閘道器
  將2 種使用不同傳輸協定的網路橋接在一起。
  OSI模型層級 L5會話層
   
  
  (參考)
  1.HUB：
  我們稱做集線器，一般而言，HUB有兩大特性，一個就是廣播，一個就是半雙工。
  廣播是指，當A電腦要透過HUB送資料給B電腦的時候，A送出來的資料其實連接在這台HUB上的電腦都會收到，但是只有B電腦會將資料收起來，其他電腦則是將封包丟掉。
  半雙工是指，收資料或送資料不能同時，你一次只能做其中一種。
  由於HUB的這種特性，所以當HUB連接非常多電腦時，網路就會變慢。
  
  
  2.Switch：
  中文叫交換器，和HUB看起來一樣，但實際上差別很大。首先switch並不一直廣播，而且是全雙工的。主要是SWITCH會記錄封包中的MAC位址所以當電腦A傳送資料給電腦B時，其他電腦並不會也收到資料，而且這個時候別的電腦也可以同時互相傳送資料。雖然SWITCH有上述的好處，但是要傳送的資料封包每一個都必須經過SWITCH判斷決定要送往哪一台電腦，所以會有一些延遲，因此有時候電腦數少於五台，用HUB反而比SWITCH快。
  
  3.IP分享器：
  這個設備通常會有一個WAN port和1~4個不等的Lan port(其實是Switch)。WAN port一般是接ADSL modem(也就是小烏龜啦)，而Lan port則是接到PC電腦。這個設備主要的功能是NAT，也就是做IP分享的意思，他會將WAN port的真實IP(可以是固定IP或浮動IP)分享給LAN port的電腦使用。
  
  備註解釋一下NAT功能：
  一般IP分享器LAN port裡的電腦室使用虛擬IP，也就是俗稱的假IP，這個網段通常是192.168.X.X，最常見的是192.168.0.X與192.168.1.X。這個IP網段是保留的網段，在實際網際網路並不能使用。NAT這個功能負責記錄網卡MAC位址與假IP的關係並做轉換。
  
  舉例來說，假設使用者有兩台PC透過IP分享器上網
  A電腦IP為192.168.0.2，網路卡MAC位址是00046F12301A
  B電腦IP為192.168.0.50，網路卡MAC位址是000879215B09
  
  當A電腦想要連網站yahoo.com.tw時，A電腦會送出資料給yahoo，而IP分享器會記錄192.168.0.2的MAC是00046F12301A，並把資料內來源IP 192.168.0.2改成WAN port的真實IP，然後送往YAHOO。Yahoo收到以後會依照真實IP位址回傳資料給IP分享器，IP分享器再依照資料內的MAC位址判別出這封包是要給A電腦的，於是把目的IP改成192.168.0.2送往A電腦。簡單的說，IP分享器是透過傳送封包內的MAC位址來分辨這個封包資料是要給哪一台電腦的，進而達到分享IP的功能。請注意，有些IP分享器會說自己是IP sharing router或者是寬頻Router，但這與實際的Router有一段差距。
  
  4.Router：
  中文叫路由器，路由器通常最少會有兩個介面，而這兩個介面分別區隔不同的IP網段。例如IP分享器有WAN和LAN兩種介面，區隔WAN的實際IP與LAN的虛擬IP網段，所以說IP分享器是Router其實並沒有錯誤。不過我們技術人員口中所說的router都是那種超級貴死人，而且兩個介面都是用在真實IP網段的設備。
  
  好像有點離題了，其實如果你對switch的原理有一點瞭解，那麼其實router有一點像switch，只不過Router是依照封包的目的IP來決定資料是要傳往哪一個介面的哪一個網域。
  
  

• 4.2 何謂IP fragmentation?

  IP fragmentation (IP 分段)
  一個封包被拆分為兩個或多個封包。Symantec Protection Agent 支援 IP 分段，這是一種透過網路接收或傳送不完整封包的功能。
  

• 4.3 說明DHCP server功能

  DHCP伺服器主要功能就是用來配發IP，
  一來因為伺服器會自動配發IP而節省人力，
  二來不會發生IP重疊而互相衝突，
  三來可將IP回收循環使用(例：50個IP提供給錯開時段的70台腦使用)。
  DHCP能分配實體IP與虛擬IP，
  只要在DHCP Pool裡設定可分配的IP範圍，
  就會依需求自動分配IP。
  

• 4.4 說明IP、subnet mask

  IP位址（IP Address）
  在Internet上，一種給主機編址的方式。
  常見的IP位址，分為IPv4與IPv6兩大類。
  
  A Subnet mask 
  is a 32-bit number that masks an IP address, 
  and divides the IP address into network address and host address. Subnet Mask is made by setting network bits to all "1"s and setting host bits to all "0"s.
  

• 4.5 說明 3-way handshaking

  三向交握 (Three-way handshake) 參考
  TCP 通訊協定是一種 connection-oriented 協定，
  它在實際資料傳送前，
  會在來源端與目的端主機以三向交握 (three-way handshake)
   的方式先建立連線，所有屬於相同訊息的 TCP 封包，
  就利用此連線傳送，此種作法有助於資料傳輸的正確性。
  以下是三向交握的流程說明：
  　
  (1) 當傳送端想要與接收端連線時，
  同時會啟用一個大於 1023 的通訊埠作為溝通的介面，
  並且送出一個要求連線的 SYN 封包，
  此封包內帶有起始序號 (例如 100)。
  (2) 接收端確認收到連線的 SYN 封包後，
  會回送一個 SYN+ACK 封包給傳送端，
  封包內則帶有回應號碼 (連線 SYN 封包的序號 + 1)，以及接收端的起始序號 (例如 2200)，等待傳送端的回應確認。
  (3) 當傳送端收到來自接收端的回應號碼，
  確認之前的連線要求封包已被收到，便會再傳送一個 ACK 封包給接收端，封包內會帶有回應號碼 (SYN+ACK 封包的序號 + 1)。
  　
  待接收端收到帶有正確回應號碼的 ACK 封包，
  此連線便正式建立。
  

擬真試題2 :

1.名詞解釋

• volatile variable
• static variable
• char const *p;
• char* const p;
• void (*fp)();

2.名詞解釋

• interrupt

  (wiki) 在電腦科學中，中斷（英語：Interrupt）
  是指處理器接收到來自硬體或軟體的信號，
  提示發生了某個事件，應該被注意，這種情況就稱為中斷。
  通常，在接收到來自外圍硬體（相對於中央處理器和記憶體）的非同步訊號，
  或來自軟體的同步訊號之後，
  處理器將會進行相應的硬體／軟體處理。
  發出這樣的訊號稱為進行中斷請求（interrupt request，IRQ）。
  硬體中斷導致處理器通過一個執行資訊切換（context switch）
  來儲存執行狀態（以程式計數器和程式狀態字等暫存器資訊為主）；
  軟體中斷則通常作為CPU指令集中的一個指令，
  以可編程的方式直接指示這種執行資訊切換，
  並將處理導向一段中斷處理代碼。
  中斷在電腦多工處理，尤其是即時系統中尤為有用。
  這樣的系統，包括執行於其上的作業系統，也被稱為「中斷驅動的」（interrupt-driven）。
  

• MBR(master boot record)

  (wiki) 主開機紀錄（Master Boot Record，縮寫：MBR），
  又叫做主啟動磁區，是電腦開機後存取硬碟時所必須要讀取的首個磁區，
  主啟動磁區記錄著硬碟本身的相關資訊以及硬碟各個分割的大小及位置資訊
  

3.用C實作

• 交換兩個數字
• 刪除linklist中間的node
• 把string轉成double

  使用這類函數時，要先 
  #include  或 #include 
  
  1. atof：將字串轉為倍精度浮點數
  double atof ( const char * str );
  ex:
   char buffer[] = "2.675";
   double f = atof(buffer);
  
  2. atoi：將字串轉為整數
   int atoi ( const char * str );
  ex:
   char buffer[] = "23";
   int i = atoi(buffer);
  
  3. atol：將字串轉為長整數
  long int atol ( const char * str );
  ex:
   char buffer[] = "23";
   long int i = atol(buffer);
  
  4. strtod： 將字串轉為倍精度浮點數
  double strtod ( const char * str, char ** endptr );
  ex: 
   char buffer[] = "1011.113";
   double a = strtod(buffer, NULL);
  
  5. strtol：將字串視為任意進制，轉為長整數
  long int strtol ( const char * str, char ** endptr, int base );
  ex: 
   char buffer[] = "1011";
   long a = strtol(buffer, NULL，2); 
  // 將 "1011" 視為2進制，轉完之後 a 即為 11
  
  6. strtoul：將字串視為任意進制，轉為無號長整數
  unsigned long int strtoul ( const char * str, char ** endptr, int base );
  ex: 
   char *buffer = "1011";
   unsigned long a = strtoul(buffer, NULL，2); 
  // 將 "1011" 視為2進制，轉完之後 a 即為 11
  
   7. itoa: 整數轉為任意進制字串 (非標準函式）
  char* itoa(int value, char* string, int radix);
  ex: 
  char buffer[200];
  int value = 234;
  itoa(value, buffer, 2); // 將 234 轉為存成２進制之字串
  
  8. ltoa：長整數轉為任意進制字串 (非標準函式)
  char* ltoa(long int value, char* string, int radix);
  ex: 
  char buffer[200];
  lnt value = 234;
  ltoa(value, buffer, 2); // 將 234 轉為存成２進制之字串
  

4.計結 MUL BIC(Bit Clear)

5.sort 1000個數字最快的方法 用C把code寫下來

經典排序算法- 桶排序Bucket sort

補充說明三點
1,桶排序是穩定的
2,桶排序是常見排序裡最快的一種,比快排還要快…大多數情況下
3,桶排序非常快,但是同時也非常耗空間,基本上是最耗空間的一種排序算法


例如待排數字[6 2 4 1 5 9]

準備10個空桶, 最大數個空桶
[6 2 4 1 5 9] 待排數組
[0 0 0 0 0 0 0 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶編號(實際不存在)

1,順序從待排數組中取出數字,首先6被取出,然後把6入6號桶,這個過程類似這樣: 空桶[待排數組[ 0 ] ] =待排數組[ 0 ]
[ 6 2 4 1 5 9]待排數組
[0 0 0 0 0 0 6 0 0 0]空桶
[0 1 2 3 4 5 6 7 8 9]桶編號(實際不存在)

2,順序從待排數組中取出下一個數字,此時2被取出,將其放入2號桶,是幾就放幾號桶
[ 6 2 4 1 5 9]待排數組
[0 0 2 0 0 0 6 0 0 0]空桶
[0 1 2 3 4 5 6 7 8 9]桶編號(實際不存在)

 

3,4,5,6省略,過程一樣,全部入桶後變成下邊這樣

[ 6 2 4 1 5 9 ]待排數組

[0 1 2 0 4 5 6 0 0 9 ]空桶

[0 1 2 3 4 5 6 7 8 9 ]桶編號(實際不存在)

 

0表示空桶,跳過,順序取出即可:1 2 4 5 6 9

6.解釋semaphore和mutex 及其C++的實作

7.C++ constructor + 繼承

###

擬真試題3

1). variable 是否可以同時宣告成const 和 volatile

一個參數可以同時是const也是volatile嗎? 解釋為什麼。
∙是的。舉的例子是"只讀的狀態暫存器"。它是volatile因為它可能被意想不到地改變。它是const因為程式不應該試圖去修改它。

∙一個指標可以是volatile 嗎? 解釋為什麼。
∙是的。儘管這並不很常見。舉的例子是當一個執行中的次程序修該一個指向一個buffer的指標時。

2). 詳述有關interrupt定義或行為

3). 題目說明: ARM(?) 會自動對齊每個entries 「註」還有幾題在考ARM記憶體相關
_Packet struct
{
char a;
int b;
char c;
short d;
}

• 3a. 在記憶體配置情形(下面有個圖應該是要畫圖)
• 3b. 不用_Packet指令要怎麼宣告struct才能節省記憶體配置

4). 對於某自然數N 當它是奇數時 N*3+1 當它是偶數是N/2 最後一定會算成 1

• 4a. 請問N=15需要幾次計算才會算到1
• 4b. 附了一個程式，要把bug找出來(15的時候會出錯，其他情況都對)

5).某個3D-shooting Game被QA驗出，一到某個Scene會broken還是Violation XXXXX

• 5a. 你推測是啥原因
• 5b. 你會用怎樣的架構去驗證錯誤

6). 給了一個A List Of Windows Interrupts 共32種

• 6a. APC和DPC差異 (英文簡寫忘了是啥 上面有附???)
• 6b. Interrupt 在某階層以上時是發生什麼事(not sure)

7). 計算Big-Endian Little-Endian的不知道什麼的計算(我根本不知道啥米Endian)

8). 寫個程式，判斷linked list 是否發生了circular

9). 寫一個程式 輸入整數回傳這是幾bits-set  e.g. 0x000003 = 2-bits Set 0xFFFF000 = 16-bits Set

###

擬真試題4

1.what is calling convention?

2.什麼情況下會造成calling convention? how to resolve?

3.what is inline?

4.what is deadlock ? please demonstrate it.

5.what is macro?

所謂巨集, 就是用 #define 的語法定義一個簡短巨集名稱來取代一長串的算式。根據前處理指令 #define 會由前置處理器處理,也就是說在前置處理過程中, 巨集名稱都會被代換成指定的算式。

6.請你把一段程式用macro的方式修改

int square(int x) 
{ 
   return x * x; 
}
改寫成
#define SQUARE(x)    ((x) * (x))
   

7.what is virtual function

8.what is polymorphism ? what’s the difference between virtual function and polymorphism?

###

擬真試題5 :

系統方面:
1. Process 與 Thread 有何不同?

2. const 與 violate 有什麼用途? 系統是如何實做達成該用途?

3. 有兩個變數 X與Y, 如何不以乘法與加法而有效率的得到 X*Y 的數值?

4. Kernel 與 Application 如何溝通? (這題真的是問到爛了 筆試與口試之常見問題)

網路方面:
5. 如何寫出程式以UDP方式傳送資料由HOST A 到 HOST B ?

6. 如何寫出程式以TCP方式傳送資料由HOST A 到 HOST B ?

7. 請詳述 ioctl 與 proc 的差異? 傳送資料的結構為何

8. DMA 相關經驗有嗎?