一、选择题

1、题目略，此处主要有一个考点，如下。

对于一个二维数组int a[3]，a和&a的值是一样的，但是也是有区别的。a+1的值会根据数组a的类型决定增加的大小，这里int类型大小为4个字节，所以a+1比a大4，而使用&之后，取出的地址是没有类型的，&a+1实际只比&a大1。

2、第二题简单，只要知道short类型占两个字节即可。

二、简答题

1、static关键字的作用，个人经验主要有以下几种：1）函数局部static变量，第一次函数调用被初始化，后续每次调用将使用上次调用后保存的值；2）全局变量中static变量，可以防止被其他文件的代码使用这个变量，有点将这个全局变量设置为private的意味；3）对于static函数来说，效果和2中的变量相同；4）C++类中static方法，不需要实例化访问；5）C++定义static类成员变量，不需要实例化访问，不过需要先定义，定义的时候可以初始化数组。

2、volatile用来声明一个变量，并强制程序在每次使用变量的重新从变量地址读取数据，这是为了防止变量在其他地方被改变，而程序仍然使用没有更新的数据。

3、略

4、略

三、编程题

1、给定升序自然数数组，数字有重复，二分算法求给定任意数字位置，参数决定是给定数字的开始位置还是结束位置。这里关键是开始结束位置的高效判定，代码如下。

1 #include 
     
       2  3 int array[]={
   1,2,2,2,2,3,3,3,3,4,4,4,4,6,6,6,8,8,8,10}; 4  5 int search(int *array, int begin, int end, int number, int left) 6 { 7     if(array == NULL) 8         return -1; 9 10     if(begin > end)11         return -1;12 13     int middle = (begin + end) / 2;14     if(array[middle] == number) 15     {16         if(left)17         {18             int leftindex = middle - 1;19             if(leftindex >= begin)20             {21                 if(array[leftindex] < array[middle])22                     return middle;23                 else24                     end = leftindex;25             }26             else27                 return middle;28         }29         else30         {31             int rightindex = middle + 1;32             if(rightindex <= end)33             {34                 if(array[rightindex] > array[middle])35                     return middle;36                 else37                     begin = rightindex;38             }39             else40                 return middle;41         }42     }43     else if(array[middle] < number)44         begin = middle + 1;45     else46         end = middle - 1;47 48     return search(array, begin, end, number, left);49 }50 51 int main()52 {53     int n = search(array, 0, sizeof(array)/sizeof(int) - 1, 4, 0);54     printf("%d\n", n);55     return 0;56 }
     

2、给定一个乱序的自然数数组，求里面的数字能够组成最长连续数组的长度，例如给定[100,2,1,3]，有[1,2,3]，所以返回值为3，要求复杂度O（n）。

直接做的话，复杂度是nlog(n)的，用一个hash表的方法，复杂度为O（数组中最大数-数组中最小数），目测还不如直接做，n复杂度的如下。

1 #include 
     
       2  3 int array[]={
   100, 2, 1, 3, 8, 5, 4}; 4 int size = sizeof(array) / sizeof(int); 5  6 //构造两个简陋的hash表，一个是用来查询数字是否存在，一个用于标记数字是否使用过 7 char hash_exist[1024]; 8 char hash_used[1024]; 9 10 int main()11 {12     int i, j, n, max = 0, maxnum = array[0], minnum = array[0];13     for(i = 0; i < size; i++)14     {15         //标记数字存在16         hash_exist[array[i]] = 1;17         //找出数组最大元素18         if(maxnum < array[i]) maxnum = array[i];19         //找出数组最小元素20         if(minnum > array[i]) minnum = array[i];21     }22     for(i = 0; i < size; i++)23     {24         j = array[i];25         //如果已经统计过，就跳过26         if(hash_used[j])27             continue;28         //标记本身29         n = 1;30         hash_used[j] = 1;31         //比array[i]大的连续元素统计32         while(++j <= maxnum)33         {34             if(hash_exist[j])35             {36                 n++;37                 hash_used[j] = 1;38             }39             else40                 break;41         }42         //比array[i]小的连续元素统计43         j = array[i];44         while(--j >= minnum)45         {46             if(hash_exist[j])47             {48                 n++;49                 hash_used[j] = 1;50             }51             else52                 break;53         }54         //更新最大连续数字55         if(n > max) max = n;56     }57     printf("%d\n", max);58     return 0;59 }