2025年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試模擬卷考試時間：______分鐘總分：______分姓名：______一、單項(xiàng)選擇題（每小題2分，共20分）1.下列數(shù)據(jù)結(jié)構(gòu)中，適合用于實(shí)現(xiàn)棧的是（）。A.順序表B.鏈表C.隊(duì)列D.二叉樹2.在深度為5的二叉樹中，最多有多少個結(jié)點(diǎn)？（）A.32B.31C.16D.153.若使用鏈地址法處理沖突的哈希表，哈希函數(shù)為H(key)，則查找成功時平均需要比較的鍵值次數(shù)（不考慮鏈表長度的影響）為（）。A.n/2B.1C.nD.1+n4.對于具有n個元素的線性表，在最壞情況下，使用快速排序算法進(jìn)行排序所需進(jìn)行的比較次數(shù)為（）。A.n(n-1)/2B.nlog2nC.n(n+1)/2D.n^25.計(jì)算機(jī)硬件能直接識別和執(zhí)行的指令代碼是（）。A.匯編語言指令B.高級語言指令C.機(jī)器語言指令D.自然語言指令6.在計(jì)算機(jī)存儲系統(tǒng)中，Cache的作用是（）。A.提高主存的存取速度B.增加主存的存儲容量C.降低主存的成本D.替代硬盤存儲7.采用分段存儲管理方式時，邏輯地址是（）。A.兩個段內(nèi)地址的簡單組合B.段號和段內(nèi)偏移量的組合C.頁號和頁內(nèi)偏移量的組合D.順序地址8.在操作系統(tǒng)中，臨界資源的特點(diǎn)是（）。A.只能由一個進(jìn)程使用B.可以被多個進(jìn)程同時使用C.只能由操作系統(tǒng)使用D.任何資源都可以是臨界資源9.在TCP/IP協(xié)議簇中，負(fù)責(zé)將IP地址轉(zhuǎn)換為物理地址的協(xié)議是（）。A.IP協(xié)議B.ICMP協(xié)議C.ARP協(xié)議D.TCP協(xié)議10.下列關(guān)于HTTP協(xié)議的說法中，錯誤的是（）。A.HTTP是一種無連接的協(xié)議B.HTTP是一種面向?qū)ο蟮膮f(xié)議C.HTTP協(xié)議使用TCP作為傳輸層協(xié)議D.HTTP協(xié)議支持靜態(tài)資源和動態(tài)資源二、填空題（每空2分，共20分）1.在樹形結(jié)構(gòu)中，一個結(jié)點(diǎn)擁有多少個子結(jié)點(diǎn)，就稱為該結(jié)點(diǎn)的______。2.冒泡排序算法的平均時間復(fù)雜度是______。3.在計(jì)算機(jī)系統(tǒng)中，指令和數(shù)據(jù)都以______的形式存儲在存儲器中。4.CPU的主要性能指標(biāo)之一是______，它表示CPU每秒能執(zhí)行的指令條數(shù)。5.操作系統(tǒng)中，用于實(shí)現(xiàn)進(jìn)程同步的信號量機(jī)制中，P操作對應(yīng)______操作。6.計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)中，OSI參考模型的七層自下而上依次為：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、______層、傳輸層、會話層、應(yīng)用層。7.在以太局域網(wǎng)中，采用______協(xié)議解決介質(zhì)訪問沖突問題。8.無連接的傳輸服務(wù)通常不如面向連接的傳輸服務(wù)可靠，主要原因是缺乏______機(jī)制。9.IP地址0屬于______類地址。10.DNS協(xié)議的主要功能是將域名解析為______。三、簡答題（每小題5分，共20分）1.簡述棧的LIFO（后進(jìn)先出）特性及其基本操作。2.簡述操作系統(tǒng)引入虛擬內(nèi)存的目的及其主要實(shí)現(xiàn)技術(shù)。3.簡述計(jì)算機(jī)系統(tǒng)中總線的基本功能。4.簡述TCP協(xié)議與UDP協(xié)議的主要區(qū)別。四、計(jì)算題（每小題10分，共20分）1.設(shè)有一個順序存儲的線性表（數(shù)據(jù)元素為整型，按升序排列），采用二分查找法查找元素45。請描述查找過程，并說明比較次數(shù)（假設(shè)元素初始排列如下：[10,20,30,35,45,55,65,75,85]）。2.假設(shè)某計(jì)算機(jī)的Cache采用直接映射方式，Cache容量為128KB，每個塊（Line）大小為32B。主存地址為32位。請計(jì)算主存地址中哪些位用于確定塊號，哪些位用于確定塊內(nèi)地址。五、綜合應(yīng)用題（每小題15分，共30分）1.設(shè)有三個進(jìn)程P0、P1、P2需要訪問共享資源R（初始資源數(shù)量為1）。若每個進(jìn)程都需要先獲取資源R，使用后再釋放。請?jiān)O(shè)計(jì)一個簡單的同步機(jī)制（可以使用信號量S，并給出P、V操作的偽代碼），保證這三個進(jìn)程在任意時刻最多只有一個進(jìn)程能訪問資源R，并簡要說明其工作原理。2.簡述TCP連接建立的三次握手過程，并說明為什么需要三次握手而不是兩次握手。---試卷答案一、單項(xiàng)選擇題1.B2.B3.A4.A5.C6.A7.B8.A9.C10.B二、填空題1.度2.O(n^2)3.二進(jìn)制4.主頻5.P6.應(yīng)用7.CSMA/CD8.差錯控制9.C10.IP地址三、簡答題1.棧是一種特殊的線性表，其插入和刪除操作都限定在表的一端進(jìn)行，稱為棧頂（Top），另一端稱為棧底（Bottom）。棧具有LIFO（后進(jìn)先出）特性?；静僮靼ǎ撼跏蓟瘲＃↖nitStack）、判斷?？眨⊿tackEmpty）、入棧（Push）、出棧（Pop）、獲取棧頂元素（GetTop）。2.引入虛擬內(nèi)存的主要目的是解決主存容量有限與程序所需空間可能超出主存容量之間的矛盾，以及提高內(nèi)存利用率和系統(tǒng)吞吐量。主要實(shí)現(xiàn)技術(shù)包括分段存儲管理、分頁存儲管理（特別是請求分頁、快表等）。3.總線是計(jì)算機(jī)各功能部件之間傳送信息的公共通路。其基本功能包括：數(shù)據(jù)傳輸、地址傳輸、控制傳輸。4.TCP協(xié)議是面向連接的、可靠的、基于字節(jié)流的傳輸層協(xié)議。UDP協(xié)議是無連接的、不可靠的、面向數(shù)據(jù)報的傳輸層協(xié)議。主要區(qū)別在于：連接管理（TCP需要建立和終止連接，UDP無需）、可靠性（TCP提供可靠傳輸，UDP不保證）、傳輸模式（TCP面向字節(jié)流，UDP面向數(shù)據(jù)報）、傳輸效率（TCP由于需要保證可靠性，開銷較大，效率相對較低；UDP開銷小，效率較高）。四、計(jì)算題1.查找過程：-初始狀態(tài)：low=0,high=8,mid=(0+8)/2=4。比較元素[45]與中間元素[55]。-第一次比較：low=0,high=3,mid=(0+3)/2=1。比較元素[45]與中間元素[20]。-第二次比較：low=2,high=3,mid=(2+3)/2=2。比較元素[45]與中間元素[30]。-第三次比較：low=3,high=3,mid=(3+3)/2=3。比較元素[45]與中間元素[35]。-找到，結(jié)束。比較次數(shù)為3次。2.計(jì)算過程：-總線地址位數(shù)：32位。-Cache容量：128KB=128*1024*8bits=2^17*8bits=2^19bytes=2^17B。-塊大小：32B=2^5B。-塊數(shù)：Cache容量/塊大小=2^17B/2^5B=2^12塊=4096塊。塊號需要12位。-主存地址結(jié)構(gòu)：[高位地址|塊號|塊內(nèi)地址]。-塊號位數(shù)：12位。-塊內(nèi)地址位數(shù)：塊大小/字節(jié)大小=32B/1B=32位。-高位地址位數(shù)：總地址位-塊號位-塊內(nèi)地址位=32-12-32=-12位。這里計(jì)算有誤，高位地址=總地址位-塊號位=32-12=20位。-正確的主存地址結(jié)構(gòu)應(yīng)為：[高位地址(20位)|塊號(12位)|塊內(nèi)地址(5位)]。-結(jié)論：主存地址中，前20位用于確定塊號，后5位用于確定塊內(nèi)地址。五、綜合應(yīng)用題1.同步機(jī)制設(shè)計(jì)：```定義信號量S=1;P(S);//訪問共享資源R的臨界區(qū)代碼V(S);```工作原理：初始時，信號量S的值為1。每個進(jìn)程在進(jìn)入臨界區(qū)前必須執(zhí)行P(S)操作，這會將S的值減1。如果S的值變?yōu)?，則表示已有進(jìn)程在臨界區(qū)，當(dāng)前進(jìn)程將被阻塞等待。當(dāng)?shù)谝粋€進(jìn)程完成臨界區(qū)操作并執(zhí)行V(S)操作時，S的值變?yōu)?，阻塞的下一個進(jìn)程可以繼續(xù)執(zhí)行P(S)并進(jìn)入臨界區(qū)。由于S的值在任何時刻最多為1，因此最多只有一個進(jìn)程能進(jìn)入臨界區(qū)，從而實(shí)現(xiàn)了互斥。2.TCP三次握手過程：1.第一次握手：客戶端（Initiator）向服務(wù)器端（Server）發(fā)送一個SYN=1的SYN包（SYN=seq=x），請求建立連接?？蛻舳诉M(jìn)入SYN_SENT狀態(tài)。2.第二次握手：服務(wù)器端收到SYN包后，若同意連接，向客戶端發(fā)送一個SYN=1,ACK=1的SYN-ACK包（SYN=seq=y,ACK=ack=x+1），表示確認(rèn)客戶端的請求，并進(jìn)入SYN_RCVD狀態(tài)。3.第三次握手：客戶端收到SYN-ACK包后，向服務(wù)器端發(fā)送一個ACK=1的ACK包（ACK=ack=y+1），表示確認(rèn)服務(wù)器的響應(yīng)，客戶端進(jìn)入ESTABLISHED狀態(tài)。服務(wù)器端收到ACK包后，進(jìn)入ESTABLISHED狀態(tài)，連接建立成功。為什么需要三次握手而非兩次握手：-三次握手可以確保服務(wù)器端確認(rèn)收到客戶端的連接請求，并且客戶端也確認(rèn)收到了服務(wù)器的同意連接的響應(yīng)。這避免了因網(wǎng)絡(luò)延遲或丟包