09年計(jì)算機(jī)專業(yè)考研考試大綱及解析

［考查目標(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)理論問(wèn)題和實(shí)際問(wèn)題。

口考試形式和試卷結(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分）

綜合應(yīng)用題70分

in考查范圍

數(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è)計(jì)與分析。

3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。

一、線性表

（-）線性表的定義和基本操作

（二）線性表的實(shí)現(xiàn)

1.順序存儲(chǔ)結(jié)構(gòu)

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.線性表的應(yīng)用

二、棧、隊(duì)列和數(shù)組

（-）棧和隊(duì)列的基本概念

（~）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

（三）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

（四）棧和隊(duì)列的應(yīng)用

（五）特殊矩陣的壓縮存儲(chǔ)

三、樹(shù)與二叉樹(shù)

（-）樹(shù)的概念

（二）二叉樹(shù)

1.二叉樹(shù)的定義及其主要特征

2.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.二叉樹(shù)的遍歷

4.線索二叉樹(shù)的基本概念和構(gòu)造

5.二叉排序樹(shù)

6.平衡二叉樹(shù)

（三）樹(shù)、森林

1.樹(shù)的存儲(chǔ)結(jié)構(gòu)

2.森林與二叉樹(shù)的轉(zhuǎn)換

3.樹(shù)和森林的遍歷

（四）樹(shù)的應(yīng)用

1.等價(jià)類問(wèn)題

2.哈夫曼（Huffman）樹(shù)和哈夫曼編碼

三、圖

（-）圖的概念

（-）圖的存儲(chǔ)及基本操作

1.鄰接矩陣法

2.鄰接表法

（三）圖的遍歷

1.深度優(yōu)先搜索

2.廣度優(yōu)先搜索

（四）圖的基本應(yīng)用及其復(fù)雜度分析

1.最?。ù鷥r(jià)）生成樹(shù)

2.最短路徑

3.拓?fù)渑判?/p>

4.關(guān)鍵路徑

查找的基本概念

（-）順序查找法

（三）折半查找法

（四）B-樹(shù)

（五）散列（Hash）表及其查找

（六）查找算法的分析及應(yīng)用

四、查找

五、內(nèi)部排序

（-）排序的基本概念

（二）插入排序

1.直接插入排序

2.折半插入排序

（三）氣泡排序（bubblesort）

（四）簡(jiǎn)單選擇排序

（五）希爾排序（shellsort）

（六）快速排序

（七）堆排序

（八）二路歸并排序（mergesort）

（九）基數(shù)排序

（十）各種內(nèi)部排序算法的比較

（十一）內(nèi)部排序算法的應(yīng)用

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

【考查目標(biāo)】

1.理解單處理器計(jì)算機(jī)系統(tǒng)中各部件的內(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í)際問(wèn)題進(jìn)行計(jì)算、分

析，并能對(duì)一些基本部件進(jìn)行簡(jiǎn)單設(shè)計(jì)。

一、計(jì)算機(jī)系統(tǒng)概述

（-）計(jì)算機(jī)發(fā)展歷程

（-）計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)

1.計(jì)算機(jī)硬件的基本組成

2.計(jì)算機(jī)軟件的分類

3.計(jì)算機(jī)的工作過(guò)程

（三）計(jì)算機(jī)性能指標(biāo)

吞吐量、響應(yīng)時(shí)間；CPU時(shí)鐘周期、主頻、CPLCPU執(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ù)的表示

無(wú)符號(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)準(zhǔn)

2.浮點(diǎn)數(shù)的加/減運(yùn)算

（四）算術(shù)邏輯單元ALU

1.串行加法器和并行加法器

2.算術(shù)邏輯單元ALU的功能和機(jī)構(gòu)

三、存儲(chǔ)器層次機(jī)構(gòu)

（-）存儲(chǔ)器的分類

（-）存儲(chǔ)器的層次化結(jié)構(gòu)

（三）半導(dǎo)體隨機(jī)存取存儲(chǔ)器

1.SRAM存儲(chǔ)器的工作原理

2.DRAM存儲(chǔ)器的工作原理

（四）只讀存儲(chǔ)器

（五）主存儲(chǔ)器與CPU的連接

（六）雙口RAM和多模塊存儲(chǔ)器

（七）高速緩沖存儲(chǔ)器（Cache）

1.程序訪問(wèn)的局部

2.Cache的基本工作原理

3.Cache和主存之間的映射方式

4.Cache中主存塊的替換算法

5.Cache寫策略

（A）虛擬存儲(chǔ)器

1.虛擬存儲(chǔ)器的基本概念

2.頁(yè)式虛擬存儲(chǔ)器

3.段式虛擬存儲(chǔ)器

4.段頁(yè)式虛擬存儲(chǔ)器

5.TLB（快表）

四、指令系統(tǒng)

（-）指令格式

1.指令的基本格式

2.定長(zhǎng)操作碼指令格式

3.擴(kuò)展操作碼指令格式

（-）指令的尋址方式

1.有效地址的概念

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

3.常見(jiàn)尋址方式

（三）CISC和RISC的基本概念

五、中央處理器（CPU）

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

（-）指令執(zhí)行過(guò)程

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

（四）控制器的功能和工作原理

1.硬布線控制器

2.微程序控制器

微程序、微指令和微命令；微指令的編碼方式；微地址的形式方式。

（五）指令流水線

1.指令流水線的基本概念

2.超標(biāo)量和動(dòng)態(tài)流水線的基本概念

六、總線

（-）總線概述

1.總線的基本概念

2.總線的分類

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

（-）總線仲裁

1.集中仲裁方式

2.分布仲裁方式

（三）總線操作和定時(shí)

1.同步定時(shí)方式

2.異步定時(shí)方式

（四）總線標(biāo)準(zhǔn)

七、輸入輸出（I/O）系統(tǒng)

（-）I/O系統(tǒng)基本概念

（-）外部設(shè)備

1.輸入設(shè)備：鍵盤、鼠標(biāo)

2.輸出設(shè)備：顯示器、打印機(jī)

3.外存儲(chǔ)器：硬盤存儲(chǔ)器、磁盤陣列、光盤存儲(chǔ)器

（=）I/O接口（I/O控制器）

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

2.I/O端口及其編址

（四）I/O方式

1.程序查詢方式

2.程序中斷方式

中斷的基本概念；中斷響應(yīng)過(guò)程；中斷處理過(guò)程；多重中斷和中斷屏蔽的概念。

3.DMA方式

DMA控制器的組成；DMA傳送過(guò)程。

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ù)分析問(wèn)題和解決問(wèn)題。

一、操作系統(tǒng)概述

（-）操作系統(tǒng)的概念、特征、功能和提供的服務(wù)

（二）操作系統(tǒng)的發(fā)展與分類

（三）操作系統(tǒng)的運(yùn)行環(huán)境

二、進(jìn)程管理

（-）進(jìn)程與線程

1.進(jìn)程概念

2.進(jìn)程的狀態(tài)與轉(zhuǎn)換

3.進(jìn)程控制

4.進(jìn)程組織

5.進(jìn)程通信

共享存儲(chǔ)系統(tǒng)；消息傳遞系統(tǒng)；管道通信。

6.線程概念與多線程模型

（-）處理機(jī)調(diào)度

1.調(diào)度的基木概念

2.調(diào)度時(shí)機(jī)、切換與過(guò)程

3.調(diào)度的基本準(zhǔn)則

4.調(diào)度方式

5.典型調(diào)度算法

先來(lái)先服務(wù)調(diào)度算法；短作業(yè)（短任務(wù)、短進(jìn)程、短線程）優(yōu)先調(diào)度算法；時(shí)間片輪轉(zhuǎn)調(diào)度算法；優(yōu)

先級(jí)調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級(jí)反饋隊(duì)列調(diào)度算法。

（三）進(jìn)程同步

1.進(jìn)程同步的基本概念

2.實(shí)現(xiàn)臨界區(qū)互斥的基本方法

軟件實(shí)現(xiàn)方法；硬件實(shí)現(xiàn)方法。

3.信號(hào)量

4.管程

5.經(jīng)典同步問(wèn)題

生產(chǎn)者-消費(fèi)者問(wèn)題；讀者-寫者問(wèn)題；哲學(xué)家進(jìn)餐問(wèn)題。

（四）死鎖

1.死鎖的概念

2.死鎖處理策略

3.死鎖預(yù)防

4.死鎖避免

系統(tǒng)安全狀態(tài)：銀行家算法。

5.死鎖檢測(cè)和解除

內(nèi)存管理

（-）內(nèi)存管理基礎(chǔ)

1.內(nèi)存管理概念

程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護(hù)。

2.交換與覆蓋

3.連續(xù)分配管理方式

單一連續(xù)分配；分區(qū)分配。

4.非連續(xù)分配管理方式

分頁(yè)管理方式；分段管理方式；段頁(yè)式管理方式。

（-）虛擬內(nèi)存管理

1.虛擬內(nèi)存基本概念

2.請(qǐng)求分頁(yè)管理方式

3.頁(yè)面置換算法

最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時(shí)

鐘置換算法（CLOCK）。

4.頁(yè)面分配策略

5.抖動(dòng)

抖動(dòng)現(xiàn)象；工作集。

6.請(qǐng)求分段管理方式

7.請(qǐng)求段頁(yè)式管理方式

四、文件管理

（-）文件系統(tǒng)基礎(chǔ)

1.文件概念

2.文件結(jié)構(gòu)

順序文件；索引文件；索引順序文件。

3.目錄結(jié)構(gòu)

文件控制塊和索引節(jié)點(diǎn)；單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)；樹(shù)形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)。

4.文件共享

共享動(dòng)機(jī)；共享方式；共享語(yǔ)義。

5.文件保護(hù)

訪問(wèn)類型；訪問(wèn)控制。

（-）文件系統(tǒng)實(shí)現(xiàn)

1.文件系統(tǒng)層次結(jié)構(gòu)

2.目錄實(shí)現(xiàn)

3.文件實(shí)現(xiàn)

（三）磁盤組織與管理

1.磁盤的結(jié)構(gòu)

2.磁盤調(diào)度算法

3.磁盤的管理

五、輸入輸出（I/O）管理

（-）I/。管理概述

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ù)＜SPOOLing）

5.出錯(cuò)處理

計(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)

（-）計(jì)算機(jī)網(wǎng)絡(luò)概述

1.計(jì)算機(jī)網(wǎng)絡(luò)的概念、組成與功能

2.計(jì)算機(jī)網(wǎng)絡(luò)的分類

3.計(jì)算機(jī)網(wǎng)絡(luò)與互聯(lián)網(wǎng)的發(fā)展歷史

4.計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織

（-）計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型

1.計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)

2.計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、接口、服務(wù)等概念

3.ISO/OSI參考模型和TCP/IP模型

二、物理層

（-）通信基礎(chǔ)

1.信道、信號(hào)、寬帶、碼元、波特、速率等基本概念

2.奈奎斯特定理與香農(nóng)定理

3.信源與信宿

4.編碼與調(diào)制

5.電路交換、報(bào)文交換與分組交換

6.數(shù)據(jù)報(bào)與虛電路

（―）傳輸介質(zhì)

1.雙絞線、同軸電纜、光纖與無(wú)線傳輸介質(zhì)

2.物理層接口的特性

（三）物理層設(shè)備

1.中繼器

2.集線器

三、數(shù)據(jù)鏈路層

（-）數(shù)據(jù)鏈路層的功能

（二）組幀

（三）差錯(cuò)控制

1.檢錯(cuò)編碼

2.糾錯(cuò)編碼

（四）流量控制與可靠傳輸機(jī)制

1.流量控制、可靠傳輸與滑輪窗口機(jī)制

2.單幀滑動(dòng)窗口與停止-等待協(xié)議

3.多幀滑動(dòng)窗口與后退N幀協(xié)議（GBN）

4.多幀滑動(dòng)窗口與選擇重傳協(xié)議（SR）

（五）介質(zhì)訪問(wèn)控制

1.信道劃分介質(zhì)訪問(wèn)控制

頻分多路復(fù)用、時(shí)分多路復(fù)用、波分多路復(fù)用、碼分多路復(fù)用的概念和基本原理。

2.隨即訪問(wèn)介質(zhì)訪問(wèn)控制

ALOHA協(xié)議；CSMA協(xié)議；CSMA/CD協(xié)議；CSMA/CA協(xié)議。

3.輪詢?cè)L問(wèn)介質(zhì)訪問(wèn)控制：令牌傳遞協(xié)議

（六）局域網(wǎng)

1.局域網(wǎng)的基本概念與體系結(jié)構(gòu)

2.以太網(wǎng)與IEEE802.3

3.IEEE802.11

4.令牌環(huán)網(wǎng)的基本原理

（七）廣域網(wǎng)

1.廣域網(wǎng)的基本概念

2.PPP協(xié)議

3.HDLC協(xié)議

4.ATM網(wǎng)絡(luò)基本原理

（A）數(shù)據(jù)鏈路層設(shè)備

1.網(wǎng)橋

網(wǎng)橋的概念；透明網(wǎng)橋與生成樹(shù)算法；源選徑網(wǎng)橋與源選徑算法。

2.局域網(wǎng)交換機(jī)及其工作原理。

四、網(wǎng)絡(luò)層

（-）網(wǎng)絡(luò)層的功能

1.異構(gòu)網(wǎng)絡(luò)互聯(lián)

2.路由與轉(zhuǎn)發(fā)

3.擁塞控制

（二）路由算法

1.靜態(tài)路由與動(dòng)態(tài)路由

2.距離-向量路由算法

3.鏈路狀態(tài)路由算法

4.層次路由

（三）IPv4

1.IPv4分組

2.IPv4地址與NAT

3.子網(wǎng)劃分與子網(wǎng)掩碼、CIDR

4.ARP協(xié)議、DHCP協(xié)議與ICMP協(xié)議

（四）IPv6

1.IPv6的主要特點(diǎn)

2.IPv6地址

（五）路由協(xié)議

1.自治系統(tǒng)

2.域內(nèi)路由與域間路由

3.RIP路由協(xié)議

4.OSPF路由協(xié)議

5.BGP路由協(xié)議

（六）IP組播

1.組播的概念

2.IP組播地址

3.組播路由算法

（七）移動(dòng)IP

1.移動(dòng)IP的概念

2.移動(dòng)IP的通信過(guò)程

（A）網(wǎng)絡(luò)層設(shè)備

1.路由器的組成和功能

2.路由表與路由轉(zhuǎn)發(fā)

五、傳輸層

（-）傳輸層提供的服務(wù)

1.傳輸層的功能

2.傳輸層尋址與端口

3.無(wú)連接服務(wù)與面向連接服務(wù)

（二）UDP協(xié)議

1.UDP數(shù)據(jù)報(bào)

2.UDP校驗(yàn)

（三）TCP協(xié)議

1.TCP段

2.TCP連接管理

3.TCP可靠傳輸

4.TCP流量控制與擁塞控制

六、應(yīng)用層

（四）網(wǎng)絡(luò)應(yīng)用模型

1.客戶/服務(wù)器模型

2.P2P模型

(五)DNS系統(tǒng)

1.層次域名空間

2.域名服務(wù)器

3.域名解析過(guò)程

(六)FTP

1.FTP協(xié)議的工作原理

2.控制連接與數(shù)據(jù)連接

(七)電子郵件

1.電子郵件系統(tǒng)的組成結(jié)構(gòu)

2.電子郵件格式與MIME

3.SMTP協(xié)議與POP3協(xié)議

(八)WWW

1.WWW的概念與組成結(jié)構(gòu)

2.HTTP協(xié)議

IV.試題示例

一、單項(xiàng)選擇題：7~4。小題，每小題2分，共8。分。在每小題給出的四個(gè)選項(xiàng)中，請(qǐng)選出一項(xiàng)最符

合題目要求的。

試題示例：

7、下列排序算法中，時(shí)間復(fù)雜度為O(nlog2n)且占用額外空間最少的是

A.堆排序B.起泡排序C.快速排序D.希爾排序

2、下列序列中，滿足堆定義的是

A.(700,86,48,73,35,39,42,57,66,27)

B.(72,70,33,65,24,56,43,92,86,33)

C.(703,97,56,38,66,23,42,12,30,52,6,26)

D.(5,56,20,23,40,38,29,67,35,76,28,100)

3、程序計(jì)數(shù)器PC用來(lái)存放指令地址，其位數(shù)和下列哪個(gè)寄存器相同？

A.指令寄存器IRB.主存數(shù)據(jù)寄存器MDR

C.程序狀態(tài)字寄存器PSWRD.主存地址寄存器MAR

彳、假定一個(gè)十進(jìn)制數(shù)為-66,按補(bǔ)碼形式存放在一個(gè)8位寄存器中，該寄存器的內(nèi)容用十六進(jìn)制表示為

A.C2HB.BEHC.BDHD.42H

5、下列進(jìn)程狀態(tài)轉(zhuǎn)換中，不可能發(fā)生的轉(zhuǎn)換是

A.運(yùn)行一就緒B.運(yùn)行一等待C.等待一運(yùn)行D.等待一就緒

6、高某系統(tǒng)中有3個(gè)并發(fā)過(guò)程都需要7個(gè)同類資源，該系統(tǒng)不會(huì)發(fā)生死鎖的最少資源是

A.9B.10C.11D.12

7、根據(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.2B.4C.6D.8

二、綜合應(yīng)用題：中小題，共7。分。

試題示例：

H1.（70分）設(shè)無(wú)向圖G=（V,E）,其中V=〃，2,3,4,5},E=f（7,2,4）,（2,5,5）,（7,3,

2）,（2,彳，4）,（3,%7）,（4,5,3）,（7,5,8）},每條邊由一個(gè)三元組表示，三元組中前兩個(gè)元

素為與該邊關(guān)聯(lián)的頂點(diǎn)，第三個(gè)元素為該邊的權(quán)。請(qǐng)寫出圖G中從頂點(diǎn)7到其余各點(diǎn)的了短路徑的求解

過(guò)程。要求列出最短路徑上的頂點(diǎn)，并計(jì)算路徑長(zhǎng)度?

^2-（15分）已知一棵二叉樹(shù)采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)構(gòu)造為；LeftChildDataRightChild.root指向根

結(jié)點(diǎn)?，F(xiàn)定義二義樹(shù)中結(jié)點(diǎn)X。的根路徑為從根結(jié)點(diǎn)到X。結(jié)點(diǎn)的一條路徑，請(qǐng)編寫算法輸出該二叉樹(shù)

中最長(zhǎng)的根路徑（多條最長(zhǎng)根路徑中只輸出一條即可。算法可使用C或C++或JAVA語(yǔ)言實(shí)現(xiàn)）。

43.（77分）某計(jì)算機(jī)的主存地址位數(shù)為32位，按字節(jié)編址。假定數(shù)據(jù)Cache中最多存放728個(gè)主存

塊，采用4路組相聯(lián)方式，塊大小為64Byte,每塊設(shè)置了7位有效位“臟（Dirty）”位。

要求：

（7）分別支出主存地址中標(biāo)記（Tag）、組號(hào)（Index）和塊內(nèi)地址（Offset）三部分的位置和位數(shù)

（2）計(jì)算該數(shù)據(jù)Cache的總位數(shù)（請(qǐng)給出詳細(xì)計(jì)算過(guò)程）

4e（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ù)通路，箭頭表示信息傳遞方向。

要求：

（7）請(qǐng)寫出圖中a、b、c、d四個(gè)寄存器的名稱

（2）