考研數(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)TOC\o"1-5"\h\z數(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分皿.考查內(nèi)容數(shù)據(jù)結(jié)構(gòu)［考查目標(biāo)］?掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。?掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，?能夠運(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?鏈?zhǔn)酱鎯?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ù)的定義及其主要特證?二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?二叉樹(shù)的遍歷（三）樹(shù)、森林1樹(shù)的存儲(chǔ)結(jié)構(gòu) 1樹(shù)的存儲(chǔ)結(jié)構(gòu) 2?3?樹(shù)和森林的遍歷森林與二叉樹(shù)的轉(zhuǎn)換（四）樹(shù)與二叉樹(shù)的應(yīng)用（四）樹(shù)與二叉樹(shù)的應(yīng)用1二叉排序樹(shù) 1二叉排序樹(shù) 2?平衡二叉樹(shù) 3?哈夫曼（Huffman）樹(shù)和哈夫曼編碼四、圖（一） 圖的基本概念（二） 圖的存儲(chǔ)及基本操作 1?鄰接矩陣法2?鄰接表法（三） 圖的遍歷 1深度優(yōu)先搜索2?廣度優(yōu)先搜索（四） 圖的基本應(yīng)用 1?最?。ù鷥r(jià)）生成樹(shù)2?最短路徑 3?拓?fù)渑判?4?關(guān)鍵路徑五、查找（一） 查找的基本概念（二） 順序查找法（三） 折半查找法（四） B樹(shù)及其基本操作、B樹(shù)的基本概念+（六）查找算法的分析及應(yīng)用六、排序（一） 排序的基本概念（二） 插入排序 1直接插入排序 2?折半插入排序（三） 起泡排序（bubblesort）（四） 簡(jiǎn)單選擇排序（五） 希爾排序（shellsort）（六） 快速排序（七） 堆排序（八） 二路歸并排序（mergesort）（九） 基數(shù)排序（十）外部排序（十一）各種排序算法的比較（十二）排序算法的應(yīng)用重點(diǎn)章：緒論線性表?xiàng)：完?duì)列（數(shù)組）樹(shù)圖查找排序第1章緒論【復(fù)習(xí)要點(diǎn)】數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)的三要素：邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)運(yùn)算算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析與計(jì)算【考題分析】年份單選題份綜合題/分考查內(nèi)容2009年002010年0V分析給定程序段的時(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ù)雜度年

1設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)的時(shí)間復(fù)雜度是，下面程序片段x=2；while(xvn/2)x=2*x1設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)的時(shí)間復(fù)雜度是，下面程序片段x=2；while(xvn/2)x=2*x；A.O(log2n) B.O(n)D.O(n2)年C.O(nlog2n)1求整數(shù)n(nMO)階乘的算法如下，其時(shí)間復(fù)雜度intfact(intn){if(nv=1)return1;returnn*fact(n-1);}C.O(nlog2n)A.O(logC.O(nlog2n)D.O(n2)年1.已知兩個(gè)長(zhǎng)度分別為m和n的升序鏈表，若將它們合并為一個(gè)長(zhǎng)度為m+n的降序鏈表，則最壞情況下的時(shí)間復(fù)雜度是 。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)酱鎯?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年002009年42.(15分)已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為=1假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，査找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù))。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回1；否則，只返回=10。要求:(1)(1)描述算法的基本設(shè)計(jì)思想描述算法的詳細(xì)實(shí)現(xiàn)步驟根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言(3)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法(使用C或C++或JAVA語(yǔ)言實(shí)現(xiàn))，關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。年=142.(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)變換為(XpXp+1……Xn-1X0X1……Xp-1)要求：=1(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言表述算法，關(guān)鍵之處給出注釋。(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度年42.(15分)一個(gè)長(zhǎng)度為L(zhǎng)(LM1)的升序序列S,處在第 個(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?，F(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ù)雜度。年42?假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)空間，例如，“l(fā)oading”和“being”的存儲(chǔ)映像如下圖所示。設(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ù)雜度。年ap[=ap2=—=aptn=xUm>n/2(0<pk<n.\<k<m)?（0, 5，5，3,5，7，5,5）,側(cè)5為主元素；又如A二A屮沒(méi)有主元素。假設(shè)A屮的?個(gè)元素保存在?個(gè)一纟的算法，找出A的主元素。若存在主元素，則輸出該元（Q給出算法的基本設(shè)計(jì)思想。（2） 根據(jù)設(shè)計(jì)思想，采川C或C++|^Java語(yǔ)言描述算辛（3） 說(shuō)明你所設(shè)訃算法的時(shí)間復(fù)雜度和簾間復(fù)雜度?！敬鸢附馕觥?2.K個(gè)節(jié)點(diǎn)P1鏈表，并用指針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(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é)點(diǎn)。ijiiJIJJJJ=1■I■■■■

IWijiiJ(3)算法描述:K個(gè)節(jié)點(diǎn)K個(gè)節(jié)點(diǎn)listP=list;P一listi=1；while(P1){P1=P1->link;i++；if(i〉k)p二p-〉next如果/i>k則p也往后移}if(p==list)return0;說(shuō)朋鏈表沒(méi)有k個(gè)結(jié)點(diǎn)else{print“(％d\n“，p-〉data);return1;}}2010年42.循環(huán)左移p位解法―：(1)算法的基本設(shè)計(jì)思想:分三次倒置：先倒置前P個(gè)元素，再倒置后n-p個(gè)元素，最后全部元素倒置。(2)詳細(xì)程序voidReverseSeg(intR[],intfrom,intto){for(inti=0;iv(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)解法二：算法的基本設(shè)計(jì)思想：另設(shè)一個(gè)臨時(shí)數(shù)組，存放前面的p個(gè)元素；將后面的n-p個(gè)元素放到前面;再將臨時(shí)數(shù)組中的元素回放到后面。借助輔助數(shù)組來(lái)實(shí)現(xiàn)⑵詳細(xì)程序voidConverseLeft2(intR[],intn,intp){intT[MAX];inti;for(i=0;ivp;i++)T[i]=R[i];for(i=p;ivn;i++)R[i-p]=R[i];for(i=n-p;ivn;i++)R[i]=T[i-p-n];}(3)時(shí)間復(fù)雜度O(N);空間復(fù)雜度o(p)解法三：(1)算法的基本設(shè)計(jì)思想：每次拿出最前一個(gè)元素，將元素向前平移一位；再將拿出的元素放入最后一個(gè)位置，重復(fù)p次。詳細(xì)程序voidConverseLeft3(intR[],intn,intp){for(intj=0；jvp；j++)inttemp=R[0];for(inti=1;ivn;i++)R[i-1]=R[i];R[n-1]=temp;}時(shí)間復(fù)雜度O(pXN);空間復(fù)雜度o(1)循環(huán)右移p位方法一：l￥l分三次倒置：先倒置前n-p個(gè)元素，再倒置后p個(gè)元素，最后全部元素倒置。l￥l方法二另設(shè)一個(gè)臨時(shí)數(shù)組，存放前面的n-p個(gè)將后面的p個(gè)元素放到前面；再將臨時(shí)數(shù)組中的元素回放到后面。方法三：①每次拿出最后一個(gè)元素，將元素向后平移一位；②再將拿出的元素放入最前一個(gè)位置，重復(fù)p次。年42.(1)算法的基本設(shè)計(jì)思路如下：分別求兩個(gè)升序序列A、B的中位數(shù)，設(shè)為a和bo求序列A、B的中位數(shù)的過(guò)程如下:若a=b,則a或b即為所求的中位數(shù);2）若avb，則舍棄序列A中較小的一半，同時(shí)舍棄序列B中較大的一半，要求兩次舍棄的元素個(gè)數(shù)相同。3）若a>b，則舍棄序列A中較大的一半，同時(shí)舍棄序列B中較小的一半，要求兩次舍棄的元素個(gè)數(shù)相同。在保留的兩個(gè)升序序列中，重復(fù)上述過(guò)程,直到兩個(gè)序列中均只含一個(gè)元素時(shí)為止，則較小者即為所求的中位數(shù)。若a<b，則肯定不在S1的左半邊，因?yàn)槿绻赟1的左半邊則中位數(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)）始終保持S1,S2等長(zhǎng)intget_middle_number（inta[],intb[],intn）intstartl=0,endl=n-1,ml;//分別表示序列A的首位數(shù)、末尾數(shù)和中位數(shù)的位置intstart2=0,end2=n-1,m2;//分別表示序列A的首位數(shù)、末尾數(shù)和中位數(shù)的位置while(startl!=endl||start2!=end2){m1=(start1+end1)/2;m2=(start2+end2)/2;if(a[m1]==b[m2]) //a=breturna[m1];if(a[m1]<b[m2]){ //avbif((start1+end1)%2==0){〃若元素個(gè)數(shù)為奇數(shù)start1=m1; 〃舍棄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>bif((start1+end1)%2==0){endl=ml;start2=m2;}else{endl=ml;start2=m2+1;}}}returna[start1]<b[start2]?a[start1]:b[start2];}年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ù)*/intlistlen(SNode*head){intlen=0;whlle(head->next!=NULL){len++;head=head->next;}returnlen;}/*找出共同后綴的起始地址*/SNode*find_addr(SNode*strl,SNode*str2){intm,n;SNode*p,*q;m=listlen(strl);〃求strl的長(zhǎng)度n=listlen(str2);〃求str2的長(zhǎng)度f(wàn)or(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;}//whilereturnp->next;//返回共同后綴的起始地址}年42.“在一個(gè)集合中，刪除兩個(gè)不同的數(shù)，則集合的主元素保持不變。”（1）給出算法的基本設(shè)計(jì)思想：（4分）算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個(gè)可能成為主元素的元素Num。然后重新計(jì)數(shù)，確認(rèn)Num是否是主元素。算法可分為以下兩步：選取候選的主元素：依次掃描所給數(shù)組中的每個(gè)整數(shù)，將第一個(gè)遇到的整數(shù)Num保存到c中，記錄Num的出現(xiàn)次數(shù)為1；若遇到的下一個(gè)整數(shù)仍等于Num,則計(jì)數(shù)加1,否則計(jì)數(shù)減1；當(dāng)計(jì)數(shù)減到0時(shí)，將遇到的下一個(gè)整數(shù)保存到c中，計(jì)數(shù)重新記為1,開(kāi)始新一輪計(jì)數(shù)，即從當(dāng)前位置開(kāi)始重復(fù)上述過(guò)程，直到掃描完全部數(shù)組元素。判斷c中元素是否是真正的主元素：再次掃描該數(shù)組，統(tǒng)計(jì)c中元素出現(xiàn)的次數(shù)，若大于n/2,則為主元素；否則，序列中不存在主元素。2）算法實(shí)現(xiàn)：（7分）intMajority(intA[],intn){inti,c,count=1; //c用來(lái)保存候選主元素，count用來(lái)計(jì)數(shù)c=A[0];候選主元素for(i=1;i<n;i++)素//設(shè)置A[0]為//查找候選主元if(A[i]==c)

count++;主元素計(jì)數(shù)elseif(count>0)主元素的情況count--;else素，重新計(jì)數(shù)//對(duì)A中的候選//處理不是候選//更換候選主元{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ù)雜度O(n)O(n)空間復(fù)雜度O(1)O(n)(1)得分44(2)得分76O(nlog2n)其他36MO(n2)其他35intMajority1(intA[],intn)//采用計(jì)數(shù)排序思想，時(shí)間：O(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ù)組清0max=0;for(k=0;k<n;k++){p[A[k]]++;//計(jì)數(shù)器+1if(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ù)雜度為O(“)，空間復(fù)雜度為O(1)?！驹u(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í)，劃分元素所在位置為k。如果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(lowvhigh){if(lowvhigh&&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,po