2025年計(jì)算機(jī)專(zhuān)業(yè)課考試試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.以下關(guān)于平衡二叉樹(shù)（AVL樹(shù)）的描述中，錯(cuò)誤的是（）。A.任意節(jié)點(diǎn)的左右子樹(shù)高度差絕對(duì)值不超過(guò)1B.插入操作可能引發(fā)多次旋轉(zhuǎn)調(diào)整C.查找時(shí)間復(fù)雜度為O(logn)D.刪除操作不會(huì)改變樹(shù)的平衡因子答案：D解析：刪除操作可能導(dǎo)致多個(gè)祖先節(jié)點(diǎn)的平衡因子變化，需要從刪除位置向上回溯調(diào)整，因此可能改變平衡因子。2.某進(jìn)程在時(shí)間片輪轉(zhuǎn)調(diào)度中被分配了5ms的時(shí)間片，當(dāng)它執(zhí)行3ms后發(fā)生I/O請(qǐng)求并進(jìn)入阻塞態(tài)，此時(shí)CPU的調(diào)度行為是（）。A.立即剝奪該進(jìn)程CPU，調(diào)度下一個(gè)進(jìn)程B.等待該進(jìn)程I/O完成后繼續(xù)執(zhí)行剩余2msC.將該進(jìn)程時(shí)間片重置為5ms，重新進(jìn)入就緒隊(duì)列D.該進(jìn)程繼續(xù)占用CPU直到時(shí)間片耗盡答案：A解析：時(shí)間片輪轉(zhuǎn)調(diào)度中，進(jìn)程因I/O阻塞時(shí)會(huì)主動(dòng)釋放CPU，調(diào)度程序立即選擇下一個(gè)就緒進(jìn)程執(zhí)行。3.在TCP協(xié)議中，若發(fā)送方窗口大小為1000字節(jié)，接收方通告窗口大小為800字節(jié)，此時(shí)發(fā)送方實(shí)際可發(fā)送的最大數(shù)據(jù)量是（）。A.1000字節(jié)B.800字節(jié)C.1800字節(jié)D.由擁塞窗口決定答案：B解析：TCP發(fā)送窗口取接收方通告窗口和擁塞窗口的較小值，本題未提及擁塞窗口，默認(rèn)取接收方通告窗口。4.關(guān)系模式R(A,B,C,D)，函數(shù)依賴(lài)為A→B,B→C,C→D，則R的最高范式是（）。A.1NFB.2NFC.3NFD.BCNF答案：B解析：候選鍵為A，非主屬性B、C、D均部分依賴(lài)于A（A→B→C→D存在傳遞依賴(lài)），因此不滿足3NF，但滿足2NF（無(wú)部分依賴(lài)）。5.以下關(guān)于虛擬內(nèi)存的描述中，正確的是（）。A.虛擬內(nèi)存的大小僅受限于物理內(nèi)存容量B.頁(yè)面置換算法的目標(biāo)是減少缺頁(yè)中斷次數(shù)C.抖動(dòng)現(xiàn)象是由于進(jìn)程訪問(wèn)的頁(yè)面均在內(nèi)存中引起的D.段頁(yè)式管理中，段表和頁(yè)表都只需存儲(chǔ)在內(nèi)存中答案：B解析：虛擬內(nèi)存大小受限于地址空間和外存容量（A錯(cuò)誤）；抖動(dòng)是頻繁缺頁(yè)導(dǎo)致（C錯(cuò)誤）；段表和頁(yè)表可部分存于外存（D錯(cuò)誤）。6.若一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)和m條邊，其鄰接矩陣存儲(chǔ)的空間復(fù)雜度為（）。A.O(n)B.O(m)C.O(n2)D.O(n+m)答案：C解析：鄰接矩陣是n×n的二維數(shù)組，空間復(fù)雜度為O(n2)。7.某計(jì)算機(jī)的主存地址為32位，按字節(jié)編址，若使用4M×8位的DRAM芯片構(gòu)成64MB的主存，需要的芯片數(shù)量是（）。A.8片B.16片C.32片D.64片答案：B解析：每片芯片容量為4M×8位=4MB（8位=1字節(jié)），64MB/4MB=16片。8.以下關(guān)于廣度優(yōu)先搜索（BFS）的描述中，錯(cuò)誤的是（）。A.可以用于求解無(wú)權(quán)圖的最短路徑問(wèn)題B.需要使用隊(duì)列作為輔助數(shù)據(jù)結(jié)構(gòu)C.遍歷順序與遞歸深度優(yōu)先搜索（DFS）相同D.時(shí)間復(fù)雜度為O(V+E)（V為頂點(diǎn)數(shù)，E為邊數(shù)）答案：C解析：BFS按層遍歷，DFS按深度優(yōu)先，遍歷順序不同。9.在數(shù)據(jù)庫(kù)事務(wù)中，“一個(gè)事務(wù)的執(zhí)行不被其他事務(wù)干擾”體現(xiàn)了事務(wù)的（）特性。A.原子性（Atomicity）B.一致性（Consistency）C.隔離性（Isolation）D.持久性（Durability）答案：C解析：隔離性要求事務(wù)間互不干擾，保證各自的執(zhí)行環(huán)境。10.某指令系統(tǒng)采用定長(zhǎng)指令字（32位），操作碼占8位，地址碼字段設(shè)計(jì)為3個(gè)16位的地址碼，這種設(shè)計(jì)會(huì)導(dǎo)致（）。A.指令長(zhǎng)度超過(guò)32位B.地址碼總長(zhǎng)度超過(guò)24位C.無(wú)法表示三地址指令D.操作碼空間浪費(fèi)答案：D解析：3個(gè)16位地址碼總長(zhǎng)度為48位，超過(guò)32位，因此實(shí)際需縮短地址碼長(zhǎng)度，導(dǎo)致操作碼占8位時(shí)地址碼空間不足，需采用擴(kuò)展操作碼技術(shù)，原設(shè)計(jì)會(huì)浪費(fèi)操作碼空間。二、填空題（每空2分，共20分）1.數(shù)據(jù)結(jié)構(gòu)中，棧的基本操作包括入棧、出棧、取棧頂元素和__________（判斷棧是否為空）。答案：判空2.操作系統(tǒng)中，進(jìn)程的三種基本狀態(tài)是運(yùn)行態(tài)、就緒態(tài)和__________。答案：阻塞態(tài)（或等待態(tài)）3.TCP協(xié)議中，三次握手的第三個(gè)報(bào)文是__________（填寫(xiě)標(biāo)志位組合）。答案：ACK4.關(guān)系數(shù)據(jù)庫(kù)中，若兩個(gè)關(guān)系R和S的笛卡爾積有m×n個(gè)元組，則R有m個(gè)元組，S有__________個(gè)元組。答案：n5.計(jì)算機(jī)組成原理中，CPU的主要組成部分包括運(yùn)算器、控制器和__________。答案：寄存器組6.圖的遍歷中，深度優(yōu)先搜索的非遞歸實(shí)現(xiàn)通常使用__________作為輔助數(shù)據(jù)結(jié)構(gòu)。答案：棧7.虛擬內(nèi)存管理中，常用的頁(yè)面置換算法有最佳置換算法（OPT）、先進(jìn)先出算法（FIFO）和__________（寫(xiě)出一種）。答案：最近最久未使用算法（LRU）8.數(shù)據(jù)庫(kù)設(shè)計(jì)的四個(gè)階段是需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和__________。答案：物理設(shè)計(jì)9.指令周期是指CPU從__________到執(zhí)行完該指令所需的全部時(shí)間。答案：取出一條指令10.在無(wú)向圖中，若存在一個(gè)頂點(diǎn)v，使得刪除v后圖的連通分量數(shù)目增加，則v稱(chēng)為_(kāi)_________。答案：關(guān)節(jié)點(diǎn)（或割點(diǎn)）三、簡(jiǎn)答題（每題8分，共40分）1.簡(jiǎn)述快速排序的基本思想，并說(shuō)明其平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度的區(qū)別及原因。答案：快速排序的基本思想是通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分小，然后分別對(duì)這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。平均時(shí)間復(fù)雜度為O(nlogn)，此時(shí)每次劃分能將序列大致均分，遞歸深度為logn，每層處理n個(gè)元素。最壞時(shí)間復(fù)雜度為O(n2)，當(dāng)序列已經(jīng)有序（正序或逆序）時(shí)，每次劃分僅減少一個(gè)元素（基準(zhǔn)元素為最值），遞歸深度為n，每層處理n、n-1、…、1個(gè)元素，總時(shí)間為n(n+1)/2≈O(n2)。2.說(shuō)明操作系統(tǒng)中進(jìn)程與線程的區(qū)別（至少列出4點(diǎn)）。答案：（1）資源分配：進(jìn)程是資源分配的基本單位，線程是CPU調(diào)度的基本單位；（2）獨(dú)立性：進(jìn)程間資源獨(dú)立（除共享內(nèi)存等特殊情況），同一進(jìn)程內(nèi)的線程共享進(jìn)程資源；（3）并發(fā)性：進(jìn)程間并發(fā)需切換上下文，開(kāi)銷(xiāo)大；線程間并發(fā)切換僅需切換線程上下文，開(kāi)銷(xiāo)小；（4）創(chuàng)建/銷(xiāo)毀開(kāi)銷(xiāo)：進(jìn)程創(chuàng)建需分配內(nèi)存、文件等資源，開(kāi)銷(xiāo)大；線程創(chuàng)建僅需分配少量寄存器和棧空間，開(kāi)銷(xiāo)小；（5）地址空間：進(jìn)程擁有獨(dú)立的地址空間，線程共享所屬進(jìn)程的地址空間。3.描述TCP協(xié)議中擁塞控制的四個(gè)階段及其核心機(jī)制。答案：TCP擁塞控制分為四個(gè)階段：（1）慢開(kāi)始（SlowStart）：初始時(shí)擁塞窗口（cwnd）從1MSS（最大報(bào)文段長(zhǎng)度）開(kāi)始，每經(jīng)過(guò)一個(gè)RTT（往返時(shí)間），cwnd翻倍，直到達(dá)到慢開(kāi)始門(mén)限（ssthresh）；（2）擁塞避免（CongestionAvoidance）：當(dāng)cwnd≥ssthresh時(shí)，進(jìn)入擁塞避免階段，每經(jīng)過(guò)一個(gè)RTT，cwnd增加1MSS，線性增長(zhǎng)；（3）快速重傳（FastRetransmit）：當(dāng)發(fā)送方收到3個(gè)重復(fù)ACK時(shí)，認(rèn)為發(fā)生輕度擁塞，立即重傳丟失的報(bào)文段，無(wú)需等待超時(shí)；（4）快速恢復(fù)（FastRecovery）：快速重傳后，將ssthresh設(shè)為當(dāng)前cwnd的一半，cwnd設(shè)為ssthresh+3MSS（3個(gè)重復(fù)ACK表明有3個(gè)報(bào)文段已到達(dá)接收方），然后進(jìn)入擁塞避免階段。4.解釋數(shù)據(jù)庫(kù)中事務(wù)的ACID特性，并說(shuō)明日志（Log）在保證ACID中的作用。答案：ACID特性：-原子性（Atomicity）：事務(wù)的所有操作要么全部完成，要么全部不完成；-一致性（Consistency）：事務(wù)執(zhí)行前后數(shù)據(jù)庫(kù)處于一致?tīng)顟B(tài)；-隔離性（Isolation）：事務(wù)間互不干擾，執(zhí)行結(jié)果與串行執(zhí)行相同；-持久性（Durability）：事務(wù)提交后，其修改永久保存在數(shù)據(jù)庫(kù)中。日志的作用：-原子性：通過(guò)日志記錄事務(wù)的所有操作，若事務(wù)失敗，利用日志回滾（Undo）未完成的操作；-持久性：事務(wù)提交前將日志寫(xiě)入磁盤(pán)（先寫(xiě)日志后寫(xiě)數(shù)據(jù)庫(kù)），確保即使系統(tǒng)崩潰，可通過(guò)日志重做（Redo）已提交但未寫(xiě)入數(shù)據(jù)庫(kù)的操作；-隔離性：通過(guò)日志配合鎖機(jī)制或時(shí)間戳，記錄事務(wù)對(duì)數(shù)據(jù)的修改，確保其他事務(wù)不會(huì)看到未提交的中間狀態(tài)。5.說(shuō)明計(jì)算機(jī)中Cache（高速緩存）的作用，并解釋直接映射、全相聯(lián)映射和組相聯(lián)映射的區(qū)別。答案：Cache的作用是解決CPU與主存速度不匹配的問(wèn)題，利用局部性原理，將主存中近期頻繁訪問(wèn)的內(nèi)容復(fù)制到高速的Cache中，減少CPU訪問(wèn)主存的時(shí)間。三種映射方式的區(qū)別：（1）直接映射：主存塊只能映射到Cache的一個(gè)特定位置（主存塊號(hào)modCache塊數(shù)），實(shí)現(xiàn)簡(jiǎn)單但沖突率高（不同主存塊映射到同一Cache位置時(shí)需替換）；（2）全相聯(lián)映射：主存塊可映射到Cache的任意位置，沖突率低但需要全比較電路（查找時(shí)需比較所有Cache塊的標(biāo)記），實(shí)現(xiàn)復(fù)雜；（3）組相聯(lián)映射：將Cache分為若干組，每組包含k個(gè)塊，主存塊映射到特定組（主存塊號(hào)mod組數(shù)），組內(nèi)全相聯(lián)。結(jié)合了直接映射的簡(jiǎn)單性和全相聯(lián)的低沖突率，k為組的大?。ㄈ?路組相聯(lián)、4路組相聯(lián)）。四、算法設(shè)計(jì)題（每題10分，共20分）1.設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表是否為回文鏈表（即正讀和反讀相同）。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)（允許修改原鏈表）。答案：算法步驟：（1）使用快慢指針?lè)ㄕ业芥湵淼闹虚g節(jié)點(diǎn)：快指針每次走2步，慢指針每次走1步，快指針到達(dá)末尾時(shí)，慢指針指向中間（奇數(shù)個(gè)節(jié)點(diǎn)）或前半部分末尾（偶數(shù)個(gè)節(jié)點(diǎn)）；（2）反轉(zhuǎn)鏈表的后半部分：以慢指針的下一個(gè)節(jié)點(diǎn)為起點(diǎn)，反轉(zhuǎn)后半部分鏈表；（3）比較前半部分和反轉(zhuǎn)后的后半部分鏈表：逐一比較節(jié)點(diǎn)值，若全部相同則為回文；（4）恢復(fù)原鏈表（可選，根據(jù)題目要求是否保留原結(jié)構(gòu)）。代碼實(shí)現(xiàn)（偽代碼）：```functionisPalindrome(head):ifhead==nullorhead.next==null:returntrue找中間節(jié)點(diǎn)slow=headfast=headwhilefast.next!=nullandfast.next.next!=null:slow=slow.nextfast=fast.next.next反轉(zhuǎn)后半部分secondHalf=reverseList(slow.next)比較p1=headp2=secondHalfwhilep2!=null:ifp1.val!=p2.val:returnfalsep1=p1.nextp2=p2.nextreturntruefunctionreverseList(head):prev=nullcurr=headwhilecurr!=null:next=curr.nextcurr.next=prevprev=currcurr=nextreturnprev```2.給定一個(gè)整數(shù)數(shù)組nums和一個(gè)目標(biāo)值target，設(shè)計(jì)一個(gè)算法找出所有滿足a+b+c=target的三元組（a,b,c），要求不包含重復(fù)的三元組。答案：算法思路（雙指針?lè)ǎ海?）排序數(shù)組：先對(duì)nums進(jìn)行排序，便于去重和后續(xù)雙指針操作；（2）遍歷固定第一個(gè)數(shù)a：從i=0開(kāi)始，若nums[i]>target（當(dāng)target為正時(shí)）可提前終止（因數(shù)組已排序，后續(xù)數(shù)更大）；（3）去重第一個(gè)數(shù)：若nums[i]==nums[i-1]（i>0），跳過(guò)以避免重復(fù)三元組；（4）雙指針尋找b和c：設(shè)左指針left=i+1，右指針right=len(nums)-1，計(jì)算sum=nums[i]+nums[left]+nums[right]；（5）根據(jù)sum與target的關(guān)系調(diào)整指針：-若sum==target：記錄三元組，然后移動(dòng)左指針（跳過(guò)重復(fù)值）和右指針（跳過(guò)重復(fù)值）；-若sum<target：左指針右移（增大sum）；-若sum>target：右指針左移（減小sum）。代碼實(shí)現(xiàn)（偽代碼）：```functionthreeSum(nums,target):sort(nums)result=[]n=len(nums)forifrom0ton-3:ifi>0andnums[i]==nums[i-1]:去重acontinuea=nums[i]ifa>targetandtarget>0:提前終止（可選優(yōu)化）breakleft=i+1right=n-1whileleft<right:b=nums[left]c=nums[right]sum=a+b+cifsum==target:result.append([a,b,c])去重bwhileleft<rightandnums[left]==nums[left+1]:left+=1去重cwhileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifsum<target:left+=1else:right-=1returnresult```五、綜合應(yīng)用題（每題10分，共20分）1.某操作系統(tǒng)采用可變分區(qū)存儲(chǔ)管理，內(nèi)存初始狀態(tài)為0~1023KB空閑?，F(xiàn)有以下進(jìn)程請(qǐng)求分配內(nèi)存：-進(jìn)程A：200KB-進(jìn)程B：300KB-進(jìn)程C：150KB-進(jìn)程D：400KB（1）若采用首次適應(yīng)算法（FirstFit），畫(huà)出分配后的內(nèi)存布局（標(biāo)注分區(qū)起始地址、大小及狀態(tài)）；（2）若進(jìn)程B和進(jìn)程C先后釋放內(nèi)存，采用伙伴系統(tǒng)（BuddySystem）管理時(shí)，釋放后的空閑分區(qū)如何合并？答案：（1）首次適應(yīng)算法分配過(guò)程：初始空閑分區(qū)：0~1023KB（1024KB）。-分配進(jìn)程A（200KB）：從0開(kāi)始分配，剩余空閑分區(qū)為200~1023KB（824KB）；-分配進(jìn)程B（300KB）：從200開(kāi)始分配，剩余空閑分區(qū)為500~1023KB（524KB）；-分配進(jìn)程C（150KB）：從500開(kāi)始分配，剩余空閑分區(qū)為650~1023KB（374KB）；-分配進(jìn)程D（400KB）：剩余空閑分區(qū)374KB<400KB，無(wú)法分配（需等待或換出）。最終內(nèi)存布局（地址單位：KB）：0~199：進(jìn)程A（200KB，已分配）200~499：進(jìn)程B（300KB，已分配）500~649：進(jìn)程C（150KB，已分配）650~1023：空閑（374KB）（2）伙伴系統(tǒng)合并過(guò)程（假設(shè)內(nèi)存總大小為1024KB=2^10）：-進(jìn)程B釋放300KB：伙伴系統(tǒng)要求分區(qū)大小為2的冪次，進(jìn)程B實(shí)際分配的分區(qū)大小為512KB（2^9，因300KB≤512KB且512KB是≥300KB的最小2的冪）；原進(jìn)程B的分區(qū)起始地址為200KB，512KB分區(qū)的起始地址需對(duì)齊到512KB邊界（200KB不在0、512、1024…，矛盾，說(shuō)明首次適應(yīng)分配的分區(qū)可能不滿足伙伴系統(tǒng)的對(duì)齊要求。因此需重新假設(shè)伙伴系統(tǒng)下的分配：伙伴系統(tǒng)中，進(jìn)程B請(qǐng)求300KB，分配512KB（2^9），起始地址為0~511KB（假設(shè)首次分配）；但原題中首次適應(yīng)的分配與伙伴系統(tǒng)的分配策略不同，需明確伙伴系統(tǒng)下的分配：正確步驟應(yīng)為：初始空閑塊為1024KB（2^10）。-進(jìn)程A請(qǐng)求200KB，分配256KB（2^8），剩余空閑塊為1024-256=768KB（分為256KB和512KB？不，伙伴系統(tǒng)分配時(shí)拆分大的塊。正確拆分：1024KB拆分為512KB和512KB，其中一個(gè)512KB拆分為256KB和256KB，分配256KB給A（起始地址0~255KB）；-進(jìn)程B請(qǐng)求300KB，分配512KB（2^9），從剩余的512KB塊分配（起始地址256~767KB）；-進(jìn)程C請(qǐng)求150KB，分配256KB（2^8），從剩余的256KB塊（768~1023KB）分配（起始地址768~1023KB中的前256KB，即768~1023KB被拆分為256KB和256KB，分配256KB給C）；當(dāng)進(jìn)程B（512KB，地址256~767KB）和進(jìn)程C（256KB，地址768~1023KB中的768~1023？不，正確地址應(yīng)為768~1023KB是512KB塊，拆分為256KB和256KB，假設(shè)C分配的是768~1023KB中的768~1023KB？可能更簡(jiǎn)單的方式是：釋放進(jìn)程B（512KB，地址256~767KB）和進(jìn)程C（256KB，地址768~1023KB中的768~1023KB？實(shí)際伙伴系統(tǒng)中，相鄰且