834計算機科學專業(yè)基礎(chǔ)綜合

1、考試科目：834計算機科學專業(yè)基礎(chǔ)綜合一、復習要求：計算機學科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)結(jié)構(gòu)、計算機組成原理、操作系統(tǒng)、計算機圖形學和計算機網(wǎng)絡(luò)等5個學科專業(yè)的基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。二、試卷滿分及考試時間:本試卷滿分為150分，考試時間為180分鐘。1)答題方式為閉卷、筆試2)考試內(nèi)容結(jié)構(gòu)包括：數(shù)據(jù)結(jié)構(gòu)45分計算機組成原理35分操作系統(tǒng)25分計算機圖形學20分計算機網(wǎng)絡(luò)25分3)試卷題型結(jié)構(gòu)單項選擇題80分(40小題，每小題2分)70三、復習內(nèi)容：A.數(shù)據(jù)結(jié)構(gòu)部分

2、1.復習要求：1)掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。2)掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度的分析。3)能夠數(shù)據(jù)結(jié)構(gòu)基本原理和方法進行問題的分析與求解，具備采用C或C+或?qū)崿F(xiàn)算法的能力。2.主要復習內(nèi)容：1)線性表(1)線性表的定義和基本操作(2)線性表的實現(xiàn)a.順序存儲b.鏈式存儲c.線性表的應用2)棧、隊列和數(shù)組(1)棧和隊列的基本概念(2)棧和隊列的順序存儲結(jié)構(gòu)(3)棧和隊列的鏈式存儲結(jié)構(gòu)(4)棧和隊列的應用(五)特殊矩陣的壓縮存儲3)樹與二叉樹(1)樹的概念(2)二叉樹a.二叉樹的定義及其主要特征b.二叉樹的順序存儲結(jié)構(gòu)和鏈

3、式存儲結(jié)構(gòu)c.二叉樹的遍歷d.線索二叉樹的基本概念和構(gòu)造(3)樹、森林a.樹的存儲結(jié)構(gòu)b.森林與二叉樹的轉(zhuǎn)換c.樹和森林的遍歷(4)樹與二叉樹的應用a.二叉排序樹b.平衡二叉樹c.哈夫曼(Huffman)樹和哈夫曼編碼4)圖(1)圖的基本概念(2)圖的存儲及基本操作a.鄰接矩陣法b.鄰接表法(3)圖的遍歷a.深度優(yōu)先搜索b.廣度優(yōu)先搜索(4)圖的基本應用a.最小(代價)生成樹b.最短路徑c.拓撲排序d.關(guān)鍵路徑5)查找(1)查找的基本概念(2)順序查找法(三)折半查找法(四)B樹及其基本操作、B+樹的基本概念(五)散列(Hash)表(六)查找算法的分析及應用6)排序(1)排序的基本概念(2)插

4、入排序a.直接插入排序b.折半插入排序(3)氣泡排序(bubblesort)(4)簡單選擇排序(5)希爾排序(shellsort)(6)快速排序B.計算機組成原理部分1.復習要求：1 .理解單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念。2 .理解計算機系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法。3 .能夠運用計算機組成的基本原理和基本方法，對有關(guān)計算機硬件系統(tǒng)中的理論和實際問題進行計算、分析，并能對一些基本部件進行簡單設(shè)計。2.主要復習內(nèi)容：1)計算機系統(tǒng)概述(1)計算機發(fā)展歷程(2)計算機系統(tǒng)

5、層次結(jié)構(gòu)a.計算機硬件的基本組成b.計算機軟件的分類c.計算機的工作過程(3)計算機性能指標吞吐量、響應時間；CPU寸鐘周期、主頻、CPI、CP瞅行時間；MIPSMFLOPS2)數(shù)據(jù)的表示和運算(1)數(shù)制與編碼a.進位計數(shù)制及其相互轉(zhuǎn)換b.真值和機器數(shù)c.BCD碼d.字符與字符串e.校驗碼(2)定點數(shù)的表示和運算a.定點數(shù)的表示無符號數(shù)的表示；有符號數(shù)的表示。b.定點數(shù)的運算定點數(shù)的位移運算；原碼定點數(shù)的加/減運算；補碼定點數(shù)的加/減運算；定點數(shù)的乘/除運算；溢出概念和判別方法。(3)浮點數(shù)的表示和運算a.浮點數(shù)的表示IEEE754標準b.浮點數(shù)的加/減運算(4)算術(shù)邏輯單元ALUa.串行加法

6、器和并行加法器b.算術(shù)邏輯單元ALU的功能和結(jié)構(gòu)3)存儲器層次結(jié)構(gòu)(1)存儲器的分類(2)存儲器的層次化結(jié)構(gòu)(3)半導體隨機存取存儲器a.SRAM存儲器的工作原理b.DRAM存儲器的工作原理c.只讀存儲器(4)主存儲器與CPU的連接(5)雙口RAMW多模塊存儲器(6)高速緩沖存儲器(Cache)a.Cache的基本工作原理b.Cache和主存之間的映射方式c.Cache中主存塊的替換算法d.Cache寫策略(7)虛擬存儲器a.虛擬存儲器的基本概念b.頁式虛擬存儲器c.段式虛擬存儲器d.段頁式虛擬存儲器e.TLB(快表)4)指令系統(tǒng)(1)指令格式a.指令的基本格式b.定長操作碼指令格式c.擴展操

7、作碼指令格式(2)指令的尋址方式a.有效地址的概念b.數(shù)據(jù)尋址和指令尋址c.常見尋址方式(3)CISC和RISC的基本概念5)中央處理器(CPU(1)CPU勺功能和基本結(jié)構(gòu)(2)指令執(zhí)行過程(3)數(shù)據(jù)通路的功能和基本結(jié)構(gòu)(4)控制器的功能和工作原理a.硬布線控制器b.微程序控制器微程序、微指令和微命令；微指令的編碼方式；微地址的形式方式。(5)指令流水線a.指令流水線的基本概念b.指令流水線的基本實現(xiàn)c.超標量和動態(tài)流水線的基本概念(6)多核處理器的基本概念6)總線(1)總線概述a.總線的基本概念b.總線的分類c.總線的組成及性能指標(2)總線仲裁a.集中仲裁方式b.分布仲裁方式(3)總線操作

8、和定時a.同步定時方式b.異步定時方式(4)總線標準7)輸入輸出(I/O)系統(tǒng)(1)I/O系統(tǒng)基本概念(2)外部設(shè)備a.輸入設(shè)備：鍵盤、鼠標b.輸出設(shè)備：顯示器、打印機c.外存儲器：硬盤存儲器、磁盤陣列、光盤存儲器(3) I/O接口(I/O控制器)a.I/O接口的功能和基本結(jié)構(gòu)b.I/O端口及其編址c.I/O地址空間及其編碼(4) I/O方式a.程序查詢方式b.程序中斷方式中斷的基本概念；中斷響應過程；中斷處理過程；多重中斷和中斷屏蔽的概念。c.DMA方式DMA空制器的組成；DMA專送過程。d.通道方式C.操作系統(tǒng)部分1 .復習要求：1)掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)

9、的整體運行過程。2)掌握操作系統(tǒng)進程、內(nèi)存、文件和I/O管理的策略、算法、機制以及相互關(guān)系。3)能夠運用所學的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題，并能利用C語言描述相關(guān)算法。2 .主要復習內(nèi)容：1)操作系統(tǒng)概述(1)操作系統(tǒng)的概念、特征、功能和提供的服務(wù)(2)操作系統(tǒng)的發(fā)展與分類(3)操作系統(tǒng)的運行環(huán)境a.內(nèi)核態(tài)與用戶態(tài)b.中斷、異常c.系統(tǒng)調(diào)用(4)操作系統(tǒng)體系結(jié)構(gòu)2)進程管理(1)進程與線程a.進程概念b.進程的狀態(tài)與轉(zhuǎn)換c.進程控制d.進程組織e.進程通信共享存儲系統(tǒng)；消息傳遞系統(tǒng)；管道通信。f.線程概念與多線程模型(2)處理機調(diào)度a.調(diào)度的基本概念b.調(diào)度時機、切換與過程c.調(diào)

10、度的基本準則d.調(diào)度方式e.典型調(diào)度算法先來先服務(wù)調(diào)度算法；短作業(yè)(短進程、短線程)優(yōu)先調(diào)度算法；時間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級調(diào)度算法；高響應比優(yōu)先調(diào)度算法；多級反饋隊列調(diào)度算法。(3)同步與互斥a.進程同步的基本概念b.實現(xiàn)臨界區(qū)互斥的基本方法軟件實現(xiàn)方法；硬件實現(xiàn)方法。c.信號量d.管程e.經(jīng)典同步問題生產(chǎn)者-消費者問題；讀者-寫者問題；哲學家進餐問題。(4)死鎖a.死鎖的概念b.死鎖處理策略c.死鎖預防d.死鎖避免系統(tǒng)安全狀態(tài)：銀行家算法。e.死鎖檢測和解除3)內(nèi)存管理(1)內(nèi)存管理基礎(chǔ)a.內(nèi)存管理概念程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護。b.交換與覆蓋c.連續(xù)分配管理方式d.

11、非連續(xù)分配管理方式分頁管理方式；分段管理方式；段頁式管理方式。(2)虛擬內(nèi)存管理a.虛擬內(nèi)存基本概念b.請求分頁管理方式c.頁面置換算法最佳置換算法(OPT;先進先出置換算法(FIFO);最近最少使用置換算法(LRU;時鐘置換算法(CLOCK。d.頁面分配策略e.工作集f.抖動4)文件管理(1)文件系統(tǒng)基礎(chǔ)a.文件概念b.文件的邏輯結(jié)構(gòu)順序文件；索引文件；索引順序文件。c.目錄結(jié)構(gòu)文件控制塊和索引節(jié)點；單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)。d.文件共享e.文件保護訪問類型；訪問控制。(2)文件系統(tǒng)實現(xiàn)a.文件系統(tǒng)層次結(jié)構(gòu)b.目錄實現(xiàn)c.文件實現(xiàn)(3)磁盤組織與管理a.磁盤的結(jié)

12、構(gòu)b.磁盤調(diào)度算法c.磁盤的管理5)輸入輸出(I/O)管理(1) I/O管理概述a.I/O控制方式b.I/O軟件層次結(jié)構(gòu)(2) I/O核心子系統(tǒng)a.I/O調(diào)度概念b.高速緩存與緩沖區(qū)c.設(shè)備分配與回收d.彳取脫機技術(shù)(SPOOLinge.出錯處理D.計算機圖形學部分1 .復習要求：1)掌握計算機圖形學基本概念、基本原理和基本方法。2)掌握現(xiàn)代計算機渲染流水線的過程，理解典型圖形結(jié)構(gòu)的存儲，以及算法的工作原理。3)能夠?qū)镜膱D形數(shù)據(jù)結(jié)構(gòu)進行分析，具備采用C或C+對簡單圖形表達結(jié)構(gòu)進行解析和處理的基本技能。2 .主要復習內(nèi)容：1)計算機圖形學基礎(chǔ)(1)圖形學概念a.兩種圖形表達方法b.常用圖形數(shù)

13、據(jù)結(jié)構(gòu)c.計圖形數(shù)據(jù)文件d.圖形渲染流水線(2)計算機網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型2)三維立體的表示方法(1)多邊形表面表不a.網(wǎng)格表不法b.掃描表不法c.八叉樹表小法d.翼邊結(jié)構(gòu)表示法(2)結(jié)構(gòu)實體幾何表示法(3)三維變換3)圖形顯示算法(1)直線生成算法(2)圓弧生成算法(3)規(guī)則曲線生成算法E.計算機網(wǎng)絡(luò)部分1 .復習要求：1)掌握計算機網(wǎng)絡(luò)的基本概念、基本原理和基本方法。2)掌握計算機網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議，了解典型網(wǎng)絡(luò)設(shè)備的組成和特點，理解典型網(wǎng)絡(luò)設(shè)備的工作原理。3)能夠運用計算機網(wǎng)絡(luò)的基本概念、基本原理和基本方法進行網(wǎng)絡(luò)系統(tǒng)的分析、設(shè)計和應用2 .主要復習內(nèi)容：1)計算機網(wǎng)絡(luò)基礎(chǔ)(

14、1)計算機網(wǎng)絡(luò)概述a.計算機網(wǎng)絡(luò)的概念、組成與功能b.計算機網(wǎng)絡(luò)的分類c.計算機網(wǎng)絡(luò)與互聯(lián)網(wǎng)的發(fā)展歷史d.計算機網(wǎng)絡(luò)的標準化工作及相關(guān)組織(2)計算機網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型a.計算機網(wǎng)絡(luò)分層結(jié)構(gòu)b.計算機網(wǎng)絡(luò)協(xié)議、接口、服務(wù)等概念c.ISO/OSI參考模型和TCP/IP模型2)物理層(1)通信基礎(chǔ)a.信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念b.奈奎斯特定理與香農(nóng)定理c.編碼與調(diào)制d.電路交換、報文交換與分組交換e.數(shù)據(jù)報與虛電路(2)傳輸介質(zhì)a.雙絞線、同軸電纜、光纖與無線傳輸介質(zhì)b.物理層接口的特性(3)物理層設(shè)備a.中繼器b.集線器3)數(shù)據(jù)鏈路層(1)數(shù)據(jù)鏈路層的功能(2)

15、組幀(3)差錯控制a.檢錯編碼b.糾錯編碼(4)流量控制與可靠傳輸機制a.流量控制、可靠傳輸與滑輪窗口機制b.停止-等待協(xié)議c.后退N幀協(xié)議(GBNd.選擇重傳協(xié)議(SR)(5)介質(zhì)訪問控制a.信道劃分介質(zhì)訪問控制頻分多路復用、時分多路復用、波分多路復用、碼分多路復用的概念和基本原理b.隨即訪問介質(zhì)訪問控制ALOH即議；CSMA、議；CSMA/C脅議；CSMA/C脅議。c.輪詢訪問介質(zhì)訪問控制：令牌傳遞協(xié)議(6)局域網(wǎng)a.局域網(wǎng)的基本概念與體系結(jié)構(gòu)b.以太網(wǎng)與IEEE802.3c.IEEE802.11d.令牌環(huán)網(wǎng)的基本原理(7)廣域網(wǎng)a.廣域網(wǎng)的基本概念b.PPP協(xié)議c.HDLC協(xié)議(8)數(shù)據(jù)

16、鏈路層設(shè)備a.網(wǎng)橋的概念和基本原理b.局域網(wǎng)交換機及其工作原理。4)網(wǎng)絡(luò)層(1)網(wǎng)絡(luò)層的功能a.異構(gòu)網(wǎng)絡(luò)互聯(lián)b.路由與轉(zhuǎn)發(fā)c.擁塞控制(2)路由算法a.靜態(tài)路由與動態(tài)路由b.距離-向量路由算法c.鏈路狀態(tài)路由算法d.層次路由(3)IPv4a.IPv4分組b.IPv4地址與NATc.子網(wǎng)劃分與子網(wǎng)掩碼、CIDRd.ARP協(xié)議、DHC的議與ICMP協(xié)議(4)IPv6a.IPv6的主要特點b.IPv6地址(5)路由協(xié)議a.自治系統(tǒng)b.域內(nèi)路由與域間路由c.RIP路由協(xié)議d.OSPF路由協(xié)議e.BGP路由協(xié)議(6)IP組播a.組播的概念b.IP組播地址(7)移動IPa.移動IP的概念b.移動IP的通信過程(8)網(wǎng)絡(luò)層設(shè)備a.路由器的組成和功能b.路由表與路由轉(zhuǎn)發(fā)5)傳輸層(1)傳輸層提供的服務(wù)a.傳輸層的功能b.