計算機學科專業(yè)基礎綜合考試是為高等院校和科研院所招收計算機科學與技術學科的碩士研究生而設置的具有選拔性質的聯考科目，其目的是科學、公平、有效地測試考生掌握計算機科學與技術學科大學本科階段專業(yè)知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校計算機科學與技術學科優(yōu)秀本科畢業(yè)生所能達到的及格或及格以上水平，以利于各高等院校和科研院所擇優(yōu)選拔，確保碩士研究生的招生質量。
II 考查目標
計算機學科專業(yè)基礎綜合考試涵蓋數據結構、計算機組成原理、操作系統(tǒng)和計算機網絡等學科專業(yè)基礎課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。
III 考試形式和試卷結構
一、試卷滿分及考試時間
本試卷滿分為150分，考試時間為180分鐘。
二、答題方式
答題方式為閉卷、筆試。
三、試卷內容結構
數據結構 45分
計算機組成原理 45分
操作系統(tǒng) 35分
計算機網絡 25分
四、試卷題型結構
單項選擇題 80分 （40小題，每小題2分）
綜合應用題 70分
IV 考查內容
數據結構
【考查目標】
1.掌握數據結構的基本概念、基本原理和基本方法。
2.掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本的時間復雜度與空間復雜度的分析。
3.能夠運用數據結構基本原理和方法進行問題的分析與求解，具備采用C或C++語言設計與實現算法的能力。
一、線性表
�。ㄒ唬┚�性表的定義和基本操作
�。ǘ┚�性表的實現
1.順序存儲
2.鏈式存儲
3.線性表的應用
二、棧、隊列和數組
�。ㄒ唬：完犃械幕靖拍�
（二）棧和隊列的順序存儲結構
（三）棧和隊列的鏈式存儲結構
�。ㄋ模：完犃械膽�
�。ㄎ澹┨厥饩仃嚨膲嚎s存儲
三、樹與二叉樹
（一）樹的基本概念
�。ǘ┒鏄�
1.二叉樹的定義及其主要特征
2.二叉樹的順序存儲結構和鏈式存儲結構
3.二叉樹的遍歷
4.線索二叉樹的基本概念和構造
�。ㄈ洹⑸�
1.樹的存儲結構
2.森林與二叉樹的轉換
3.樹和森林的遍歷
�。ㄋ模渑c二叉樹的應用
1.二叉排序樹
2.平衡二叉樹
3.哈夫曼（Huffman）樹和哈夫曼編碼
四、圖
�。ㄒ唬﹫D的基本概念
（二）圖的存儲及基本操作
1.鄰接矩陣法
2.鄰接表法
3.鄰接多重表、十字鏈表
（三）圖的遍歷
1.深度優(yōu)先搜索
2.廣度優(yōu)先搜索
�。ㄋ模﹫D的基本應用
1.小（代價）生成樹
2.短路徑
3.拓撲排序
4.關鍵路徑
五、查找
�。ㄒ唬┎檎业幕靖拍�
（二）順序查找法
�。ㄈ┓謮K查找法
（四）折半查找法
�。ㄎ澹〣樹及其基本操作、B+樹的基本概念
�。┥⒘校℉ash）表
�。ㄆ撸┳址Ｊ狡ヅ�
�。ò耍┎檎宜惴ǖ姆治黾皯�
六、排序
（一）排序的基本概念
�。ǘ┎迦肱判�
1.直接插入排序
2.折半插入排序
�。ㄈ馀菖判颍╞ubble sort）
�。ㄋ模┖唵芜x擇排序
（五）希爾排序（shell sort）
�。┛焖倥判�
（七）堆排序
�。ò耍┒窔w并排序（Merge Sort）
�。ň牛┗鶖蹬判�
�。ㄊ┩獠颗判�
�。ㄊ唬└鞣N內部排序算法的比較
�。ㄊ┡判蛩惴ǖ膽�
計算機組成原理
【考查目標】
1.理解單處理器計算機系統(tǒng)中各部件的內部工作原理、組成結構以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念。
2.理解計算機系統(tǒng)層次化結構概念，熟悉硬件與軟件之間的界面，掌握指令集體系結構的基本知識和基本實現方法。
3.能夠綜合運用計算機組成的基本原理和基本方法，對有關計算機硬件系統(tǒng)中的理論和實際問題進行計算、分析，對一些基本部件進行簡單設計；并能對高級程序設計語言（如C語言）中的相關問題進行分析。
一、計算機系統(tǒng)概述
（一）計算機發(fā)展歷程
�。ǘ┯嬎銠C系統(tǒng)層次結構
1.計算機系統(tǒng)的基本組成
2.計算機硬件的基本組成
3.計算機軟件和硬件的關系
4.計算機系統(tǒng)的工作過程
（三）計算機性能指標
吞吐量、響應時間，CPU時鐘周期、主頻、CPI、CPU執(zhí)行時間，MIPS、MFLOPS 、GFLOPS、TFLOPS、PFLOPS。
二、數據的表示和運算
�。ㄒ唬⿺抵婆c編碼
1.進位計數制及其相互轉換
2.真值和機器數
3.BCD碼
4.字符與字符串
5.校驗碼
（二）定點數的表示和運算
1.定點數的表示
無符號數的表示,有符號整數的表示。
2.定點數的運算
定點數的位移運算,原碼定點數的加/減運算,補碼定點數的加/減運算,定點數的乘/除運算,溢出概念和判別方法。
�。ㄈ└↑c數的表示和運算
1.浮點數的表示
IEEE 754標準。
2.浮點數的加/減運算
�。ㄋ模┧阈g邏輯單元ALU
1.串行加法器和并行加法器
2.算術邏輯單元ALU的功能和結構
三、存儲器層次結構
（一）存儲器的分類
�。ǘ┐鎯ζ鞯膶哟位Y構
�。ㄈ┌雽w隨機存取存儲器
1.SRAM存儲器
2.DRAM存儲器
3.只讀存儲器
4.Flash存儲器
�。ㄋ模┲鞔鎯ζ髋cCPU的連接
（五）雙口RAM和多模塊存儲器
�。└咚倬彌_存儲器（Cache）
1.Cache的基本工作原理
2.Cach和主存之間的映射方式
3.Cache中主存塊的替換算法
4.Cache寫策略
（七）虛擬存儲器
1.虛擬存儲器的基本概念
2.頁式虛擬存儲器
3.段式虛擬存儲器
4.段頁式虛擬存儲器
5.TLB（快表）
四、指令系統(tǒng)
（一）指令格式
1.指令的基本格式
2.定長操作碼指令格式
3.擴展操作碼指令格式
�。ǘ┲噶畹膶ぶ贩绞�
1.有效地址的概念
2.數據尋址和指令尋址
3.常見尋址方式
�。ㄈ〤ISC和RISC的基本概念
五、中央處理器（CPU）
�。ㄒ唬〤PU的功能和基本結構
�。ǘ┲噶顖�(zhí)行過程
�。ㄈ⿺祿返墓δ芎突窘Y構
�。ㄋ模┛刂破鞯墓δ芎凸ぷ髟�
1.硬布線控制器
2.微程序控制器
微程序、微指令和微命令，微指令格式，微命令的編碼方式，微地址的形式方式。
�。ㄎ澹┲噶盍魉�
1.指令流水線的基本概念
2. 指令流水線的基本實現
3.超標量和動態(tài)流水線的基本概念
六、總線
（一）總線概述
1.總線的基本概念
2.總線的分類
3.總線的組成及性能指標
�。ǘ┛偩�仲裁
1.集中仲裁方式
2.分布仲裁方式
�。ㄈ┛偩�操作和定時
1.同步定時方式
2.異步定時方式
�。ㄋ模┛偩�標準
七、輸入輸出（I/O）系統(tǒng)
�。ㄒ唬㊣/O系統(tǒng)基本概念
�。ǘ┩獠吭O備
1.輸入設備：鍵盤、鼠標
2.輸出設備：顯示器、打印機
3.外存儲器：硬盤存儲器、磁盤陣列、光盤存儲器
�。ㄈ㊣/O接口（I/O控制器）
1.I/O接口的功能和基本結構
2.I/O端口及其編址
（四）I/O方式
1.程序查詢方式
2.程序中斷方式
中斷的基本概念；中斷響應過程；中斷處理過程；多重中斷和中斷屏蔽的概念。
3.DMA方式
DMA控制器的組成，DMA傳送過程。
操作系統(tǒng)
【考查目標】
1.掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)的整體運行過程。
2. 掌握操作系統(tǒng)進程、內存、文件和I/O管理的策略、算法、機制以及相互關系。
3.能夠運用所學的操作系統(tǒng)原理、方法與技術分析問題和解決問題，并能利用C語言描述相關算法。
一、操作系統(tǒng)概述
（一）操作系統(tǒng)的概念、特征、功能和提供的服務
�。ǘ┎僮飨到y(tǒng)的發(fā)展與分類
�。ㄈ┎僮飨到y(tǒng)的運行環(huán)境
1.內核態(tài)與用戶態(tài)
2.中斷、異常
3.系統(tǒng)調用
（四）操作系統(tǒng)體系結構
二、進程管理
�。ㄒ唬┻M程與線程
1.進程概念
2.進程的狀態(tài)與轉換
3.進程控制
4.進程組織
5.進程通信
共享存儲系統(tǒng)，消息傳遞系統(tǒng)，管道通信。
6.線程概念與多線程模型
�。ǘ┨幚頇C調度
1.調度的基本概念
2.調度時機、切換與過程
3.調度的基本準則
4.調度方式
5.典型調度算法
先來先服務調度算法，短作業(yè)（短進程、短線程）優(yōu)先調度算法，時間片輪轉
調度算法，優(yōu)先級調度算法，高響應比優(yōu)先調度算法，多級反饋隊列調度算法。
�。ㄈ┩脚c互斥
1.進程同步的基本概念
2.實現臨界區(qū)互斥的基本方法
軟件實現方法，硬件實現方法。
3.信號量
4.管程
5.經典同步問題
生產者-消費者問題，讀者-寫者問題，哲學家進餐問題。
�。ㄋ模┧梨i
1.死鎖的概念
2.死鎖處理策略
3.死鎖預防
4.死鎖避免
系統(tǒng)安全狀態(tài)，銀行家算法。
5.死鎖檢測和解除
三、內存管理
�。ㄒ唬﹥却婀芾砘A
1.內存管理概念
程序裝入與鏈接，邏輯地址與物理地址空間，內存保護。
2.交換與覆蓋
3.連續(xù)分配管理方式
4.非連續(xù)分配管理方式
分頁管理方式，分段管理方式，段頁式管理方式。
�。ǘ┨摂M內存管理
1.虛擬內存基本概念
2.請求分頁管理方式
3.頁面置換算法
佳置換算法（OPT），先進先出置換算法（FIFO），近少使用置換算法（LRU），時鐘置換算法（CLOCK）。
4.頁面分配策略
5.工作集
6.抖動
四、文件管理
�。ㄒ唬┪募到y(tǒng)基礎
1.文件概念
2.文件的邏輯結構
順序文件，索引文件，索引順序文件。
3.目錄結構
文件控制塊和索引節(jié)點，單級目錄結構和兩級目錄結構，樹形目錄結構，圖形目錄結構。
4.文件共享
5.文件保護
訪問類型，訪問控制。
�。ǘ┪募到y(tǒng)實現
1.文件系統(tǒng)層次結構
2.目錄實現
3.文件實現
�。ㄈ┐疟P組織與管理
1.磁盤的結構
2.磁盤調度算法
3.磁盤的管理
五、輸入輸出（I/O）管理
�。ㄒ唬㊣/O管理概述
1.I/O控制方式
2. I/O軟件層次結構
�。ǘ㊣/O核心子系統(tǒng)
1.I/O調度概念
2.高速緩存與緩沖區(qū)
3.設備分配與回收
4.假脫機技術（SPOOLing）
計算機網絡
【考查目標】
1.掌握計算機網絡的基本概念、基本原理和基本方法。
2.掌握計算機網絡的體系結構和典型網絡協(xié)議，了解典型網絡設備的組成和特點，理解典型網絡設備的工作原理。
3.能夠運用計算機網絡的基本概念、基本原理和基本方法進行網絡系統(tǒng)的分析、設計和應用。
一、計算機網絡體系結構
�。ㄒ唬┯嬎銠C網絡概述
1.計算機網絡的概念、組成與功能
2.計算機網絡的分類
3.計算機網絡的標準化工作及相關組織
�。ǘ┯嬎銠C網絡體系結構與參考模型
1.計算機網絡分層結構
2.計算機網絡協(xié)議、接口、服務等概念
3.ISO/OSI參考模型和TCP/IP模型
二、物理層
�。ㄒ唬┩ㄐ呕A
1.信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念
2.奈奎斯特定理與香農定理
3.編碼與調制
4.電路交換、報文交換與分組交換
5.數據報與虛電路
�。ǘ﹤鬏斀橘|
1.雙絞線、同軸電纜、光纖與無線傳輸介質
2.物理層接口的特性
�。ㄈ┪锢韺釉O備
1.中繼器
2.集線器
三、數據鏈路層
�。ㄒ唬⿺祿溌穼拥墓δ�
�。ǘ┙M幀
（三）差錯控制
1.檢錯編碼
2.糾錯編碼
�。ㄋ模┝髁靠刂婆c可靠傳輸機制
1.流量控制、可靠傳輸與滑動窗口機制
2.停止-等待協(xié)議
3.后退N幀協(xié)議（GBN）
4.選擇重傳協(xié)議（SR）
�。ㄎ澹┙橘|訪問控制
1.信道劃分
頻分多路復用、時分多路復用、波分多路復用、碼分多路復用的概念和基本原理。
2.隨機訪問
ALOHA協(xié)議，CSMA協(xié)議，CSMA/CD協(xié)議，CSMA/CA協(xié)議。
3.輪詢訪問
令牌傳遞協(xié)議
�。┚钟蚓W
1.局域網的基本概念與體系結構
2.以太網與IEEE 802.3
3.IEEE 802.11
4.令牌環(huán)網的基本原理
�。ㄆ撸⿵V域網
1.廣域網的基本概念
2.PPP協(xié)議
3.HDLC協(xié)議
�。ò耍⿺祿溌穼釉O備
1.網橋的概念及其基本原理
2.局域網交換機及其工作原理。
四、網絡層
�。ㄒ唬┚W絡層的功能
1.異構網絡互聯
2.路由與轉發(fā)
3.擁塞控制
�。ǘ┞酚伤惴�
1.靜態(tài)路由與動態(tài)路由
2.距離-向量路由算法
3.鏈路狀態(tài)路由算法
4.層次路由
�。ㄈ㊣Pv4
1.IPv4分組
2.IPv4地址與NAT
3.子網劃分與子網掩碼、CIDR
4.ARP協(xié)議、DHCP協(xié)議與ICMP協(xié)議
�。ㄋ模㊣Pv6
1.IPv6的主要特點
2.IPv6地址
（五）路由協(xié)議
1.自治系統(tǒng)
2.域內路由與域間路由
3.RIP路由協(xié)議
4.OSPF路由協(xié)議
5.BGP路由協(xié)議
�。㊣P組播
1.組播的概念
2.IP組播地址
（七）移動IP
1.移動IP的概念
2.移動IP通信過程
�。ò耍┚W絡層設備
1.路由器的組成和功能
2.路由表與路由轉發(fā)
五、傳輸層
�。ㄒ唬﹤鬏攲犹峁┑姆⻊�
1.傳輸層的功能
2.傳輸層尋址與端口
3.無連接服務與面向連接服務
�。ǘ︰DP協(xié)議
1.UDP數據報
2.UDP校驗
�。ㄈ㏕CP協(xié)議
1.TCP段
2.TCP連接管理
3.TCP可靠傳輸
4.TCP流量控制與擁塞控制
六、應用層
�。ㄒ唬┚W絡應用模型
1.客戶/服務器模型
2.P2P模型
（二）DNS系統(tǒng)
1.層次域名空間
2.域名服務器
3.域名解析過程
�。ㄈ〧TP
1.FTP協(xié)議的工作原理
2.控制連接與數據連接
�。ㄋ模╇娮余]件
1.電子郵件系統(tǒng)的組成結構
2.電子郵件格式與MIME
3.SMTP協(xié)議與POP3協(xié)議
�。ㄎ澹￤WW
1.WWW的概念與組成結構
2.HTTP協(xié)議
