考研專業課資料資料結構的複習重點歸納

我們在進行考研專業課的複習時，需要把資料資料結構的複習重點歸納好。小編為大家精心準備了考研專業課資料資料結構的複習知識點，歡迎大家前來閱讀。

一、資料結構的章節結構及重點構成

資料結構學科的章節劃分基本上為：概論，線性表，棧和佇列，串，多維陣列和廣義表，樹和二叉樹，圖，查詢，內排，外排，檔案，動態儲存分配。

對於絕大多數的學校而言，“外排，檔案，動態儲存分配”三章基本上是不考的，在大多數高校的計算機本科教學過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對於報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那麼這部分朋友就要留意這三章了。

按照以上我們給出的章節以及對後三章的介紹，資料結構的章節比重大致為：

概論：內容很少，概念簡單，分數大多隻有幾分，有的學校甚至不考。

線性表：基礎章節，必考內容之一。考題多數為基本概念題，名校考題中，鮮有大型演算法設計題。如果有，也是與其它章節內容相結合。

棧和佇列：基礎章節，容易出基本概念題，必考內容之一。而棧常與其它章節配合考查，也常與遞迴等概念相聯絡進行考查。

串 ：基礎章節，概念較為簡單。專門針對於此章的大型演算法設計題很少，較常見的是根據KMP進行演算法分析。

多維陣列及廣義表 ：基礎章節，基於陣列的演算法題也是常見的，分數比例波動較大，是出題的“可選單元”或“侯補單元”。一般如果要出題，多數不會作為大題出。陣列常與“查詢，排序”等章節結合來作為大題考查。

樹和二叉樹 ：重點難點章節，各校必考章節。各校在此章出題的不同之處在於，是否在本章中出一到兩道大的演算法設計題。通過對多所學校的試卷分析，絕大多數學校在本章都曾有過出大型演算法設計題的歷史。

圖 ：重點難點章節，名校尤愛考。如果作為重點來考，則多出現於分析與設計題型當中，可與樹一章共同構成演算法設計大題的題型設計。

查詢 ：重點難點章節，概念較多，聯絡較為緊密，容易混淆。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。演算法設計型題中可以陣列結合來考查，也可以與樹一章結合來考查。

排序 ：與查詢一章類似，本章同屬於重點難點章節，且概念更多，聯絡更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序演算法的優劣比較此類的題。演算法設計大題中，如果作為出題，那麼常與陣列結合來考查。

二、資料結構各章節重點勾劃：

第0章　概述

本章主要起到總領作用，為讀者進行資料結構的學習進行了一些先期鋪墊。大家主要注意以下幾點：資料結構的基本概念，時間和空間複雜度的概念及度量方法，演算法設計時的注意事項。本章考點不多，只要稍加註意理解即可。

第一章　線性表

作為線性結構的開篇章節，線性表一章線上性結構的學習乃至整個資料結構學科的學習中，其作用都是不可低估的。在這一章，第一次系統性地引入鏈式儲存的概念，鏈式儲存概念將是整個資料結構學科的重中之重，無論哪一章都涉及到了這個概念。

總體來說，線性表一章可供考查的重要考點有以下幾個方面：

1.線性表的相關基本概念，如：前驅、後繼、表長、空表、首元結點，頭結點，頭指標等概念。

2.線性表的結構特點，主要是指：除第一及最後一個元素外，每個結點都只有一個前趨和只有一個後繼。

3.線性表的順序儲存方式及其在具體語言環境下的兩種不同實現：表空間的靜態分配和動態分配。靜態連結串列與順序表的相似及不同之處。

4.線性表的鏈式儲存方式及以下幾種常用連結串列的特點和運算：單鏈表、迴圈連結串列，雙向連結串列，雙向迴圈連結串列。其中，單鏈表的歸併演算法、迴圈連結串列的歸併演算法、雙向連結串列及雙向迴圈連結串列的插入和刪除演算法等都是較為常見的考查方式。此外，近年來在不少學校中還多次出現要求用遞迴演算法實現單鏈表輸出(可能是順序也可能是倒序)的問題。

在連結串列的小題型中，經常考到一些諸如：判表空的題。在不同的連結串列中，其判表空的方式是不一樣的，請大家注意。

5.線性表的順序儲存及鏈式儲存情況下，其不同的優缺點比較，即其各自適用的場合。單鏈表中設定頭指標、迴圈連結串列中設定尾指標而不設定頭指標以及索引儲存結構的各自好處。

第二章　棧與佇列

棧與佇列，是很多學習DS的同學遇到第一隻攔路虎，很多人從這一章開始坐暈車，一直暈到現在。所以，理解棧與佇列，是走向DS高手的一條必由之路，。

學習此章前，你可以問一下自己是不是已經知道了以下幾點：

1.棧、佇列的定義及其相關資料結構的概念，包括：順序棧，鏈棧，共享棧，迴圈佇列，鏈隊等。棧與佇列存取資料(請注意包括：存和取兩部分)的特點。

2.遞迴演算法。棧與遞迴的關係，以及藉助棧將遞迴轉向於非遞迴的經典演算法：n!階乘問題，fib數列問題，hanoi問題，揹包問題，二叉樹的遞迴和非遞迴遍歷問題，圖的深度遍歷與棧的關係等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節中進行考查。

3.棧的應用：數值表示式的求解，括號的配對等的原理，只作原理性瞭解，具體要求考查此為題目的演算法設計題不多。

4.迴圈佇列中判隊空、隊滿條件，迴圈佇列中入隊與出隊演算法。

如果你已經對上面的幾點了如指掌，棧與佇列一章可以不看書了。注意，我說的是可以不看書，並不是可以不作題哦。

第三章　串

經歷了棧一章的痛苦煎熬後，終於迎來了串一章的柳暗花明。

串，在概念上是比較少的一個章節，也是最容易自學的章節之一，但正如每個過來人所瞭解的，KMP演算法是這一章的重要關隘，突破此關隘後，走過去又是一馬平川的大好DS山河了，呵呵。

串一章需要攻破的主要堡壘有：

1.串的基本概念，串與線性表的關係(串是其元素均為字元型資料的特殊線性表)，空串與空格串的區別，串相等的條件

2.串的基本操作，以及這些基本函式的使用，包括：取子串，串連線，串替換，求串長等等。運用串的基本操作去完成特定的演算法是很多學校在基本操作上的考查重點。

3.順序串與鏈串及塊鏈串的區別和聯絡，實現方式。

演算法思想。KMP中next陣列以及nextval陣列的求法。明確傳統模式匹配演算法的不足，明確next陣列需要改進之外。其中，理解演算法是核心，會求陣列是得分點。不用我多說，這一節內容是本章的重中之重。可能進行的考查方式是：求next和nextval陣列值，根據求得的next或nextval陣列值給出運用KMP演算法進行匹配的匹配過程。

第四章　陣列與廣義表

學過程式語言的朋友，陣列的概念我們已經不是第一次見到了，應該已經“一回生，二回熟”了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學裡的程式語言所關注的不太一樣，下面會作介紹。

廣義表的概念，是資料結構裡第一次出現的。它是線性表或表元素的有限序列，構成該結構的每個子表或元素也是線性結構的，所以，這一章也歸入線性結構中。

本章的考查重點有：

1.多維陣列中某陣列元素的position求解。一般是給出陣列元素的首元素地址和每個元素佔用的地址空間並組給出多維陣列的維數，然後要求你求出該陣列中的某個元素所在的位置。

2.明確按行儲存和按列儲存的區別和聯絡，並能夠按照這兩種不同的儲存方式求解1中型別的題。

3.將特殊矩陣中的元素按相應的換算方式存入陣列中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同儲存方式：三元組，帶輔助行向量的二元組，十字連結串列儲存。掌握將稀疏矩陣的三元組或二元組向十字連結串列進行轉換的演算法。

4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點，是理解整個廣義表一節演算法的基礎。近來，在一些學校中，出現了這樣一種題目型別：給出對某個廣義表L若干個求了若干次的取頭和取尾操作後的串值，要求求出原廣義表L。大家要留意。

5.與廣義表有關的遞迴演算法。由於廣義表的定義就是遞迴的，所以，與廣義表有關的演算法也常是遞迴形式的。比如：求表深度，複製廣義表等。這種題目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對錶頭和表尾進行操作;二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。

第五章　樹與二叉樹

從對線性結構的研究過度到對樹形結構的研究，是資料結構課程學習的一次躍變，此次躍變完成的好壞，將直接關係到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的'專業課總分。所以，樹這一章的重要性，已經不說自明瞭。

總體來說，樹一章的知識點包括：

二叉樹的概念、性質和儲存結構，二叉樹遍歷的三種演算法(遞迴與非遞迴)，在三種基本遍歷演算法的基礎上實現二叉樹的其它演算法，線索二叉樹的概念和線索化演算法以及線索化後的查詢演算法，最優二叉樹的概念、構成和應用，樹的概念和儲存形式，樹與森林的遍歷演算法及其與二叉樹遍歷演算法的聯絡，樹與森林和二叉樹的轉換。

1、資料結構

嚴蔚敏教材+資料結構習題與解析(清華大學出版社第三版)

8月：結合自己的做題經驗再看看教材。然後，這個月的重點是專攻演算法題，每天看1、2道，寫1、2道，記住一定要每天，千萬不要偷懶。

2、組成原理

組成原理其實不需要做太多的題，重點是理解和記憶。

8月：爭取做完一本完整的習題書。

3、作業系統

作業系統是4門課裡最簡單的了，這35分要力爭拿30分或以上。

8月：做一本習題，還是推薦習題與解析(清華大學出版社第3版)，大題小題均有詳細講解。作業系統每天看看教材和做習題，掃清盲點即可。另外，每週動手做一個PV操作的演算法題，爭取這個階段的複習，能夠把演算法題做到“從會到熟“的地步。

4、計算機網路

畢竟網路就25分，不要花費太多的時間。

8月：找些質量好的題來訓練，再結合著讀一讀教材。這門課保證拿20分左右就可以，畢竟這門專業課要拉開分數，主要靠的是資料結構和組成原理這兩部分。

一、考查目標

1、理解單處理器計算機系統中各部件的內部工作原理、組成結構以及相互連線方式，具有完整的計算機系統的整機概念。

2、理解計算機系統層次化結構概念，熟悉硬體與軟體之間的介面，掌握指令集體系結構的基本知識和基本實現方法。

3、能夠運用計算機組成的基本原理和基本方法，對有關計算機硬體系統中的理論和實際問題進行計算、分析，並能對一些基本部件進行簡單設計。

二、知識點解析

在計算機組成原理方面，主要考查計算機系統基礎知識、資料的表示和運算、儲存器層次結構、指令系統、中央處理器、匯流排、輸入輸出系統。

1、計算機系統概述

學習計算機組成原理之前，我們先要了解計算機的發展歷程，搞清楚計算機的系統層次結構，包括計算機硬體的基本組成(五大部件的構成)、計算機軟體的分類，以及計算機的基本工作過程。

從體系結構上來看，有多種不同型別的計算機，那麼這些不同的計算機誰好誰壞?如何評價?所以，還需要我們瞭解計算機效能評價指標和相關引數，包括吞吐量、響應時間;CPU時鐘週期、主頻、CPI、CPU執行時間;MIPS、MFLOPS等。

2、資料的表示和運算

我們日常所使用的是十進位制資料，但在計算機中，除了十進位制資料外，還有二進位制、八進位制、十六進位制表示方法，我們要掌握這些進位計數制及其相互轉換的方法，要搞清楚真值(實際的數值)和機器數(計算機中表示的數值)之間的關係，特別是負數的各種表示。另外，還要理解BCD碼、字元與字串的編碼方法，以及資料的校驗碼(奇偶校驗、CRC冗餘校驗等)。

不管是哪種進位制和校驗方法，計算機中資料的表示有原碼、反碼、補碼等方法，我們要搞清楚它們之間的關聯與區別。

在計算機中對資料進行計算，分為定點表示和浮點表示。

在定點數的表示和運算方面，我們要掌握定點數的表示(無符號數的表示，有符號數的表示)和定點數的運算，包括定點數的位移運算、原碼定點數的加/減運算、補碼定點數的加/減運算、定點數的乘/除運算、溢位概念和判別方法。在浮點數的表示和運算方面，我們要掌握浮點數的表示(浮點數的表示範圍和IEEE754標準)和浮點數的加/減運算。

本知識點的最後一個考點就是算術邏輯單元ALU，我們要掌握序列加法器和並行加法器、算術邏輯單元ALU的功能和結構。

3、儲存器層次結構

從整個計算機的儲存體系來看，可以看成是一個“Cache—記憶體—外存”三級結構，在這個層次化結構中，我們要掌握儲存器的分類以及各類儲存器的基本工作原理，包括半導體隨機存取儲存器(SRAM、DRAM)、只讀儲存器(ROM)，掌握主儲存器(記憶體)與CPU的連線和資料交換、雙口RAM和多模組儲存器，還有就是外儲存器。

在儲存器這個知識點中，2個很重要的考點是高速緩衝儲存器(Cache)和虛擬儲存器。

在CPU和記憶體之間增加一層Cache，其目的是為了解決CPU和記憶體的速度匹配問題。在這一點，我們要掌握程式訪問的區域性性原理(時間區域性性、空間區域性性)、Cache的基本工作原理(命中率)、Cache和主存之間的對映方式、Cache中主存塊的替換演算法，以及Cache寫策略。

虛擬儲存器的重點在於“虛擬”二字，我們要掌握虛擬儲存器的基本概念及種類，包括頁式虛擬儲存器、段式虛擬儲存器、段頁式虛擬儲存器、TLB(快表)等，理解這些虛擬儲存器的基本原理、碎片的處理，各種方法的優點和缺點。

4、指令系統

在指令系統知識點中，我們要掌握指令的格式(包括指令的基本格式、定長操作碼指令格式、擴充套件操作碼指令格式)和各種定址方式，還要能夠區分資料定址和指令定址的區別。

本知識點的另外一個重要考點就是CISC(複雜指令系統計算機)和RISC(精簡指令系統計算機)，我們要掌握它們的基本概念、特徵，以及它們之間的主要區別。

5、中央處理器

中央處理器，也就是我們常說的CPU。在這個知識點，我們要掌握CPU的功能和基本結構，以及工作原理，具體包括指令執行過程、資料通路的功能和基本結構、控制器的功能和工作原理(硬佈線控制器、微程式控制器)。特別是在微程式控制器考點中，要掌握微程式、微指令和微命令，微指令的編碼方式，以及微地址的形式方式。

在這個知識點中，一個最重要的考點是流水線(主要是指令流水線)。我們要搞清楚流水線的基本概念(包括超標量和動態流水線)，為什麼需要流水線，流水線有哪些優勢，哪些因素會影響流水線，等等。在這一點，有可能出現計算題，例如，求流水線的週期、求指令的執行時間。有關流水線，還有一些評價指標，例如流水線的吞吐率、加速比等。

6、匯流排

匯流排就是一組進行互連和傳輸資訊(指令、資料和地址)的訊號線，我們要掌握匯流排的基本概念，匯流排的分類，以及匯流排的組成和效能指標(例如，各類匯流排的寬度會影響哪些部件的效能等)。

其次，就是要掌握匯流排仲裁方法(包括集中仲裁方式和分佈仲裁方式)和匯流排操作和定時(包括同步定時方式和非同步定時方式)。

最後，就是要對匯流排的標準(正式標準和工業標準)有所瞭解，匯流排標準主要規定匯流排的機械結構規範、功能結構規範和電氣規範。

7、輸入輸出系統

在輸入輸出(I/O)系統知識點，我們首先要掌握I/O系統的基本概念，理解各種外部裝置，其中包括輸入裝置(鍵盤、滑鼠、掃描器等)、輸出裝置(顯示器、印表機等)、外儲存器(硬碟儲存器、磁碟陣列、光碟儲存器等)。要理解這些裝置的基本工作原理和常見的效能指標。例如顯示器的解析度、磁碟的讀寫時間等，特別是磁碟的有關讀寫過程(尋道時間、等待時間等)，是一定要掌握的。

其次，我們要掌握I/O介面(I/O控制器)的功能和基本結構、I/O埠及其編址方式。

在I/O方式中，主要掌握程式查詢方式、程式中斷方式、DMA方式、通道方式的基本概念、工作原理和過程，以及這些方式之間的區別、各自的優點和缺點、應用場合。在這些方式中，以程式中斷方式為考查重點，我們要掌握中斷的基本概念、中斷響應過程、中斷處理過程、多重中斷和中斷遮蔽的概念。

三、複習方法

學習方法

計算機組成原理的基本要求是使考生掌握計算機常用的邏輯器件、部件的原理、引數及使用方法，學懂簡單、完備的單臺計算機的基本組成原理，學習計算機設計中的入門性知識，掌握維護、使用計算機的技能。

總的來講，計算機組成原理課程中屬於記憶型的知識比較多，需要我們花時間去對相關概念、原理進行識記。另外，就是有關引數和效能指標的計算和評價，這一塊是需要理解的，不能靠死記硬背。在學習計算機組成原理課程中，要注意以下幾方面的問題：

(1)要正確理解考試大綱中規定的各種基本概念，掌握各概念中的要點。

(2)要能將有關的概念和原理聯絡起來，不要孤立地學習各個部分的內容，比如資料表示、運算和運算器部件等，都要關聯起來。

(3)要把握重點、難點問題，分清主次。所以，學習時要緊緊抓住考試大綱。