====
7、交换两个变量的值,不使用第三个变量,即a=3, b=5, 交换后b=3, a=5。
    unsigned char a = 3, b = 5;
    a = a + b; 
    b = a - b; 
    a = a - b; 
或者 
    a = a ^ b; 
    b = a ^ b; 
    a = a ^ b;
如果写成函数：
void swap(int a,int b)
{ 
    a = a ^ b; 
    b = a ^ b; 
    a = a ^ b;
}
或者
void swap(int a, int b)
{ 
    a = a + b; 
    b = a - b; 
    a = a - b; 
}
不过这两种方法只是修改了函数的形参，如果要修改实参，可以采用如下的方法:
void swap(int* a, int *b)
{ 
    *a = *a ^ *b; 
    *b = *b ^ *a; 
    *a = *a ^ *b; 
    printf("In %s:a=%d,b=%d\n",__FUNCTION__,*a,*b); 
}
权重：较高
备注：主要考察对数据在硬件中的存储规则

====
11、如何判别一个数是unsigned？
#define issignal(x) ((x>=0 && ~x>=0) ? 1:0) //为1是无符号 为0有符号
权重：较高
备注：可以直接记住。
    signed最高位只是用来做标记(sign)，标记整数的正负，0表示正，1表示负。
    signed都是正数，而unsigned有正数有负数

====
试题1：请写一个C函数，若处理器是Big_endian的，则返回0；若是Little_endian的，则返回1
解答： 
int checkCPU()
{
    union w
    { 
        int a;
        char b;
    } c;
    c.a = 1;

    return (c.b == 1);
}
剖析：
　 　嵌入式系统开发者应该对Little-endian和Big-endian模式非常了解。采用Little-endian模式的CPU对操作数的存放方式是从低字节到高字节，而Big-endian模式对操作数的存放方式是从高字节到低字节。例如，16bit宽的数0x1234在Little-endian模式CPU内存中的存放方式（假设从地址0x4000开始存放）为：
内存地址 存放内容 
0x4000 0x34 
0x4001 0x12 
　　而在Big-endian模式CPU内存中的存放方式则为：
内存地址 存放内容 
0x4000 0x12 
0x4001 0x34 
　　32bit宽的数0x12345678在Little-endian模式CPU内存中的存放方式（假设从地址0x4000开始存放）为：
内存地址 存放内容 
0x4000 0x78 
0x4001 0x56 
0x4002 0x34 
0x4003 0x12 
　　而在Big-endian模式CPU内存中的存放方式则为：
内存地址 存放内容 
0x4000 0x12 
0x4001 0x34 
0x4002 0x56 
0x4003 0x78 
　　联合体union的存放顺序是所有成员都从低地址开始存放，面试者的解答利用该特性，轻松地获得了CPU对内存采用Little-endian还是Big-endian模式读写
权重：高

====
试题2：写一个函数返回1+2+3+…+n的值（假定结果不会超过长整型变量的范围） 
解答
int Sum( int n )
{ 
　 return ( (long)1 + n) * n / 2;　　//或return (1l + n) * n / 2;

}
剖析：
对于这个题，只能说，也许最简单的答案就是最好的答案。下面的解答，或者基于下面的解答思路去优化，不管怎么“折腾”，其效率也不可能与直接return ( 1 l + n ) * n / 2相比。
权重：中

====
42、编一个简单的求n!的程序
权重：中

====
26:写一语句实现x是否为2的若干次幂的判断。
参考答案：!(X)&(X-1)
权重：较高
备注：理解并记住

====
3 一语句实现x是否为2的若干次幂的判断
int i = 512;
cout << boolalpha << ((i & (i - 1)) ? false : true) << endl;
权重：中

===
5.下面算法中可以判断出一个有向图是否有环的是(BD)[多选]
A.求短路径
B.深度优先遍历
C.广度优先遍历
D.拓扑排序
分析：判断无向图 中是否存在回路（环）的算法描述
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。
算法：
第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。
第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点，则存在环，否则没有环。
有向图是否有环的判定算法，主要有深度优先和拓扑排序两种方法。
权重：中

====
15.线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为©
A O(i)
B O(1)
C O(n)
D O(i-1)
权重：中

====
17.对一个含有20个元素的有序数组做二分查找，数组起始下标为1，则查找A[2]的比较序列的下标为(B)

A 9,5,4,2
B 10,5,3,2
C 9,6,2
D 20,10,5,3,2
解析：
(high-low)/2+low = middle; 下标从1开始，因为查找查找A[2]， low始终为1；
20-1）/2+1=10;
(10-1)/2+1 = 5;
(5-1)/2+1 = 3;
(3-1)/2+1 = 2;
权重：中

====
25.以下()属于线性分类器佳准则?（ACD）【多选】
A 感知准则函数
B 贝叶斯分类
C 支持向量机
D Fisher准则
权重：较低

====
1、写出两个排序算法，并说明哪个好?
答：一般使用冒泡法和快速排序法，对堆栈局域比较小的单片机来说冒泡法比较好，对时间要求苛刻的实时响应来说快速排序法好。
题注：时间复杂度：一个算法花费的时间与算法中语句的执行次数成正比例，用T(n)表示，n为问题的规模，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。时间频度不同，但时间复杂度可能相同。如：T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
本题中，最坏的情况要计算9+8+7+6+5+4+3+2+1次，即n的级数，结果为n（n/2）=n2/2。所以冒泡法时间复杂度O（n2）
1） 冒泡法：从小到大排，时间复杂度On2
#define MAX_NUM 10
int a_data[MAX_NUM]={1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; // 也可以用scanf获取
int main(void)
{
    int i=0, j=0, tmp=0;
    for(i=0; i<MAX_NUM-1; i++) {
        for(j=i+1; j<MAX_NUM; j++) {
            if(a_data[i] > a_data[j]) { // 如果i不是小于j，则调换
                tmp = a_data[i];
                a_data[i] = a_data[j];
                a_data[j] = tmp;
            }
        }
    }
    return 0;
}

2）交换排序-快速排序，类似于二分法：采用递归。选第一个点或中间的点，左边放最小值，右边放最大值，依次递归到最低层的两个元素。因为每递归一次要压栈一次，占用存储空间，所以空间复杂度较高。时间复杂度Onlog2n
#define MAX_NUM 16
int a_data[MAX_NUM]={1, 2, 3, 4, 5, 6, 7, 8, 9, 0,11,12,13,14,15,16}; // 也可以用scanf获取
//快速排序  
void quick_sort(int s[], int l, int r)
{
	if (l < r)
	{
		//Swap(s[l], s[(l + r) / 2]); // 将中间的这个数和第一个数交换 可换可不换  
		int i = l, j = r, x = s[l]; // s[l]会先被替换，最后这个值会被写回到s[i]，它们也充当了临时变量的角色
		while (i < j)
		{
			while (i < j && s[j] >= x) // 从右向左找第一个小于x的数  
				j--;
			if (i < j)
				s[i++] = s[j];

			while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数  
				i++;
			if (i < j)
				s[j--] = s[i];
		}
		s[i] = x;
		quick_sort(s, l, i - 1); // 递归调用   
		quick_sort(s, i + 1, r);
	}
}
int main(void)
{
    sort(a_data, 0, MAX_NUM - 1);
}
权重：高

====
21、可重入函数的条件有哪些？
答：主要用于多任务环境中，可被中断。除了自己栈上的变量外不调用全局变量（即便少量使用也要用同步与互斥进行保护）；不能调用malloc和free；操作硬件时屏蔽硬件中断，操作完成后释放硬件中断。

====
1、将一整数逆序后放入一数组中（要求递归实现）
void convert(int *result, int n) {
     if(n>=10)
         convert(result+1, n/10);
     *result = n%10; 
}

int main(int argc, char* argv[]) {
     int n = 123456789, result[20]={};
     convert(result, n);
     printf("%d:", n);
     for(int i=0; i<9; i++)
         printf("%d", result[i]);
}
权重：中

====
2、求高于平均分的学生学号及成绩（学号和成绩人工输入）
答：
double find(int total, int n) {
     int number, score,  average;
     scanf("%d", &number);
     if(number != 0) {
         scanf("%d", &score);
         average = find(total+score, n+1);
         if(score >= average)
              printf("%d:%d\n", number, score);
         return average;
     } else {
         printf("Average=%d\n", total/n);
         return total/n;
     }
}
int main(int argc, char* argv[]) {
     find(0, 0);
}
权重：中

====
3、递归实现回文判断（如：abcdedbca就是回文，判断一个面试者对递归理解的简单程序）
int find(char *str, int n) {
     if(n<=1) return 1;
     else if(str[0]==str[n-1])   return find(str+1, n-2);
     else     return 0;
}
int main(int argc, char* argv[]) {
     char *str = "abcdedcba";
     printf("%s: %s\n", str, find(str, strlen(str)) ? "Yes" : "No");
}
权重：较高
 
====
8.冒泡排序算法的时间复杂度是什么？
      时间复杂度是O(n^2)。
权重：中

====
2.数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
答
算法思想：先对1..N-1之间的所有整数累加求和，再对数组中的所有元素累加求和；用后者减去前者得到的差就是重复的数字。
参考源代码(C++)：
#include "iostream.h"

void main()
{
    int arr[] = {6, 2, 3, 4, 3, 5, 1};
    int N = 7;
    int sum1, sum2;
    int i;

    for(i=1,sum1=0; i<N; sum1+=i,i++);
    for(i=0,sum2=0; i<N; sum2+=arr[i],i++);
    cout<<"重复的数字是 "<<sum2-sum1<<endl;
}
时间复杂度：O（n）
算法特点：对于数组中数值的出现顺序不做任何要求，即无需有序（这是二楼算法的缺陷）。
权重：中

====
2.写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。函数接口为：int find_orderk(const int* narry,const int n,const int k) 
要求算法复杂度不能是O(n^2）
答：
    可以先用快速排序进行排序，其中用另外一个进行地址查找
代码如下，在VC++6.0运行通过。
//快速排序
#include <iostream>
using namespace std;
int Partition (int *L, int low, int high)
{
    int temp = L[low];
    int pt = L[low];

    while (low < high)
    {
        while (low < high && L[high] >= pt)
            --high;
        L[low] = L[high];
        while (low < high && L[low] <= pt)
            ++low;
        L[low] = temp;
    }
    L[low] = temp;

    return low;
}

void QSort (int*L, intlow, int high)
{
    if (low < high)
    {
        int pl = Partition (L, low, high);

        QSort (L, low, pl - 1);
        QSort (L, pl + 1, high);
    }
}

int main()
{
    int narry[100], addr[100];
    int sum = 1, t;

    cout << "Input number:" << endl;
    cin >> t;

    while (t != -1)
    {
        narry[sum] = t;
        addr[sum - 1] = t;
        sum++;

        cin >> t;
    }

    sum -= 1;
    QSort (narry,1,sum);

    for (int i = 1; i <= sum;i++)
        cout << narry[i] << '\t';
    cout << endl;

    int k;
    cout << "Please input place you want:" << endl;
    cin >> k;

    int aa = 1;
    int kk = 0;
    for (;;)
    {
        if (aa == k)
            break;
        if (narry[kk] != narry[kk + 1])
        {
            aa += 1;
            kk++;
        }
    }

    cout << "The NO." << k << "number is:" << narry[sum - kk] << endl;
    cout << "And it's place is:" ;
    for (i = 0; i < sum; i++)
    {
    if (addr[i] == narry[sum - kk])
        cout << i << '\t';
    }

    return 0;
}
权重：较高

====
3、用递归算法判断数组a[N]是否为一个递增数组。
答：
递归的方法，记录当前最大的，并且判断当前的是否比这个还大，大则继续，否则返回false结束：
bool fun( int a[], int n )
{
    if( n == 1 )
    return true;
    if( n == 2 )
    return a[n-1] >= a[n-2];
    return fun(a, n-1) && ( a[n-1] >= a[n-2] );
}
权重：较高
备注：嵌入式使用递归要特别注意，事先预估好可能的递归次数，每次函数压栈时占用的空间，不要堆栈溢出了

====
5 设周期性任务P1,P2,P3的周期为T1,T2,T3分别为100，150，400；执行时间分别为20，40，100。请设计一种调度算法进行任务调度，满足任务执行周期及任务周期。
答：
1.  任务当然可以分段执行，不然P3执行时间100大于P1最大的间隔时间80（100-20，即从P1本次执行完毕到下次开始执行的间隔），无论如何都不可能。
2.  整个调度是可以循环的，即我们假设在一个时间轴上安排了一系列的任务运行，时间轴在某时刻与0时刻重合，这样就可以一直进行下去
权重：中