久久久国产精品亚洲一区_亚洲电影免费观看高清完整版在线观看 _亚洲欧美精品在线_亚洲影院色在线观看免费

834“數(shù)據(jù)結(jié)構(gòu)、計算機(jī)組成原理”復(fù)習(xí)參考提綱

一、 考察目標(biāo)

834 數(shù)據(jù)結(jié)構(gòu)、計算機(jī)組成原理要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。

二、 考試形式和試卷結(jié)構(gòu)

1、 試卷滿分及考試時間：本試卷滿分為150，考試時間為180分鐘

2、 答題方式：閉卷，筆試

3、 試卷內(nèi)容結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)75分、計算機(jī)組成原理75分

三、 考察范圍

數(shù)據(jù)結(jié)構(gòu)：

【總體要求】

 “數(shù)據(jù)結(jié)構(gòu)”要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的構(gòu)造和實現(xiàn)，具備應(yīng)用數(shù)據(jù)結(jié)構(gòu)分析、設(shè)計和求解實際問題的能力。要求掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；掌握線性結(jié)構(gòu)、樹和圖的邏輯結(jié)構(gòu)、存儲（物理）結(jié)構(gòu)，以及基本操作在不同存儲結(jié)構(gòu)上的實現(xiàn)，并能夠?qū)舅惴ㄟM(jìn)行時間復(fù)雜度和空間復(fù)雜度分析；掌握基本的查找和排序方法及其算法實現(xiàn)，并能夠利用這些方法對實際問題進(jìn)行分析和求解，具備采用C或C++或 Java等編程語言設(shè)計與實現(xiàn)算法的能力。

（一）線性表

　　  1）線性表的基本概念和基本操作

      2）線性表的順序存儲及實現(xiàn)

      3）線性表的鏈?zhǔn)酱鎯皩崿F(xiàn)

  4）線性表的應(yīng)用

（二）棧和隊列

　    1）棧和隊列的基本概念和基本操作

      2）棧和隊列的存儲結(jié)構(gòu)與實現(xiàn)

        （1）棧的順序存儲及實現(xiàn)

        （2）棧的鏈?zhǔn)酱鎯皩崿F(xiàn)

        （3）隊列的鏈?zhǔn)酱鎯皩崿F(xiàn)

    （4）循環(huán)隊列的定義及實現(xiàn)
      3）棧和隊列的應(yīng)用

（三）串

1）串的基本概念和基本操作

      2）串的順序存儲、鏈?zhǔn)酱鎯皩崿F(xiàn)

      3）串的模式匹配

    （1）基本的模式匹配算法

    （2）KMP模式匹配算法（模式串的next函數(shù)計算）

（四）數(shù)組和廣義表

1）數(shù)組的基本概念和基本操作

2）數(shù)組的順序存儲

3）特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲

4）廣義表的基本概念和存儲結(jié)構(gòu)

（五）樹與二叉樹

1）樹的基本概念
      2）二叉樹

       （1）二叉樹的定義及性質(zhì)

       （2）二叉樹的順序存儲和鏈?zhǔn)酱鎯?/p>

       （3）二叉樹的先序、中序、后序遍歷和層序遍歷運算

       （4）線索二叉樹的定義與基本運算

3）樹和森林

       （1）樹的存儲結(jié)構(gòu)

       （2）樹（森林）與二叉樹的相互轉(zhuǎn)換

       （3）樹和森林的遍歷

4）哈夫曼（Huffman）樹的構(gòu)造與應(yīng)用

（六）圖

1）圖的基本概念和基本操作

  2）圖的存儲結(jié)構(gòu)

       （1）數(shù)組表示法（鄰接矩陣表示法）

       （2）鄰接表表示法、逆鄰接表表示法

       （3）鄰接多重表

       （4）十字鏈表

      3）圖的遍歷
       （1）深度優(yōu)先遍歷（DFS）算法

       （2）廣度優(yōu)先遍歷（BFS）算法

4）圖的應(yīng)用

 （1）最小生成樹求解方法（Prim算法、Kruskal算法）
       （2）最短路徑求解方法（Dijkstra算法、Floyd算法）
       （3）AOV-網(wǎng)和拓?fù)渑判蚍椒?br/>       （4）AOE-網(wǎng)和關(guān)鍵路徑求解方法

（七）查找

1）查找的基本概念
      2）靜態(tài)查找表

  （1）無序順序表、有序順序表

（2）順序查找算法

    （3）折半查找算法、折半查找判定樹的構(gòu)造
      3）動態(tài)查找表

        （1）二叉查找樹（二叉檢索樹、二叉排序樹）的構(gòu)造及查找、插入和刪除運算

        （2）平衡二叉樹的構(gòu)造及查找運算
        （3）B-樹的特點及查找運算

        （4）B+樹的基本概念

      4）哈希表

    （1）哈希表的基本概念

         （2）哈希表的構(gòu)造及查找運算

      5）查找算法的分析（平均查找長度計算）及應(yīng)用

（八）排序

1）排序的基本概念（排序過程中的基本操作、排序算法的時空復(fù)雜度及穩(wěn)定性）

2）簡單排序方法

        （1）直接插入排序算法

        （2）冒泡排序算法

        （3）簡單選擇排序算法

3）快速排序

4）堆排序

      5）歸并排序

      6）基數(shù)排序

        （1）多關(guān)鍵排序方法

        （2）鏈?zhǔn)交鶖?shù)排序方法及特點

7）外部排序的基本概念

計算機(jī)組成原理:

【總體要求】

 “計算機(jī)組成原理”要求學(xué)生掌握單處理器計算機(jī)系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機(jī)系統(tǒng)的整機(jī)概念。要求掌握計算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面；掌握計算機(jī)數(shù)據(jù)表示的方法，包括定點數(shù)和浮點數(shù)的表示；掌握運算器的原理和實現(xiàn)電路；掌握存儲層次的概念，掌握不同類型存儲器特性，包括SRAM、DRAM、ROM；掌握主存結(jié)構(gòu)及基本設(shè)計方法；會解決Cache存儲的一些基本問題；掌握磁盤基本原理及RAID；掌握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法；熟悉中央處理器的時序邏輯，即指令周期、CPU周期、節(jié)拍周期、時鐘周期之間的關(guān)系；掌握中央處理器控制器的基本設(shè)計方法，即硬布線和微程序控制，能夠根據(jù)模擬CPU及系統(tǒng)框架設(shè)計控制信號邏輯或者編寫簡單微操作流程；掌握計算機(jī)輸入輸出系統(tǒng)的基本概念，程序查詢方式、中斷方式和直接存儲器存取方式；掌握總線的仲裁方式和特點；基本掌握并行計算機(jī)的原理和發(fā)展趨勢；基本掌握對稱多處理器系統(tǒng)、多計算機(jī)系統(tǒng)的結(jié)構(gòu)及特點；掌握流水線技術(shù)，能夠計算各種流水線的性能指標(biāo)參數(shù)，分析流水線的特點，解決數(shù)據(jù)相關(guān)的方法等；能夠運用計算機(jī)組成的基本原理和基本方法，對有關(guān)計算機(jī)硬件系統(tǒng)中的理論和實際問題進(jìn)行計算、分析，并能對一些基本部件進(jìn)行簡單設(shè)計。

研究生課程考試是所學(xué)知識的總結(jié)性考試，考試水平應(yīng)達(dá)到或超過本科專業(yè)相應(yīng)的課程要求水平。

（一）計算機(jī)系統(tǒng)概論       

1.復(fù)習(xí)內(nèi)容

計算機(jī)的基本組成，馮.諾依曼計算機(jī)原理，計算機(jī)系統(tǒng)的層次結(jié)構(gòu)，計算機(jī)的分類及性能描述，計算機(jī)的發(fā)展歷程

2.具體要求

*計算機(jī)的基本組成

***硬件組成

***軟件組成

*馮.諾依曼計算機(jī)工作原理

***馮.諾依曼計算機(jī)結(jié)構(gòu)及工作過程

***馮.諾依曼計算機(jī)特點

*計算機(jī)系統(tǒng)的層次結(jié)構(gòu)

***層次結(jié)構(gòu)圖

*計算機(jī)的分類及性能描述

***Flynn分類法

***Amdahl定律和應(yīng)用

***吞吐量、響應(yīng)時間

***CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間

***MIPS、MFLOPS

（二）計算機(jī)系統(tǒng)中的數(shù)據(jù)表示       

1.復(fù)習(xí)內(nèi)容

數(shù)制與編碼，定點數(shù)據(jù)表示，浮點數(shù)據(jù)表示，糾錯和校驗

2.具體要求

*數(shù)制與編碼

***數(shù)制及相互轉(zhuǎn)換

***真值和機(jī)器數(shù)

*** BCD碼

*定點數(shù)據(jù)表示

***無符號數(shù)的表示

***有符號數(shù)的表示

***原碼、反碼、補(bǔ)碼、移碼

*浮點數(shù)據(jù)表示

***格式定義

***規(guī)格化

***數(shù)據(jù)范圍

***IEEE754標(biāo)準(zhǔn)

*糾錯和校驗

***奇偶校驗

***漢明編碼

***循環(huán)冗余校驗

（三）運算方法與運算器

1.復(fù)習(xí)內(nèi)容

定點數(shù)的位移運算，原碼定點數(shù)的加/減運算，補(bǔ)碼定點數(shù)的加/減運算，定點數(shù)的乘/除運算，溢出概念和判別方法，浮點數(shù)的加/減運算，浮點數(shù)的乘/除運算，算術(shù)邏輯單元ALU

2.具體要求

*原碼定點數(shù)的加/減運算

***方法，應(yīng)用

*補(bǔ)碼定點數(shù)的加/減運算

***方法，應(yīng)用

***行波進(jìn)位、先行進(jìn)位加法器

***移位處理

***溢出處理和判斷

*定點數(shù)的乘/除運算

***原碼乘法，補(bǔ)碼乘法

***恢復(fù)余數(shù)，不恢復(fù)余數(shù)除法

***陣列乘法器

***陣列除法器

*浮點數(shù)的加/減運算

***對階

***尾數(shù)加減

***規(guī)格化

***溢出處理

*浮點數(shù)的乘/除運算

***方法

***應(yīng)用

***規(guī)格化

*算術(shù)邏輯單元ALU

***組成

***類型

（四）存儲系統(tǒng)

1.復(fù)習(xí)內(nèi)容

存儲器的分類，存儲器的層次化結(jié)構(gòu)，半導(dǎo)體隨機(jī)存取存儲器，主存儲器與CPU的連接，雙口RAM和多模塊存儲器，高速緩沖存儲器，虛擬存儲器，硬盤存儲器

2.具體要求

*存儲器的分類

***按照不同方式進(jìn)行分類的方法

***存儲器容量、速度、可靠性

*存儲系統(tǒng)的層次化結(jié)構(gòu)

***具體層次化形式

***各種存儲器的位置

*半導(dǎo)體隨機(jī)存取存儲器

***SRAM存儲器的工作原理

***DRAM存儲器的工作原理

***ROM存儲器的工作原理

*主存儲器的構(gòu)成方法

***字?jǐn)U展方式

***位擴(kuò)展方式

*多端口、多模塊、相聯(lián)存儲器

***多端口存儲器--多端口組織形式

***多模塊存儲器--交叉存儲方式

***相聯(lián)存儲器--按內(nèi)容訪問的存儲器

*高速緩沖存儲器

***程序局部性及Cache工作原理

***Cache與主存地址映射與變換方式

***Cache替換算法

***Cache寫策略

*虛擬存儲器

***虛擬存儲器的基本概念

*硬盤存儲器

***磁記錄原理

***磁記錄方式

***磁盤的基本參數(shù)及計算 

***RAID

（五）指令系統(tǒng)       

1.復(fù)習(xí)內(nèi)容

指令格式，尋址方式，CISC和RISC基本概念。

2.具體要求

*指令格式

***指令的基本格式

***定長操作碼設(shè)計

***擴(kuò)展操作碼設(shè)計

***存儲器操作數(shù)的大/小端存儲、邊界對齊、堆棧操作、哈佛存儲結(jié)構(gòu)

*操作數(shù)的尋址方式

***有效地址的概念

***數(shù)據(jù)尋址和指令尋址

***常用尋址方式

* CISC和RISC的基本概念

***RISC的發(fā)展歷程

***CISC和RISC的技術(shù)特點

（六）中央處理器       

1.復(fù)習(xí)內(nèi)容

CPU的功能和基本結(jié)構(gòu)，指令執(zhí)行過程，數(shù)據(jù)通路的功能和基本結(jié)構(gòu)，控制器的功能和工作原理。

2.具體要求

* CPU的功能和基本結(jié)構(gòu)

***CPU的主要構(gòu)成部件

***CPU內(nèi)的常見寄存器

***CPU內(nèi)部的數(shù)據(jù)通路

*指令執(zhí)行過程

***時序發(fā)生器

***CPU內(nèi)部時序概念

***典型指令的執(zhí)行過程

*數(shù)據(jù)通路的功能和基本結(jié)構(gòu)

*控制器的功能和工作原理

***硬布線控制器結(jié)構(gòu)及設(shè)計方法

***微程序控制器結(jié)構(gòu)及設(shè)計方法

***微操作、微命令、微指令、微程序

***微操作和微命令序列（流程）設(shè)計

***微命令的互斥和相容

（七）流水線技術(shù)與指令級并行       

1.復(fù)習(xí)內(nèi)容

流水線概念，流水線分類，流水線性能指標(biāo)，流水線相關(guān)處理，超標(biāo)量處理，VLIW，多核處理器的基本概念。

2.具體要求

*流水線概念

*流水線分類

***不同方式的分類

***靜態(tài)多功能流水線

***動態(tài)多功能流水線

*流水線性能指標(biāo)

***吞吐率

***效率

***加速比

***時空圖

*流水線相關(guān)判定及處理

***結(jié)構(gòu)相關(guān)

***數(shù)據(jù)相關(guān)

***控制相關(guān)

***相關(guān)處理方式：等待（停頓）、直接通路、分支預(yù)測等

*超標(biāo)量處理器概念及特點

*VLIW處理器概念及特點

*多核處理器的基本概念

（八）總線與輸入輸出系統(tǒng)  

1.復(fù)習(xí)內(nèi)容

總線概述，總線仲裁，總線操作和定時，總線標(biāo)準(zhǔn)，I/O系統(tǒng)基本概念，外部設(shè)備，I/O接口，I/O方式。

2.具體要求

*總線概述

***總線的基本概念

***總線的分類

***總線的組成及性能指標(biāo)

*總線仲裁

***集中仲裁方式：菊花鏈方式、輪詢計數(shù)、獨立請求方式

***分布仲裁方式

*總線操作和定時

***總線讀寫操作

***同步定時方式

***異步定時方式

*總線標(biāo)準(zhǔn)

* I/O系統(tǒng)基本概念

*外部設(shè)備

***輸入設(shè)備

***輸出設(shè)備

* I/O接口

*** I/O接口的功能和基本結(jié)構(gòu)

*** I/O端口及其編址

*** I/O地址空間

* I/O方式

***程序查詢方式

***程序中斷方式：中斷的基本概念；中斷響應(yīng)過程；中斷處理過程；多重中斷和中斷屏蔽的概念

***DMA方式：DMA控制器的組成；DMA傳送過程

***通道方式：I/O通道的基本概念

（九）并行體系結(jié)構(gòu)  

1.復(fù)習(xí)內(nèi)容

并行處理的基本途徑，互連網(wǎng)絡(luò)，對稱多處理器。

2.具體要求

*并行處理的基本途徑

***時間重疊

***資源重復(fù)

***資源共享

*互連網(wǎng)絡(luò)

***定義

***基本互連網(wǎng)絡(luò)：交叉開關(guān)網(wǎng)絡(luò)、多級互連網(wǎng)絡(luò)、環(huán)形網(wǎng)絡(luò)、網(wǎng)格型網(wǎng)絡(luò)

*對稱多處理器系統(tǒng)結(jié)構(gòu)及特點

*多計算機(jī)系統(tǒng)結(jié)構(gòu)及特點