考研數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)

全國(guó)碩士研究生入學(xué)統(tǒng)一考試

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專(zhuān)

業(yè)基礎(chǔ)綜合考試大綱

I.考查目標(biāo)

計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合考試是為高等院校和科研院

所招收計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的碩士研究生而設(shè)置的具有

選拔性質(zhì)的聯(lián)考科目，其目的是科學(xué)、公平、有效地測(cè)試考

生掌握計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科大學(xué)本科階段專(zhuān)業(yè)基礎(chǔ)知識(shí)、

基本理論、基本方法的水平和分析問(wèn)題、解決問(wèn)題的能力，

評(píng)價(jià)的標(biāo)準(zhǔn)是高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科優(yōu)秀本科生

所能達(dá)到的及格或及格以上水平，以利于各高等院校和科研

院所擇優(yōu)選拔，確保碩士研究生的入學(xué)質(zhì)量。

計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)機(jī)構(gòu)、計(jì)算機(jī)組

成原理、操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科專(zhuān)業(yè)基礎(chǔ)課程。要求

考生系統(tǒng)地掌握上述專(zhuān)業(yè)基礎(chǔ)課程的概念、基本原理和基本

方法，能夠運(yùn)用所學(xué)的基本原理和基本方法分析、判斷和解

決有關(guān)理論問(wèn)題和實(shí)際問(wèn)題。

II.考試形式和試卷結(jié)構(gòu)

一、試卷滿分及考試時(shí)間：本試卷滿分為150分，考試時(shí)間

為180分鐘。

二、答題方式：答題方式為閉卷、筆試。

三、試卷內(nèi)容結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)45分計(jì)算機(jī)組成原理45分

操作系統(tǒng)35分計(jì)算機(jī)網(wǎng)絡(luò)25分

四、試卷題型結(jié)構(gòu)

單項(xiàng)選擇題80分（40小題，每小題2分）綜

合應(yīng)用題70分

III.考查內(nèi)容

數(shù)據(jù)結(jié)構(gòu)

［考查目標(biāo)］

1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。

2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn),

能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。

3.能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進(jìn)行問(wèn)題的分

析與求解，具備采用C或C++或Java語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法

的能力。一、線性表

（一）線性表的定義和基本操作

（二）線性表的實(shí)現(xiàn)1.順序存儲(chǔ)結(jié)構(gòu)2.鏈

式存儲(chǔ)結(jié)構(gòu)3.線性表的應(yīng)用

二、棧、隊(duì)列和數(shù)組

（一）棧和隊(duì)列的基本概念

（二）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

（三）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

（四）棧和隊(duì)列的應(yīng)用

（五）特殊矩陣的壓縮存儲(chǔ)

三、樹(shù)與二叉樹(shù)

（一）樹(shù)的基本概念

（二）二叉樹(shù)

1.二叉樹(shù)的定義及其主要特證

2.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.二叉樹(shù)的遍歷

4.線索二叉樹(shù)的基本概念和構(gòu)造

（三）樹(shù)、森林

1.樹(shù)的存儲(chǔ)結(jié)構(gòu)2.森林與二叉樹(shù)的轉(zhuǎn)換

3.樹(shù)和森林的遍歷

（四）樹(shù)與二叉樹(shù)的應(yīng)用

1.二叉排序樹(shù)2.平衡二叉樹(shù)3.哈夫曼

（Huffman）樹(shù)和哈夫曼編碼

四、圖

（一）圖的基本概念

（二）圖的存儲(chǔ)及基本操作1.鄰接矩陣法

2.鄰接表法

（三）圖的遍歷1.深度優(yōu)先搜索

2.廣度優(yōu)先搜索

（四）圖的基本應(yīng)用1.最小（代價(jià)）生成樹(shù)

2.最短路徑3.拓?fù)渑判?.關(guān)鍵路徑

五、查找

（-）查找的基本概念

（二）順序查找法

（三）折半查找法

（四）B樹(shù)及其基本操作、B樹(shù)的基本概念+

（五）散歹U（Hash）表

（六）查找算法的分析及應(yīng)用

六、排序

（一）排序的基本概念

（二）插入排序1.直接插入排序2.折半插

入排序

（三）起泡排序（bubblesort）

（四）簡(jiǎn)單選擇排序

（五）希爾排序（shellsort）

（六）快速排序

（七）堆排序

（八）二路歸并排序（mergesort）

（九）基數(shù)排序

（+）外部排序

（十一）各種排序算法的比較

（十二）排序算法的應(yīng)用

重點(diǎn)章：緒論線性表?xiàng)：完?duì)列（數(shù)組）樹(shù)

圖查找排序

第1章緒論

【復(fù)習(xí)要點(diǎn)】

1.數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本概念和術(shù)語(yǔ)

2.數(shù)據(jù)結(jié)構(gòu)的三要素：邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)運(yùn)算

3.算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析與計(jì)算

【考題分析】

年份單選題綜合題考查內(nèi)容

/分/分

2009年00

2010年0分析給定程序段的時(shí)間復(fù)雜度

2011年1題/2V分析給定程序段的時(shí)間復(fù)雜度；

大題中分析所寫(xiě)算法的時(shí)間復(fù)

雜度

2012年1題/2V分析給定程序段的時(shí)間復(fù)雜度；

大題中分析所寫(xiě)算法的時(shí)間復(fù)

雜度

2013年1題/2V分析給定程序段的時(shí)間復(fù)雜度；

大題中分析所寫(xiě)算法的時(shí)間復(fù)

雜度

2014年1題/20分析給定程序段的時(shí)間復(fù)雜度

2011年

1.設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段

的時(shí)間復(fù)雜度是。

x=2；

while(x<n/2)

x=2*x；

A.O(log2n)B.0(n)C.O(nlog2n)

D.0(n2)

2012年

1.求整數(shù)n(n，0)階乘的算法如下，其時(shí)間復(fù)雜度

是O

intfact(intn){

if(n<=1)return1;

returnn*fact(n-1);

}

A.O(log2n)B.O(n)C.O(nlog2n)

D.O(n2)

2013年

1.已知兩個(gè)長(zhǎng)度分別為m和n的升序鏈表，若將它

們合并為一個(gè)長(zhǎng)度為m+n的降序鏈表，則

最壞情況下的時(shí)間復(fù)雜度是o

A.0(n)B.O(mXn)C.

O(min(m,n))D.O(max(m,n))

第2章線性表

【考綱內(nèi)容】

(-)線性表的定義和基本操作

(二)線性表的實(shí)現(xiàn)1.順序存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱?/p>

儲(chǔ)結(jié)構(gòu)3.線性表的應(yīng)用

【考題分析】

年份單選題綜合題/考查內(nèi)容

/分分

2009年01題/15查找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

2010年01題/13將數(shù)組中的序列循環(huán)左移

2011年01題/15求兩個(gè)有序順序表中的中位數(shù)

2012年01題/13求兩個(gè)單鏈表中的公共結(jié)點(diǎn)

2013年01題/15尋找一個(gè)數(shù)組序列中的主元素

2014年00

2009年

42.(15分)已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)

結(jié)構(gòu)為

假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前

提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒

數(shù)第k個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù))。若查找成功,

算法輸出該結(jié)點(diǎn)的data值，并返回1；否則，只返回

0o要求：

(1)描述算法的基本設(shè)計(jì)思想

(2)描述算法的詳細(xì)實(shí)現(xiàn)步驟

(3)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言

描述算法(使用C或C++求JAVA博言實(shí)現(xiàn))，關(guān)

鍵之處請(qǐng)給出簡(jiǎn)要注釋。

2010年

42.(13分)設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù)組R中,

試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法，

將R中保有的序列循環(huán)左移P(0<P<n)個(gè)位置，

即將R中的數(shù)據(jù)由(X0X1……Xn-1)變換為(Xp

Xp+1……Xn-1X0X1……Xp-1)要求：

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言表

述算法，關(guān)鍵之處給出注釋。

(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度

2011年

42.(15分)一個(gè)長(zhǎng)度為L(zhǎng)(L21)的升序序列S,

處在第L/2個(gè)位置的數(shù)稱為S的中位數(shù)。例如,

若序列S1=(11,13,15,17,19),則S1的中

位數(shù)是15,兩個(gè)序列的中位數(shù)是含它們所有元素的升

序

序列的中位數(shù)。例如，若S2=(2,4,6,8,20),

則S1和S2的中位數(shù)是11。現(xiàn)在有兩個(gè)等長(zhǎng)升序序

列A和B,試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能

高效的算法，找出兩個(gè)序列A和B的中位數(shù)。要求:

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言描

述算法，關(guān)鍵之處給出注釋。

(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

2012年

42.假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單

詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)

空間，例如，“l(fā)oading”和“being”的存儲(chǔ)映像如

下圖所示。

strl

str2

設(shè)strl和str2分別指向兩個(gè)單詞所在單鏈表的頭結(jié)

點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)

間上盡可能高效的算法，找出由strl和str2所指向

兩個(gè)鏈表共同后綴的起始位置（如圖中字符i所在結(jié)

點(diǎn)的位置p）。要求：

1）給出算法的基本設(shè)計(jì)思想。

2）根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言描述

算法，關(guān)鍵之處給出注釋。

3）說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。

2013年

打.（13分）已知一個(gè)整數(shù)序列，=…Ml）,J

cipi=ap2=…=a=x且m>n12(0<pk<n,\<k<m)，

（0,5,5,3,5,7,5,5）,側(cè)5為主元素；又如4

A中沒(méi)有主元素。假設(shè)A中的〃個(gè)元素保存在一個(gè)一2

的算法，找出4的主元素。若存在主元素，則輸出該元

（1）給出算法的基本設(shè)計(jì)思想.

（2）根據(jù)設(shè)計(jì)思想，采用C或C+T或Java語(yǔ)言描述算充

（3）說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

【答案解析】

2009年

42.

K個(gè)節(jié)點(diǎn)

（1）算法基本思想如下：從頭至尾遍歷單

鏈表，并用指針P指向當(dāng)前節(jié)點(diǎn)的前K個(gè)

節(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)節(jié)點(diǎn)時(shí)，指

針P所指向的節(jié)點(diǎn)即為所查找的節(jié)點(diǎn)。

(2)詳細(xì)實(shí)現(xiàn)步驟：增加兩個(gè)指針變量和

一個(gè)整型變量，從鏈表頭向后遍歷，其中指

針P1指向當(dāng)前遍歷的節(jié)點(diǎn)，指針P指向P1

所指向節(jié)點(diǎn)的前K個(gè)節(jié)點(diǎn)，如果P1之前沒(méi)

有K個(gè)節(jié)點(diǎn)，那么P指向表頭節(jié)點(diǎn)。用整

型變量i表示當(dāng)前遍歷了多少節(jié)點(diǎn)，當(dāng)i>k

時(shí)，指針p隨著每次遍歷，也向前移動(dòng)一個(gè)

節(jié)點(diǎn)。當(dāng)遍歷完成時(shí)，p或者指向表頭就節(jié)

點(diǎn)，或者指向鏈表中倒數(shù)第K個(gè)位置上的節(jié)

(3)算法描述：

intLocateElement(linklistlist,intk){

P1=list->link;

while(P1){

P1=P1->link;

i++；

if(i>k)p=p->next;〃如果i>k,貝Up也

往后移

)

if(p==list)

return0;〃說(shuō)明鏈表沒(méi)有k個(gè)結(jié)點(diǎn)

else

{printf("％d\n",p->data);return1;}

}

2010年

42.循環(huán)左移p位

解法一：

(1)算法的基本設(shè)計(jì)思想：

分三次倒置：先倒置前p個(gè)元素，再倒置后

n?p個(gè)元素，最后全部元素倒置。

(2)詳細(xì)程序

voidReverseSeg(intR[],intfromjntto){

for(inti=0;i<(to-from+1)/2;i++)

{inttemp;temp=R[from+i];

R[from+i]=R[to-i];R[to-i]=temp;}

}

voidConverseLeft(intR[],intn,intp)

{ReverseSeg(R,0,p-1);

ReverseSeg(R,p,n-1);

ReverseSeg(R,0,n-1);

}

(3)時(shí)間復(fù)雜度O(N);空間復(fù)雜度o(p)

解法二：

(1)算法的基本設(shè)計(jì)思想：

①另設(shè)一個(gè)臨時(shí)數(shù)組，存放前面的p

個(gè)元素；

②將后面的n-p個(gè)元素放到前面；

③再將臨時(shí)數(shù)組中的元素回放到后

面。借助輔助數(shù)組來(lái)實(shí)現(xiàn)

(2)詳細(xì)程序

voidConverseLeft2(intR[],intn,intp)

{intT[MAX];

inti;

for(i=0;i<p;i++)T[i]=R[i];

for(i=p;i<n;i++)R[i-p]=R[i];

for(i=n-p;i<n;i++)R[i]=T[i-p-n];

)

(3)時(shí)間復(fù)雜度O(N);空間復(fù)雜度o(p)

解法三：

(1)算法的基本設(shè)計(jì)思想：

①每次拿出最前一個(gè)元素，將元素

向前平移一位；

②再將拿出的元素放入最后一個(gè)位

置，重復(fù)P次。

(2)詳細(xì)程序

voidConverseLeft3(intR[],intn,intp){

for(intj=O;j<p;j++)

{inttemp=R[0];

for(inti=1;i<n;i++)R[i<1]=R[i];

R[n-1]=temp;

}

}

(3)時(shí)間復(fù)雜度0(pXN);空間復(fù)雜度

o(1)

循環(huán)右移p位

方法一：

分三次倒置：先倒置前n?p個(gè)元素，再倒置

后p個(gè)元素，最后全部元素倒置。

方法二：

①另設(shè)一個(gè)臨時(shí)數(shù)組，存放前面的n?p個(gè)

元素；

②將后面的p個(gè)元素放到前面；

③再將臨時(shí)數(shù)組中的元素回放到后面。

方法三：

①每次拿出最后一個(gè)元素，將元素向后平

移一位；

②再將拿出的元素放入最前一個(gè)位置，重

復(fù)P次。

2011年

42.

(1)算法的基本設(shè)計(jì)思路如下：

分別求兩個(gè)升序序列A、B的中位數(shù)，設(shè)為

a和b。求序列A、B的中位數(shù)的過(guò)程如下:

1)若a=b,則a或b即為所求的中位數(shù);

2）若a<b,則舍棄序列A中較小的一半，

同時(shí)舍棄序列B中較大的一半,要求兩次舍

棄的元素個(gè)數(shù)相同。

3）若a>b,則舍棄序列A中較大的一半，

同時(shí)舍棄序列B中較小的一半,要求兩次舍

棄的元素個(gè)數(shù)相同。

在保留的兩個(gè)升序序列中，重復(fù)上述過(guò)程，

直到兩個(gè)序列中均只含一個(gè)元素時(shí)為止，則

較小者即為所求的中位數(shù)。

若2處，則肯定不在si的左半邊，因?yàn)槿绻趕i的左半邊則中

位數(shù)<a〈b,即也在S2的左半邊，在整個(gè)S1+S2中也是在左半邊,

不是在中點(diǎn)，與中位數(shù)矛盾;同理不在s2的右半邊

若a>b時(shí),原理同上

當(dāng)S1長(zhǎng)度為奇數(shù)時(shí)，左半邊=右半邊，直接舍棄即可

當(dāng)S1長(zhǎng)度為偶數(shù)時(shí)，左半邊+1=右半邊。若a〈b,舍棄a的左半

邊（包括中點(diǎn)）舍棄b的右半邊（保留中點(diǎn)）

始終保持SI,S2等長(zhǎng)

intget_middle_number（inta[],intb[],

intn）

intstartl=0,end1=n-1,ml;//分另1J表

示序列A的首位數(shù)、末尾數(shù)和中位數(shù)的位置

intstart2=0,end2=n-1,m2;//分別表

示序列A的首位數(shù)、末尾數(shù)和中位數(shù)的位置

while(startl!=end1||start2!=end2)

(

ml=(startl+end1)/2;

m2=(start2+end2)/2;

if(a[m1]==b[m2])//a=b

returna[m1];

if(a[m1]<b[m2]){//a<b

if((startl+end1)%2==0){〃若

元素個(gè)數(shù)為奇數(shù)

startl=ml;〃舍

棄A中間點(diǎn)以前的部分且保留中間點(diǎn)

end2=m2;〃舍

棄B中間點(diǎn)以后的部分且保留中間點(diǎn)

}else{//若元

素個(gè)數(shù)為偶數(shù)

startl=ml+1;//舍棄

A中間點(diǎn)及中間點(diǎn)以前的部分

end2=m2;//舍棄

B中間點(diǎn)以后的部分且保留中間點(diǎn)

}

}else{//a>b

if((start1+end1)%2==0){

end1=ml;

start2=m2;

}else{

end1=ml;

start2=m2+1;

)

)

}

returna[start1]<b[start2]?a[start1]:

b[start2];

}

2012年

42.公共后綴

【解析】（1）算法思想：順序遍歷兩個(gè)鏈

表到尾結(jié)點(diǎn)時(shí)，并不能保證兩個(gè)鏈表同時(shí)到

達(dá)尾結(jié)點(diǎn)。這是因?yàn)閮蓚€(gè)鏈表的長(zhǎng)度不同。

假設(shè)一個(gè)鏈表比另一個(gè)鏈表長(zhǎng)k個(gè)結(jié)點(diǎn)，我

們先在長(zhǎng)鏈表上遍歷k個(gè)結(jié)點(diǎn)，之后同步遍

歷兩個(gè)鏈表。這樣我們就能夠保證它們同時(shí)

到達(dá)最后一個(gè)結(jié)點(diǎn)了。由于兩個(gè)鏈表從第一

個(gè)公共結(jié)點(diǎn)到鏈表的尾結(jié)點(diǎn)都是重合的。所

以它們肯定同時(shí)到達(dá)第一個(gè)公共結(jié)點(diǎn)。于是

得到算法思路：

①遍歷兩個(gè)鏈表求的它們的長(zhǎng)度L1,L2；

②比較L1,L2,找出較長(zhǎng)的鏈表，并求

L=|L1-L2|；

③先遍歷長(zhǎng)鏈表的L個(gè)結(jié)點(diǎn)；

④同步遍歷兩個(gè)鏈表，直至找到相同結(jié)點(diǎn)或

鏈表結(jié)束。

typedefstructNode{

chardata;

structNode*next;

}SNode;

/*求鏈表長(zhǎng)度的函數(shù)7

intlistlen(SNode*head){

intlen=0;

while(head->next!=NULL){

len++;

head=head->next;

}

returnlen;

)

/*找出共同后綴的起始地址7

SNode*find_addr(SNode*strl,SNode

*str2){

intm,n;

SNode*p,*q;

m=listlen(strl);〃求strl的長(zhǎng)度

n=listlen(str2);〃求str2的長(zhǎng)度

for(p=str1;m>n;m--)〃若m>n,使p

指向鏈表中的第m-n+1個(gè)結(jié)點(diǎn)

p=p->next;

for(q=str2;mvn;n“)〃若mvn,使q指

向鏈表中的第n-m+l個(gè)結(jié)點(diǎn)

q=q->next;

while(p->next!=NULL&&

p->next!=q->next){

//將指針p和q同步向后移動(dòng)

p=p->next;

q=q->next;

}//while

returnp->next;//返回共同后綴的起

始地址

}

2013年

42.“在一個(gè)集合中，刪除兩個(gè)不同的數(shù)，則

集合的主元素保持不變?！?/p>

(1)給出算法的基本設(shè)計(jì)思想：(4分)

算法的策略是從前向后掃描數(shù)組元素，標(biāo)記

出一個(gè)可能成為主元素的元素機(jī)。然后重

新計(jì)數(shù)，確認(rèn)N"機(jī)是否是主元素。

算法可分為以下兩步：

①選取候選的主元素：依次掃描所給數(shù)組中

的每個(gè)整數(shù)，將第一個(gè)遇到的整數(shù)加保存

至!Jc中，記錄N〃機(jī)的出現(xiàn)次數(shù)為1；若遇到的

下一個(gè)整數(shù)仍等于N〃帆，則計(jì)數(shù)加1,否則

計(jì)數(shù)減1；當(dāng)計(jì)數(shù)減到0時(shí)，將遇到的下一個(gè)

整數(shù)保存到。中，計(jì)數(shù)重新記為1,開(kāi)始新一

輪計(jì)數(shù)，即從當(dāng)前位置開(kāi)始重復(fù)上述過(guò)程，

直到掃描完全部數(shù)組元素。

②判斷。中元素是否是真正的主元素：再次

掃描該數(shù)組，統(tǒng)計(jì)c中元素出現(xiàn)的次數(shù)，若

大于山2,則為主元素；否則，序列中不存

在主元素。

(2)算法實(shí)現(xiàn)：(7分)

intMajority(intA[],intn)

|

inti,c,count=l;//c用來(lái)保存候

選主元素，count用來(lái)計(jì)數(shù)

c=A[0];//設(shè)置A[0]為

候選主元素

for(i=l;i<n;i++)//查找候選主元

素

if(A[i]==c)

count++;//對(duì)A中的候選

主兀素計(jì)數(shù)

else

if(count>0)//處理不是候選

主元素的情況

count-;

else//更換候選主元

素，重新計(jì)數(shù)

{c=A[i];

count=1;

}

if(count>0)

for(i=count=0;i<n;i++)//統(tǒng)計(jì)

候選主元素的實(shí)際出現(xiàn)次數(shù)

if(A[i]==c)

count++;

if(count>n/2)returnc;//確認(rèn)

候選主元素

elsereturn-1;//不存

在主元素

}

[(1)、(2)的評(píng)分說(shuō)明】

①若考生設(shè)計(jì)的算法滿足題目的功能要求

且正確，則(1)、(2)根據(jù)所實(shí)現(xiàn)算法的

效率給分，細(xì)則見(jiàn)下表：

時(shí)間復(fù)雜度空間復(fù)雜度(1)得分(2)得夕

0(n)。(1)47

0(n)0(n)46

0(nlogln)其他36

2。(nl)其他35

intMajorityl(intA[],intn)//采用計(jì)數(shù)

排序思想，時(shí)間：0(n),空間：0(n)

intk,*p,max;

p=(int*)malloc(sizeof(int)*n);

//申請(qǐng)輔助計(jì)數(shù)數(shù)組

for(k=0;k<n;k++)p[k]=0;

//計(jì)數(shù)數(shù)組清0

max=0;

for(k=0;k<n;k++)

{p[A[k]]++;

//計(jì)數(shù)器+1

if(p[A[k]]>p[max])max=

A[k];//記錄出現(xiàn)次數(shù)最多的元素

}

if(p[max]>n/2)returnmax;

elsereturn-1;

)

②若在算法的基本設(shè)計(jì)思想描述中因文字

表達(dá)沒(méi)有非常清晰反映出算法思路，但在算

法實(shí)現(xiàn)中能夠清晰看出算法思想且正確的，

可參照①的標(biāo)準(zhǔn)給分。

③若算法的基本設(shè)計(jì)思想描述或算法實(shí)現(xiàn)

中部分正確，可參照①中各種情況的相應(yīng)給

分標(biāo)準(zhǔn)酌情給分。

④參考答案中只給出了使用C語(yǔ)言的版本,

使用C++或Java語(yǔ)言的答案視同使用C語(yǔ)

言。

(3)說(shuō)明算法復(fù)雜性：(2分)

參考答案中實(shí)現(xiàn)的程序的時(shí)間復(fù)雜度為。

(〃)，空間復(fù)雜度為。(1)o

【評(píng)分說(shuō)明】若考生所估計(jì)的時(shí)間復(fù)雜度與

空間復(fù)雜度與考生所實(shí)現(xiàn)的算法一致，可各

給1分。

時(shí)間復(fù)雜度為線性0(n),基于分治法的線性

時(shí)間求主元素算法。

算法的基本設(shè)計(jì)思想：

中位數(shù)：數(shù)列排序后位于最中間的那個(gè)數(shù)。

如果一個(gè)數(shù)列有主元素，那么必然是其中位

數(shù)。

求一個(gè)數(shù)列有沒(méi)有主元素，只要看中位數(shù)是

不是主元素。

找中位數(shù)的方法:選擇一個(gè)元素作為劃分起

點(diǎn)，然后用快速排序的方法將小于它的移動(dòng)

到左邊，大于它的移動(dòng)到右邊。這樣就將元

素劃分為兩個(gè)部分。此時(shí)，劃分元素所在位

置為ko

如果k>n/2,那么繼續(xù)用同樣的方法在左邊

部分找；

如果kvn/2,就在右邊部分找；

k=n/2就找到了中位元素。

根據(jù)快速排序的思想，可以在平均時(shí)間復(fù)雜

度為0(n)的時(shí)間內(nèi)找出一個(gè)數(shù)列的中位數(shù)。

然后再用0(n)的時(shí)間檢查它是否是主元素。

C語(yǔ)言源碼如下：

intpartition(inta[],intlow,inthigh){

intpivotkey=a[low];

while(low<high)

(

if(low<high&&a[high]>=pivotkey)

-high;

if(low<high){

a[low]=a[high];

low++;

}

if(low<high&&a[low]<=pivotkey)

++low;

if(low<high){

a[high]=a[low];

-high;

)

}

a[low]=pivotkey;

returnlow;

)

〃快排

intquick_sort(inta[],intlow,inthigh){

if(low<high)

(

intposition=partition(a,low,high);

if(position>n/2)

quick_sort(a,low,posi