2021西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理研究生考試大綱 正文

834“數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理”復(fù)習(xí)參考提綱
一、 考察目標(biāo)
834 數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運(yùn)用所學(xué)的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實(shí)際問題。
二、 考試形式和試卷結(jié)構(gòu)
1、 試卷滿分及考試時間：本試卷滿分為150，考試時間為180分鐘
2、 答題方式：閉卷，筆試
3、 試卷內(nèi)容結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)75分、計(jì)算機(jī)組成原理75分
三、 考察范圍
數(shù)據(jù)結(jié)構(gòu)：
【總體要求】
 “數(shù)據(jù)結(jié)構(gòu)”要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的構(gòu)造和實(shí)現(xiàn)，具備應(yīng)用數(shù)據(jù)結(jié)構(gòu)分析、設(shè)計(jì)和求解實(shí)際問題的能力。要求掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；掌握線性結(jié)構(gòu)、樹和圖的邏輯結(jié)構(gòu)、存儲（物理）結(jié)構(gòu)，以及基本操作在不同存儲結(jié)構(gòu)上的實(shí)現(xiàn)，并能夠?qū)舅惴ㄟM(jìn)行時間復(fù)雜度和空間復(fù)雜度分析；掌握基本的查找和排序方法及其算法實(shí)現(xiàn)，并能夠利用這些方法對實(shí)際問題進(jìn)行分析和求解，具備采用C或C++或 Java等編程語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。
（一）線性表
　　  1）線性表的基本概念和基本操作
      2）線性表的順序存儲及實(shí)現(xiàn)
      3）線性表的鏈?zhǔn)酱鎯皩?shí)現(xiàn)
  4）線性表的應(yīng)用
（二）棧和隊(duì)列
　    1）棧和隊(duì)列的基本概念和基本操作
      2）棧和隊(duì)列的存儲結(jié)構(gòu)與實(shí)現(xiàn)
        （1）棧的順序存儲及實(shí)現(xiàn)
        （2）棧的鏈?zhǔn)酱鎯皩?shí)現(xiàn)
        （3）隊(duì)列的鏈?zhǔn)酱鎯皩?shí)現(xiàn)
    （4）循環(huán)隊(duì)列的定義及實(shí)現(xiàn)
      3）棧和隊(duì)列的應(yīng)用
（三）串
1）串的基本概念和基本操作
      2）串的順序存儲、鏈?zhǔn)酱鎯皩?shí)現(xiàn)
      3）串的模式匹配
    （1）基本的模式匹配算法
    （2）KMP模式匹配算法（模式串的next函數(shù)計(jì)算）
（四）數(shù)組和廣義表
1）數(shù)組的基本概念和基本操作
2）數(shù)組的順序存儲
3）特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲
4）廣義表的基本概念和存儲結(jié)構(gòu)
（五）樹與二叉樹
1）樹的基本概念
      2）二叉樹
       （1）二叉樹的定義及性質(zhì)
       （2）二叉樹的順序存儲和鏈?zhǔn)酱鎯?br />        （3）二叉樹的先序、中序、后序遍歷和層序遍歷運(yùn)算
       （4）線索二叉樹的定義與基本運(yùn)算
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)造及查找、插入和刪除運(yùn)算
        （2）平衡二叉樹的構(gòu)造及查找運(yùn)算
        （3）B-樹的特點(diǎn)及查找運(yùn)算
        （4）B+樹的基本概念
      4）哈希表
    （1）哈希表的基本概念
         （2）哈希表的構(gòu)造及查找運(yùn)算
      5）查找算法的分析（平均查找長度計(jì)算）及應(yīng)用
（八）排序
1）排序的基本概念（排序過程中的基本操作、排序算法的時空復(fù)雜度及穩(wěn)定性）
2）簡單排序方法
        （1）直接插入排序算法
        （2）冒泡排序算法
        （3）簡單選擇排序算法
3）快速排序
4）堆排序
      5）歸并排序
      6）基數(shù)排序
        （1）多關(guān)鍵排序方法
        （2）鏈?zhǔn)交鶖?shù)排序方法及特點(diǎn)
7）外部排序的基本概念
 
計(jì)算機(jī)組成原理:
【總體要求】
 “計(jì)算機(jī)組成原理”要求學(xué)生掌握單處理器計(jì)算機(jī)系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計(jì)算機(jī)系統(tǒng)的整機(jī)概念。要求掌握計(jì)算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面；掌握計(jì)算機(jī)數(shù)據(jù)表示的方法，包括定點(diǎn)數(shù)和浮點(diǎn)數(shù)的表示；掌握運(yùn)算器的原理和實(shí)現(xiàn)電路；掌握存儲層次的概念，掌握不同類型存儲器特性，包括SRAM、DRAM、ROM；掌握主存結(jié)構(gòu)及基本設(shè)計(jì)方法；會解決Cache存儲的一些基本問題；掌握磁盤基本原理及RAID；掌握指令集體系結(jié)構(gòu)的基本知識和基本實(shí)現(xiàn)方法；熟悉中央處理器的時序邏輯，即指令周期、CPU周期、節(jié)拍周期、時鐘周期之間的關(guān)系；掌握中央處理器控制器的基本設(shè)計(jì)方法，即硬布線和微程序控制，能夠根據(jù)模擬CPU及系統(tǒng)框架設(shè)計(jì)控制信號邏輯或者編寫簡單微操作流程；掌握計(jì)算機(jī)輸入輸出系統(tǒng)的基本概念，程序查詢方式、中斷方式和直接存儲器存取方式；掌握總線的仲裁方式和特點(diǎn)；基本掌握并行計(jì)算機(jī)的原理和發(fā)展趨勢；基本掌握對稱多處理器系統(tǒng)、多計(jì)算機(jī)系統(tǒng)的結(jié)構(gòu)及特點(diǎn)；掌握流水線技術(shù)，能夠計(jì)算各種流水線的性能指標(biāo)參數(shù)，分析流水線的特點(diǎn)，解決數(shù)據(jù)相關(guān)的方法等；能夠運(yùn)用計(jì)算機(jī)組成的基本原理和基本方法，對有關(guān)計(jì)算機(jī)硬件系統(tǒng)中的理論和實(shí)際問題進(jìn)行計(jì)算、分析，并能對一些基本部件進(jìn)行簡單設(shè)計(jì)。
研究生課程考試是所學(xué)知識的總結(jié)性考試，考試水平應(yīng)達(dá)到或超過本科專業(yè)相應(yīng)的課程要求水平。
（一）計(jì)算機(jī)系統(tǒng)概論       
1.復(fù)習(xí)內(nèi)容
計(jì)算機(jī)的基本組成，馮.諾依曼計(jì)算機(jī)原理，計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)，計(jì)算機(jī)的分類及性能描述，計(jì)算機(jī)的發(fā)展歷程
2.具體要求
*計(jì)算機(jī)的基本組成
***硬件組成
***軟件組成
*馮.諾依曼計(jì)算機(jī)工作原理
***馮.諾依曼計(jì)算機(jī)結(jié)構(gòu)及工作過程
***馮.諾依曼計(jì)算機(jī)特點(diǎn)
*計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)
***層次結(jié)構(gòu)圖
*計(jì)算機(jī)的分類及性能描述
***Flynn分類法
***Amdahl定律和應(yīng)用
***吞吐量、響應(yīng)時間
***CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間
***MIPS、MFLOPS
（二）計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)表示       
1.復(fù)習(xí)內(nèi)容
數(shù)制與編碼，定點(diǎn)數(shù)據(jù)表示，浮點(diǎn)數(shù)據(jù)表示，糾錯和校驗(yàn)
2.具體要求
*數(shù)制與編碼
***數(shù)制及相互轉(zhuǎn)換
***真值和機(jī)器數(shù)
*** BCD碼
*定點(diǎn)數(shù)據(jù)表示
***無符號數(shù)的表示
***有符號數(shù)的表示
***原碼、反碼、補(bǔ)碼、移碼
*浮點(diǎn)數(shù)據(jù)表示
***格式定義
***規(guī)格化
***數(shù)據(jù)范圍
***IEEE754標(biāo)準(zhǔn)
*糾錯和校驗(yàn)
***奇偶校驗(yàn)
***漢明編碼
***循環(huán)冗余校驗(yàn)
（三）運(yùn)算方法與運(yùn)算器
1.復(fù)習(xí)內(nèi)容
定點(diǎn)數(shù)的位移運(yùn)算，原碼定點(diǎn)數(shù)的加/減運(yùn)算，補(bǔ)碼定點(diǎn)數(shù)的加/減運(yùn)算，定點(diǎn)數(shù)的乘/除運(yùn)算，溢出概念和判別方法，浮點(diǎn)數(shù)的加/減運(yùn)算，浮點(diǎn)數(shù)的乘/除運(yùn)算，算術(shù)邏輯單元ALU
2.具體要求
*原碼定點(diǎn)數(shù)的加/減運(yùn)算
***方法，應(yīng)用
*補(bǔ)碼定點(diǎn)數(shù)的加/減運(yùn)算
***方法，應(yīng)用
***行波進(jìn)位、先行進(jìn)位加法器
***移位處理
***溢出處理和判斷
*定點(diǎn)數(shù)的乘/除運(yùn)算
***原碼乘法，補(bǔ)碼乘法
***恢復(fù)余數(shù)，不恢復(fù)余數(shù)除法
***陣列乘法器
***陣列除法器
*浮點(diǎn)數(shù)的加/減運(yùn)算
***對階
***尾數(shù)加減
***規(guī)格化
***溢出處理
*浮點(diǎn)數(shù)的乘/除運(yùn)算
***方法
***應(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ù)及計(jì)算 
***RAID
（五）指令系統(tǒng)       
1.復(fù)習(xí)內(nèi)容
指令格式，尋址方式，CISC和RISC基本概念。
2.具體要求
*指令格式
***指令的基本格式
***定長操作碼設(shè)計(jì)
***擴(kuò)展操作碼設(shè)計(jì)
***存儲器操作數(shù)的大/小端存儲、邊界對齊、堆棧操作、哈佛存儲結(jié)構(gòu)
*操作數(shù)的尋址方式
***有效地址的概念
***數(shù)據(jù)尋址和指令尋址
***常用尋址方式
* CISC和RISC的基本概念
***RISC的發(fā)展歷程
***CISC和RISC的技術(shù)特點(diǎn)
（六）中央處理器       
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è)計(jì)方法
***微程序控制器結(jié)構(gòu)及設(shè)計(jì)方法
***微操作、微命令、微指令、微程序
***微操作和微命令序列（流程）設(shè)計(jì)
***微命令的互斥和相容
（七）流水線技術(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)量處理器概念及特點(diǎn)
*VLIW處理器概念及特點(diǎn)
*多核處理器的基本概念
（八）總線與輸入輸出系統(tǒng)  
1.復(fù)習(xí)內(nèi)容
總線概述，總線仲裁，總線操作和定時，總線標(biāo)準(zhǔn)，I/O系統(tǒng)基本概念，外部設(shè)備，I/O接口，I/O方式。
2.具體要求
*總線概述
***總線的基本概念
***總線的分類
***總線的組成及性能指標(biāo)
*總線仲裁
***集中仲裁方式：菊花鏈方式、輪詢計(jì)數(shù)、獨(dú)立請求方式
***分布仲裁方式
*總線操作和定時
***總線讀寫操作
***同步定時方式
***異步定時方式
*總線標(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)及特點(diǎn)
*多計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)及特點(diǎn)
 

西安電子科技大學(xué)

本文來源：http://www.zhongzhouzhikong.com/xiandianzikeji/cankaoshumu_419275.html