(2025年)《計(jì)算機(jī)理論知識(shí)》復(fù)習(xí)題及答案一、單項(xiàng)選擇題（每題2分，共30分）1.圖靈機(jī)的核心組成不包括以下哪一項(xiàng)？A.無(wú)限長(zhǎng)的紙帶B.讀寫(xiě)頭C.狀態(tài)寄存器D.中央處理器（CPU）答案：D2.馮·諾依曼體系結(jié)構(gòu)的核心特征是：A.程序和數(shù)據(jù)存儲(chǔ)在不同介質(zhì)中B.指令和數(shù)據(jù)以二進(jìn)制形式統(tǒng)一存儲(chǔ)C.采用并行計(jì)算模式D.硬件與軟件完全解耦答案：B3.以下關(guān)于補(bǔ)碼表示的描述中，錯(cuò)誤的是：A.0的補(bǔ)碼表示唯一B.負(fù)數(shù)的補(bǔ)碼是其原碼取反加1C.8位補(bǔ)碼能表示的整數(shù)范圍是-128到+127D.補(bǔ)碼運(yùn)算時(shí)符號(hào)位不參與計(jì)算答案：D4.對(duì)于完全二叉樹(shù)，若有n個(gè)節(jié)點(diǎn)，則其深度為（log?n取下整）+1的條件是：A.節(jié)點(diǎn)按層序從左到右填充B.所有葉子節(jié)點(diǎn)在同一層C.樹(shù)中不存在度為1的節(jié)點(diǎn)D.根節(jié)點(diǎn)編號(hào)為0答案：A5.操作系統(tǒng)中，虛擬內(nèi)存的頁(yè)表主要用于：A.記錄物理內(nèi)存的空閑塊B.實(shí)現(xiàn)虛擬地址到物理地址的映射C.管理進(jìn)程的上下文切換D.優(yōu)化文件I/O速度答案：B6.TCP協(xié)議中，流量控制的主要實(shí)現(xiàn)機(jī)制是：A.超時(shí)重傳B.滑動(dòng)窗口C.校驗(yàn)和D.擁塞避免算法答案：B7.關(guān)系數(shù)據(jù)庫(kù)中，若一個(gè)關(guān)系模式滿足“所有非主屬性完全函數(shù)依賴于候選鍵”，則該模式至少屬于：A.第一范式（1NF）B.第二范式（2NF）C.第三范式（3NF）D.BC范式（BCNF）答案：B8.以下關(guān)于編譯過(guò)程的描述中，正確的是：A.詞法分析將源程序轉(zhuǎn)換為抽象語(yǔ)法樹(shù)B.語(yǔ)法分析檢查代碼的邏輯錯(cuò)誤C.語(yǔ)義分析處理變量類型匹配問(wèn)題D.目標(biāo)代碼提供階段輸出匯編語(yǔ)言答案：C9.算法的時(shí)間復(fù)雜度分析中，O(n2)和O(nlogn)的本質(zhì)區(qū)別在于：A.常數(shù)因子的大小B.問(wèn)題規(guī)模n增大時(shí)的增長(zhǎng)速率C.算法是否使用遞歸D.算法是否穩(wěn)定答案：B10.在IPv4地址中，192.168.1.1屬于：A.A類地址B.B類地址C.C類地址D.私有地址答案：D11.以下哪種數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)“后進(jìn)先出”（LIFO）的操作？A.隊(duì)列B.棧C.二叉搜索樹(shù)D.哈希表答案：B12.操作系統(tǒng)的進(jìn)程狀態(tài)中，“阻塞態(tài)”是指進(jìn)程：A.正在CPU上執(zhí)行B.等待某個(gè)事件（如I/O完成）C.已分配資源但未獲得CPU時(shí)間片D.已結(jié)束運(yùn)行答案：B13.數(shù)據(jù)庫(kù)事務(wù)的ACID特性中，“隔離性”（Isolation）指的是：A.事務(wù)一旦提交，其結(jié)果不可撤銷B.事務(wù)執(zhí)行期間不被其他事務(wù)干擾C.事務(wù)中的操作要么全部完成，要么全部不完成D.事務(wù)處理的數(shù)據(jù)符合數(shù)據(jù)庫(kù)約束答案：B14.以下關(guān)于哈希沖突的描述中，錯(cuò)誤的是：A.開(kāi)放尋址法通過(guò)探測(cè)其他位置存儲(chǔ)沖突元素B.鏈地址法為每個(gè)哈希槽維護(hù)一個(gè)鏈表C.沖突無(wú)法避免，但可以通過(guò)優(yōu)化哈希函數(shù)減少D.完美哈希函數(shù)可以完全消除沖突答案：D15.分布式系統(tǒng)中，CAP定理的三個(gè)特性不包括：A.一致性（Consistency）B.可用性（Availability）C.分區(qū)容錯(cuò)性（PartitionTolerance）D.可擴(kuò)展性（Scalability）答案：D二、填空題（每題2分，共20分）1.計(jì)算機(jī)中，浮點(diǎn)數(shù)的表示通常由符號(hào)位、階碼和尾數(shù)三部分組成。答案：符號(hào)位；階碼；尾數(shù)2.二叉樹(shù)的遍歷方式中，若前序遍歷序列為ABDCE，中序遍歷序列為DBAEC，則后序遍歷序列為DBECA（按順序填寫(xiě)，用空格分隔）。答案：DBECA3.操作系統(tǒng)的進(jìn)程調(diào)度算法中，時(shí)間片輪轉(zhuǎn)算法通過(guò)固定時(shí)間片分配CPU，適用于分時(shí)系統(tǒng)；優(yōu)先級(jí)調(diào)度算法則根據(jù)進(jìn)程優(yōu)先級(jí)決定執(zhí)行順序。答案：時(shí)間片輪轉(zhuǎn)；優(yōu)先級(jí)調(diào)度4.在TCP/IP模型中，傳輸層的兩個(gè)主要協(xié)議是TCP（面向連接）和UDP（無(wú)連接）。答案：TCP；UDP5.關(guān)系數(shù)據(jù)庫(kù)的完整性約束包括實(shí)體完整性（主鍵約束）、參照完整性（外鍵約束）和用戶定義的完整性。答案：實(shí)體完整性；參照完整性6.算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所需的額外存儲(chǔ)空間與問(wèn)題規(guī)模n的關(guān)系。答案：額外存儲(chǔ)空間7.圖的遍歷方法中，深度優(yōu)先搜索（DFS）通常使用?；蜻f歸實(shí)現(xiàn)，廣度優(yōu)先搜索（BFS）使用隊(duì)列實(shí)現(xiàn)。答案：深度優(yōu)先搜索（DFS）；廣度優(yōu)先搜索（BFS）8.虛擬內(nèi)存的置換算法中，最近最久未使用（LRU）算法選擇最近長(zhǎng)時(shí)間未訪問(wèn)的頁(yè)面置換，先進(jìn)先出（FIFO）算法選擇最早進(jìn)入內(nèi)存的頁(yè)面置換。答案：最近最久未使用（LRU）；先進(jìn)先出（FIFO）9.編譯過(guò)程中，中間代碼提供階段將語(yǔ)法分析的結(jié)果轉(zhuǎn)換為與機(jī)器無(wú)關(guān)的中間表示（如四元式）。答案：中間代碼提供10.區(qū)塊鏈的核心技術(shù)包括哈希函數(shù)、共識(shí)機(jī)制（如PoW、PoS）和Merkle樹(shù)結(jié)構(gòu)。答案：哈希函數(shù)；共識(shí)機(jī)制三、簡(jiǎn)答題（每題6分，共36分）1.簡(jiǎn)述操作系統(tǒng)中進(jìn)程與線程的區(qū)別。答案：進(jìn)程是資源分配的基本單位，線程是CPU調(diào)度的基本單位；一個(gè)進(jìn)程可包含多個(gè)線程，線程共享進(jìn)程的資源（如內(nèi)存、文件句柄），但擁有獨(dú)立的棧和寄存器上下文；進(jìn)程間切換開(kāi)銷大（需切換頁(yè)表、緩存等），線程間切換僅需保存/恢復(fù)少量寄存器，開(kāi)銷更??；進(jìn)程間通信（IPC）需通過(guò)管道、消息隊(duì)列等機(jī)制，線程間可直接共享內(nèi)存通信。2.解釋TCP三次握手的過(guò)程及目的。答案：三次握手用于建立可靠連接：（1）客戶端發(fā)送SYN=1，隨機(jī)序號(hào)x（SYN報(bào)文）；（2）服務(wù)器回復(fù)SYN=1，ACK=1，確認(rèn)號(hào)x+1，隨機(jī)序號(hào)y（SYN-ACK報(bào)文）；（3）客戶端發(fā)送ACK=1，確認(rèn)號(hào)y+1（ACK報(bào)文）。目的是同步雙方的初始序號(hào)（ISN），確認(rèn)雙方的發(fā)送和接收能力正常，避免歷史連接的重復(fù)初始化。3.說(shuō)明數(shù)據(jù)庫(kù)中事務(wù)的原子性（Atomicity）和持久性（Durability）的含義及實(shí)現(xiàn)方式。答案：原子性指事務(wù)的所有操作要么全部成功，要么全部回滾，不可部分執(zhí)行。實(shí)現(xiàn)依賴日志（如redo/undo日志），事務(wù)執(zhí)行前記錄操作，失敗時(shí)通過(guò)日志回滾。持久性指事務(wù)提交后，數(shù)據(jù)修改永久保存，即使系統(tǒng)崩潰也不丟失。實(shí)現(xiàn)依賴磁盤(pán)持久化（如寫(xiě)日志到磁盤(pán)后再提交，或使用RAID冗余存儲(chǔ)）。4.比較順序查找與二分查找的適用場(chǎng)景及時(shí)間復(fù)雜度。答案：順序查找適用于無(wú)序或小數(shù)據(jù)量的線性表，時(shí)間復(fù)雜度O(n)；二分查找要求數(shù)據(jù)有序（如升序），通過(guò)比較中間元素縮小查找范圍，時(shí)間復(fù)雜度O(logn)。順序查找對(duì)數(shù)據(jù)無(wú)要求但效率低，二分查找效率高但依賴有序性，適用于大數(shù)據(jù)量且需頻繁查找的場(chǎng)景（如數(shù)據(jù)庫(kù)索引）。5.簡(jiǎn)述計(jì)算機(jī)網(wǎng)絡(luò)中CSMA/CD（載波偵聽(tīng)多路訪問(wèn)/沖突檢測(cè)）的工作流程。答案：（1）節(jié)點(diǎn)發(fā)送數(shù)據(jù)前偵聽(tīng)信道，若空閑則發(fā)送；（2）發(fā)送過(guò)程中持續(xù)檢測(cè)沖突，若檢測(cè)到?jīng)_突則立即停止發(fā)送，并發(fā)送阻塞信號(hào)；（3）等待隨機(jī)退避時(shí)間（如二進(jìn)制指數(shù)退避算法）后，重新嘗試發(fā)送。該機(jī)制用于以太網(wǎng)，解決共享介質(zhì)下的多節(jié)點(diǎn)爭(zhēng)用問(wèn)題。6.解釋編譯原理中“詞法分析”與“語(yǔ)法分析”的區(qū)別與聯(lián)系。答案：詞法分析將源程序字符流轉(zhuǎn)換為詞法單元（Token），如關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符，處理詞法錯(cuò)誤（如非法字符）；語(yǔ)法分析根據(jù)語(yǔ)法規(guī)則（如上下文無(wú)關(guān)文法）將Token序列轉(zhuǎn)換為語(yǔ)法樹(shù)（AST），檢查語(yǔ)法錯(cuò)誤（如括號(hào)不匹配）。詞法分析是語(yǔ)法分析的基礎(chǔ)，語(yǔ)法分析依賴詞法分析提供的Token流，兩者共同完成對(duì)源程序結(jié)構(gòu)的初步驗(yàn)證。四、綜合題（共14分）題目1（6分）：已知一棵二叉樹(shù)的前序遍歷序列為ABCDE，中序遍歷序列為BADCE。（1）畫(huà)出該二叉樹(shù)的結(jié)構(gòu)；（2）寫(xiě)出其后序遍歷序列。答案：（1）二叉樹(shù)結(jié)構(gòu)：A/\BC/\DE（2）后序遍歷序列：BDECA題目2（8分）：設(shè)計(jì)一個(gè)簡(jiǎn)單的文件系統(tǒng)目錄結(jié)構(gòu)，要求包含以下內(nèi)容：-用戶“user1”的主目錄（/home/user1）；-主目錄下有“文檔”（docs）和“圖片”（pics）子目錄；-“文檔”目錄下有文件“report.txt”和子目錄“2024”；-“圖片”目錄下有文件“photo.jpg”；-給出從根目錄到“report.txt”的絕對(duì)路徑，以及從“pics”目錄到“report.txt”的相對(duì)路徑。答案：目錄結(jié)構(gòu)示例：/└