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

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

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

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

1設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)的時間復(fù)雜度是，下面程序片段x=2；while(xvn/2)x=2*x1設(shè)n是描述問題規(guī)模的非負(fù)整數(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)階乘的算法如下，其時間復(fù)雜度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的降序鏈表，則最壞情況下的時間復(fù)雜度是 。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?鏈?zhǔn)酱鎯Y(jié)構(gòu) 3?線性表的應(yīng)用【考題分析】年份單選題/分綜合題/分考查內(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假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，査找鏈表中倒數(shù)第k個位置上的結(jié)點(k為正整數(shù))。若查找成功，算法輸出該結(jié)點的data值，并返回1；否則，只返回=10。要求:(1)(1)描述算法的基本設(shè)計思想描述算法的詳細(xì)實現(xiàn)步驟根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言(3)根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言描述算法(使用C或C++或JAVA語言實現(xiàn))，關(guān)鍵之處請給出簡要注釋。年=142.(13分)設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P(0<P<n)個位置，即將R中的數(shù)據(jù)由(X0X1……Xn-1)變換為(XpXp+1……Xn-1X0X1……Xp-1)要求：=1(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度年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。現(xiàn)在有兩個等長升序序列A和B,試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求:(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。年42?假定采用帶頭結(jié)點的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間，例如，“l(fā)oading”和“being”的存儲映像如下圖所示。設(shè)strl和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為 ，請設(shè)計一個時間上盡可能高效的算法，找出由strl和str2所指向兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點的位置p）。要求:1）給出算法的基本設(shè)計思想。2）根據(jù)設(shè)計思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。3）說明你所設(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屮沒有主元素。假設(shè)A屮的?個元素保存在?個一纟的算法，找出A的主元素。若存在主元素，則輸出該元（Q給出算法的基本設(shè)計思想。（2） 根據(jù)設(shè)計思想，采川C或C++|^Java語言描述算辛（3） 說明你所設(shè)訃算法的時間復(fù)雜度和簾間復(fù)雜度?！敬鸢附馕觥?2.K個節(jié)點P1鏈表，并用指針P指向當(dāng)前節(jié)點的前K個節(jié)點。當(dāng)遍歷到鏈表的最后一個節(jié)點時，指針P所指向的節(jié)點即為所査找的節(jié)點。(2)詳細(xì)實現(xiàn)步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當(dāng)前遍歷的節(jié)點,指針P(2)詳細(xì)實現(xiàn)步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當(dāng)前遍歷的節(jié)點,指針P指向P1所指向節(jié)點的前K個節(jié)點，如果P1之前沒有K個節(jié)點，那么P指向表頭節(jié)點。用整型變量i表示當(dāng)前遍歷了多少節(jié)點，當(dāng)i>k時，指針p隨著每次遍歷，也向前移動一個節(jié)點。當(dāng)遍歷完成時，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)算法的基本設(shè)計思想:分三次倒置：先倒置前P個元素，再倒置后n-p個元素，最后全部元素倒置。(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)時間復(fù)雜度O(N);空間復(fù)雜度o(p)解法二：算法的基本設(shè)計思想：另設(shè)一個臨時數(shù)組，存放前面的p個元素；將后面的n-p個元素放到前面;再將臨時數(shù)組中的元素回放到后面。借助輔助數(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)時間復(fù)雜度O(N);空間復(fù)雜度o(p)解法三：(1)算法的基本設(shè)計思想：每次拿出最前一個元素，將元素向前平移一位；再將拿出的元素放入最后一個位置，重復(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;}時間復(fù)雜度O(pXN);空間復(fù)雜度o(1)循環(huán)右移p位方法一：l￥l分三次倒置：先倒置前n-p個元素，再倒置后p個元素，最后全部元素倒置。l￥l方法二另設(shè)一個臨時數(shù)組，存放前面的n-p個將后面的p個元素放到前面；再將臨時數(shù)組中的元素回放到后面。方法三：①每次拿出最后一個元素，將元素向后平移一位；②再將拿出的元素放入最前一個位置，重復(fù)p次。年42.(1)算法的基本設(shè)計思路如下：分別求兩個升序序列A、B的中位數(shù)，設(shè)為a和bo求序列A、B的中位數(shù)的過程如下:若a=b,則a或b即為所求的中位數(shù);2）若avb，則舍棄序列A中較小的一半，同時舍棄序列B中較大的一半，要求兩次舍棄的元素個數(shù)相同。3）若a>b，則舍棄序列A中較大的一半，同時舍棄序列B中較小的一半，要求兩次舍棄的元素個數(shù)相同。在保留的兩個升序序列中，重復(fù)上述過程,直到兩個序列中均只含一個元素時為止，則較小者即為所求的中位數(shù)。若a<b，則肯定不在S1的左半邊，因為如果在S1的左半邊則中位數(shù)<a<b,即也在S2的左半邊，在整個S1+S2中也是在左半邊,不是在中點，與中位數(shù)矛盾;同理不在s2的右半邊若a>b時，原理同上當(dāng)S1長度為奇數(shù)時，左半邊二右半邊，直接舍棄即可當(dāng)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é)點時，并不能保證兩個鏈表同時到達(dá)尾結(jié)點。這是因為兩個鏈表的長度不同。假設(shè)一個鏈表比另一個鏈表長k個結(jié)點，我們先在長鏈表上遍歷k個結(jié)點，之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達(dá)最后一個結(jié)點了。由于兩個鏈表從第一個公共結(jié)點到鏈表的尾結(jié)點都是重合的。所以它們肯定同時到達(dá)第一個公共結(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ù)，則集合的主元素保持不變?！保?）給出算法的基本設(shè)計思想：（4分）算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個可能成為主元素的元素Num。然后重新計數(shù)，確認(rèn)Num是否是主元素。算法可分為以下兩步：選取候選的主元素：依次掃描所給數(shù)組中的每個整數(shù)，將第一個遇到的整數(shù)Num保存到c中，記錄Num的出現(xiàn)次數(shù)為1；若遇到的下一個整數(shù)仍等于Num,則計數(shù)加1,否則計數(shù)減1；當(dāng)計數(shù)減到0時，將遇到的下一個整數(shù)保存到c中，計數(shù)重新記為1,開始新一輪計數(shù)，即從當(dāng)前位置開始重復(fù)上述過程，直到掃描完全部數(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++)素//設(shè)置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; //確認(rèn)候選主元素elsereturn-1; //不存在主元素}【(1)、(2)的評分說明】①若考生設(shè)計的算法滿足題目的功能要求且正確，則(1)、(2)根據(jù)所實現(xiàn)算法的效率給分，細(xì)則見下表：時間復(fù)雜度O(n)O(n)空間復(fù)雜度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;}②若在算法的基本設(shè)計思想描述中因文字表達(dá)沒有非常清晰反映出算法思路，但在算法實現(xiàn)中能夠清晰看出算法思想且正確的，可參照①的標(biāo)準(zhǔn)給分。若算法的基本設(shè)計思想描述或算法實現(xiàn)中部分正確，可參照①中各種情況的相應(yīng)給分標(biāo)準(zhǔn)酌情給分。參考答案中只給出了使用C語言的版本,使用C++或Java語言的答案視同使用C語(3)說明算法復(fù)雜性：(2分)參考答案中實現(xiàn)的程序的時間復(fù)雜度為O(“)，空間復(fù)雜度為O(1)?！驹u分說明】若考生所估計的時間復(fù)雜度與空間復(fù)雜度與考生所實現(xiàn)的算法一致，可各給1分。時間復(fù)雜度為線性0(n)基于分治法的線性時間求主元素算法。算法的基本設(shè)計思想：中位數(shù)：數(shù)列排序后位于最中間的那個數(shù)。如果一個數(shù)列有主元素，那么必然是其中位數(shù)。求一個數(shù)列有沒有主元素，只要看中位數(shù)是不是主元素。找中位數(shù)的方法:選擇一個元素作為劃分起點，然后用快速排序的方法將小于它的移動到左邊，大于它的移動到右邊。這樣就將元素劃分為兩個部分。此時，劃分元素所在位置為k。如果k>n/2,那么繼續(xù)用同樣的方法在左邊部分找；如果kvn/2，就在右邊部分找；k=n/2就找到了中位元素。根據(jù)快速排序的思想，可以在平均時間復(fù)雜度為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