本章习题
1.下面选项中错误的是（ ）？【多选】（2011·浙商银行）
A.define N 10;
int x[N];
B.int N=10;
int x[N];
C.int x[0..10];
D.int x[];
解答：BCD。只有A是对的，除了宏替换可以用来定义数组的长度，另外：
const int N=10;
int x[N];
在C++文件中也是可以的，但在C语言中却不行，原因在后续关于const一节里讲解。D要有初始化元素列表时才可以这样写，比如：
int x[]={1, 2, 3};
这样编译器就知道[]里应该填3。
注意：B选项虽然在gcc编译器下可以通过编译（gcc做了优化），但是会给出警告。
2.下述代码的输出结果是什么？（2012·网易）
void main(){
char a[]="abcd";
char ＊p=a;
int b =strlen(a);
＊a=p[b];
++p;
cout<<p<<endl;
cout<<a<<endl;
}
解答：cout<<p输出bcd，cout<<a输出为空。其中strlen(a)=4，故b=4。
程序中*a=p[b]，也就是*a=p[4]=*(p+4)=a[4]，而a[4]中为'\0'，也即*a='\0'，即a[0]='\0'，故数组a最终为"\0bcd\0"，cout输出时遇到'\0'就不再输出，故cout<<a输出为空，因p指向元素：'b'，故cout<<p输出bcd。
3. 设数组定义为a[60][70]，每个元素占2个存储单元，数组按照列优先存储，元素a[0][0]的地址为1024，那么元素a[32][58]的地址为（ ）？（2012·优酷土豆）
解答：8048。由于数组按照列优先存储，故a[32][58]前面共有58列，每列有60个元素，而a[32][58]是第58列的第32个元素，因而有1024+(58×60+32)×2=8048。
4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3]存放在什么位置？脚注(10)表示用十进制表示。（2012·搜狗）
A.688
B.678
C.692
D.696
解答：C。按行优先存储来解此题，则A[2][2]的地址676=644+(2×n+2)，故求得n=15。A[3][3]的地址为644+(3×n+3)=692。
此题按照列优先存储结果一样。
5.请用文字说明p是何种类型变量。（2012·大华股份）
int (＊p)[n];________
解答：p是数组指针，指向一个长度为n的int型数组，p的类型为int (*)[n]。
6.若有以下说明和语句：
int c[4][5], (＊p)[5];
p=c;
如何使用p而不用c来表示c[2][3]这个元素，答案中不能出现[]操作符。（2011·淘宝）
解答：*(*(p+2)+3)。
7.将以下程序补充完整。
char a[2][2][3]={{{1, 6, 3}, {5, 4, 15}}, {{3, 5, 33}, {23, 12, 7}}};
for(int i=0;i<12;i++)
printf("%d\n", ______);
在空格处填上合适的语句，顺序打印出a中的数字。（2012·迅雷）
解答：a[i/6][i/3%2][i%3]。
8.有以下定义和语句：（2011·淘宝）
int a[3][2]={1, 2, 3, 4, 5, 6, }, ＊p[3];
p[0]=a[1];
则*(p[0]+1)所代表的数组元素是______？
解答：4。p[0]指向3，且p[0]为int*类型，故p[0]+1跳过一个int元素指向4。
9.若定义int a[2][3]={0,2,4,6,8,10}，以下描述正确的有 ？【多选】（2012·中兴）
A.*(a+1) 为元素6的地址
B.*(a[1]+1) 的值为2
C.**(a+1)+2的值为8
D.a[0]与a相同
解答：AC。D中a[0]与a类型不同，a是指向数组a首元素a[0]的指针，而a[0]是指向数组a[0]首元素a[0][0]的指针，即a类型为int(*)[3]，而a[0]类型为int*。*(a[1] +1)的值为a[1][1]中的元素8。
10.int A[2][3]={1, 2, 3, 4, 5, 6};，则A[1][0]和*(*(A+1)+1)的值分别是（ ）？（2012·搜狗）
A.4 5
B.4 3
C.3 5
D.3 4
解答：A。*(*(A+1)+1)为A[1][1]中的元素。
11.以下程序打印的两个字符分别是（ ）。（2012·搜狗）
struct object{
char data[3];
};
int main(void){
object obj_array[3]={ {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'} };
object＊ cur=obj_array;
printf("%c %c\n", ＊(char＊)((char ＊)(cur)+2) , ＊(char＊)(cur+2));
return 0;
}
A.cg
B.bd
C.gg
D.gc
解答：A。需注意cur是什么类型的指针，当cur是object*类型时，每加1跳过一个object，即3个字符，当cur为char*类型时，每加1跳过一个char。事实上，printf语句也可改为：
printf("%c %c\n", ＊((char ＊)(cur)+2) , ＊(char＊)(cur+2));
12.下面程序执行结果为【说明：X86_64环境】（ ）。（2012·搜狗）
int main(void){
int a[4][4]={
{1, 2, 3, 4},
{50, 60, 70, 80},
{900, 1000, 1100, 1200},
{13000, 14000, 15000, 16000} };
int (＊p1)[4]=a;
int (＊p2)[4]=&a[0];
int ＊p3=&a[0][0];
printf("%d %d %d %d\n", ＊(＊(a+1)-1), ＊(＊(p1+3)-2)+1, ＊(＊(p2-1)+16)+2,
＊(p3+sizeof(p1)-3));
return 0;
}
A.16000110113002 2
B.4 2 3 60
C.16000 2 3 2
D.4110113002 60
解答：D。(a+1)类型为int(*)[4]，所以a+1指向{50, 60, 70, 80}这一维的地址，*(a+1)=a[1]，其类型为int*，故其指向50，则(*(a+1)-1)指向50的上一元素4。
p1、p2类型同为int(*)[4]，p1、p2、a作用完全相同，原理同上。
第四个由于p1是指针，所以sizeof(p1)为8（64位的系统），而p3类型为int*，所以第四个输出60。
13. 对于数组元素a[3][4]，下列哪个不能表示a[1][1]？（2012·腾讯）
A.*(&a[0][0]+5)
B.*(*(a+1)+1)
C.*(&a[1]+1)
D.*(&a[0][0]+4)
解答：CD。C中应改为*(a[1]+1)；
A与D显然有一个是错误的，&a[0][0]类型为int*，其+5后指向a[1][1]，而+4指向a[1][0]，故D错。
14.将一个二维N*N矩阵顺时针旋转90°，例如a[2][2]={1,2,3,4}，旋转过后a[2][2]={4,1,3,2}。
解答：可以先旋转最外围的一圈，然后依次旋转里层。代码如下：
#define N 12
void rotate(int matrix[][N]) {
for (int layer=0; layer < N / 2; ++layer) {
int first=layer;
int last=N -1- layer;
for(int i=first; i < last; ++i) {
int offset=i - first;
int top=matrix[first][i]; // save top
matrix[first][i]=matrix[last-offset][first]; // left -> top
// bottom -> left
matrix[last-offset][first]=matrix[last][last - offset];
matrix[last][last - offset]=matrix[i][last]; // right -> bottom
matrix[i][last]=top; // top -> right
}
}
}
15.数组乘积
输入：一个长度为n的整数数组input；
输出：一个长度为n的整数数组result，满足result[i]=input数组中除了input[i]之外所有数的乘积（假设不会溢出）。比如输入：input={2,3,4,5}，输出result={60,40,30,24}。
程序要求：具有线性复杂度，且不能使用除法运算符。（2012·小米、搜狗、腾讯）
C/C++：
int ＊cal(int＊ input , int n);
Java:
int[] cal(int[] input);
解答：一个可行的思路：left[i]存储input[i]之前所有元素的乘积，right[i]存储input[i]之后所有元素的乘积，那么result[i]=left[i] * right[i]。left的计算可以从左往右遍历元素一遍得出，right是从右往左遍历一遍得出。然后计算result[i]=left[i] * right[i]时，直接出结果。可见时间复杂度为O(n)，空间复杂度为O(n)。以下有一种时间复杂度为O(n)，空间复杂度为O(1)的算法（除去用于存储result的空间）。C++实现的代码如下所示。
int ＊cal(int＊ input , int n)
{ int i ;
int ＊result=new int[n];
result[0]=1;
for(i=1 ; i < n ; ++i)
result[i]=result[i-1]＊input[i-1];
result[0]=input[n-1];
for(i=n-2 ; i > 0 ; --i)
{
result[i] ＊= result[0];
result[0] ＊= input[i];
}
return result;//注意result需要由此函数调用方调用“delete[]”来释放内存
}
16.在有n个整数的序列中找出最大值和最小值，最少需要的比较次数是______？（2013·腾讯）
A.2n−2
B.3n/2
C.n−1
D.4n/3
解答：B。
解法1：扫描一次数组找出最大值，再扫描一次数组找出最小值，比较次数2n−2；
解法2：可以把数组中的数据两两分组，分组内找出最大值和最小值，之后在最大值的那部分找出最大值，在最小值那部分找出最小值。
比较次数：
1）两两比较，较小值放到左边，较大值放右边，这时比较n/2次。
2）之后在最大值部分取出最大值，比较次数n/2−1。
在最小值部分取出最小值，比较次数n/2−1。
总比较次数：1.5n−2。
虽然比较次数下降了，但是破坏了原数组，而且在比较过程中有数据的交换。
解法3：每次比较相邻两个数，然后把较小值跟当前最小值进行比较，把较大值跟当前最大值进行比较。因此每两个元素需要3次比较。如何设定当前最小值和最大值的初始值依赖于n是偶数还是奇数。如果n为奇数，就将最大值和最小值都设为第一个元素的值，然后成对地处理余下的元素。如果n为偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后成对地处理余下的元素。
如果n是奇数，那么总共做了3(n−1)/2次比较；
如果n是偶数，我们是先做一次初始比较，接着做3(n−2)/2次比较，总计3n/2−2次比较。
因此，不管是哪一种情况，比较次数至多为3㊣n/2㊣。
题目中只有B最符合。
17.从n个数里面找最大的两个数理论最少需要比较 ？（2007·百度）
A.2logn
B.2logn−1
C.n+ logn−2
D.2n−3
解答：C。
18.一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。
解答：最原始的方法是检查每一个数array[i]，看是否左边的数都小于等于它，右边的数都大于等于它。这样做的话，要找出所有这样的数，时间复杂度为O(N2)。
其实可以有更简单的方法，但需要使用额外数组，比如使用rightMin[]来记录原始数组array[i]右边（包括自己）的最小值。
假如原始数组为array[]={7,10,2,6,19,22,32}，那么rightMin[]={2,2,2,6,19,22,32}。也就是说，7右边的最小值为2，2右边的最小值也是2。
有了这样一个额外数组，当我们从头开始遍历原始数组时，我们保存一个当前最大值max，如果当前最大值刚好等于rightMin[i]，那么这个最大值一定满足条件。还是刚才的例子。
第一个值是7，最大值也是7，因为7不等于2，继续；
第二个值是10，最大值变成了10，但是10也不等于2，继续；
第三个值是2，最大值是10，但是10也不等于2，继续；
第四个值是6，最大值是10，但是10不等于6，继续；
第五个值是19，最大值变成了19，而且19也等于当前rightMin[4]=19, 所以，满足条件。如此继续下去，后面的几个都满足。
代码如下：
int arr[100] , rightMin[100];
void smallLarge(int ＊arr , int ＊rightMin , int n){
int i , leftMax;
rightMin[n -1]=arr[n -1];
for(i=n -2 ; i >= 0 ; --i){
if(arr[i] < arr[i+1])
rightMin[i]=arr[i];
else
rightMin[i]=rightMin[i+1];
}
leftMax=0x80000000;
for(i=0 ; i < n ; ++i){
if(arr[i] >= leftMax){
leftMax=arr[i];
if(leftMax == rightMin[i])
printf("%d\n", leftMax);
}
}
}
19.数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。（2013·腾讯）
解答：注意题目的意思，一个数字出现的次数超过了长度的一半，那么我们可以这样认为，这个数字出现的个数一定大于其他全部数字出现的个数之和。那么，我们的算法如下：
（1）初始化：设当前的数组为data[]，数组的长度为n。currentAxis=data[0],currentNum=1；
（2）设i=1, 遍历数组，转向（3）；
（3）当data[i]==currentAxis时，currentNum++, 转向（5）；否则转向（4）；
（4）currentNum--, 当currentNum==0时，currentAxis=data[i]；
（5）当i==data.length时，转向（6）;否则,i++, 转向（3）;
（6）输出currentAxis。
代码如下：
int funtion(int data[], int length){
int currentAxis;
int currentNum=0;
for(int i =0;i < length; i++){
if(currentNum ==0) {
currentAxis=data[i];
currentNum=1;
}
else{
if(currentAxis == data[i]) currentNum++;
else currentNum--;
}
}
return currentAxis;
}
void main(){
int data[]={0, 1, 2, 1, 1};
int axis=funtion(data, 5);
printf("%d\n", axis);
}
本题也可以这样考查，数组中有一个数字出现的次数超过了数组长度的三分之一，找出这个数字。此时可以依照上述思想写出类似代码。
那么若本题为：数组中有一个数字出现的次数超过了或等于数组长度的一半，请找出这个数字。
那么又该如何做答呢？
由于等于二分之一肯定大于三分之一，故可以将此题转化为数组中有一个数字出现的次数超过了数组长度的三分之一，找出这个数字。