（1）给出算法的基本设计思想:（4分）
算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。
算法可分为以下两步：
① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
② 判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。 

（2）算法实现：（7分）

int Majority ( int A[ ], int n )
{
    int i, c, count=1;         // c 用来保存候选主元素，count 用来计数
    c = A[0];                 // 设置 A[0]为候选主元素
    for ( i=1; i<n; i++ )      // 查找候选主元素
        if ( A[i] == c )
            count++;           // 对 A 中的候选主元素计数
        else
            if ( count > 0)    // 处理不是候选主元素的情况
                count--;
            else              // 更换候选主元素，重新计数
            { c = A[i];
                count = 1;
            }
    if ( count>0 )
        for ( i=count=0; i<n; i++ )  // 统计候选主元素的实际出现次数
            if ( A[i] == c )
                count++;
    if ( count> n/2 ) return c;    // 确认候选主元素
    else return -1;                // 不存在主元素
}

【（1）、（2）的评分说明】
① 若考生设计的算法满足题目的功能要求且正确，则（1）、（2）根据所实现算法的效率
  给分，细则见下表： 

int Majority1 ( int A[ ], int n)// 采用计数排序思想，时间：O ( n ), 空间：O ( n )
{
    int k, * p, max;
    p = ( int * ) malloc ( sizeof ( int ) * n);  // 申请辅助计数数组
    for ( k=0; k < n ; k++ ) p [k] =0;  // 计数数组清 0
    max = 0;
    for ( k=0; k<n; k++ )
    { p[ A[k] ] ++;  // 计数器+1
        if (p[A[k] ]>p [ max ] ) max = A[k];  // 记录出现次数最多的元素
    }
    if ( p[ max ] > n/2 ) return max;
    else return -1;
}

② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。
③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
④ 参考答案中只给出了使用 C 语言的版本，使用 C++或 Java 语言的答案视同使用 C 语言。

（3）说明算法复杂性：（2 分）
参考答案中实现的程序的时间复杂度为 O（n），空间复杂度为 O（1）。
【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给1 分。