1、嵌入式软件面试笔试重点总结1. 形参是放在栈里面吗？变量都是放在栈里的，不同的变量放在不同的栈里；类中的变量，放在类的栈里，所以只要这个类不存在了，类的栈pop掉了，类中的变量也就没用了；方法中的变量放在方法的栈里，所以只要这个方法执行完了，方法的栈pop掉了，方法中的变量也就没用了代码块中的变量放在代码块的栈里，所以只要这个代码块执行完了，代码块的栈pop掉了，代码块中的变量也就没用了。2. 时间和空间复杂度对于给定的一个算法，要做两项分析，第一是从数学上证明算法的正确性，第二是分析算法的时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不
2、相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。常见的算法时间复杂度由小到大依次为：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!)求解算法的时间复杂度的具体步骤是：找出算法中的基本语句；算法中执行次数最多的那条语
3、句就是基本语句，通常是最内层循环的循环体。计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。用大记号表示算法的时间性能。将基本语句执行次数的数量级放入大记号中。如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是(1)。其中(log2n)、(n)、 (nlog2n)、
4、(n2)和(n3)称为多项式时间，而(2n)和(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n)和 T2(n)=O(g(n),则 T1(n)+T2(n)=O(max(f(n), g(n)乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n)和 T2(n)=O(g(n),则 T1*T2=O(f
5、(n)*g(n)(1) 若g(n)=O(f(n),则O(f(n)+ O(g(n)= O(f(n)；(2) O(Cf(n) = O(f(n),其中C是一个正常数注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性
6、比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。3. 链表单向链表双向链表遍历查找插入创建一个链表：#include#includestructLNodeint data;structLNode *next; /*上面只是定义了一个结构体类型，并未实际分配内存空间只有定义了变量才分配内存空间*/structLNode *create(int n)inti;structLNode *head,*p1,*p2;
7、/*head用来标记链表，p1总是用来指向新分配的内存空间，p2总是指向尾结点，并通过p2来链入新分配的结点*/int a;head=NULL;for(i=1;idata=a;if(head=NULL) /*指定链表的头指针*/head=p1;p2=p1;else p2-next=p1;p2=p1;p2-next=NULL;/*尾结点的后继指针为NULL(空)*/return head;/*返回链表的头指针*/void main()int n;structLNode *q;printf(请输入链表的长度：/n);scanf(%d,&n);q=creat(n);/*链表的头指针(head)来标记
8、整个链表*/printf(/n链表中的数据：/n);while(q)/*直到结点q为NULL结束循环*/printf(%d ,q-data);/*输出结点中的值*/q=q-next;/*指向下一个结点*/4. 环形表写一个循环链表对于一个循环链表来说,其首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。#include#includetypedefstructnodecharname20;structnode*link;student;student*create(
9、intn)/*建立单链表的函数，形参n为人数*/*h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/student*p,*h,*s;inti;if(h=(student*)malloc(sizeof(student)=NULL) /*分配空间并检测*/printf(不能分配内存空间!);exit(0);h-name0=0;/*把表头结点的数据域置空*/h-link=NULL;/*把表头结点的链域置空*/p=h;/*p指向表头结点*/for(i=0;ilink=s;/*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/printf(请输入第%d个人
10、的姓名,i+1);/指向结构体中的数据scanf(%s,s-name);s-link=NULL;p=s;/如果是单向链表，这里为NULL，环形链表需要指向保存表头节点的指针。p-link=h;return(h);intmain(void)intnumber;student*head;/*head是保存单链表头结点地址的指针*/student*p;printf(请输入相应的人数:n);scanf(%d,&number);head=create(number);/*把所新建的单链表头地址赋给head*/p=head;while(p-link) printf(%sn,p-name);p=p-link
11、;return0;5. 有两个有序链表，合并成一个有序链表#includetypedefstruct Node int value; struct Node*next;Node*ListMerge(Node*head1,Node*head2)Node*head=NULL;/合并后的头指针Node *p=NULL;/永远指向最新合并的结点Node*p1=head1;/p1用于扫描链表1Node*p2=head2;/p2用于扫描链表2if(!head1)returnhead2;if(!head2)returnhead1;if(head1-valuevalue) /升序排列head=head1;p1
12、=head1-next;elsehead=head2;p2=head2-next;Node*p=head;/p永远指向最新合并的结点while(p1&p2)/如果循环停止，则p1或p2至少有一个为NULLif(p1-valuevalue)p-next=p1; /链接最新的节点p1=p1-next;/遍历下一个节点elsep-next=p2; /链接最新的节点p2=p2-next;/遍历下一个节点p=p-next; /指向最新的节点if(p1) /如果链1还没走完p-next=p1;elseif(p2) /如果链2还没走完p-next=p2;returnhead;6. 单向链表和双向链表区别和应
13、用场合：双向链表其实是单链表的改进。当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。7. 排序重点冒泡法：voidBubble_Sort(int*num,intn)inti,j;for(i=0;in-1;i+)/n
14、个数,要进行n-1次比较,因为第一个数不用和自身比较.for(j=0;i+jnumj+1)inttemp=numj;numj=numj+1;numj+1=temp;8. &是什么作用呢？让某一位清零，也就是最低位清零，而其他位保持不变，|呢？让某一位置1，其他保持不变，是异或运算。9. Q化运算Q15？表示范围-1X0.9999695Q31？不同的Q所表示的数不仅范围不同，而且精度也不相同。Q越大，数值范围越小，但精度越高；相反，Q越小，数值范围越大，但精度就越低。10. 堆，栈：stack 又称系统栈(system stack)，用于：保存函数调用后的返回地址;给局部变量分配存储空间;传递函
15、数参数;保存临时结果;heap -编译器提供的运行时支持库的一些函数(如malloc/calloc/realloc)，允许运行时为变量动态分配存储器。这些存储器就放置在.system段的全局池(global pool)或堆(heap)中。这个动态存储池的大小仅仅受限与系统中实际的存储容量。这2个选项都可以在project-build options的连接器选项中设置。11. 输出格式：%d十进制；%o八进制；%x十六进制；%c输出一个字符；%s输出一个字符串；%f输出一个小数；12. 动态申请内存（一维数组，二维数组）int*p=newintlength;一维数组deletep; /动态开辟空
16、间int*p=newint*m;/开辟行/释放开辟的资源for(inti=0;im;i+)for(i=0;iy) z = x; else z = y; return(z);int main() int max(int,int);int (*p)(int,int);用（*p）来替代函数名inta,b,c; p = max;scanf(%d,%d,&a,&b); c = (*p)(a,b);printf(a=%d,b=%d,max=%dn,a,b,c); return 0;定义一个函数的指针数组：int add1(int a1,int b1);int add2(int a2,int b2);int
17、 main(intargc,char* argv)int numa1=1,numb1=2;int numa2=2,numb2=3;int (*op2)(inta,int b); /指针变成了指针数组op0=add1;op1=add2;printf(%d %dn,op0(numa1,numb1),op1(numa2,numb2);getch();int add1(int a1,int b1)return a1+b1;int add2(int a2,int b2)return a2+b2;指针void 是一种特殊类型的指针。void 指针可以指向任意类型的数据，可以是整数，浮点数甚至字符串。唯一的
18、限制是被指向的数值不可以被直接引用（不可以对它们使用引用星号*），因为它的长度是不定的，因此，必须使用类型转换操作或赋值操作来把void 指针指向一个具体的数据类型。给空指针指向的地址赋值是错的，程序会崩溃。16. 二维数组哪个可以留空？定义数组时对第一维的长度可以不指定，但第二维的长度不能省，因为系统会根据总个数和第二维的长度计算出第一维的长度。因为二维数组是由若干个一维数组组成的，在内存中数组是按行存放的，因此，在定义二维数组时必须指定列数。17. 内联函数和宏定义的区别：内联函数和普通函数相比可以加快程序运行的速度，因为不需要中断调用，在编译的时候内联函数可以直接被镶嵌到目标代码中。避免
19、一些不必要拷贝和构造，提高工作效率而宏定义就是一个替代，相当于一个字符串18. 二叉树搜索遍历结果19. 二叉树的节点问题完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。20. 为什么不采用递归法：递归的效率低，主要是因为递归时会反复调用函数（递归函数）而函数发生调用时，程序会将当前的一些数据存入堆栈中（保存现场），等函数调用结束时，将堆栈中的数据再取出来（恢复现场）。函数调用时，是有开销的（占用堆栈资源，占用CPU时间）。无节制的递归会造成堆栈溢出21. Dijkstra算法步骤第几步问题Dijkstra算法是典型最短路算法，用于计算一个
20、节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。22. 常见算法排序的稳定性：若一个序列里面有重复的项，排完序这几个重复的项的相对位置没有发生变化，就是稳定的。不稳定排序算法：“快些选堆”“快”指快速排序，“些”指希尔排序，“选”指选择排序，“堆”指堆排序。其他自然都是稳定的。交换类排序：包括冒泡法排序以及快排快速排序：快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：选定一个key值，通过一趟排序将要排序的数据分割成key值两侧独立的两部分，其中一部
21、分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。代码：要明确递归调用结束条件，其中left=right时退出函数。对于void函数，return ; 表示退出该函数。选择排序：它的工作原理是每一次从无序组的数据元素中选出最小（或最大）的一个元素，存放在无序组的起始位置，无序组元素减少，有序组元素增加，直到全部待排序的数据元素排完。选择排序核心思想：从未排好的部分的第一个作为最小（最大）的，然后依次和剩余的比较，如果有更小（更大）的，记下下标，以此作为新的最小（最大）值，继续比较，一趟结束后，然后和第一个进行交换。代码如下：voidSelectionSort(intarray,int length) inti,min,j,temp = 0; for(i = 0;i length-1;i+) min = i;/ 每次讲min置成无序组起始位置元素下标for(j =
