CC基础及算法整理

1、9月15日 1、static有什么用途（请至少说明两种）a）限制变量的作用域b）设置变量的存储域问题扩展：1. k static全局变量与普通的全局变量有什么区别？ static局部变量和普通局 部变量有什么区别？ static函数与普通函数有什么区别？全局变量（外部变量）的说明z前再冠以static就构成了静态的全局变量。全局 变量本身就是静态存储方式，静态全局变量当然也是静态存储方式。这两者在 存储方式上并无不同。这两者的区别虽在于菲静态全局变量的作用域是整个源程 序，当一个源程序由多个源文件组成时，非静态的全局变量在各个源文件中都 是有效的。而静态全局变量则限制了其作用域，即只在定义该变

2、量的源文件内 有效，在同一源程序的其它源文件屮不能使用它。由于静态全局变量的作用域 局限于一个源文件内，只能为该源文件内的函数公用，因此可以避免在其它源 文件中引起错误。从以上分析可以看出，把局部变量改变为静态变量后是改变了它的存储方式即 改变了它的生存期。把全局变量改变为静态变量后是改变了它的作用域，限制 了它的使用范围。static函数与普通函数作用域不同。仅在本文件。只在当前源文件中使用的函数 应该说明为内部函数（static）,内部函数应该在当前源文件中说明和定义。对于 可在当前源文件以外使用的函数，应该在一个头文件中说明，要使用这些函数的 源文件要包含这个头文件static全局变量与

3、普通的全局变量有什么区别：static全局变量只初使化一次， 防止在其他文件单元中被引用；static局部变量和普通局部变量有什么区别：static局部变量只被初始化一次， 下一次依据上一次结果值；static函数与普通函数有什么区别：static函数在内存中只有一份，普通函数在 每个被调用中维持一份拷贝1.2、程序的局部变量存在于（堆栈）中，全局变量存在于（静态区）中，动 态中请数据存在于（堆）中。问题扩展：121、什么是栈？什么是堆?在具体的c/c+编程框架中，这两个概念并不是并行的。深入到汇编 级进行研究就会发现，栈是机器系统提供的数据结构，而堆是由c/c+函数库提 供的。这两个概念可以

4、从数据结构和系统两个层次去理解：1、从数据结构层次理解，栈是一种先进后岀的线性表，只要符合先进后岀的原 则的线性表都是栈。至于采用的存储方式（实现方式）是顺序存储（顺序栈）还 是链式存储（链式栈）是没有关系的。堆则是二叉树的一种，有最大堆最小堆， 排序算法中有常用的堆排序。2、从系统层次理解，栈是系统为运行的程序分配的先进后出的存储区域。在学 习boot loader吋知道，在上电后初始化阶段要为各个工作模式下分配堆栈，这 里的堆栈实际上就是指stack,堆栈的说法只是因为历史的原因。在执行函数时, 函数内部局部变量的存储单元可以在栈上创建（针对cisc架构而言，risc架构 下，局部变量的存

5、储单元是在寄存器上创建），函数执行结束时这些存储单元自 动被释放。堆是系统管理的可以被程序利用的全局存储空间，动态内存分配就是 从堆上分配。2、引用与指针有什么区别？1）引用必须被初始化，指针不必。2）引用初始化后不能被改变，指针可以改变所指的对象。3）不存在指向空值的引用，但是存在指向空值的指针。问题扩展：2.1什么是引用，什么是指针？引用只是一个变量的别名，程序中的应用不占据实际的内存空间，而指针则是一 个数值，其意义就是被指向数据所存放的内存地址，而指针同样也是一个数据， 他的存放需要占据内存空间。使用引用来代表其它变量吋，对于整个程序而言会更加安全。而使用指针可以使 得整个程序更加灵活

6、。9月16日1、描述实时系统的基木特性在特定的吋间内完成特定的任务，实吋性与可靠性。2、什么是平衡二叉树？左右子树都是平衡二叉树，且左右子树的深度差值的绝对值不大于13、堆栈溢出一般是由什么原因造成的? 没有回收垃圾资源4、什么函数不能声明为虚函数？constructor问题扩展：4.1什么是虚函数？a) 简单地说，那些被virtual关键字修饰的成员函数，就是虚函数。虚函数的 作用，用专业术语来解释就是实现多态性(polymorphism),多态性是将接口与 实现进行分离；用形象的语言来解释就是实现以共同的方法，但因个体差异而采 用不同的策略。b) 虚函数用來表现基类和派生类的成员函数z间的

7、一种关系.虚函数的定义在基类中进行，在需要定义为虚函数的成员函数的声明前冠以关键 字 virtual.基类中的某个成员函数被声明为虚函数后，此虚函数就可以在一个或多个派牛类 中被重新定义.在派生类屮重新定义时，其函数原型，包括返回类型,函数名，参数个数，参数类型及 参数的先后顺序，都必须与基类中的原型完全相同.虚函数是重载的一种表现形式，是一种动态的重载方式4.2为什么使用虚函数通过对彖指针进行的普通成员函数调用，仅仅与指针的类型有关，而与此刻正指向 什么对象无关要想实现当指针指向不同对象时执行不同的操作，就必须将基类相 应中的成员函数定义为虚函数4.3虚函数与重载函数的关系一般的重载函数，函

8、数的返回类型及所带的参数必须至少有一样不完全相同，只需 函数名相同即可.基类中定义的虚函数在派生类中重新定义时，其函数原型，包括返回类型，函数名, 参数个数，参数类型及参数的先后顺序,都必须与基类中的原型完全相同.重载虚函数时，若与基类中的函数原型出现不同，系统将根据不同情况分别处理：(1) 仅仅返回类型不同，其余相同，系统会当作出错处理；(2) 函数原型不同，仅仅函数名相同，系统会认为是一般的函数重载,将丢失虚特性 4.4纯虚函数仅仅用來为要从基类屮派生的函数占据一个位置。纯虚函数在基类中没有定义，它们被初始化为0。任何用纯虚函数派生的类，都要自己提供该函数的具体实现。定义纯虚函数virtu

9、al void mymethod(void) = 0;5、冒泡算法的时间复杂度是什么？o(na2)问题扩展：5.1根据什么评价一个算法与数据结构算法执行过程中所占用的存储单元数目和算法执行的时间效率。占用的存储单元 数目和算法的执行效率一般是用其与结点数的关系给出的，前者称为空间复杂 度，后者称为时间复杂度。5.2常见算法时间复杂度：0(1):表示算法的运行时间为常量0(n):表示该算法是线性算法0 (log 2n):二分查找算法0(n2):对数组进行排序的各种简单算法，例如直接插入排序的算法。0(眄：做两个n阶矩阵的乘法运算0(2"):求具有n个元素集合的所有子集的算法0(n!):

10、求具有n个元素的全排列的算法优<劣0(1)<0(log 2n) <0(n) <0(n2)<0(2n)时间复杂度按数量级递增排列依次为：常数阶0仃)、对数阶0(log2n).线性阶 0(n)、线性对数阶0(nlog2n).平方阶0亦)、立方阶0(1?)、k次方阶0(的、 指数阶0)。6、写出float x与“零值”比较的讦语句解释：a) 因为浮点数并不能精确表示0,所以定义一定范围，小于这个范围就认为是0。 不同系统对浮点的范围有不同定义，这里的意思是足够小的数就是0ob) float类型的浮点数的精度可以精确小数点后面的6位数，所以当 x>0. 000001

11、&&x<-0. 000001就认为x是与0相等的数浮点数是非精确存储，只能设置一个精度，然后在允许误差内的就认为是相 等的；对浮点型数比较的时候用二二是不对的，如if （0二二x）这样来与0值比较是不 对的.9月17日1、不能做switch()的参数的类型是：switch()的参数不能为实型数问题扩展：1.1什么是实型数？实型数就是通常说的浮点数，包括float、double、long double等等类型。实 型文字常量可以用科学计数法形式或者普通十进制形式表示。如2e5, 1. 0这样的2、局部变量能否和全局变量重名？答：能，局部会屏蔽全局。要用全局变量，需要使用“:

12、”局部变量可以与全局变量同名，在函数内引用这个变量时，会使用到同名的局部 变量，而不会用到全局变量。对于某些编译器而言，在同一个函数内可以定义多 个同名的局部变量，比如在两个循环体内都定义一个同名的局部变量，而那个局 部变量的作用域就在那个循环体内。3、如何引有一个己经定义过的全局变量？答:extern可以用引用头文件的方式，也可以用extern关键字，如果用引用头文件方式引用 某个在头文件中声明的全局变量，假定你将那个变量写错了，那么在编译期间会 报错，如果你用extern方式引用时，假定你犯了同样的错误，那么在编译期间不 会报错，而在连接期间报错。4、全局变量可不可以定义在可被多个c文件包

13、含的头文件屮？为什么？ 答：可以。在不同的.c文件中以static形式来声明同名全局变量。可以在不同的c文件中声明同名的全局变量，前提是其中只能有一个.c文件中对 此变量赋初值，此时连接不会报错。5、队列和栈有什么区别？队列先进先出，栈后进先出问题扩展：5.1什么是队列？队列简称队，是线性表的一种特殊形式，是一种应用很广的数据结构。对于它的 所有插入在表的一端进行，所有删除在表的另一端进行。从一端进队，从另一端 出队，即先进先出原则，称为先进先出表(first in first out)o9月18日 1、关键字const有什么含意？ 我只要一听到被面试者说：const意味着常数，我就知道我正在

14、和一个业余者 打交道。去年dan saks已经在他的文章里完全概括了 const的所有用法，因此 esp(译者：embedded systems programming)的每一位读者应该非常熟悉const 能做什么和不能做什么如果你从没有读到那篇文章，只要能说出const意味着 只读就可以了。尽管这个答案不是完全的答案，但我接受它作为一个正确的答 案。(如果你想知道更详细的答案，仔细读一下saks的文章吧。)如果应试者能正确回答这个问题，我将问他一个附加的问题：下面的声明都 是什么意思？const int a;int const a;const int *3；int * const a;int

15、 const * a const;/*/前两个的作用是一样，a是一个常整型数。第三个意味着&是一个指向常整 型数的指针(也就是，整型数是不可修改的，但指针可以)。第四个意思a是一 个指向整型数的常指针(也就是说，指针指向的整型数是可以修改的，但指针是 不可修改的)。最后一个意味着a是一个指向常整型数的常指针(也就是说，指 针指向的整型数是不可修改的，同时指针也是不可修改的)。如果应试者能正确 冋答这些问题，那么他就给我留下了一个好印象。顺带提一句，也许你可能会问, 即使不用关键字，也还是能很容易写出功能正确的程序，那么我为什么还要如 此看重关键字const呢？我也如下的几下理由：1)

16、关键字const的作用是为给读你代码的人传达非常有用的信息，实际上, 声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时 间清理其它人留下的垃圾，你就会很快学会感谢这点多余的信息。(当然，懂得 用const的程序员很少会留下的垃圾让别人來清理的。)2) 通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的 代码。3) 合理地使用关键字const可以使编译器很自然地保护那些不希望被改变 的参数，防止其被无意的代码修改。简而言之，这样可以减少bug的出现。2、数据声明(data declarations) 用变量3给岀下面的定义a) 一个整型数(an intege

17、r)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 tointegers)f) 一个指向有10个整型数数组的指针(a pointer to an array of 10 integers)g) 一个指向函数的指针，该函数有一个整型参数并返回一个整型数(a

18、pointer to a functionthat takes an integer as an argument and returns an integer)h) 一个有10个指针的数组，该指针指向一个函数，该函数有一个整型参数 并返冋一个整型数(an array of ten pointers to functions that take an intoger argument and rcturn am integer )答案是：a) int a; / an integerb) int *a; / a pointer to an integerc) int *a; / a pointe

19、r to a pointer to an integerd) int a10; / an array of 10 integerse) int *a10; / an array of 10 pointers to integersf) int (*a)10; / a pointer to an array of 10 integersg) int (*a)(int); / a pointer to a function a thattakes an i nteger argument and returns an i ntegerh) int (*q10) (int); / an array

20、of 10 pointers tofunctions that take an integer argument and return an integer 人们经常声称这里有儿个问题是那种要翻一下书才能回答的问题，我同意这种说 法。当我写这篇文章时，为了确定语法的正确性，我的确查了一下书。但是当我 被面试的吋候，我期望被问到这个问题(或者相近的问题)。因为在被面试的这 段时间里，我确定我知道这个问题的答案。应试者如果不知道所有的答案(或至 少大部分答案)，那么也就没有为这次面试做准备，如果该面试者没有为这次面 试做准备，那么他乂能为什么岀准备呢？3、写一个标准宏mtn ,这个宏输入两个参数并

21、返冋较小的一个。 ttdefine min (a, b) (a) <= (b) ? (a) : (b)这个测试是为下面的目的 而设的：1) 标识define在宏中应用的基本知识。这是很重要的。因为在 嵌入(inline) 操作符 变为标准c的一部分之前，宏是方便产生嵌入代码的唯一方法，对于嵌 入式系统来说，为了能达到要求的性能，嵌入代码经常是必须的方法。2) 三重条件操作符的知识。这个操作符存在c语言屮的原因是它使得编译器 能产生比if-then-else更优化的代码，了解这个用法是很重要的。3) 懂得在宏中小心地把参数用括号括起来4) 我也用这个问题开始讨论宏的副作用，例如：当你写下面

22、的代码时会发生什 么事？least = min(*p+, b);(这个没看懂)9月23日 1、冒泡算法 void bubblesort (int* pdata, int count) int itemp;for(int i = l;i<count;i+)for (int j=countl;j>=i;j-)if(pdataj<pdataj-l)itcmp = pdataj-1; pdataj-l = pdataj; pdataj = itemp;main ()int d5 = 1, 9, 3, 5, 2; bubblesort (d, 5);for(int i=0;i<5

23、;i+)cout<<di<<endl;2、字符串逆序输出char* rcvcrscstr(char* src)int len = strlen(src);char* dest 二(char*)malloc (1en+1);char* d 二 dest;char* s = &srclcn-l;while (len-!=0)*d+=*s-;*d=0;return dest;main ()char * str = reversestr (z，hel lo, wordl!/z); printf (，z%sn/z, str);free (str);3、josehpus 问

24、题struct josephusint code;josephus * next;void main()int number;int interval;int start;cout<<z/pleasc in put the nu mbcr of childr cn: “； cin>>number;cout<</zplease input the interval number: “； cin>>interval;cout"please input the start number of children: cin>>star

25、t;josephus * ptrjose 二 new josephusnumber; josephus * ptrcurrent 二 ptrjose;for(int i二l;i二number;i+) ptrcurrent->next=ptrjose+i%number; ptrcurrent->code=i;ptrcurrent二ptrcurrent->next;ijcout<<endl;josephus * pivot;if (start0 && start二number)if(start二二1) ptrcurrent二&ptrjosenu

26、mber-1;else ptrcurrent=&ptrjosestart-2;elsecout"start numbcr error.; return;while (ptrcurrent->next!二ptrcurrent)for(int i二0;iintcrval;i+) pivot=ptrcurrent; ptrcurrent二ptrcurrent->next;iscout<<，zno.，z<<setw(4) <<ptrcurrent->code<<，z eliminated. /z<<endl

27、;pivot->next=ptrcurrent->next;ptrcurrent二pivot;cout<<endl; coutthe winner is/z<<setw(4) <<ptrcurrent->code<<endl;delctc ptrjosc;4、快速排序 int data9 = 54, 38, 96, 23, 15, 72, 60, 45, 83; void quick sort (int data, int 1 ow, int high) "int i, j, pivot;if (1ow < hi

28、gh)pivot=datalow; i二low;j二high;wh订e (i<j)while (i<j && dataj>=pivot)j； if (i<j)datai+=dataj ;/«±eeaod%ca%di 匝%0%0用呀口忧while (i<j && datai<=pivot)i+； if(i<j)dataj-=datai;/%«±总肪站%0%'就a%, i3hedatai=pivot;/x i00i»0aquick sort(data, 1ow, il

29、);quick sort(data, i + 1, high);void main()quicksort (data, 0, 8); for(int i=0;i<8;i+)cout<<datai<<endl;下面是对这段程序的分析：“pivot二datalow表示将最低端即第一个元素作为枢轴记录，暂存到pivot中去， “while(ivj)”表示当高低指针相遇时循环终止,否则继续。“while (i<j && data|jj>=pivot) j；”表示从高端(即数组后面)开始搜索，直到搜索到一个比枢轴值小的某个元素，条 件-dataj

30、>=pivof5用的是大于或等于号，可见，在搜索过程中若遇到相等的则跳过并继续搜 索，条件“i<j"不可少，因为在搜索过程中，low与high可能相遇，此“ivj”跟外层while的条 件“ivj”无关，作用各不相同，外层while的条件“iv广是判断在进行从高端向低端搜索一趟、 从低端向高端搜索一趟之后高低指针是否相遇，而前者却是在单向的搜索过程中为防止高低 指针相遇。当经过“while (ivj && datafjl>=pivot) j-;的搜索z后，搜索到一个比枢轴小的元素，因 为在搜索完z后i、j可能相等，若相等，就没有交换的必要，因此紧接下

31、面设置了一个判 断“if(ivj)”,若成立，那么就要将比枢轴记录小的记录移到低端“datai+二dataj;”,这里的 “datai+表示先使用了 datai之后才加1,相当于udatai=data|jj; i+;”两句的效果。为什 么要i+?是因为刚交换的记录肯定比枢轴小，那么紧接下面的语句“while (i<j && dataiv=pivot)"就少了一次不必要的比较(因为：dataiv二pivot必定成立，而i<j在前面的 if语句中已成立，贝！|"ivj && datai<=pivof,必成立，若没有i+, whi

32、le中的""ivj && dataiv=pivot"”在肯定成立的情况卜执行了一次),提高了效率。执行“datai+二dataj;”之 后，高端的dataj覆盖了 datai的值，第一次覆盖时，覆盖的是dataflow因为最开始 时，“pivot二datalow;"将最低端即第一个元素作为枢轴记录暂存到pivot中去了，所以不必 担心，会丢失信息，由于dataj的值赋给了 datai,那么dataj原来的位置j就可以看做一 个空白，下一次覆盖时，就将低端的datai复制到这个位置。紧接下来的“while (i<j &&

33、; datai<=pivot) i+;”是从低端向高端搜索，直到找到一个 比枢轴大的元素，先进行判断“if(ivj)”，若成立,如前所述,执行“dataj二datai;”就将低端 的datai£制到上次赋值后空出的j位置。如此反复，直到外层while的条件不成立，即i=j,即高低指针相遇，表示已经找到了 枢轴记录pivot的最终位置i,执行“datai二pivot;"于是，枢轴记录移到最终位置。接下來的 4<quick_sort(data,low,i-1 )； quick_sort(data,i+1 ,high);”表示,对被 pivot 分开的左右子序列进 行

34、递归的快速排序。char型转换成long型 long myatol(const char* src)long 1=0;const char* p 二 src;while(*p !二0')1 = 1*10 + (int) (*p - ' o'); p+；return 1;反转字符串char* rcvcrscstr(char* src)int len = strlen(src);char* dest = (char*)malloc(len+1); /ia ?0" 0aad»,oi0%achar* d 二 dest;char* s = &srclc

35、n-l; /char* s = src + lcn - 1;while(len- != 0)*d+ = *s-;*d二'0'return dest;main ()char* test = "hello world!，z; cout<< reversestr (test) <<endl;int型转char型char* reversestr(char* src)int lcn 二 strlcn(src);/ta' 0' oaao», 6c0%asrc + len - 1;char* dest = (char)malloc(

36、len+1);char* d = dest;char* s = &srclen-l; /char* s wh订e(len- != 0)*d+ 二 *s；*d二'0'return dest;char* myitoa(int n, char* dest)bool sign = (n>0);if (!sign)n 二一n;char* d 二 dest;do*(d+) = (char) (n%10 +，o');while(n /- 10) > 0);if (! sig n)* (d+)二'-'*d二'0'char* resul

37、t 二 reversestr(dest); return result;main()int i二-321;char* dest = (char*)malloc(20); cout<< myitoa(i, dest) <<endl;int 型转 char*char* itoh(int n)char* buff = (char)malloc(11);buff0= o'buff 1二'x'buff 10二'0,;char* temp = buff + 2;for(int i=0;i<8;i+)tempi = (char)(n<<

38、;4*i>>28);tempi=tempi>=0 ? tempi : tempi+16; tempi=tempi<10 ? tempi+48 : tempi+55;return buff;main()int i二120;cout<< itoh (i) <<endl;递归反序输出void invcrsc(cheir* p)if (*p = ' 0')return;inverse( p+1 );printf(z，%cz，, *p);main () char* test 二"hello world! inverse( test

39、);cout<<cndl;求组合数：求n个数的组合int n, nom100 ; /*n存放在排列的数的个数,nom存要要排列的数*/!" !" !" !" !" !" !" !“ 7“ !“ 夕a、夕a、夕a、夕a、夕a、夕a、夕a、卜/void ininto /*接收输入函数*/int i;printf ("please input the number n二“)； scanf (d，&n);printf (z，plcasc in put %d nu mbcrs: rt, n); for(i

40、=0;i<n;i+)scanf (，z%d，z，&nomi);/ vzl l l l l l l l l / 吓、吓、吓、吓、吓、吓、吓、|>/void swap(int *a, int *b) /*交换函数*/ int tcmp;temp二*a;*3二*b;*b二temp;/ lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lz l lzl lzl lz lz/ztx zt

41、x ztx ztx ztx ztx ztx ztx/void print () /*打印输岀函数*/ int i;for(i=0;i<n;i+) printf(%d “, nomi); printf (，n，/);!“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“ !“/ /int sort (int k) /*回

42、溯函数*/ int i;if (k 二二 n)print (); return (0);for (i=k;i<n;i+)swap(&nomi, &nomk); sort (k+1);swap(&nomi, &nomk); /lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz lz l / /void main() /*主函数*/ inint ();sort (0);测试please input the numbcr n= 3

43、please input 3 numbers:1351 3 51 5 33 1 53 5 15 3 15 1 3求组合数：求n个数仃n）中k个数的组合# define max' 100 int amaxn;void comb(int m, int k)int i, j;for (i二m;i>=k;i-) ak=i; if (k>l) comb (il, kl);elsefor (j=a0 ; j>0; j) printf (，z%2d，z, aj);printf(rt);void ni3in()int n, m;printf("please input tw

44、o number:n)； scanf(d， &n);scanf ("%d，&m);a0=m;printf(combination result: n"); comb (n, m);测试please input two number:53combination result:5 4 35 4 25 4 15 3 25 3 15 2 14 3 24 3 1题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定 义如下：struct listnodeintm_nkey;listnode* m_pext;分析：这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面 试、笔试题中。看到这道题后，第一反应是从头到尾输出比较简单。于是很li然地想到把链表屮 链接结点的指针反转过来，改变链表的方向。然后就可以从头到尾输岀了。反转 链表的算法详见本人面试题精选系列的第19题，在此不