2025年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合(408)沖刺測(cè)試卷考試時(shí)間：______分鐘總分：______分姓名：______一、單項(xiàng)選擇題（每題2分，共40分）1.下列數(shù)據(jù)結(jié)構(gòu)中，適合表示稀疏矩陣的是（）。A.隊(duì)列B.棧C.線性表D.矩陣2.在一棵二叉樹(shù)中，若某節(jié)點(diǎn)的度為2，則該節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)是（）。A.0B.1C.2D.33.快速排序的平均時(shí)間復(fù)雜度是（）。A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)4.在下列尋址方式中，不屬于指令尋址方式的是（）。A.立即尋址B.直接尋址C.間接尋址D.相對(duì)尋址5.計(jì)算機(jī)系統(tǒng)中，Cache的作用是（）。A.提高主存的容量B.提高主存的讀寫速度C.提高輔存的讀寫速度D.提高CPU的運(yùn)算速度6.操作系統(tǒng)中，進(jìn)程調(diào)度算法的目的是（）。A.提高CPU的利用率B.提高內(nèi)存的利用率C.提高設(shè)備的利用率D.提高用戶的滿意度7.在下列進(jìn)程狀態(tài)轉(zhuǎn)換中，不可能發(fā)生的是（）。A.就緒態(tài)->運(yùn)行態(tài)B.運(yùn)行態(tài)->就緒態(tài)C.運(yùn)行態(tài)->等待態(tài)D.等待態(tài)->運(yùn)行態(tài)8.虛擬內(nèi)存技術(shù)可以（）。A.擴(kuò)大主存的物理容量B.提高主存的訪問(wèn)速度C.增加輔存的存儲(chǔ)容量D.提高輔存的訪問(wèn)速度9.文件系統(tǒng)中，文件控制塊FCB的主要作用是（）。A.存儲(chǔ)文件內(nèi)容B.描述文件屬性C.管理文件目錄D.控制文件訪問(wèn)10.在下列I/O方式中，不屬于程序查詢方式的是（）。A.等待I/O方式B.中斷方式C.直接存儲(chǔ)器訪問(wèn)方式D.DMA方式11.計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)是指（）。A.計(jì)算機(jī)網(wǎng)絡(luò)的硬件組成B.計(jì)算機(jī)網(wǎng)絡(luò)的軟件組成C.計(jì)算機(jī)網(wǎng)絡(luò)的層次結(jié)構(gòu)D.計(jì)算機(jī)網(wǎng)絡(luò)的功能組成12.以太網(wǎng)采用的總線型拓?fù)浣Y(jié)構(gòu)，其介質(zhì)訪問(wèn)控制方法通常采用（）。A.爭(zhēng)用協(xié)議B.輪轉(zhuǎn)協(xié)議C.令牌傳遞協(xié)議D.鏈路協(xié)議13.IP協(xié)議屬于（）。A.應(yīng)用層協(xié)議B.傳輸層協(xié)議C.網(wǎng)絡(luò)層協(xié)議D.數(shù)據(jù)鏈路層協(xié)議14.在TCP/IP協(xié)議簇中，負(fù)責(zé)路由選擇的是（）。A.TCP協(xié)議B.UDP協(xié)議C.IP協(xié)議D.ARP協(xié)議15.子網(wǎng)劃分的目的是（）。A.增加網(wǎng)絡(luò)的主機(jī)數(shù)量B.提高網(wǎng)絡(luò)的傳輸速率C.提高網(wǎng)絡(luò)的利用率D.提高網(wǎng)絡(luò)的安全性16.TCP協(xié)議提供（）服務(wù)。A.無(wú)連接的、可靠的傳輸B.無(wú)連接的、不可靠的傳輸C.有連接的、可靠的傳輸D.有連接的、不可靠的傳輸17.在下列網(wǎng)絡(luò)設(shè)備中，不屬于層設(shè)備的是（）。A.路由器B.交換機(jī)C.集線器D.網(wǎng)卡18.萬(wàn)維網(wǎng)(WWW)應(yīng)用層協(xié)議主要使用（）協(xié)議。A.FTPB.SMTPC.HTTPD.DNS19.將IP地址轉(zhuǎn)換為MAC地址的協(xié)議是（）。A.ARPB.RARPC.ICMPD.IGMP20.計(jì)算機(jī)網(wǎng)絡(luò)傳輸介質(zhì)中，傳輸速率最高的是（）。A.雙絞線B.同軸電纜C.光纖D.微波二、綜合題（每題10分，共60分）1.請(qǐng)簡(jiǎn)述棧和隊(duì)列的區(qū)別，并舉例說(shuō)明棧和隊(duì)列的應(yīng)用場(chǎng)景。2.請(qǐng)解釋什么是二叉搜索樹(shù)，并描述二叉搜索樹(shù)的插入和刪除操作。3.請(qǐng)簡(jiǎn)述中斷的概念，并說(shuō)明中斷處理的過(guò)程。4.請(qǐng)簡(jiǎn)述操作系統(tǒng)的內(nèi)存管理功能，并說(shuō)明虛擬內(nèi)存的概念及其實(shí)現(xiàn)方式。5.請(qǐng)簡(jiǎn)述計(jì)算機(jī)網(wǎng)絡(luò)的分層結(jié)構(gòu)，并說(shuō)明每一層的主要功能。6.請(qǐng)簡(jiǎn)述TCP協(xié)議的可靠傳輸機(jī)制，并說(shuō)明TCP協(xié)議如何實(shí)現(xiàn)流量控制和擁塞控制。試卷答案一、單項(xiàng)選擇題1.C解析：稀疏矩陣中零元素較多，使用稀疏矩陣可以有效地節(jié)省存儲(chǔ)空間，線性表（特別是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）適合表示稀疏矩陣。2.C解析：節(jié)點(diǎn)的度為2表示該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，根據(jù)二叉樹(shù)的定義，一個(gè)節(jié)點(diǎn)可以有0個(gè)、1個(gè)或2個(gè)子節(jié)點(diǎn)。3.B解析：快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，其基本思想是分治法，通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，然后再分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序。4.C解析：指令尋址方式包括立即尋址、直接尋址、間接尋址、寄存器尋址、相對(duì)尋址和基址尋址變址尋址等，而間接尋址不屬于指令尋址方式，而是屬于數(shù)據(jù)尋址方式。5.B解析：Cache是介于CPU和主存之間的高速存儲(chǔ)器，其作用是提高主存的讀寫速度，減輕CPU對(duì)主存的訪問(wèn)壓力。6.A解析：進(jìn)程調(diào)度算法的主要目的是提高CPU的利用率，通過(guò)合理的調(diào)度策略，使CPU始終處于忙碌狀態(tài)。7.D解析：進(jìn)程狀態(tài)轉(zhuǎn)換包括：就緒態(tài)->運(yùn)行態(tài)、運(yùn)行態(tài)->就緒態(tài)、運(yùn)行態(tài)->等待態(tài)、等待態(tài)->就緒態(tài)，等待態(tài)不可能直接轉(zhuǎn)換為運(yùn)行態(tài)，必須先變?yōu)榫途w態(tài)，然后才能被調(diào)度運(yùn)行。8.A解析：虛擬內(nèi)存技術(shù)可以將輔存的一部分空間作為主存的擴(kuò)展，從而擴(kuò)大主存的物理容量，使用戶可以運(yùn)行比實(shí)際主存容量更大的程序。9.B解析：文件控制塊FCB是描述文件屬性的數(shù)據(jù)結(jié)構(gòu)，它包含了文件的名字、大小、類型、創(chuàng)建時(shí)間、訪問(wèn)權(quán)限等信息。10.A解析：程序查詢方式是指CPU通過(guò)執(zhí)行程序指令來(lái)控制I/O操作，等待I/O方式屬于程序查詢方式，而中斷方式、直接存儲(chǔ)器訪問(wèn)方式、DMA方式均不屬于程序查詢方式。11.C解析：計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)是指計(jì)算機(jī)網(wǎng)絡(luò)的層次結(jié)構(gòu)，以及每一層所提供的功能和服務(wù)。12.A解析：以太網(wǎng)采用的總線型拓?fù)浣Y(jié)構(gòu)，其介質(zhì)訪問(wèn)控制方法通常采用爭(zhēng)用協(xié)議，即CSMA/CD協(xié)議。13.C解析：IP協(xié)議屬于網(wǎng)絡(luò)層協(xié)議，負(fù)責(zé)在網(wǎng)絡(luò)層提供數(shù)據(jù)包的傳輸服務(wù)。14.C解析：IP協(xié)議負(fù)責(zé)路由選擇，根據(jù)IP地址將數(shù)據(jù)包從源主機(jī)路由到目標(biāo)主機(jī)。15.A解析：子網(wǎng)劃分是將一個(gè)大的網(wǎng)絡(luò)劃分為多個(gè)小的子網(wǎng)絡(luò)，可以提高網(wǎng)絡(luò)的管理效率，增加網(wǎng)絡(luò)的主機(jī)數(shù)量。16.C解析：TCP協(xié)議提供有連接的、可靠的傳輸服務(wù)，它通過(guò)序列號(hào)、確認(rèn)應(yīng)答、超時(shí)重傳等機(jī)制保證數(shù)據(jù)傳輸?shù)目煽啃院晚樞蛐浴?7.C解析：集線器屬于物理層設(shè)備，而路由器、交換機(jī)、網(wǎng)卡均屬于數(shù)據(jù)鏈路層或網(wǎng)絡(luò)層設(shè)備。18.C解析：萬(wàn)維網(wǎng)(WWW)應(yīng)用層協(xié)議主要使用HTTP協(xié)議，用于瀏覽器和服務(wù)器之間的信息交互。19.A解析：ARP協(xié)議將IP地址轉(zhuǎn)換為MAC地址，用于在局域網(wǎng)內(nèi)進(jìn)行數(shù)據(jù)幀的傳輸。20.C解析：計(jì)算機(jī)網(wǎng)絡(luò)傳輸介質(zhì)中，光纖的傳輸速率最高，其帶寬可達(dá)Gbps級(jí)別。二、綜合題1.棧和隊(duì)列的區(qū)別：*棧是先進(jìn)后出的線性表，而隊(duì)列是先進(jìn)先出的線性表。*棧只允許在一端進(jìn)行插入和刪除操作，而隊(duì)列允許在兩端進(jìn)行插入和刪除操作。*棧通常用于解決括號(hào)匹配、表達(dá)式求值、函數(shù)調(diào)用等問(wèn)題，而隊(duì)列通常用于解決消息隊(duì)列、任務(wù)調(diào)度等問(wèn)題。棧和隊(duì)列的應(yīng)用場(chǎng)景：*棧：表達(dá)式求值、括號(hào)匹配、迷宮求解、函數(shù)調(diào)用棧等。*隊(duì)列：消息隊(duì)列、任務(wù)調(diào)度、打印隊(duì)列、廣度優(yōu)先搜索等。2.二叉搜索樹(shù)：*二叉搜索樹(shù)是一種特殊的二叉樹(shù)，其左子樹(shù)上所有節(jié)點(diǎn)的值均小于其根節(jié)點(diǎn)的值，其右子樹(shù)上所有節(jié)點(diǎn)的值均大于其根節(jié)點(diǎn)的值，且其左、右子樹(shù)也都是二叉搜索樹(shù)。二叉搜索樹(shù)的插入操作：*若二叉搜索樹(shù)為空，則新節(jié)點(diǎn)成為根節(jié)點(diǎn)。*若二叉搜索樹(shù)不為空，則將新節(jié)點(diǎn)與根節(jié)點(diǎn)進(jìn)行比較，若新節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，則插入到左子樹(shù)；若新節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值，則插入到右子樹(shù)。二叉搜索樹(shù)的刪除操作：*若要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則直接將其父節(jié)點(diǎn)中對(duì)應(yīng)的指針置為空。*若要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，則將其父節(jié)點(diǎn)中對(duì)應(yīng)的指針指向其子節(jié)點(diǎn)。*若要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則將其右子樹(shù)中的最小節(jié)點(diǎn)（或左子樹(shù)中的最大節(jié)點(diǎn)）替換要?jiǎng)h除的節(jié)點(diǎn)，然后刪除替換節(jié)點(diǎn)的原位置。3.中斷：*中斷是指計(jì)算機(jī)在執(zhí)行程序的過(guò)程中，出現(xiàn)某些意外事件，需要CPU暫停當(dāng)前正在執(zhí)行的程序，轉(zhuǎn)而去處理這些意外事件，處理完畢后再返回到原來(lái)被中斷的程序繼續(xù)執(zhí)行的過(guò)程。中斷處理過(guò)程：*中斷請(qǐng)求：當(dāng)出現(xiàn)中斷事件時(shí)，中斷源向CPU發(fā)出中斷請(qǐng)求。*中斷判優(yōu)：若CPU同時(shí)接收到多個(gè)中斷請(qǐng)求，則根據(jù)中斷優(yōu)先級(jí)進(jìn)行判斷，優(yōu)先處理優(yōu)先級(jí)高的中斷。*中斷響應(yīng)：CPU在當(dāng)前指令執(zhí)行完畢后，若中斷請(qǐng)求的優(yōu)先級(jí)高于當(dāng)前正在執(zhí)行的中斷，則響應(yīng)中斷請(qǐng)求。*中斷隱指令：CPU執(zhí)行中斷隱指令，保存當(dāng)前程序的狀態(tài)（如程序計(jì)數(shù)器、寄存器等），并轉(zhuǎn)到中斷服務(wù)程序的人口地址。*中斷服務(wù)程序：CPU執(zhí)行中斷服務(wù)程序，處理中斷事件。*中斷返回：中斷服務(wù)程序執(zhí)行完畢后，執(zhí)行中斷返回指令，恢復(fù)之前保存的程序狀態(tài)，繼續(xù)執(zhí)行被中斷的程序。4.操作系統(tǒng)的內(nèi)存管理功能：*內(nèi)存分配：為進(jìn)程分配內(nèi)存空間。*內(nèi)存保護(hù)：防止進(jìn)程訪問(wèn)非法內(nèi)存區(qū)域。*內(nèi)存共享：允許多個(gè)進(jìn)程共享同一塊內(nèi)存空間。*內(nèi)存交換：將暫時(shí)不使用的內(nèi)存內(nèi)容交換到輔存，以騰出更多的內(nèi)存空間。虛擬內(nèi)存：*虛擬內(nèi)存是一種內(nèi)存管理技術(shù)，它將輔存的一部分空間作為主存的擴(kuò)展，從而擴(kuò)大主存的邏輯容量，使用戶可以運(yùn)行比實(shí)際主存容量更大的程序。虛擬內(nèi)存的實(shí)現(xiàn)方式：*分頁(yè)：將主存和輔存都分成大小相等的頁(yè)，進(jìn)程的地址空間也分成大小相等的頁(yè)，通過(guò)頁(yè)表進(jìn)行地址映射。*分段：將進(jìn)程的地址空間分成多個(gè)段，每個(gè)段的大小可以不同，通過(guò)段表進(jìn)行地址映射。5.計(jì)算機(jī)網(wǎng)絡(luò)的分層結(jié)構(gòu)：*物理層：負(fù)責(zé)比特流的傳輸。*數(shù)據(jù)鏈路層：負(fù)責(zé)幀的傳輸。*網(wǎng)絡(luò)層：負(fù)責(zé)路由選擇和數(shù)據(jù)包傳輸。*傳輸層：負(fù)責(zé)端到端的可靠傳輸。*應(yīng)用層：提供用戶應(yīng)用程序接口。每一層的主要功能：*物理層：提供物理連接，傳輸比特流。*數(shù)據(jù)鏈路層：提供數(shù)據(jù)幀的傳輸，差錯(cuò)控制和介質(zhì)訪問(wèn)控制。*網(wǎng)絡(luò)層：提供路由選擇和數(shù)據(jù)包傳輸，實(shí)現(xiàn)網(wǎng)絡(luò)互連。*傳輸層：提供端到端的可靠傳輸，流量控制和擁塞控制。*應(yīng)用層：提供用戶應(yīng)用程序接口，例如電子郵件、萬(wàn)維網(wǎng)等。6.TCP協(xié)議的可靠傳輸機(jī)制：*序列號(hào)：TCP將發(fā)送的數(shù)據(jù)分成多個(gè)數(shù)據(jù)段，并為每個(gè)數(shù)據(jù)段分配一個(gè)序列號(hào)，接收方通過(guò)序列號(hào)可以檢測(cè)數(shù)據(jù)是否丟失