嵌入式面试题（算法部分）

一、基础部分

1、数组与链表的区别？

（1）数组的元素个数在定义时就必须确定，且元素的类型必须一致；而链表的元素个数自由，且元素内可以有不同类型的数据。
（2）数组的元素在内存中是按顺序存储的，而链表的元素是随机存储的。
（3）要访问数组的元素可以按下标索引来访问，速度比较快；如果对它进行插入/删除操作的话，就得移动很多元素，所以对数组进行插入/删除操作效率很低。由于链表是随机存储的，如果要访问链表中的某个元素的话，那就得从链表的头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问的效率就比数组要低；链表在插入/删除操作上有很高的效率（相对数组）。一句话总结就是：数组的访问效率高，而链表的插入/删除效率高。

2、C语言程序代码优化方法

（1）选择合适的数据结构与算法；
（2）使用尽量小的数据类型；
（3）使用自加、自减指令；
（4）用移位实现乘除法运算；
（5）求余运算用&（如a=a%8改为a=a&7）；
（6）平方运算用*（如a=pow(a,2.0)改为a=a*a）；
（7）延时函数的自加改为自减；
（8）switch语句中根据发生频率来进行case排序；
（9）减少运算的强度。

3、堆和栈的的区别？

C语言内存分配的堆和栈	栈是向下生长的，栈中分配函数参数和局部变量，其分配方式类似于数据结构中的栈。堆是向上生长的，堆中分配程序员申请的内存空间（一旦忘记释放会造成内存泄漏），其分配方式类似于数据结构中的链表
数据结构的堆和栈	栈是一种先进后出的数据结构。堆是一种经过排序的树形数据结构（通常是二叉堆），每个结点都有一个值，根结点的值最小或最大，常用来实现优先队列，堆的存储是随意的

4、内联函数的优缺点和适用场景是什么？

（1）优点：内联函数与宏定义一样会在原地展开，省去了函数调用开销，同时又能做类型检查。

（2）缺点：它会使程序的代码量增大，消耗更多内存空间。

（3）适用场景：函数体内没有循环（执行时间短）且代码简短（占用内存空间小）

4、下面代码输出是什么？

#include<stdio.h> 
void main()  
{
      
    int a[5] = {
    1, 2, 3, 4, 5};  
    int *ptr = (int *)(&a + 1);  
    printf("%d, %d", *(a + 1), *(ptr - 1));  
}  

答案：输出为2, 5

解读： a是数组首元素地址，所以*(a + 1)就是第二个元素a[1]。&a是数组地址，所以&a +1是整个数组结尾的下一个地址，*(ptr - 1)就是a[4]。

5、结构体struct和联合体union的区别？

（1）两者最大的区别在于内存的使用。

（2）结构体各成员拥有自己的内存，各自使用且互不干涉，遵循内存对齐原则。

（3）联合体所有成员共用一块内存空间，并且同时只有一个成员可以得到这块内存的使用权。一个联合体变量的总长度应至少能容纳最大的成员变量，且需要进行内存补齐。

6、函数参数的传递方式有几种？

（1）两种：值传递、指针传递。
（2）严格来看，只有一种传递，值传递，指针传递也是按值传递的，复制的是地址。

7、堆和栈的的区别？

C语言内存分配的堆和栈	栈是向下生长的，栈中分配函数参数和局部变量，其分配方式类似于数据结构中的栈。堆是向上生长的，堆中分配程序员申请的内存空间（一旦忘记释放会造成内存泄漏），其分配方式类似于数据结构中的链表
数据结构的堆和栈	栈是一种先进后出的数据结构。堆是一种经过排序的树形数据结构（通常是二叉堆），每个结点都有一个值，根结点的值最小或最大，常用来实现优先队列，堆的存储是随意的。

二、算法部分

1、如何判读一个系统的大小端存储模式？

(1) 方法一：int 强制类型转换为char ，用“[]”解引用

void checkCpuMode(void)  
{
      
    int c = 0x12345678;  
    char *p = (char *)&c;  
    if(p[0] == 0x12)  
        printf("Big endian.\n");  
    else if(p[0] == 0x78)  
        printf("Little endian.\n");  
    else  
        printf("Uncertain.\n");  
}  

（2）方法二：int *强制类型转换为char ，用“”解引用

void checkCpuMode(void)  
{
      
    int c = 0x12345678;  
    char *p = (char *)&c;  
    if(*p == 0x12)  
        printf("Big endian.\n");  
    else if(*p == 0x78)  
        printf("Little endian.\n");  
    else  
        printf("Uncertain.\n");  
}  

（3）方法三：包含short跟char的共用体

void checkCpuMode(void)  
{
      
    union Data  
    {
      
        short a;  
        char b[sizeof(short)];  
    }data;  
    data.a = 0x1234;  
  
    if(data.b[0] == 0x12)  
        printf("Big endian.\n");  
    else if(data.b[0] == 0x34)  
        printf("Little endian.\n");  
    else  
        printf("uncertain.\n");  
}  

大端小端模式：

大端模式：是指一个数据的低位字节序的内容放在高地址处，高位字节序存的内容放在低地址处。

小端模式：是指一个数据的低位字节序内容存放在低地址处，高位字节序的内容存放在高地址处。

如：一个数0x12345678存放在一个4字节空间里
0x12345678中，1234属于高位，如果低地址的第一个字节存的0x12 则 是高位字节 存储在了低地址，是大端模式。
低地址 --------------------> 高地址
0x12 | 0x34 | 0x56 | 0x78

如：一个数0x12345678存放在一个4字节空间里
0x12345678中，1234属于高位，如果低地址的第一个字节存的0x12 则是高位字节 存储在了 高地址，是小端模式。
低地址 --------------------> 高地址
0x78 | 0x56 | 0x34 | 0x12

原文链接：https://blog.csdn.net/ALakers/article/details/116225089

2、验证回文串：给定一个字符串，验证它是否是回文串，只考虑字符和数字字符，可以忽略字母的大小写

（回文串即左右对称的字符串，如"A man, a plan, a canal: Panama"）

思路：双指针法，一个指针指向字符串开头，另一个指向字符串结尾，两个指针都往中间
移动并寻找字符和数字，并将字母统一转为小写，然后比较是否相同，若不相同则返回false，若相同则继续寻找……如此循环，若直到两指针相遇都没返回false，则返回true。

bool isPalindrome(char * s)  
{
      
    char *left = s, *right = s + strlen(s) - 1;  
  
    if(strlen(s) == 0) return true;  
      
    while(left < right)  
    {
      
        while(!((*left >= 'a' && *left <= 'z') || (*left >= 'A' && *left <= 'Z') || (*left >= '0' && *left <= '9')) && left < right)  // 找到字母或数字 
            left++;  
        while(!((*right >= 'a' && *right <= 'z') || (*right >= 'A' && *right <= 'Z') || (*right >= '0' && *right <= '9')) && right > left)  // 找到字母或数字 
            right--;  
          
        if(left < right)  
        {
      
            if((*left >= 'A' && *left <= 'Z'))  // 若为大写，则转为小写 
                *left = *left + 32;  
            if((*right >= 'A' && *right <= 'Z'))  // 若为大写，则转为小写 
                *right = *right + 32;  
  
            if(*left == *right)  // 比较 
            {
      
                left++;  
                right--;  
            }     
            else  
                return false;  
        }  
        else  
            return true;  
    }  
      
    return true;  
}  

3、写一个程序, 要求功能：求出用1，2，5这三个数不同个数组合的和为100的组合个数。 如：100个1是一个组合，5个1加19个5是一个组合。

（1）最容易想到的算法是暴力解法 思路：设x是1的个数，y是2的个数，z是5的个数，number是组合数，注意到0 <= x <=> 100，0 <= y <= 50，0 <= z <= 20。

void count(void)  
{
      
    int x, y, z, number;  
    number = 0;  
    for (x = 0; x <= 100 / 1; x++)  
    {
      
        for (y = 0; y <= 100 / 2; y++)  
        {
      
            for (z = 0; z <= 100 / 5; z++)  
            {
      
                if (x + 2 * y + 5 * z == 100)  
                number++;  
            }  
        }  
    }  
    printf("%d\t", number);  
}  

（2）上述暴力解法的时间复杂度为O(n³)，程序有些冗余，对其进行优化如下

思路：注意到上面代码的第三个for循环其实不是必要的，因为当1和2的数目确定了之后，加上一定数目的5能不能组成100也就确定了，没必要用for循环一个个去尝试，直接计算即可，优化后时间复杂度变为O(n2)。

void count(void)  
{
      
    int x, y, z, number;  
    number = 0;  
    for (x = 0; x <= 100 / 1; x++)   
    {
      
        for (y = 0; y <= 100 / 2; y++)  
        {
      
            if (100 - x - y * 2 >= 0 && (100 - x - y * 2) % 5 == 0) // 判断能否5整除 
            number++;  
        }  
    }  
    printf("%d\t", number);  
} 

4、判断链表是否有环。

思路：双指针法，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（fast> == NULL）都没有追上第一个指针，那么链表就不是环形链表。

bool IsLoop(NODE *head)   
{
      
    if (head == NULL)  
        return false;  
  
    NODE *slow = head -> next;  // 初始时，慢指针从第一个节点开始走1步 
    if (slow == NULL)  
        return false;  
  
    NODE *fast = slow -> next;  // 初始时，快指针从第一个节点开始走2步 
    while (fast != NULL && slow != NULL)  // 当单链表没有环时，循环到链表末尾结束 
    {
      
        if (fast == slow)  // 快指针追上慢指针 
            return true;  
        slow = slow -> next;  // 慢指针走一步 
        fast = fast -> next;  // 快指针走两步 
        if (fast != NULL)  
            fast = fast -> next;  
    }  
    return false;  
}