一、选择题
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 <stdio.h>
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 else
24 end = leftindex;
25 }
26 else
27 return middle;
28 }
29 else
30 {
31 int rightindex = middle + 1;
32 if(rightindex <= end)
33 {
34 if(array[rightindex] > array[middle])
35 return middle;
36 else
37 begin = rightindex;
38 }
39 else
40 return middle;
41 }
42 }
43 else if(array[middle] < number)
44 begin = middle + 1;
45 else
46 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 <stdio.h>
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 else
40 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 else
52 break;
53 }
54 //更新最大连续数字
55 if(n > max) max = n;
56 }
57 printf("%d\n", max);
58 return 0;
59 }