![中国人才网](http://static.jianlimoban.c321.cn/img/cn_logo2.jpg"){kind=logo}
选择题：
1、二维数组int a[3][4]，下列能表示a[1][2]的是?
A.*(*(a+1)+2) B.*(a+3) C.(&a[0]+1)[2] D.(a[0]+1)
2、short a[100]，则sizeof(a)的值是?
A.2 B.4 C.200 D.400
问答题：
1、解释说明static、const和volatile两个关键字的作用?
关键字static有三个明显的作用：
1、在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
2、 在模块内(但在函数体外)，一个被声明为静态的变量可以被模块内所有函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。
3、在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用。
const 有什么用途?
1、可以定义 const 常量
2、const可以修饰函数的参数、返回值，甚至函数的定义体。被const修饰的东西都受到强制保护，可以预防意外的变动，能提高程序的健壮性。
volatile问题：
volatile的作用: 作为指令关键字,确保本条指令不会因编译器的优化而省略,且要求每次直接读值。。。
volatile的语法与const是一样的，但是volatile的意思是“在编译器认识的范围外，这个数据可以被改变”。不知何故，环境正在改变数据(可能通过多任务处理)，所以，volatile告诉编译器不要擅自作出有关数据的任何假设——在优化起家这是特别重要的。如果编译器说：“我已经把数据读入寄存器，而且在没有与寄存器接触。”在一般情况下，它不需要再读入这个数据。但是，如果数据是volatile修饰的，编译器则是不能做出这样的假定，因为数据可能被其他进程改变了，编译器必须重新读这个数据而不是优化这个代码。就像建立const对象一样，程序员也可以建立volatile对象，甚至还建立const volatile对象。这个对象不能被程序员改变，但可通过外面的工具改变。
volatile对象每次被访问时必须重新读取这个变量的值，而不是用保存在寄存器中的备份。下面时volatile变量的几个例子：
.并行设备的硬件寄存器(如状态寄存器);
.一个中断服务子程序中会访问到的非自动变量(Non-automatic variables);
.多现成应用中被几个任务共享的变量。
一个参数可以const同时也是volatile，一个指针也是可以为volatile的，但是具体编程时要小心，要保证不被意外修改。
1、static关键字的作用，个人经验主要有以下几种：1)函数局部static变量，第一次函数调用被初始化，后续每次调用将使用上次调用后保存的值;2)全局变量中static变量，可以防止被其他文件的代码使用这个变量，有点将这个全局变量设置为private的意味;3)对于static函数来说，效果和2中的变量相同;4)C++类中static方法，不需要实例化访问;5)C++定义static类成员变量，不需要实例化访问，不过需要先定义，定义的时候可以初始化数组。
2、volatile用来声明一个变量，并强制程序在每次使用变量的重新从变量地址读取数据，这是为了防止变量在其他地方被改变，而程序仍然使用没有更新的数据。
2、说明C++内存分配方式有几种?每种使用都有哪些注意项?
1.从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。
2.在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
3.从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。
----------------------------------------
一般所说的堆栈(stack)往往是指栈，先进后出，它是一块内存区。用以存放程序的局部变量，临时变量，函数的参数，返回地址等。在这块区域中的变量的分配和释放由系统自动进行。不需要用户的参与。
而在堆(heap,先进先出)上的空间则是由用户进行分配，并由用户负责释放
编程题：
1、给定一个升序排列的自然数数组，数组中包含重复数字，例如：[1,2,2,3,4,4,4,5,6,7,7]。问题：给定任意自然数，对数组进行二分查找，返回数组正确的位置，给出函数实现。注：连续相同的数字，返回第一个匹配位置还是最后一个匹配位置，由函数传入参数决定。
分析：既然是二分查找的变形，那么先写个正确的二分查找吧：
#include
using namespace std;
int bin_search(int arr[],int n,int value)
{
if(arr==NULL||n<1)
return -1;
int left=0;
int right=n-1;
while(left<=right)
{
int mid=left+((right-left)>>1);
if(arr[mid]>value)
{
right=mid-1;
}
else if(arr[mid]
{
left=mid+1;
}
else
return mid;
}
return -1;
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9};
int b=bin_search(arr,9,9);
cout<
system("pause");
return 0;
}
代码如下：
/*
* 测试样例
* 11
* 1 2 2 3 4 4 4 5 7 7 7
*/
#include
#include
#define MAX 20
int n;
int sets[MAX];
enum MATCH_POS{PRE,POST};//分别为第一个匹配和最后一个匹配
int bi_search(int *arr,int b,int e,int v,MATCH_POS pos)
{
int left,right,mid;
left=b-1;right=e;
while(left+1 < right)
{
mid=left+(right - left)/2;
if(v < arr[mid])
{
right = mid;
}else if(v > arr[mid])
{
left=mid;
}else
{
if(pos==PRE)
{//如寻找第一个匹配，right向左移动
right = mid;
}
else
left = mid;
}
}
if(arr[right] == v)
return right;
else if(arr[left] == v)
return left;
return -1;
}
int main(){
int i;
int sets[]={1, 2, 2, 3, 4, 4, 4, 5, 7, 7, 7};
int t=bi_search(sets,0,10,7,PRE);
printf("%d\n",t);
system("pause");
return 0;
}
2、一个无序自然数数组，比如[100,2,1,3]求在0(n)时间复杂度内求出最大的连续自然数个数：输出应该是3，要求算法的时间复杂度为O(n)
方法一：排序
可以采用一些排序方法比如基数排序、桶排序、记数排序等先进行排序。然后遍历一遍所有元素即可。当前这些排序有一些限制条件的。
方法二：维持一个hash表
维持一个hash表，大小为最大整数。遍历一次数组，用hash表记录出现在原始数组中的数。
然后设置四个个指示变量start，end，length，bestLength = 0。初始，start = end = 数组中第一个数，length = 1。然后不断执行下列操作：
end = end + 1.然后ziahash表中寻找end，如果能够找到，说明end存在原始数组中。一直到找不到end位置。
然后设置length = end - start。如果length大于bestLength，则更新：bestLength = length。
然后将start和end都设置为刚才为查找到的那个数，length = 1，接着重复上面的操作，最终的bestLength 便是最大的连续自然数个数。
由于hash的查找等操作都能在O(1)时间复杂度内完成，因此hash方法能够满足O(n)时间复杂度。
方法三：位图
用位图。类似方法二。
位图大小和最大的整数有关。位图中每一位为0或者1。位图某个位置index上为1表示index出现在原始数组中，反之不存在。遍历一遍原始数组建立位图之后，采用类似方法二中遍历hash表的方法遍历位图，找出最大的连续自然数个数。
位图的方法存在一个问题就是：可能最大的数很大，但是数的数目有很小，这时候要申请的位图的空间依然是很大，时候复杂度不是O(n)。
方法四：维持两个hash表
维持两个hash表tables：
Start表，其中的条目都是如下格式(start-point,length)，包含的某个连续序列起始数以及序列长度。
End表，其中的条目都是如下格式(end-point,length)，包含的某个连续序列结束数以及序列长度。
扫描原始数组，做如下操作：
对于当前值value，
判断value + 1是否存在于start表中。
如果存在，删除相应的条目，创建一个新条目(value,length + 1)，同时更新end表相应条目，结束数不变，该对应长度加一。
判断value - 1是否存在于end表中。
如果存在，删除相应的条目，创建一个新条目(value,length + 1)，同时更新start表相应条目，开始数不表，该对应长度加一。
如果在两个表中都存在，则合并两个已经存在的连续序列为一个。将四个条目删除，新建两个条目，每两个条目代表一个连续序列。
如果都不存在，则只需要在两个表中创建一个新的长度为1的条目。
一直这样等到数组中所有元素处理完毕，然后扫描start表寻找length值最大的那个即可。
这里要达到O(n)时间复杂度，start表和end表都用hash表实现，而且必须满足相关操作查找/添加/删除能够在O(1)时间复杂度内完成。
实例分析：
int[] input = {10,21,45,22,7,2,67,19,13,45,12, 11,18,16,17,100,201,20,101};
初始化状态：
Start table：{}
End table：{}
开始遍历数组：
10：两个数组中都不存在，添加条目。
Start table：{(10,1)}
End table：{(10,1)}
21：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,1)}
End table：{(10,1)，(21,1)}
45：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,1)，(45,1)}
End table：{(10,1)，(21,1)，(45,1)}
22：22-1=21存在于end表中需要进行更新。
Start table：{(10,1)，(21,2)，(45,1)}
End table：{(10,1)，(22,2)，(45,1)}
7：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)}
2：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)}
67：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)}
19：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
13：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
45：两个数组中都不存在，添加条目。
Start table：{(10,1)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
End table：{(10,1)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
12：12+1=13存在start表中，更新。
Start table：{(10,1)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(12,2)}
End table：{(10,1)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,2)}
11：11+1=12都存在，合并。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
18：18+1=19存在start表中，更新。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(18,2)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,2)}
16：都不存在，添加条目。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(18,2)，(16,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,2)，(16,1)}
17：都存在，合并。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)}
100：都不存在，添加条目。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)，(100,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)，(100,1)}
201：都不存在，添加条目。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)，(100,1)，(201,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)，(100,1)，(201,1)}
20：都存在，合并。
Start table：{(10,4)，(16,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)}
End table：{(13,4)，(22,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)}
101：都存在，合并。
Start table：{(10,4)，(16,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)，(101,1)}
End table：{(13,4)，(22,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)，(201,1)}
最后搜索start表，找到length值最大的，为7.连续自然数序列是：(16,17,18,19,20,21,22).
结束。
#include
int array[]={100, 2, 1, 3, 8, 5, 4};
int size = sizeof(array) / sizeof(int);
//构造两个简陋的hash表，一个是用来查询数字是否存在，一个用于标记数字是否使用过
char hash_exist[1024];
char hash_used[1024];
int main()
{
int i, j, n, max = 0, maxnum = array[0], minnum = array[0];
for(i = 0; i < size; i++)
{
//标记数字存在
hash_exist[array[i]] = 1;
//找出数组最大元素
if(maxnum < array[i]) maxnum = array[i];
//找出数组最小元素
if(minnum > array[i]) minnum = array[i];
}
for(i = 0; i < size; i++)
{
j = array[i];
//如果已经统计过，就跳过
if(hash_used[j])
continue;
//标记本身
n = 1;
hash_used[j] = 1;
//比array[i]大的连续元素统计
while(++j <= maxnum)
{
if(hash_exist[j])
{
n++;
hash_used[j] = 1;
}
else
break;
}
//比array[i]小的连续元素统计
j = array[i];
while(--j >= minnum)
{
if(hash_exist[j])
{
n++;
hash_used[j] = 1;
}
else
break;
}
//更新最大连续数字
if(n > max) max = n;
}
printf("%d\n", max);
return 0;
}