軟韌體工程師面試- C語言與OS作業系統 常見題目(筆試考題)

目錄:
資料結構
關於變數儲存與記憶體
關於 multi-thread 執行緒 在Linux/Windows
基本演算法
轉自ptt: [重要] 發文前務必閱讀:C/C++常見問題十三誡
擬真試題1
擬真試題2
擬真試題3
擬真試題4
直接列出考古題1(精華完整47題含解答)
直接列出考古題2(精華完整34題含解答)

資料結構

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

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



一個小小的實驗: (出處)

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)則是由高而低。

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

Linux thread

產生child process

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)

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

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

(參考出處)
前言 :最近遇到一些跨平台的程序,本想自己封裝windows下的CreateThread和linux下的pthread,後來發現Linux社區早就提供了windows下的pthread庫,和linux下一模一樣 :
windows下的pthread庫叫做:pthreads-win32,官方網站是:http://sourceware.org/pthreads-win32/,官方FTP是:
ftp://sources.redhat.com/pub/pthreads-win32/。

考慮FTP裡面的內容比較亂,部分已經編譯的庫有問題。我下載了一個看起來比較新的庫,結果弄了半天不能鏈接。建議大家下載:
ftp://sources.redhat.com/pub/pthreads-win32/pthreads-w32-2-7-0-release.exe 這個自解壓文件,壓縮包裡的pthreads.2目錄是源碼,Pre-built.2目錄是編譯所需的頭文件和庫文件。

範例程式 :
* thread_sample.h 代碼 :

* thread_sample.cpp 代碼 :

執行結果 :

Print Message: Thread1
Print Message: Thread2
Thread1 return 0
Thread2 return 0

 

24 thoughts on “軟韌體工程師面試- C語言與OS作業系統 常見題目(筆試考題)

  1. 昭哥

    發現一個小bug
    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 + n*(n-1); <= 這裡錯了 是 sum = sum + i*(i-1); 才對
    }
    return sum;
    }

  2. R.C.

    板主您好,對於這題的解答請問是否應修正為以下這樣,如有錯誤,請不吝賜教:

    1.2 32-bit machine用C語言對位址 0x00005000 的第三個bit設成0,第五個bit設成1。
    #define BIT3 (0x0004)
    #define BIT5 (0x0010)

    unsigned int a=0x00005000;
    void clear_bit3(void) { a &= ~BIT3;}
    void set_bit5(void) { a |= BIT5;}

發表迴響