考研計算機專業課核心考點

我們在進行考研計算機專業課的複習時，需要掌握好一些核心的考點。小編爲大家精心準備了考研計算機核心考點指南攻略，歡迎大家前來閱讀。

一：隊列和棧結構的概念理解

棧是僅限制在表的一端進行插入和刪除運算的線性表，稱插入、刪除這一端爲棧頂。表中無元素時爲空棧。棧的修改是按後進先出的原則進行的。通常棧有順序棧和鏈棧兩種存儲結構。

隊列是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱爲隊頭，允許插入的一端稱爲隊尾，隊列的操作原則是先進先出的。隊列也有順序存儲和鏈式存儲兩種存儲結構。

核心考點二：線性表中單鏈表相關算法設計與實現

一些基礎但又重要的單鏈表相關算法，如：

1.打印單鏈表，void PrintList(List list); 使用一個指針遍歷所有鏈表節點。

2.兩個升序鏈表,打印tarList中的相應元素，這些元素的序號由SeqList指定，void PrintLots(List tarList, List seqList); 使用兩個指針分別遍歷兩個鏈表，每次取出序列鏈表的一個序號後，根據該序號，到達目標鏈表指定節點。

3.兩個升序鏈表的交集 ，List Intersect(List l1, List l2);

4.兩個升序鏈表的並集 ，List Join(List l1, List l2);

5.單鏈表就地置逆，void Reverse(List l); 使用三個指針表示前驅，當前和後繼節點，每次將當前節點的Next指向前驅節點，然後向後遍歷直到鏈表末尾。

核心考點三：二叉樹的遍歷

遍歷的過程就是把非線性結構的二叉樹中的結點排成一個線性序列的過程。

二叉樹遍歷方法可分爲兩大類，一類是“寬度優先”法，即從根結點開始，由上到下，從左往右一層一層的遍歷;另一類是“深度優先法”，即一棵子樹一棵子樹的遍歷。

從二叉樹結構的整體看，二叉樹可以分爲根結點，左子樹和右子樹三部分，只要遍歷了這三部分，就算遍歷了二叉樹。設D表示根結點，L表示左子樹，R表示右子樹，則DLR的組合共有6種，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左後右，則只有DLR，LDR，LRD三種，分別稱爲先(前)序法(先根次序法)，中序法(中根次序法，對稱法)，後序法(後根次序法)。三種遍歷的遞歸算法如下：

1.先序法(DLR)

若二叉樹爲空，則空操作，否則：訪問根結點先序遍歷左子樹先序遍歷右子樹。

2.中序法(LDR)

若二叉樹爲空，則空操作，否則：中序遍歷左子樹訪問根結點中序遍歷右子樹.

3.後序法(LRD)

若二叉樹爲空，則空操作，否則：後序遍歷左子樹後序遍歷右子樹訪問根結點.

核心考點四：完全二叉樹中有關結點個數計算

完全二叉樹的定義：深度爲k，有n個結點的二叉樹當且僅當其每一個結點都與深度爲k的滿二叉樹中編號從1至n的結點一一對應時，稱爲完全二叉樹。

完全二叉樹的葉子數爲(n + 1) / 2取下整。

核心考點五：森林與二叉樹之間的轉換以及轉換過程中結點之間的關係

將一棵樹轉換爲二叉樹的方法是：

1.樹中所有相鄰兄弟之間加一條連線。

2.對樹中的每個結點，只保留其與第一個孩子結點之間的連線，刪去其與其它孩子結點之間的連線。

3.以樹的根結點爲軸心，將整棵樹順時針旋轉一定的角度，使之結構層次分明。

森林轉換爲二叉樹的方法如下：

1.將森林中的每棵樹轉換成相應的二叉樹。

2.第一棵二叉樹不動，從第二棵二叉樹開始，依次把後一棵二叉樹的根結點作爲前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起後，所得到的二叉樹就是由森林轉換得到的二叉樹。

樹和森林都可以轉換爲二叉樹，二者的不同是:樹轉換成的二叉樹,其根結點必然無右孩子，而森林轉換後的二叉樹，其根結點有右孩子。將一棵二叉樹還原爲樹或森林，具體方法如下：

1.若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子、……都與該結點 的雙親結點用線連起來。

2.刪掉原二叉樹中所有雙親結點與右孩子結點的連線。

3.整理由1、2兩步所得到的樹或森林，使之結構層次分明。

核心考點六：對無向連通圖特性的理解

無向圖的每條邊，在頂點計算度的過程中，都要兩次參與計算(與邊兩關聯的2個頂點)，因此所有頂點的度之和爲偶數。

具有n個頂點的無向連通圖，其邊數大於或等於n-1。

在無向連通圖中，所有頂點的度數都有可能大於1。

核心考點七：對m階B樹定義的理解

一棵m階的B樹滿足下列條件：

1. 每個結點至多有m棵子樹。

2. 除根結點外，其它每個分支至少有m/2棵子樹。

3. 根結點至少有兩棵子樹(除非B樹只有一個結點)。

4. 所有葉結點在同一層上。B樹的葉結點可以看成一種外部結點，不包含任何信息。

5. 有j個孩子的非葉結點恰好有j-1個關鍵碼，關鍵碼按遞增次序排列。結點中包含的信息爲 ∶ (p0,k1,p1,k2,p2, … ,kj-1,pj-1)

其中，ki爲關鍵碼，且滿足ki

核心考點八：帶權圖的最短路徑算法及應用

迪傑斯特拉(Dijkstra)算法求單源最短路徑，算法思想：

設S爲最短距離已確定的頂點集(看作紅點集)，V-S是最短距離尚未確定的頂點集(看作藍點集)。

1.初始化：初始化時，只有源點s的最短距離是已知的(SD(s)=0)，故紅點集S={s}，藍點集爲空。

2.重複以下工作，按路徑長度遞增次序產生各頂點最短路徑，在當前藍點集中選擇一個最短距離最小的藍點來擴充紅點集，以保證算法按路徑長度遞增的次序產生各頂點的最短路徑。當藍點集中僅剩下最短距離爲∞的藍點，或者所有藍點已擴充到紅點集時，s到所有頂點的最短路徑就求出來了。

注意：①若從源點到藍點的路徑不存在，則可假設該藍點的最短路徑是一條長度爲無窮大的虛擬路徑。②從源點s到終點v的最短路徑簡稱爲v的最短路徑;s到v的最短路徑長度簡稱爲v的最短距離，並記爲SD(v)。

核心考點九：堆排序

大根堆的定義：完全二叉樹，任一非葉子結點都大於等於它的孩子，也就是說根結點是最大的。而且顯然大根堆的任一棵子樹也是大根堆。

堆排序的基本思想：記錄區的分爲無序區和有序區前後兩部分;用無序區的數建大根堆，得到的根(最大的數)和無序區的最後一個數交換，也就是將該根歸入有序區的最前端;如此重複下去，直至有序區擴展至整個記錄區。

具體操作可按下面步驟實現：

1.建大根堆

2.交換根和無序區最後一個數

3.重建大根堆，因爲交換隻是使根改變了，所以左右子樹依然分別是大根堆。

4.比較根，左子樹的根和右子樹的根，如果根最大，則無須再作調整，樹已經是大根堆了;如果左子樹的根最大，交換它與根，再遞歸調整左子樹;如果右子樹的根最大，交換它與根，再遞歸調整右子數。

5.遞歸調整到葉子的時候，樹就是大根堆了。

核心考點十：各類排序算法的特點及比較

幾種主要的排序算法：冒泡排序、選擇排序、插入排序、快速排序、歸併排序、Shell排序、堆排序等。

冒泡排序算法思想：將待排序的元素看作是豎着排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。

選擇排序算法思想：選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。

插入排序算法思想：經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。

快速排序算法思想：快速排序的基本思想是基於分治策略的。對於輸入的子序列L[p..r]，如果規模足夠小則直接進行排序，否則分三步處理：1. 分解(Divide)：將輸入的序列L[p..r]劃分成兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大於L[q+1..r]中任一元素的值。2. 遞歸求解(Conquer)：通過遞歸調用快速排序算法分別對L[p..q]和L[q+1..r]進行排序。3. 合併(Merge)：由於對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序後不需要執行任何計算L[p..r]就已排好序。

歸併排序算法思想：分而治之(divide - conquer)。每個遞歸過程涉及三個步驟：1.分解，把待排序的n個元素的序列分解成兩個子序列，每個子序列包括 n/2 個元素。2. 治理，對每個子序列分別調用歸併排序MergeSort，進行遞歸操作。3. 合併，合併兩個排好序的子序列,生成排序結果。

Shell排序算法思想：算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。

堆排序算法思想：用大根堆排序的基本思想：1.先將初始文件R[1..n]建成一個大根堆，此堆爲初始的無序區。2.再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1]≤R[n]。3. 由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整爲堆。

計算機科目的考試大綱中，操作系統科考查目標是掌握計算機網絡的基本概念、基本原理和基本方法;掌握計算機網絡的體系結構和典型網絡協議、瞭解典型網絡的組成的特點、理解典型網絡設備的工作原理;能夠運用計算機網絡的基本概念、基本原理和基本方法進行網絡系統的分析、設計和應用。

對於教材的選擇，建議大家選擇電子工業出版社謝希仁主編的《計算機網絡(第五版)》。這本書的提綱和考試大綱非常接近。計算機網絡科目中基本概念很多，如果沒有時間複習教材，可直接從精確提煉考綱中涉及的內容，突出考試重點的講義類輔導書入手，如《計算機學科專業基礎綜合輔導講義》就是不錯的選擇。

計算機網絡科目的知識點非常分散，所以對於計算機網絡的複習，首先要理解網絡分層結構，OSI參考模型和TCP/IP模型的區別和聯繫，然後按照OSI七層模型展開復習。

下面來看一下複習重點：

1.計算機網絡體系結構

這部分內容要了解計算機網絡概念的概念、組成;計算機網絡的分類，發展過程等。理解網絡分層結構、網絡協議、接口、服務等概念。重點掌握OSI參考模型和TCP/IP模型的區別和聯繫。

2.物理層

對這部分內容的考查，以基本原理和概念的形式爲主。掌握信道、信號、帶寬、碼元、波特、速率、信元、信宿、編碼與調製、電路交換、報文交換、分組交換、數據報、虛電路等基本概念。重點掌握奈奎斯特定理和香農定理。此外，還要注意複習每層上的網絡設備，在考查目標中特別強調了對典型網絡設備的工作原理及應用的考查。物理層設備有集線器、中繼器。

3.數據鏈路層

這部分內容的'複習可以從數據鏈路層所提供的功能入手，便於理解和記憶。數據鏈路層的主要功能：差錯控制、流量控制與可靠傳輸機制、介質訪問控制。建議重點複習流量控制與可靠傳輸機制、介質訪問控制這兩部分內容。數據鏈路層的協議中，建議重點複習CSMA/CD協議。在前兩年的考試中，考查了後退N幀協議，CSMA/CD協議等內容，這些內容不好理解，大家可以通過《計算機學科專業基礎綜合輔導講義》的中相應例題的講解來理解掌握這部分內容。

4.網絡層

網絡層的主要功能是路由與轉發，因此路由協議和路由算法是考試的重點。路由算法重點複習距離-向量路由算法、鏈路狀態路由算法。IP協議也是考試的重點，要求掌握IPV4地址與NAT、子網劃分、子網掩碼、CIDR。另外，IPV6協議是未來的方展方向，要了解IPV6的報文結構和地址分配方式。

5.傳輸層

傳輸層重點考查UDP協議和TCP協議。要掌握UDP數據報的發送和UDP校驗方式;TCP連接管理、三次握手協議、TCP可靠傳輸，以及TCP流量控制與擁塞控制。這部分要多做習題來加深理解。我給大家推薦的是《計算機學科專業基礎綜合輔導講義同步練習》，這本書是與《計算機學科專業基礎綜合輔導講義》配套的一本習題集，大家可以通過同步習題訓練加深對知識的理解，掌握解題思路和技巧。

6.應用層

應用層要重點掌握DNS、FTP、電子郵件及xxx的概念、基本原理，所涉及的網絡協議等。

▶考研計算機考什麼?

1、計算機科學與技術學科的初試科目調整後爲4門，即政治理論、外國語、數學一和計算機學科專業基礎綜合，卷面滿分值分別爲100分、100分、150分和150分。

2、計算機學科專業基礎綜合的考試內容包括：數據結構、計算機組成原理、操作系統和計算機網絡，重點考查考生掌握相關基礎知識、基本理論和分析問題解決問題的能力。考試內容及試卷結構在考試大綱中確定。

3、計算機學科專業基礎綜合科目實行聯合命題，命題工作由全國學位與研究生教育學會工科委員會在教育部考試中心指導下組織實施，閱卷工作由省級招生考試機構統一組織，有關考務工作要求另行通知。

4、對於授理學學位的招生單位，第三單元考試科目可選數學一，也可自命題;第四單元考試科目必須採用聯考的計算機學科專業基礎綜合。

5、相關招生單位均應根據初試科目內容、要求的變化和《教育部關於加強碩士研究生招生複試工作的指導意見》(教學〔2006〕4號)的要求，及時對該學科複試內容、辦法和其他相關工作作出相應調整。

6、有關招生單位可充分利用接收推免生的方式招收跨學科專業的生源，對此招生部門應主動做好與培養、推薦部門的銜接工作。

▶複習建議

建議廣大考生至少從九月份就應該開始專業課的複習了。並且按照由難到易的順序複習專業課科目，即按照《數據結構》，《計算機組成原理》，《操作系統》，《計算機網絡》的順序來規劃複習專業課。

▶複習思路

1、"數據結構"複習思路

"數據結構"的複習應以"線性結構→樹型結構→圖型結構→查找表→排序算法"爲主線進行復習，重點在"線性結構"、"圖"和"排序"三個部分，"線性結構"、"樹"和"圖"側重基礎概念、基礎原理和基礎方法的掌握，"圖"、"查找"和"排序"則側重具體應用的考覈。

2、"計算機組成原理"複習思路

"計算機組成原理"按照馮·諾伊曼計算機5部分組成結構爲大塊進行復習。"計算機系統概述"和"數的表示和運算"重點在於基本概念的掌握，沒有具體應用。而"存儲器的層次結構"，"指令系統"，"中央處理器"，"總線"和"輸入輸出系統"部分除了掌握基本原理，基本方法外，重點掌握應用。

3、"操作系統"複習思路操作系統"複習思路

"操作系統"按照操作系統的基本功能爲主線進行復習，即"進程管理"，"內存管理"，"文件管理"和"輸入輸出管理"。其中重點部分在"進程管理"和"內存管理"。

4、"計算機網絡"複習思路計算機網絡"複習思路

"計算機網絡"按照OSI網絡參考模型的層次結構爲順序進行復習，複習重點在於"數據鏈路層"，"網絡層"，"傳輸層"和"應用層"。

5、關於計算機專業基礎綜合考試、時間上安排、各階段選用什麼樣的複習資料

第一階段是全面複習、打好基礎的階段。時間一般從3月份開始到7月份左右。

這一階段選用的複習資料主要是和大綱比較吻合的教材以及配套的習題。目前來說，教材已經基本統一。數據結構選用嚴蔚敏主編、清華大學出版社出版的C語言版的《數據結構》，習題建議選用李春葆主編、清華大學出版社出版的《數據結構習題與解析》;計算機組成原理有兩個版本的教材，可以任選其一：一個版本是白中英主編、科學出版社出版的《計算機組織與結構》(最新版是第4版)及配套習題，另外一個版本是唐朔飛主編、高等教育出版社出版的《計算機組成原理》及配套習題;操作系統一般選用湯子瀛主編、西安電子科技大學出版社出版的《計算機操作系統》，配套習題可以選用李春葆主編、清華大學出版社出版的《操作系統習題與解析》;計算機網絡選用的教材是謝希仁主編、電子工業出版社出版的《計算機網絡》(最新版是第5版)及配套習題。

第二階段是強化複習、重點深入的階段。時間一般是7、8月份到10月份。

這一階段可以選用高等教育出版社出版的的《計算機專業基礎綜合考試大綱解析》，或者選用復旦大學出版社出版的《計算機專業基礎綜合考試複習指南》。這兩本書都是根據考研大綱編寫的，並且都配有相當數量的習題。

第三階段是系統總結、模擬訓練的階段。時間一般從11月份到考前。

這一階段考生必須對學過的知識進行系統總結，找出自己的薄弱環節，查漏補缺，同時要精選一定量的模擬試題或歷年真題演練，去年這方面的模擬試題很少，比較有代表性的就是鞏微主編、原子能出版社出版的《計算機學科專業基礎綜合考試全真模擬試題集》。通過模擬訓練，一方面可以幫助考生髮現自己的薄弱環節;另一方面，也有助於培養考生的臨考狀態，是適應真實考場必不可少的一步。

以上三個階段，對於基礎比較好的同學，也可以直接從第二個階段開始。

▶特別注意

一是合理安排時間、制訂複習計劃：在可能的情況下，儘量及早準備，保證按計劃完成階段性複習和總複習;二是重視基礎、多做總結、提高效率：儘量多動手、多總結，把學過的知識系統化，複習過程中可以眼、腦、手並用，保證複習效果;三是注意生活規律、適當調節：考研是一場持久戰，不是速決戰，考生一定要注意在緊張複習的同時，適當調節，以始終保持良好的複習狀態。

▶參考書目及習題冊推薦

《數據結構》(數據結構》(C語言版)嚴蔚敏吳偉民編著清華大學出版社

《計算機操作系統》湯子瀛等主編西安電子科技大學出版社

《計算機網絡(第五版)》謝希仁編著電子工業出版社

《計算機組成原理(第2版)》唐朔飛主編高等教育出版社