2010年計(jì)算機(jī)基礎(chǔ)綜合大綱

1、WORD格式2010 年計(jì)算機(jī)基礎(chǔ)綜合考試大綱考查目標(biāo)計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)機(jī)構(gòu) , 計(jì)算機(jī)組成原理 , 操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科專業(yè)基礎(chǔ)課程 . 要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的概念 , 基本原理和方法 ,能夠運(yùn)用所學(xué)的基本原理和基本方法分析, 判斷和解決有關(guān)理論問題和實(shí)際問題 .考試形式和試卷結(jié)構(gòu)一 , 試卷滿分及考試時(shí)間本試卷滿分為 150 分 , 考試時(shí)間為 180 分鐘二 , 答題方式答題方式為閉卷 , 筆試三 , 試卷內(nèi)容結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 45 分計(jì)算機(jī)組成原理 45 分操作系統(tǒng) 35 分計(jì)算機(jī)網(wǎng)絡(luò) 25分四 ,試卷題型結(jié)構(gòu)單項(xiàng)選擇題 80分(40 小題 , 每小

2、題 2分)綜合應(yīng)用題 70分考查范圍專業(yè)資料整理1數(shù)據(jù)結(jié)構(gòu)【考查目標(biāo)】1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念 ; 掌握數(shù)據(jù)的邏輯結(jié)構(gòu) , 存儲(chǔ)結(jié)構(gòu)及其差異 , 以及各種基本操作的實(shí)現(xiàn) .2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上 , 能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度進(jìn)行設(shè)計(jì)與分析 .3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解, 具備采用 C 或 C+或 JAVA語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力 .一, 線性表2.鄰接表法( 一) 線性表的定義和基本操作( 三) 圖的遍歷( 二) 線性表的實(shí)現(xiàn)1.深度優(yōu)先搜索1.順序存儲(chǔ)2.廣度優(yōu)先搜索2.鏈?zhǔn)酱鎯?chǔ)( 四) 圖的基本應(yīng)用3.線性表的應(yīng)用1.最小(代價(jià))

3、生成樹二, 棧, 隊(duì)列和數(shù)組( 一) 棧和隊(duì)列的基本概念2.最短路徑( 二) 棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)3.拓?fù)渑判? 三) 棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4.關(guān)鍵路徑( 四) 棧和隊(duì)列的應(yīng)用五,查找( 五) 特殊矩陣的壓縮存儲(chǔ)( 一)查找的基本概念三 , 樹與二叉樹( 二)順序查找法( 一) 樹的基本概念( 三)折半查找法( 二) 二叉樹( 四) B- 樹及其基本操作 ,B+樹的基本1.二叉樹的定義及其主要特征概念2.二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)( 五)散列 (Hash) 表及其查找結(jié)構(gòu)( 六)查找算法的分析及應(yīng)用3.二叉樹的遍歷六,內(nèi)部排序4.線索二叉樹的基本概念和構(gòu)造( 一)排序的基本概念(三)樹

4、,森林( 二)插入排序1.書的存儲(chǔ)結(jié)構(gòu)1.直接插入排序2.森林與二叉樹的轉(zhuǎn)換2.折半插入排序3.樹和森林的遍歷( 三)起泡排序 (bubble sort)( 四) 樹與二叉樹的應(yīng)用( 四)簡(jiǎn)單選擇排序1.二叉排序樹( 五)希爾排序 (shell sort)2.平衡二叉樹( 六)快速排序3.哈夫曼 (Huffman) 樹和哈夫曼編碼( 七)堆排序四 ,圖( 八)二路歸并排序 (merge sort)( 一)圖的基本概念( 九)基數(shù)排序( 二)圖的存儲(chǔ)及基本操作( 十)各種內(nèi)部排序算法的比較1.鄰接矩陣法( 十一 ) 內(nèi)部排序算法的應(yīng)用2計(jì)算機(jī)組成原理【考查目標(biāo)】1. 理解單處理器計(jì)算機(jī)系統(tǒng)中各部

5、件的內(nèi)部工作原理 , 組成結(jié)構(gòu)以及相互連接方式, 具有完整的計(jì)算機(jī)系統(tǒng)的整機(jī)概念 .2. 理解計(jì)算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念 , 熟悉硬件與軟件之間的界面 , 掌握指令集體系結(jié)構(gòu)的基本知識(shí)和基本實(shí)現(xiàn)方法.3. 能夠運(yùn)用計(jì)算機(jī)組成的基本原理和基本方法 , 對(duì)有關(guān)計(jì)算機(jī)硬件系統(tǒng)中的理論和實(shí)際問題進(jìn)行計(jì)算 , 分析 , 并能對(duì)一些基本部件進(jìn)行簡(jiǎn)單設(shè)計(jì) .一 ,計(jì)算機(jī)系統(tǒng)概述( 一)存儲(chǔ)器的分類( 一)計(jì)算機(jī)發(fā)展歷程( 二)存儲(chǔ)器的層次化結(jié)構(gòu)( 二)計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)( 三)半導(dǎo)體隨機(jī)存取存儲(chǔ)器1.計(jì)算機(jī)硬件的基本組成1. SRAM 存儲(chǔ)器的工作原理2.計(jì)算機(jī)軟件的分類2. DRAM 存儲(chǔ)器的工作原理3.

6、計(jì)算機(jī)的工作過程 ( 三) 計(jì)算機(jī)性能指標(biāo)吞吐量 , 響應(yīng)時(shí)間 ;CPU 時(shí)鐘周期 , 主頻 ,CPI,CPU 執(zhí)行時(shí)間 ;MIPS,MFLOPS.二 , 數(shù)據(jù)的表示和運(yùn)算( 一)數(shù)制與編碼1. 進(jìn)位計(jì)數(shù)制及其相互轉(zhuǎn)換2. 真值和機(jī)器數(shù)3. BCD 碼4. 字符與字符串5. 校驗(yàn)碼( 二)定點(diǎn)數(shù)的表示和運(yùn)算1. 定點(diǎn)數(shù)的表示無符號(hào)數(shù)的表示 ; 有符號(hào)數(shù)的表示 .2. 定點(diǎn)數(shù)的運(yùn)算定點(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)算1. 浮點(diǎn)數(shù)的表示浮點(diǎn)數(shù)的表示范圍 ;IEEE754 標(biāo)

7、準(zhǔn)2. 浮點(diǎn)數(shù)的加 / 減運(yùn)算( 四)算術(shù)邏輯單元 ALU1. 串行加法器和并行加法器2. 算術(shù)邏輯單元 ALU 的功能和機(jī)構(gòu)三 , 存儲(chǔ)器層次機(jī)構(gòu)( 四)只讀存儲(chǔ)器( 五)主存儲(chǔ)器與 CPU 的連接( 六)雙口 RAM 和多模塊存儲(chǔ)器( 七)高速緩沖存儲(chǔ)器 (Cache)1. 程序訪問的局部2. Cache 的基本工作原理3. Cache 和主存之間的映射方式4. Cache 中主存塊的替換算法5. Cache 寫策略( 八)虛擬存儲(chǔ)器1. 虛擬存儲(chǔ)器的基本概念2. 頁式虛擬存儲(chǔ)器3. 段式虛擬存儲(chǔ)器4. 段頁式虛擬存儲(chǔ)器5. TLB( 快表 )四 , 指令系統(tǒng) ( 一) 指令格式1. 指令

8、的基本格式2. 定長(zhǎng)操作碼指令格式3. 擴(kuò)展操作碼指令格式 ( 二) 指令的尋址方式1. 有效地址的概念2. 數(shù)據(jù)尋址和指令尋址3. 常見尋址方式( 三) CISC和 RISC 的基本概念五 , 中央處理器 (CPU)( 一) CPU 的功能和基本結(jié)構(gòu)3( 二)指令執(zhí)行過程七, 輸入輸出 (I/O) 系統(tǒng)( 三)數(shù)據(jù)通路的功能和基本結(jié)構(gòu)( 一) I/O系統(tǒng)基本概念( 四)控制器的功能和工作原理( 二) 外部設(shè)備1.硬布線控制器1.輸入設(shè)備 : 鍵盤 , 鼠標(biāo)2.微程序控制器2.輸出設(shè)備 : 顯示器 , 打印機(jī)微程序 , 微指令和微命令 ; 微指令的編3.外存儲(chǔ)器 : 硬盤存儲(chǔ)器 , 磁盤陣列

9、,碼方式 ; 微地址的形式方式 .光盤存儲(chǔ)器( 五)指令流水線( 三) I/O接口 (I/O 控制器 )1.指令流水線的基本概念1.I/O接口的功能和基本結(jié)構(gòu)2.超標(biāo)量和動(dòng)態(tài)流水線的基本概念2.I/O端口及其編址六 ,總線( 四) I/O方式( 一)總線概述1.程序查詢方式1.總線的基本概念2.程序中斷方式2.總線的分類中斷的基本概念 ; 中斷響應(yīng)過程 ; 中斷3.總線的組成及性能指標(biāo)處理過程 ; 多重中斷和中斷屏蔽的( 二)總線仲裁概念 .1.集中仲裁方式3.DMA 方式2.分布仲裁方式DMA控制器的組成 ;DMA 傳送過程 .( 三)總線操作和定時(shí)4.通道方式1. 同步定時(shí)方式2. 異步定

10、時(shí)方式 ( 四) 總線標(biāo)準(zhǔn)4操作系統(tǒng)【考查目標(biāo)】1. 了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用 , 地位 , 發(fā)展和特點(diǎn) .2. 理解操作系統(tǒng)的基本概念 , 原理 , 掌握操作系統(tǒng)設(shè)計(jì)方法與實(shí)現(xiàn)技術(shù) .3. 能夠運(yùn)用所學(xué)的操作系統(tǒng)原理 , 方法與技術(shù)分析問題和解決問題 .一, 操作系統(tǒng)概述系統(tǒng)安全狀態(tài) : 銀行家算法 .( 一 ) 操作系統(tǒng)的概念 , 特征 , 功能和提供的服務(wù)5.死鎖檢測(cè)和解除( 二 ) 操作系統(tǒng)的發(fā)展與分類三,內(nèi)存管理( 三 ) 操作系統(tǒng)的運(yùn)行環(huán)境( 一) 內(nèi)存管理基礎(chǔ)二, 進(jìn)程管理1.內(nèi)存管理概念( 一 ) 進(jìn)程與線程程序裝入與鏈接 ; 邏輯地址與物理地址空間 ; 內(nèi)存1.進(jìn)程概

11、念保護(hù) .2.進(jìn)程的狀態(tài)與轉(zhuǎn)換2.交換與覆蓋3.進(jìn)程控制3.連續(xù)分配管理方式4.進(jìn)程組織4.非連續(xù)分配管理方式5.進(jìn)程通信分頁管理方式 ; 分段管理方式 ; 段頁式管理方式 .共享存儲(chǔ)系統(tǒng) ; 消息傳遞系統(tǒng) ; 管道通信 .( 二) 虛擬內(nèi)存管理6.線程概念與多線程模型1.虛擬內(nèi)存基本概念( 二 ) 處理機(jī)調(diào)度2.請(qǐng)求分頁管理方式1.調(diào)度的基本概念3.頁面置換算法2.調(diào)度時(shí)機(jī) , 切換與過程最佳置換算法 (OPT); 先進(jìn)先出置換算法 (FIFO); 最3.調(diào)度的基本準(zhǔn)則近最少使用置換算4.調(diào)度方式法(LRU); 時(shí)鐘置換算法 (CLOCK).5.典型調(diào)度算法4.頁面分配策略先來先服務(wù)調(diào)度算法

12、 ; 短作業(yè) ( 短進(jìn)程 , 短線程 )5.抖動(dòng)優(yōu)先調(diào)度算法 ; 時(shí)間片輪轉(zhuǎn)調(diào)度算法 ; 優(yōu)抖動(dòng)現(xiàn)象 ; 工作集 .先級(jí)調(diào)度算法 ; 高響應(yīng)比優(yōu)先調(diào)度算法 ; 多級(jí)反6.請(qǐng)求分段管理方式饋隊(duì)列調(diào)度算法 .7.請(qǐng)求段頁式管理方式( 三) 進(jìn)程同步四,文件管理1.進(jìn)程同步的基本概念( 一) 文件系統(tǒng)基礎(chǔ)2.實(shí)現(xiàn)臨界區(qū)互斥的基本方法1.文件概念軟件實(shí)現(xiàn)方法 ; 硬件實(shí)現(xiàn)方法 .2.文件的邏輯結(jié)構(gòu)3.信號(hào)量順序文件 ; 索引文件 ; 索引順序文件 .4.管程3.目錄結(jié)構(gòu)5.經(jīng)典同步問題文件控制塊和索引節(jié)點(diǎn) ; 單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄生產(chǎn)者 - 消費(fèi)者問題 ; 讀者 - 寫者問題 ; 哲學(xué)家進(jìn)結(jié)構(gòu) ;

13、樹形目錄結(jié)構(gòu) ; 圖形餐問題 .目錄結(jié)構(gòu) .(四) 死鎖4.文件共享1.死鎖的概念5.文件保護(hù)2.死鎖處理策略訪問類型 ; 訪問控制 .3.死鎖預(yù)防( 二) 文件系統(tǒng)實(shí)現(xiàn)4.死鎖避免1.文件系統(tǒng)層次結(jié)構(gòu)52. 目錄實(shí)現(xiàn)3. 文件實(shí)現(xiàn)( 三 ) 磁盤組織與管理1. 磁盤的結(jié)構(gòu)2. 磁盤調(diào)度算法3. 磁盤的管理五 , 輸入輸出 (I/O) 管理 ( 一 ) I/O 管理概述1. I/O 設(shè)備2. I/O 管理目標(biāo)3. I/O 管理功能4. I/O 應(yīng)用接口5. I/O 控制方式( 二 ) I/O核心子系統(tǒng)1. I/O 調(diào)度概念2. 高速緩存與緩沖區(qū)3. 設(shè)備分配與回收4. 假脫機(jī)技術(shù) (SPOOL

14、ing)5. 出錯(cuò)處理6計(jì)算機(jī)網(wǎng)絡(luò)【考查目標(biāo)】1. 掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念 , 基本原理和基本方法 .2. 掌握計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議 , 了解典型網(wǎng)絡(luò)設(shè)備的組成和特點(diǎn) , 理解典型網(wǎng)絡(luò)設(shè)備的工作原理3. 能夠運(yùn)用計(jì)算機(jī)網(wǎng)絡(luò)的基本概念 , 基本原理和基本方法進(jìn)行網(wǎng)絡(luò)系統(tǒng)的分析 , 設(shè)計(jì)和應(yīng)用一,計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)3.多幀滑動(dòng)窗口與后退 N 幀協(xié)議 (GBN)( 一 ) 計(jì)算機(jī)網(wǎng)絡(luò)概述4.多幀滑動(dòng)窗口與選擇重傳協(xié)議 (SR)1.計(jì)算機(jī)網(wǎng)絡(luò)的概念 , 組成與功能( 五)介質(zhì)訪問控制2.計(jì)算機(jī)網(wǎng)絡(luò)的分類1.信道劃分介質(zhì)訪問控制3.計(jì)算機(jī)網(wǎng)絡(luò)與互聯(lián)網(wǎng)的發(fā)展歷史頻分多路復(fù)用 , 時(shí)分多路復(fù)

15、用 , 波分多路復(fù)用 , 碼分4.計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織多路復(fù)用的概念和基( 二 ) 計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型本原理 .1.計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)2.隨即訪問介質(zhì)訪問控制2.計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議 , 接口 , 服務(wù)等概念A(yù)LOHA協(xié)議 ;CSMA 協(xié)議 ;CSMA/CD協(xié)議 ;CSMA/CA3. ISO/OSI 參考模型和 TCP/IP 模型協(xié)議 .二,物理層3.輪詢?cè)L問介質(zhì)訪問控制 : 令牌傳遞協(xié)議( 一) 通信基礎(chǔ)( 六)局域網(wǎng)1.信道, 信號(hào) , 寬帶 , 碼元, 波特, 速率等基本概1.局域網(wǎng)的基本概念與體系結(jié)構(gòu)念2.以太網(wǎng)與 IEEE 802.32.奈奎斯特定理與香農(nóng)定理3.IE

16、EE 802.113.信源與信宿4.令牌環(huán)網(wǎng)的基本原理4.編碼與調(diào)制( 七)廣域網(wǎng)5.電路交換 , 報(bào)文交換與分組交換1.廣域網(wǎng)的基本概念6.數(shù)據(jù)報(bào)與虛電路2.PPP協(xié)議( 二) 傳輸介質(zhì)3.HDLC 協(xié)議1.雙絞線 , 同軸電纜 , 光纖與無線傳輸介質(zhì)( 八)數(shù)據(jù)鏈路層設(shè)備2.物理層接口的特性1.網(wǎng)橋的概念和基本原理( 三 ) 物理層設(shè)備2.局域網(wǎng)交換機(jī)及其工作原理 .1.中繼器四,網(wǎng)絡(luò)層2.集線器( 一)網(wǎng)絡(luò)層的功能三,數(shù)據(jù)鏈路層1.異構(gòu)網(wǎng)絡(luò)互聯(lián)( 一 ) 數(shù)據(jù)鏈路層的功能2.路由與轉(zhuǎn)發(fā)(二) 組幀3.擁塞控制( 三) 差錯(cuò)控制( 二)路由算法1.檢錯(cuò)編碼1.靜態(tài)路由與動(dòng)態(tài)路由2.糾錯(cuò)編碼

17、2.距離 - 向量路由算法( 四 ) 流量控制與可靠傳輸機(jī)制3.鏈路狀態(tài)路由算法1.流量控制 , 可靠傳輸與滑輪窗口機(jī)制4.層次路由2.單幀滑動(dòng)窗口與停止 - 等待協(xié)議( 三) IPv41.IPv4分組2.IPv4地址與 NAT3.子網(wǎng)劃分與子網(wǎng)掩碼 ,CIDR4. ARP 協(xié)議 ,DHCP 協(xié)議與 ICMP 協(xié)議7( 四 ) IPv61.UDP 數(shù)據(jù)報(bào)1.IPv6的主要特點(diǎn)2.UDP 校驗(yàn)2.IPv6地址( 三) TCP 協(xié)議( 五 )路由協(xié)議1.TCP 段1.自治系統(tǒng)2.TCP 連接管理2.域內(nèi)路由與域間路由3.TCP 可靠傳輸3.RIP路由協(xié)議4.TCP 流量控制與擁塞控制4.OSPF

18、路由協(xié)議六,應(yīng)用層5.BGP 路由協(xié)議( 一)網(wǎng)絡(luò)應(yīng)用模型(六) IP組播1.客戶 / 服務(wù)器模型1.組播的概念2.P2P 模型2.IP組播地址( 二) DNS 系統(tǒng)3.組播路由算法1.層次域名空間( 七 )移動(dòng) IP2.域名服務(wù)器1.移動(dòng) IP的概念3.域名解析過程2.移動(dòng) IP的通信過程( 三) FTP( 八 )網(wǎng)絡(luò)層設(shè)備1.FTP 協(xié)議的工作原理1.路由器的組成和功能2.控制連接與數(shù)據(jù)連接2.路由表與路由轉(zhuǎn)發(fā)( 四)電子郵件五,傳輸層1.電子郵件系統(tǒng)的組成結(jié)構(gòu)( 一 )傳輸層提供的服務(wù)2.電子郵件格式與 MIME1.傳輸層的功能3. SMTP 協(xié)議與 POP3 協(xié)議2.傳輸層尋址與端口(

19、 五) WWW3.無連接服務(wù)與面向連接服務(wù)1. WWW的概念與組成結(jié)構(gòu)( 二) UDP 協(xié)議2. HTTP 協(xié)議8. 試題示例一 , 單項(xiàng)選擇題 :140 小題 , 每小題 2 分, 共 80 分. 在每小題給出的四個(gè)選項(xiàng)中 , 請(qǐng)選出一項(xiàng)最符合題目要求的 .試題示例 :1, 下列排序算法中 , 時(shí)間復(fù)雜度為 O(nlog2n) 且占用額外空間最少的是 A. 堆排序 B. 起泡排序 C. 快速排序 D. 希爾排序2,下列序列中 , 滿足堆定義的是A.(100,86,48,73,35,39,42,57,66,21)B.(12,70,33,65,24,56,48,92,86,33)C.(103,9

20、7,56,38,66,23,42,12,30,52,6,26)D.(5,56,20,23,40,38,29,61,35,76,28,100)3, 程序計(jì)數(shù)器 PC 用來存放指令地址 , 其位數(shù)和下列哪個(gè)寄存器相同?A. 指令寄存器 IR B. 主存數(shù)據(jù)寄存器MDRC.程序狀態(tài)字寄存器PSWR D主.存地址寄存器MAR4, 假定一個(gè)十進(jìn)制數(shù)為 -66, 按補(bǔ)碼形式存放在一個(gè) 8 位寄存器中 , 該寄存器的內(nèi)容用十六進(jìn)制表示為A.C2H B.BEH C.BDH D.42H5, 下列進(jìn)程狀態(tài)轉(zhuǎn)換中 , 不可能發(fā)生的轉(zhuǎn)換是A. 運(yùn)行就緒 B. 運(yùn)行等待 C. 等待運(yùn)行 D. 等待就緒6, 高某系統(tǒng)中有

21、 3個(gè)并發(fā)過程都需要4個(gè)同類資源 , 該系統(tǒng)不會(huì)發(fā)生死鎖的最少資源是A.9 B.10 C.11 D.127, 根據(jù) CSMA/CD協(xié)議的工作原理 , 下列情形中需要提高最短幀長(zhǎng)度的是 A. 網(wǎng)絡(luò)傳輸速率不變 , 沖突域的最大距離變短B. 沖突域的最大距離不變 , 網(wǎng)絡(luò)傳輸速率提高C.上層協(xié)議使用 TCP 的概率增加D.在沖突域不變的情況下減少線路中的中繼器數(shù)量8, 在選擇重傳協(xié)議 (SR) 中, 當(dāng)幀的序號(hào)字段為 3 比特 , 且接收窗口與發(fā)送窗口尺寸相同時(shí) , 發(fā)送窗口的最大尺寸為A.2 B.4 C.6 D.8二 , 綜合應(yīng)用題 :4147 小題 , 共 70 分.試題示例 :41.(10

22、分 ) 設(shè)無向圖 G=(V,E), 其中 V=1,2,3,4,5,E=(1,2,4),(2,5,5),(1,3,2),(2,4,4),(3,4,1),(4,5,3),(1,5,8),每條邊由一個(gè)三元組表示 , 三元組中前兩個(gè)元素為與該邊關(guān)聯(lián)的頂點(diǎn), 第三個(gè)元素為該邊的權(quán) . 請(qǐng)寫出圖 G 中從頂點(diǎn) 1 到其余各點(diǎn)的了短路徑的求解過程. 要求列出最短路徑上的頂點(diǎn) , 并計(jì)算路徑長(zhǎng)度.42.(15 分 ) 已 知 一 棵 二 叉 樹 采 用 二 叉 鏈 表 存 儲(chǔ) , 結(jié) 點(diǎn) 構(gòu) 造 為 : LeftChild DataRightChild ,root 指向根結(jié)點(diǎn) . 現(xiàn)定義二叉樹中結(jié)點(diǎn) X0 的

23、根 路徑為從根結(jié)點(diǎn)到 X0 結(jié)點(diǎn)的一條路徑 , 請(qǐng)編寫算法輸出該二叉樹中最長(zhǎng)的根路徑 ( 多條最長(zhǎng)根路徑中只輸出一條即可 . 算法可使用 C 或 C + + 或 JAVA 語言實(shí)現(xiàn) ).43.(11分 ) 某計(jì)算機(jī)的主存地址位數(shù)為32位, 按字節(jié)編址 . 假定數(shù)據(jù) Cache 中最多存放 128 個(gè)主存塊 , 采用 4路組相聯(lián)方式 , 塊大小為 64Byte, 每塊設(shè)置了 1位有效位 " 臟 (Dirty)"9位 .要求 :(1) 分別支出主存地址中標(biāo)記 (Tag), 組號(hào) (Index) 和塊內(nèi)地址 (Offset) 三部分的位置和位數(shù)(2) 計(jì)算該數(shù)據(jù) Cache 的總位數(shù) ( 請(qǐng)給出詳細(xì)計(jì)算過程 )44.(10 分 ) 下圖是一個(gè)簡(jiǎn)化的 CPU 與主存連接結(jié)構(gòu)示意圖 ( 圖中省略了所有多路選擇器 ). 其中有一個(gè)累加寄存器 AC, 一個(gè)狀態(tài)數(shù)據(jù)寄存器和其他四個(gè)寄存器 : 主存地址寄存器MAR,主存數(shù)據(jù)寄存器 MDR,程序計(jì)數(shù)器 PC 和指令寄存器 IR, 各部件及其之間的連線表示數(shù)據(jù)通路 , 箭頭表示信息傳遞方向 .要求 :(1) 請(qǐng)寫出圖中 a,b,c,d 四個(gè)寄存器的名稱(2) 簡(jiǎn)述圖中指令從