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

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

計算機科學與技術(shù)學科聯(lián)考計算機學科專

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

1設n是描述問題規(guī)模的非負整數(shù)的時間復雜度是，下面程序片段x=2；while(xvn/2)x=2*x1設n是描述問題規(guī)模的非負整數(shù)的時間復雜度是，下面程序片段x=2；while(xvn/2)x=2*x；A.O(log2n) B.O(n)D.O(n2)年C.O(nlog2n)1求整數(shù)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章線性表【考綱內(nèi)容】線性表的定義和基本操作線性表的實現(xiàn) 1?順序存儲結(jié)構(gòu) 2?鏈式存儲結(jié)構(gòu) 3?線性表的應用【考題分析】年份單選題/分綜合題/分考查內(nèi)容2009年01題/15查找鏈表中倒數(shù)第k個結(jié)點2010年01題/13將數(shù)組中的序列循環(huán)左移2011年01題/15求兩個有序順序表中的中位數(shù)2012年01題/13求兩個單鏈表中的公共結(jié)點2013年01題/15尋找一個數(shù)組序列中的主兀素

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

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

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