本章習題

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]的地址為（　?。浚?012·優酷土豆）

解答：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]時，直接出結果?？梢姇r間復雜度為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);
            }

本題也可以這樣考查，數組中有一個數字出現的次數超過了數組長度的三分之一，找出這個數字。此時可以依照上述思想寫出類似代碼。

那么若本題為：數組中有一個數字出現的次數超過了或等于數組長度的一半，請找出這個數字。

那么又該如何做答呢？

由于等于二分之一肯定大于三分之一，故可以將此題轉化為數組中有一個數字出現的次數超過了數組長度的三分之一，找出這個數字。