43. 寫一個在一個字符串(n)中尋找一個子串(m)第一個位置的函數。

KMP算法效率最好，時間復雜度是Ｏ(n+m)。

44. 多重繼承的內存分配問題：

比如有class A : public class B, public class C {}

那么A的內存結構大致是怎么樣的？

這個是compiler-dependent的, 不同的實現其細節可能不同。

如果不考慮有虛函數、虛繼承的話就相當簡單；否則的話，相當復雜。

可以參考《深入探索C++對象模型》，或者：

http://blog.csdn.net/wfwd/archive/2006/05/30/763797.aspx

45. 如何判斷一個單鏈表是有環的？（注意不能用標志位，最多只能用兩個額外指針）

struct node { char val; node* next;}

bool check(const node* head) {} //return false : 無環；true: 有環

一種O（n）的辦法就是（搞兩個指針，一個每次遞增一步，一個每次遞增兩步，如果有環的話兩者必然重合，反之亦然）：

bool check(const node* head)

{

if(head==NULL) return false;

node *low=head, *fast=head->next;

while(fast!=NULL && fast->next!=NULL)

{

low=low->next;

fast=fast->next->next;

if(low==fast) return true;

}

return false;

}

1、一個學生的信息是：姓名，學號，性別，年齡等信息，用一個鏈表，把這些學生信息連在一起， 給出一個age, 在些鏈表中刪除學生年齡等于age的學生信息。

程序代碼

＃i nclude "stdio.h"

＃i nclude "conio.h"

struct stu{

char name[20];

char sex;

int no;

int age;

struct stu * next;

}*linklist;

struct stu *creatlist(int n)

{

int i;

//h為頭結點，p為前一結點，s為當前結點

struct stu *h,*p,*s;

h = (struct stu *)malloc(sizeof(struct stu));

h->next = NULL;

p=h;

for(i=0;i<n;i++)

{

s = (struct stu *)malloc(sizeof(struct stu));

p->next = s;

printf("Please input the information of the student: name sex no age n");

scanf("%s %c %d %d",s->name,&s->sex,&s->no,&s->age);

s->next = NULL;

訪問固定的內存位置（Accessing fixed memory locations） C C++ Development

10. 嵌入式系統經常具有要求程序員去訪問某特定的內存位置的特點。在某工程中，要求設置一絕對地址為0x67a9的整型變量的值為0xaa66。編譯器是一個純粹的ANSI編譯器。寫代碼去完成這一任務。

這一問題測試你是否知道為了訪問一絕對地址把一個整型數強制轉換（typecast）為一指針是合法的。這一問題的實現方式隨著個人風格不同而不同。典型的類似代碼如下：

int *ptr;

ptr = (int *)0x67a9;

*ptr = 0xaa55;

一個較晦澀的方法是：

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

即使你的品味更接近第二種方案，但我建議你在面試時使用第一種方案。

中斷（Interrupts）

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

__interrupt double compute_area (double radius)

{

double area = PI * radius * radius;

printf(" Area = %f", area);

return area;

}

這個函數有太多的錯誤了，以至讓人不知從何說起了：

1). ISR 不能返回一個值。如果你不懂這個，那么你不會被雇用的。

2). ISR 不能傳遞參數。如果你沒有看到這一點，你被雇用的機會等同第一項。

3). 在許多的處理器/編譯器中，浮點一般都是不可重入的。有些處理器/編譯器需要讓額處的寄存器入棧，有些處理器/編譯器就是不允許在ISR中做浮點運算。此外，ISR應該是短而有效率的，在ISR中做浮點運算是不明智的。

4). 與第三點一脈相承，printf()經常有重入和性能上的問題。如果你丟掉了第三和第四點，我不會太為難你的。不用說，如果你能得到后兩點，那么你的被雇用前景越來越光明了。

代碼例子（Code examples）