2025年計(jì)算機(jī)408深度剖析模擬卷考試時(shí)間：______分鐘總分：______分姓名：______一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分。在每小題列出的四個(gè)選項(xiàng)中，只有一個(gè)是符合題目要求的，請(qǐng)將正確選項(xiàng)字母填在題后的括號(hào)內(nèi)。）1.下列關(guān)于棧的描述中，正確的是（）。A.在棧中，插入和刪除操作都可以在棧頂進(jìn)行B.在棧中，插入和刪除操作都必須在棧底進(jìn)行C.棧是一種先進(jìn)后出（FIFO）的數(shù)據(jù)結(jié)構(gòu)D.棧是一種先進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)2.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度最多為（）。A.log2(n)B.nC.n^2D.2^n3.采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)線性表時(shí)，其地址計(jì)算是（）。A.隨機(jī)的B.不確定的C.基于首地址加上偏移量的D.無法進(jìn)行的4.在下列數(shù)據(jù)結(jié)構(gòu)中，適合用來表示稀疏矩陣的是（）。A.順序表B.線性鏈表C.二叉樹D.稀疏矩陣壓縮存儲(chǔ)（如三元組表）5.計(jì)算機(jī)中用于存儲(chǔ)當(dāng)前正在執(zhí)行的指令和操作數(shù)的部件是（）。A.運(yùn)算器B.存儲(chǔ)器C.控制器D.輸入/輸出設(shè)備6.在計(jì)算機(jī)系統(tǒng)中，Cache的作用是（）。A.提高主存的讀寫速度B.增加主存的存儲(chǔ)容量C.實(shí)現(xiàn)主存與輔存之間的數(shù)據(jù)交換D.存儲(chǔ)系統(tǒng)中的臨時(shí)文件7.下列關(guān)于中斷的描述中，錯(cuò)誤的是（）。A.中斷是CPU對(duì)系統(tǒng)中發(fā)生的事件做出的反應(yīng)B.中斷處理過程通常包括中斷請(qǐng)求、中斷判優(yōu)、中斷響應(yīng)、中斷服務(wù)、中斷返回C.中斷會(huì)打斷當(dāng)前程序的執(zhí)行，轉(zhuǎn)而去執(zhí)行中斷服務(wù)程序D.中斷只能由外部設(shè)備請(qǐng)求引起8.在操作系統(tǒng)中，進(jìn)程的基本狀態(tài)轉(zhuǎn)換不包括（）。A.創(chuàng)建狀態(tài)B.運(yùn)行狀態(tài)C.等待狀態(tài)D.傳輸狀態(tài)9.文件系統(tǒng)中的目錄結(jié)構(gòu)主要有（）兩種。A.線性結(jié)構(gòu)和樹形結(jié)構(gòu)B.網(wǎng)狀結(jié)構(gòu)和環(huán)形結(jié)構(gòu)C.單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)D.連接結(jié)構(gòu)和索引結(jié)構(gòu)10.TCP協(xié)議提供的服務(wù)是（）。A.無連接、不可靠的數(shù)據(jù)報(bào)服務(wù)B.無連接、可靠的數(shù)據(jù)報(bào)服務(wù)C.有連接、不可靠的數(shù)據(jù)流服務(wù)D.有連接、可靠的數(shù)據(jù)流服務(wù)二、填空題（本大題共10小題，每小題1.5分，共15分。請(qǐng)將答案填寫在答題紙上對(duì)應(yīng)題號(hào)后的橫線上。）11.在深度為k的二叉樹中，最多含有_______個(gè)結(jié)點(diǎn)。12.隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，其操作通常包括入隊(duì)和_______。13.在順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（i合法）時(shí)，至少需要移動(dòng)_______個(gè)元素。14.計(jì)算機(jī)的指令系統(tǒng)通常由操作碼和_______兩部分組成。15.Cache與主存之間的地址映射方式主要有直接映射、全相聯(lián)映射和_______三種。16.在多道程序設(shè)計(jì)中，操作系統(tǒng)通過_______技術(shù)實(shí)現(xiàn)內(nèi)存的共享和保護(hù)。17.進(jìn)程調(diào)度算法的目標(biāo)主要是提高CPU利用率和_______。18.磁盤調(diào)度算法的目標(biāo)主要是減少平均尋道時(shí)間，常用的算法有FCFS、SSTF和_______。19.文件系統(tǒng)中，邏輯文件到物理文件之間的映射通常通過_______來實(shí)現(xiàn)。20.在TCP/IP協(xié)議簇中，負(fù)責(zé)網(wǎng)絡(luò)層數(shù)據(jù)報(bào)傳輸?shù)膮f(xié)議是_______。三、簡答題（本大題共5小題，每小題5分，共25分。請(qǐng)將答案填寫在答題紙上對(duì)應(yīng)題號(hào)后的橫線上或指定的答題區(qū)域內(nèi)。）21.簡述棧和隊(duì)列的主要區(qū)別。22.什么是二叉樹的遍歷？列出三種常見的二叉樹遍歷方式及其訪問結(jié)點(diǎn)的順序。23.簡述計(jì)算機(jī)內(nèi)存層次結(jié)構(gòu)（如寄存器、Cache、主存、輔存）的設(shè)計(jì)目標(biāo)。24.什么是中斷？中斷處理過程大致可分為哪幾個(gè)階段？25.簡述操作系統(tǒng)實(shí)現(xiàn)進(jìn)程切換大致需要經(jīng)歷的步驟。四、綜合應(yīng)用題（本大題共3小題，共40分。請(qǐng)將答案填寫在答題紙上對(duì)應(yīng)題號(hào)后的橫線上或指定的答題區(qū)域內(nèi)。）26.（10分）已知一個(gè)棧的初始狀態(tài)為空，現(xiàn)依次壓入元素A、B、C、D、E。請(qǐng)回答：（1）棧頂元素是什么？（2）若此時(shí)依次執(zhí)行一次出棧操作和一次入棧操作（元素為F），棧頂元素是什么？（3）請(qǐng)描述出棧操作直到棧為空的過程，并給出每次出棧前棧內(nèi)元素的狀態(tài)（可使用“|”表示棧底，“|A|B|C|D|E”表示元素A在棧頂）。27.（15分）假設(shè)某計(jì)算機(jī)主存容量為256MB，Cache容量為16KB，采用直接映射方式，主存塊大小為4KB，Cache塊大小也為4KB。（1）計(jì)算該Cache共有多少個(gè)塊？（2）主存地址有多少位？Cache地址有多少位？（3）當(dāng)主存地址0000H0000F被訪問時(shí)，該地址映射到Cache的哪個(gè)塊號(hào)？對(duì)應(yīng)的Cache內(nèi)單元地址是多少？假設(shè)Cache初始狀態(tài)為空，且未發(fā)生替換，請(qǐng)簡述訪問過程。28.（15分）有一個(gè)單鏈表，結(jié)點(diǎn)數(shù)據(jù)域包含整數(shù)值。設(shè)計(jì)一個(gè)算法，不使用額外的存儲(chǔ)空間，刪除該單鏈表中所有值為x的結(jié)點(diǎn)，并將剩余結(jié)點(diǎn)按值從小到大排序（假設(shè)鏈表初始時(shí)已按值排序）。請(qǐng)簡述算法思想，并說明如何保證不使用額外存儲(chǔ)空間。試卷答案一、單項(xiàng)選擇題1.D2.B3.C4.D5.B6.A7.D8.D9.C10.D二、填空題11.2^k-112.出隊(duì)13.i-114.地址碼（或操作數(shù)地址）15.組相聯(lián)映射16.內(nèi)存保護(hù)（或虛擬內(nèi)存）17.提高系統(tǒng)吞吐量（或用戶滿意度）18.SCAN（或電梯算法）19.文件控制塊（FCB）（或索引節(jié)點(diǎn)）20.IP三、簡答題21.棧是先進(jìn)后出（LIFO）結(jié)構(gòu)，僅允許在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出（FIFO）結(jié)構(gòu)，允許在隊(duì)頭進(jìn)行刪除操作，在隊(duì)尾進(jìn)行插入操作。22.二叉樹遍歷是指按照一定的規(guī)則訪問二叉樹中的所有結(jié)點(diǎn)，通常分為三種方式：前序遍歷（訪問根結(jié)點(diǎn)->遍歷左子樹->遍歷右子樹）、中序遍歷（遍歷左子樹->訪問根結(jié)點(diǎn)->遍歷右子樹）、后序遍歷（遍歷左子樹->遍歷右子樹->訪問根結(jié)點(diǎn)）。23.計(jì)算機(jī)內(nèi)存層次結(jié)構(gòu)的設(shè)計(jì)目標(biāo)是在成本、速度和容量之間取得平衡，利用高速、小容量、高成本的存儲(chǔ)器存放頻繁訪問的數(shù)據(jù)和程序，利用低速、大容量、低成本的存儲(chǔ)器存放不頻繁訪問的數(shù)據(jù)和程序，從而提高整個(gè)存儲(chǔ)系統(tǒng)的性能和效率。24.中斷是計(jì)算機(jī)系統(tǒng)中，發(fā)生異步事件請(qǐng)求CPU暫停當(dāng)前工作，轉(zhuǎn)而去處理該事件的過程。中斷處理過程大致可分為：中斷請(qǐng)求、中斷判優(yōu)（如果有多個(gè)中斷請(qǐng)求）、中斷響應(yīng)（CPU暫停當(dāng)前工作）、中斷服務(wù)（執(zhí)行中斷服務(wù)程序處理事件）、中斷返回（恢復(fù)中斷前的狀態(tài)繼續(xù)執(zhí)行原程序）。25.操作系統(tǒng)實(shí)現(xiàn)進(jìn)程切換大致需要經(jīng)歷的步驟：保存當(dāng)前進(jìn)程的狀態(tài)（如程序計(jì)數(shù)器PC、通用寄存器內(nèi)容等）到其進(jìn)程控制塊PCB中；從就緒隊(duì)列中選擇一個(gè)新的進(jìn)程；將新進(jìn)程的狀態(tài)信息加載到CPU的寄存器中；使CPU開始執(zhí)行新進(jìn)程。四、綜合應(yīng)用題26.（1）E（2）F（3）初始狀態(tài)：|壓入A：|A壓入B：|A|B壓入C：|A|B|C壓入D：|A|B|C|D壓入E：|A|B|C|D|E出棧：|A|B|C|D棧頂：D入棧F：|A|B|C|D|F出棧：|A|B|C|F棧頂：F出棧：|A|B|C棧頂：C出棧：|A|B棧頂：B出棧：|A棧頂：A出棧：|?？?7.（1）16KB/4KB=4塊（2）256MB=2^28Bytes，需要28位地址。Cache地址=log2(4KB)=log2(2^12)=12位，主存地址=28-12=16位。（3）主存地址0000H0000F=000000000000000011111111，低12位00001111是Cache塊號(hào)（0-3），高16位0000000000000000是Cache內(nèi)單元地址（相對(duì)于塊內(nèi)偏移的地址，塊內(nèi)地址也需要12位，但這里只需要標(biāo)明是塊內(nèi)地址即可）。訪問過程：將主存地址的低12位作為Cache塊號(hào)，在Cache中查找對(duì)應(yīng)塊，若命中則直接從Cache中讀取數(shù)據(jù)；若未命中，則從主存中讀取相應(yīng)4KB塊到Cache中（假設(shè)未發(fā)生替換或采用特定替換策略），然后從Cache中讀取數(shù)據(jù)。此題假設(shè)未發(fā)生替換且未具體說明替換策略，故主要描述地址映射和命中情況。28.算法思想：由于鏈表初始時(shí)已排序，刪除值為x的結(jié)點(diǎn)后仍需保持排序順序。不使用額外存儲(chǔ)空間意味著不能創(chuàng)建新鏈表，只能在原鏈表上操作?？梢圆捎秒p向鏈表方便從前向后查找和刪除，但題目未明確類型，可考慮在單鏈表上通過調(diào)整指針實(shí)現(xiàn)。方法是：使用一個(gè)指針p遍歷鏈表，用pre指針記錄p的前驅(qū)。當(dāng)p所指向的結(jié)點(diǎn)值等于x時(shí)，執(zhí)行刪除操作：pre->next=p->next；如果p->next不為空，則可能需要調(diào)整排序（