全國碩士研究生入學統一考試

計算機科學與技術學科聯考計算機學科專

業基礎綜合考試大綱I?考查目標計算機學科專業基礎綜合考試是為高等院校和科研院所招收計算機科學與技術學科的碩士研究生而設置的具有選拔性質的聯考科目其目的是科學、公平、有效地測試考生掌握計算機科學與技術學科大學本科階段專業基礎知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等學校計算機科學與技術學科優秀本科生所能達到的及格或及格以上水平，以利于各高等院校和科研院所擇優選拔，確保碩士研究生的入學質量。計算機學科專業基礎綜合考試涵蓋數據機構、計算機組成原理、操作系統和計算機網絡等學科專業基礎課程。要求考生系統地掌握上述專業基礎課程的概念、基本原理和基本方法，能夠運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。II?考試形式和試卷結構一、 試卷滿分及考試時間：本試卷滿分為150分，考試時間為180分鐘。二、 答題方式：答題方式為閉卷、筆試。三、 試卷內容結構TOC\o"1-5"\h\z數據結構 45分 計算機組成原理 45分操作系統 35分 計算機網絡 25分四、 試卷題型結構單項選擇題 80分（40小題，每小題2分） 綜合應用題 70分皿.考查內容數據結構［考查目標］?掌握數據結構的基本概念、基本原理和基本方法。?掌握數據的邏輯結構、存儲結構及基本操作的實現，?能夠運用數據結構的基本原理和方法進行問題的分析與求解，具備采用C或C++或Java語言設計與實現算法的能力。一、線性表（一） 線性表的定義和基本操作（二） 線性表的實現 1順序存儲結構 2?鏈式存儲結構 3?線性表的應用二、 棧、隊列和數組（一） 棧和隊列的基本概念（二） 棧和隊列的順序存儲結構（三） 棧和隊列的鏈式存儲結構（四） 棧和隊列的應用（五） 特殊矩陣的壓縮存儲三、 樹與二叉樹（一） 樹的基本概念（二） 二叉樹1二叉樹的定義及其主要特證?二叉樹的順序存儲結構和鏈式存儲結構?二叉樹的遍歷（三）樹、森林1樹的存儲結構 1樹的存儲結構 2?3?樹和森林的遍歷森林與二叉樹的轉換（四）樹與二叉樹的應用（四）樹與二叉樹的應用1二叉排序樹 1二叉排序樹 2?平衡二叉樹 3?哈夫曼（Huffman）樹和哈夫曼編碼四、圖（一） 圖的基本概念（二） 圖的存儲及基本操作 1?鄰接矩陣法2?鄰接表法（三） 圖的遍歷 1深度優先搜索2?廣度優先搜索（四） 圖的基本應用 1?最小（代價）生成樹2?最短路徑 3?拓撲排序 4?關鍵路徑五、查找（一） 查找的基本概念（二） 順序查找法（三） 折半查找法（四） B樹及其基本操作、B樹的基本概念+（六）查找算法的分析及應用六、排序（一） 排序的基本概念（二） 插入排序 1直接插入排序 2?折半插入排序（三） 起泡排序（bubblesort）（四） 簡單選擇排序（五） 希爾排序（shellsort）（六） 快速排序（七） 堆排序（八） 二路歸并排序（mergesort）（九） 基數排序（十）外部排序（十一）各種排序算法的比較（十二）排序算法的應用重點章：緒論線性表棧和隊列（數組）樹圖查找排序第1章緒論【復習要點】數據結構相關的基本概念和術語數據結構的三要素：邏輯結構、物理結構和數據運算算法的時間復雜度和空間復雜度的分析與計算【考題分析】年份單選題份綜合題/分考查內容2009年002010年0V分析給定程序段的時間復雜度2011年1題/2V分析給定程序段的時間復雜度；大題中分析所寫算法的時間復雜度2012年1題/2V分析給定程序段的時間復雜度；大題中分析所寫算法的時間復雜度2013年1題/2V分析給定程序段的時間復雜度；大題中分析所寫算法的時間復雜度2014年1題/20分析給定程序段的時間復雜度年

1設n是描述問題規模的非負整數的時間復雜度是，下面程序片段x=2；while(xvn/2)x=2*x1設n是描述問題規模的非負整數的時間復雜度是，下面程序片段x=2；while(xvn/2)x=2*x；A.O(log2n) B.O(n)D.O(n2)年C.O(nlog2n)1求整數n(nMO)階乘的算法如下，其時間復雜度intfact(intn){if(nv=1)return1;returnn*fact(n-1);}C.O(nlog2n)A.O(logC.O(nlog2n)D.O(n2)年1.已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是 。A.0(n) B.O(mXn) C?O(min(m,n))D.O(max(m,n))第2章線性表【考綱內容】線性表的定義和基本操作線性表的實現 1?順序存儲結構 2?鏈式存儲結構 3?線性表的應用【考題分析】年份單選題/分綜合題/分考查內容2009年01題/15查找鏈表中倒數第k個結點2010年01題/13將數組中的序列循環左移2011年01題/15求兩個有序順序表中的中位數2012年01題/13求兩個單鏈表中的公共結點2013年01題/15尋找一個數組序列中的主兀素

2014年002009年42.(15分)已知一個帶有表頭結點的單鏈表，結點結構為=1假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，査找鏈表中倒數第k個位置上的結點(k為正整數)。若查找成功，算法輸出該結點的data值，并返回1；否則，只返回=10。要求:(1)(1)描述算法的基本設計思想描述算法的詳細實現步驟根據設計思想和實現步驟，采用程序設計語言(3)根據設計思想和實現步驟，采用程序設計語言描述算法(使用C或C++或JAVA語言實現)，關鍵之處請給出簡要注釋。年=142.(13分)設將n(n,1)個整數存放到一維數組R中，試設計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環左移P(0<P<n)個位置，即將R中的數據由(X0X1……Xn-1)變換為(XpXp+1……Xn-1X0X1……Xp-1)要求：=1(1)給出算法的基本設計思想。(2)根據設計思想，采用C或C++或JAVA語言表述算法，關鍵之處給出注釋。(3)說明你所設計算法的時間復雜度和空間復雜度年42.(15分)一個長度為L(LM1)的升序序列S,處在第 個位置的數稱為S的中位數。例如,若序列S1=(11,13,15,17,19)，則S1的中位數是15,兩個序列的中位數是含它們所有元素的升序序列的中位數。例如，若S2=(2,4,6,8,20)，則S1和S2的中位數是11。現在有兩個等長升序序列A和B,試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數。要求:(1)給出算法的基本設計思想。(2)根據設計思想，采用C或C++或JAVA語言描述算法，關鍵之處給出注釋。(3)說明你所設計算法的時間復雜度和空間復雜度。年42?假定采用帶頭結點的單鏈表保存單詞，當兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間，例如，“loading”和“being”的存儲映像如下圖所示。設strl和str2分別指向兩個單詞所在單鏈表的頭結點，鏈表結點結構為 ，請設計一個時間上盡可能高效的算法，找出由strl和str2所指向兩個鏈表共同后綴的起始位置（如圖中字符i所在結點的位置p）。要求:1）給出算法的基本設計思想。2）根據設計思想，采用C或C++或JAVA語言描述算法，關鍵之處給出注釋。3）說明你所設計算法的時間復雜度。年ap[=ap2=—=aptn=xUm>n/2(0<pk<n.\<k<m)?（0, 5，5，3,5，7，5,5）,側5為主元素；又如A二A屮沒有主元素。假設A屮的?個元素保存在?個一纟的算法，找出A的主元素。若存在主元素，則輸出該元（Q給出算法的基本設計思想。（2） 根據設計思想，采川C或C++|^Java語言描述算辛（3） 說明你所設訃算法的時間復雜度和簾間復雜度。【答案解析】42.K個節點P1鏈表，并用指針P指向當前節點的前K個節點。當遍歷到鏈表的最后一個節點時，指針P所指向的節點即為所査找的節點。(2)詳細實現步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當前遍歷的節點,指針P(2)詳細實現步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當前遍歷的節點,指針P指向P1所指向節點的前K個節點，如果P1之前沒有K個節點，那么P指向表頭節點。用整型變量i表示當前遍歷了多少節點，當i>k時，指針p隨著每次遍歷，也向前移動一個節點。當遍歷完成時，p或者指向表頭就節點，或者指向鏈表中倒數第K個位置上的節點。ijiiJIJJJJ=1■I■■■■

IWijiiJ(3)算法描述:K個節點K個節點listP=list;P一listi=1；while(P1){P1=P1->link;i++；if(i〉k)p二p-〉next如果/i>k則p也往后移}if(p==list)return0;說朋鏈表沒有k個結點else{print“(％d\n“，p-〉data);return1;}}2010年42.循環左移p位解法―：(1)算法的基本設計思想:分三次倒置：先倒置前P個元素，再倒置后n-p個元素，最后全部元素倒置。(2)詳細程序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)時間復雜度O(N);空間復雜度o(p)解法二：算法的基本設計思想：另設一個臨時數組，存放前面的p個元素；將后面的n-p個元素放到前面;再將臨時數組中的元素回放到后面。借助輔助數組來實現⑵詳細程序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)時間復雜度O(N);空間復雜度o(p)解法三：(1)算法的基本設計思想：每次拿出最前一個元素，將元素向前平移一位；再將拿出的元素放入最后一個位置，重復p次。詳細程序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;}時間復雜度O(pXN);空間復雜度o(1)循環右移p位方法一：l￥l分三次倒置：先倒置前n-p個元素，再倒置后p個元素，最后全部元素倒置。l￥l方法二另設一個臨時數組，存放前面的n-p個將后面的p個元素放到前面；再將臨時數組中的元素回放到后面。方法三：①每次拿出最后一個元素，將元素向后平移一位；②再將拿出的元素放入最前一個位置，重復p次。年42.(1)算法的基本設計思路如下：分別求兩個升序序列A、B的中位數，設為a和bo求序列A、B的中位數的過程如下:若a=b,則a或b即為所求的中位數;2）若avb，則舍棄序列A中較小的一半，同時舍棄序列B中較大的一半，要求兩次舍棄的元素個數相同。3）若a>b，則舍棄序列A中較大的一半，同時舍棄序列B中較小的一半，要求兩次舍棄的元素個數相同。在保留的兩個升序序列中，重復上述過程,直到兩個序列中均只含一個元素時為止，則較小者即為所求的中位數。若a<b，則肯定不在S1的左半邊，因為如果在S1的左半邊則中位數<a<b,即也在S2的左半邊，在整個S1+S2中也是在左半邊,不是在中點，與中位數矛盾;同理不在s2的右半邊若a>b時，原理同上當S1長度為奇數時，左半邊二右半邊，直接舍棄即可當S1長度為偶數時，左半邊+1=右半邊。若a<b，舍棄a的左半邊（包括中點）舍棄b的右半邊（保留中點）始終保持S1,S2等長intget_middle_number（inta[],intb[],intn）intstartl=0,endl=n-1,ml;//分別表示序列A的首位數、末尾數和中位數的位置intstart2=0,end2=n-1,m2;//分別表示序列A的首位數、末尾數和中位數的位置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){〃若元素個數為奇數start1=m1; 〃舍棄A中間點以前的部分且保留中間點end2=m2; 〃舍棄B中間點以后的部分且保留中間點〃若元}else{〃若元素個數為偶數startl=ml+1; 〃舍棄A中間點及中間點以前的部分〃舍棄end2=m2;〃舍棄B中間點以后的部分且保留中間點}}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）算法思想：順序遍歷兩個鏈表到尾結點時，并不能保證兩個鏈表同時到達尾結點。這是因為兩個鏈表的長度不同。假設一個鏈表比另一個鏈表長k個結點，我們先在長鏈表上遍歷k個結點，之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達最后一個結點了。由于兩個鏈表從第一個公共結點到鏈表的尾結點都是重合的。所以它們肯定同時到達第一個公共結點。于是得到算法思路：①遍歷兩個鏈表求的它們的長度L1,L2；②比較L1,L2,找出較長的鏈表，并求L=|L1-L2|；先遍歷長鏈表的L個結點;同步遍歷兩個鏈表，直至找到相同結點或鏈表結束。typedefstructNode{chardata;structNode*next;}SNode;/*求鏈表長度的函數*/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的長度n=listlen(str2);〃求str2的長度for(p=str1;m>n;m--)//若m>n,使p指向鏈表中的第m-n+1個結點p=p->next;for(q=str2;mvn;n??)//若mvn,使q指向鏈表中的第n-m+l個結點q=q->next;while(p->next!=NULL&&p->next!=q->next){//將指針p和q同步向后移動p=p->next;q=q->next;}//whilereturnp->next;//返回共同后綴的起始地址}年42.“在一個集合中，刪除兩個不同的數，則集合的主元素保持不變。”（1）給出算法的基本設計思想：（4分）算法的策略是從前向后掃描數組元素，標記出一個可能成為主元素的元素Num。然后重新計數，確認Num是否是主元素。算法可分為以下兩步：選取候選的主元素：依次掃描所給數組中的每個整數，將第一個遇到的整數Num保存到c中，記錄Num的出現次數為1；若遇到的下一個整數仍等于Num,則計數加1,否則計數減1；當計數減到0時，將遇到的下一個整數保存到c中，計數重新記為1,開始新一輪計數，即從當前位置開始重復上述過程，直到掃描完全部數組元素。判斷c中元素是否是真正的主元素：再次掃描該數組，統計c中元素出現的次數，若大于n/2,則為主元素；否則，序列中不存在主元素。2）算法實現：（7分）intMajority(intA[],intn){inti,c,count=1; //c用來保存候選主元素，count用來計數c=A[0];候選主元素for(i=1;i<n;i++)素//設置A[0]為//查找候選主元if(A[i]==c)

count++;主元素計數elseif(count>0)主元素的情況count--;else素，重新計數//對A中的候選//處理不是候選//更換候選主元{c=A[i];count=1;if(count>0)for(i=count=0;i<n;i++)//統計候選主元素的實際出現次數if(A[i]==c)count++;if(count>n/2)returnc; //確認候選主元素elsereturn-1; //不存在主元素}【(1)、(2)的評分說明】①若考生設計的算法滿足題目的功能要求且正確，則(1)、(2)根據所實現算法的效率給分，細則見下表：時間復雜度O(n)O(n)空間復雜度O(1)O(n)(1)得分44(2)得分76O(nlog2n)其他36MO(n2)其他35intMajority1(intA[],intn)//采用計數排序思想，時間：O(n),空間：0(n)intk,*p,max;p=(int*)malloc(sizeof(int)*n);//申請輔助計數數組for(k=0;k<n;k++)p[k]=0;//計數數組清0max=0;for(k=0;k<n;k++){p[A[k]]++;//計數器+1if(p[A[k]]>p[max])max=A[k];//記錄出現次數最多的元素}if(p[max]>n/2)returnmax;elsereturn-1;}②若在算法的基本設計思想描述中因文字表達沒有非常清晰反映出算法思路，但在算法實現中能夠清晰看出算法思想且正確的，可參照①的標準給分。若算法的基本設計思想描述或算法實現中部分正確，可參照①中各種情況的相應給分標準酌情給分。參考答案中只給出了使用C語言的版本,使用C++或Java語言的答案視同使用C語(3)說明算法復雜性：(2分)參考答案中實現的程序的時間復雜度為O(“)，空間復雜度為O(1)。【評分說明】若考生所估計的時間復雜度與空間復雜度與考生所實現的算法一致，可各給1分。時間復雜度為線性0(n)基于分治法的線性時間求主元素算法。算法的基本設計思想：中位數：數列排序后位于最中間的那個數。如果一個數列有主元素，那么必然是其中位數。求一個數列有沒有主元素，只要看中位數是不是主元素。找中位數的方法:選擇一個元素作為劃分起點，然后用快速排序的方法將小于它的移動到左邊，大于它的移動到右邊。這樣就將元素劃分為兩個部分。此時，劃分元素所在位置為k。如果k>n/2,那么繼續用同樣的方法在左邊部分找；如果kvn/2，就在右邊部分找；k=n/2就找到了中位元素。根據快速排序的思想，可以在平均時間復雜度為0(n)的時間內找出一個數列的中位數。然后再用0(n)的時間檢查它是否是主元素。C語言源碼如下: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