2025年國企計算機類筆試題及答案一、計算機基礎與理論（共30分）1.計算機組成原理（10分）（1）某32位計算機的主存地址空間為4GB，按字節(jié)編址。若采用單字寬（32位）的DRAM芯片構成主存，且該芯片的存儲容量為512M×8位。①計算主存需要的DRAM芯片數(shù)量。②若主存地址總線中，用于片選的地址線有4根，說明該主存的組織方式（是否采用多體交叉或低位交叉等）。（2）已知某8位機器中，X的補碼為10110100，Y的原碼為01001010，計算X-Y的補碼結果（要求寫出計算過程）。2.編程語言基礎（10分）（1）C++中，以下代碼的輸出結果是什么？并解釋虛函數(shù)與純虛函數(shù)的區(qū)別。```cppinclude<iostream>usingnamespacestd;classBase{public:virtualvoidfunc(){cout<<"Base::func"<<endl;}};classDerived:publicBase{public:voidfunc(){cout<<"Derived::func"<<endl;}};intmain(){Basep=newDerived();p->func();deletep;return0;}```（2）Python中，執(zhí)行以下代碼后，a、b、c的值分別是多少？并說明Python中列表切片`list[start:end:step]`的規(guī)則（當step為負數(shù)時的特殊處理）。```pythona=[1,2,3,4,5]b=a[1:-1:2]c=a[::-1]```3.離散數(shù)學（10分）（1）用命題邏輯符號化以下語句：“如果明天下雨或刮大風，那么運動會推遲舉行，除非組委會提前通知取消”。（要求定義命題變元）（2）化簡邏輯表達式：(P∧Q)∨(?P∧R)∨(Q∧R)，要求用邏輯等價式推導并給出最簡與或式。二、算法與數(shù)據(jù)結構（共30分）1.鏈表操作（10分）給定一個單鏈表的頭節(jié)點`head`，其中每個節(jié)點包含一個整數(shù)`val`。要求實現(xiàn)一個函數(shù)，將鏈表中所有值為奇數(shù)的節(jié)點移動到偶數(shù)節(jié)點的前面，且奇數(shù)節(jié)點和偶數(shù)節(jié)點各自的相對順序保持不變。例如，輸入鏈表1→3→2→5→4，輸出應為1→3→5→2→4。（要求：時間復雜度O(n)，空間復雜度O(1)，用C++或Python實現(xiàn)）2.樹與圖（10分）（1）已知一棵二叉樹的前序遍歷序列為ABDECF，中序遍歷序列為DBEAFC。畫出該二叉樹的結構，并寫出后序遍歷序列。（2）使用Dijkstra算法計算圖中節(jié)點1到其他所有節(jié)點的最短路徑（權值均為非負）。圖的鄰接表表示如下（節(jié)點編號1-5）：1:{2:3,3:5}2:{1:3,4:6}3:{1:5,4:2,5:7}4:{2:6,3:2,5:1}5:{3:7,4:1}3.動態(tài)規(guī)劃（10分）給定一個長度為n的整數(shù)數(shù)組`nums`，找出最長的嚴格遞增子序列（子序列元素在原數(shù)組中順序保持不變，但不一定連續(xù)）。例如，輸入[10,9,2,5,3,7,101,18]，輸出長度為4（如2,3,7,101）。要求用動態(tài)規(guī)劃方法實現(xiàn)，時間復雜度O(n2)，并給出狀態(tài)轉移方程及具體推導過程。三、操作系統(tǒng)（共20分）1.進程與線程（10分）（1）有4個進程P1-P4，到達時間與執(zhí)行時間如下表所示（時間單位：ms）：|進程|到達時間|執(zhí)行時間|||-|-||P1|0|8||P2|1|4||P3|2|9||P4|3|5|分別計算采用先來先服務（FCFS）和短作業(yè)優(yōu)先（SJF，非搶占式）調度算法時的平均周轉時間（周轉時間=完成時間-到達時間）。2.內存管理（10分）（1）某系統(tǒng)采用頁式存儲管理，頁大小為4KB，邏輯地址空間為32位。某進程的頁表如下（頁號從0開始）：|頁號|物理塊號|有效位|||-|--||0|5|1||1|-|0||2|3|1||3|7|1|①邏輯地址0x201F（十六進制）對應的物理地址是多少？（要求寫出轉換步驟）②若訪問邏輯地址0x1000時發(fā)生缺頁，操作系統(tǒng)需要完成哪些操作？（從頁表查找、缺頁中斷處理、頁面置換（若需要）、TLB更新等方面描述）四、數(shù)據(jù)庫系統(tǒng)（共20分）1.SQL編程（10分）某公司數(shù)據(jù)庫有以下表結構：-`員工表(員工ID,姓名,部門ID,入職時間)`-`部門表(部門ID,部門名稱,負責人ID)`（負責人ID是員工ID的外鍵）-`項目表(項目ID,項目名稱,預算,起始時間)`-`參與表(員工ID,項目ID,角色)`（多對多關系，角色如“開發(fā)”“測試”）根據(jù)需求編寫SQL語句：（1）查詢2023年1月1日之后入職，且所在部門負責人與自己為同一人的員工姓名、部門名稱。（2）統(tǒng)計每個部門參與項目數(shù)量超過3個的員工人數(shù)（結果包括部門名稱、人數(shù)）。2.數(shù)據(jù)庫設計（10分）（1）某關系模式R(課程編號,課程名稱,教師編號,教師姓名,學生編號,學生姓名,成績)，其函數(shù)依賴如下：-課程編號→課程名稱-教師編號→教師姓名-(課程編號,學生編號)→成績-學生編號→學生姓名判斷R屬于第幾范式？若不屬于3NF，將其分解為3NF模式集（要求分解具有無損連接性和函數(shù)依賴保持性）。五、計算機網絡（共20分）1.TCP/IP協(xié)議（10分）（1）簡述TCP三次握手的過程，并說明第二次握手時服務器發(fā)送的TCP報文中SYN、ACK標志位的取值（0或1）及序列號（seq）、確認號（ack）的計算方式（假設客戶端初始序列號為x）。（2）某主機的IP地址為00/26，默認網關為5。分析該主機能否直接與IP地址為29的主機通信？并說明理由（要求計算子網地址）。2.應用層協(xié)議（10分）（1）HTTP/1.1中，GET和POST請求的主要區(qū)別有哪些？列舉至少3點。（2）某網站采用Cookie實現(xiàn)用戶會話跟蹤，當用戶首次訪問時，服務器返回的響應頭如下：`Set-Cookie:sessionid=abc123;Path=/;Max-Age=3600;HttpOnly`解釋各字段的含義，并說明`HttpOnly`屬性的作用。答案與解析一、計算機基礎與理論1.計算機組成原理（1）①主存總容量4GB=4×23?B=232B；單芯片容量512M×8位=512×22?×1B=22?B。每字節(jié)需要8位（1B=8bit），因此主存需要的芯片數(shù)量=總容量/(單芯片容量)=232B/22?B=8片。②片選地址線4根，說明有2?=16個片選信號，因此主存采用多體交叉組織，每個體的容量為4GB/16=256MB，共16個體。（2）X補碼10110100→符號位1，數(shù)值位取反加1得原碼：11001100→X=-1001100B=-76（十進制）。Y原碼01001010→正數(shù)，Y=+74（十進制）。X-Y=-76-74=-150。8位補碼中，-150的絕對值150>127（8位有符號數(shù)范圍-128~127），需擴展為9位計算：-150的9位原碼：110010110→補碼：101101010（符號位不變，數(shù)值位取反加1）。但8位機器中溢出，實際結果為截斷后的低8位：01101010（溢出標志位為1）。2.編程語言基礎（1）輸出結果：`Derived::func`。虛函數(shù)與純虛函數(shù)的區(qū)別：虛函數(shù)在基類中定義具體實現(xiàn)（`virtualvoidfunc(){}`），子類可重寫；純虛函數(shù)在基類中無實現(xiàn)（`virtualvoidfunc()=0`），子類必須重寫，包含純虛函數(shù)的類是抽象類，無法實例化。（2）b=[2,4]（a[1:-1]是[2,3,4]，步長2取索引1和3→2,4）；c=[5,4,3,2,1]（步長-1表示逆序）。切片規(guī)則：`start`默認0，`end`默認列表長度，`step`默認1；`step<0`時，`start`默認列表末尾，`end`默認-1（即反向遍歷）。3.離散數(shù)學（1）定義命題變元：P：明天下雨；Q：明天下大風；R：運動會推遲舉行；S：組委會提前通知取消。符號化：?S→((P∨Q)→R)（“除非S，否則如果P∨Q則R”等價于“如果非S，則(P∨Q)→R”）。（2）化簡過程：原式=(P∧Q)∨(?P∧R)∨(Q∧R)=(P∧Q)∨R∧(?P∨Q)（分配律）=(P∧Q)∨R∧(P→Q)（?P∨Q等價于P→Q）=(P∧Q)∨R∧(?P∨Q)=(P∧Q)∨(?P∧R)∨(Q∧R)（展開后觀察Q∧R可被前兩項覆蓋？重新推導：利用吸收律：(P∧Q)∨(Q∧R)=Q∧(P∨R)，因此原式=Q∧(P∨R)∨(?P∧R)=Q∧P∨Q∧R∨?P∧R=P∧Q∨R∧(Q∨?P)=P∧Q∨R∧(?P∨Q)=P∧Q∨(?P∨Q)∧R=(P∧Q)∨(?P∧R)∨(Q∧R)（無法進一步化簡，最簡式為原式或等價形式）。二、算法與數(shù)據(jù)結構1.鏈表操作（C++實現(xiàn)）```cppstructListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};ListNodeoddEvenList(ListNodehead){if(!head||!head->next)returnhead;ListNodeodd=head,even=head->next,evenHead=even;while(even&&even->next){odd->next=even->next;//奇數(shù)節(jié)點指向下一個奇數(shù)（當前偶數(shù)的下一個）odd=odd->next;//奇數(shù)指針后移even->next=odd->next;//偶數(shù)節(jié)點指向下一個偶數(shù)even=even->next;//偶數(shù)指針后移}odd->next=evenHead;//奇數(shù)鏈表末尾連接偶數(shù)鏈表頭returnhead;}```2.樹與圖（1）二叉樹結構：前序A為根，中序DBE在左，F(xiàn)C在右。左子樹前序BDE，中序DBE→B為根，D左，E右；右子樹前序CF，中序FC→C為根，F(xiàn)左。樹結構：```A/\BC/\/DEF```后序遍歷：D→E→B→F→C→A。（2）Dijkstra算法步驟（節(jié)點1為起點）：|節(jié)點|初始距離|第一次松弛（通過1）|第二次松弛（通過2或3）|第三次松弛（通過4）|最終最短距離|||-||||--||1|0|0|0|0|0||2|∞→3|3（1→2）|3|3|3||3|∞→5|5（1→3）|5|5|5||4|∞→min(3+6=9,5+2=7)→7|7（1→3→4）|7|7|7||5|∞→min(5+7=12,7+1=8)→8|8（1→3→4→5）|8|8|8|3.動態(tài)規(guī)劃狀態(tài)定義：`dp[i]`表示以`nums[i]`結尾的最長遞增子序列長度。狀態(tài)轉移方程：`dp[i]=max(dp[j]+1)（j<i且nums[j]<nums[i]）`。初始條件：所有`dp[i]=1`（每個元素自身是長度為1的子序列）。示例輸入[10,9,2,5,3,7,101,18]：-dp[0]=1（10）-dp[1]=1（9<10，無更?。?dp[2]=1（2<9,10，無更?。?dp[3]=max(dp[2]+1)=2（5>2）-dp[4]=max(dp[2]+1)=2（3>2）-dp[5]=max(dp[2]+1,dp[3]+1,dp[4]+1)=3（7>2,5,3）-dp[6]=max(dp[0]+1,...,dp[5]+1)=4（101>所有）-dp[7]=max(dp[0]+1,...,dp[5]+1)=4（18>2,5,3,7）最長長度為4。三、操作系統(tǒng)1.進程調度（1）FCFS調度順序：P1→P2→P3→P4。完成時間：P1=8，P2=8+4=12，P3=12+9=21，P4=21+5=26。周轉時間：P1=8-0=8，P2=12-1=11，P3=21-2=19，P4=26-3=23。平均周轉時間=(8+11+19+23)/4=61/4=15.25ms。（2）SJF（非搶占）調度順序（到達時間排序后選最短）：0ms時只有P1（執(zhí)行8ms），8ms時可用進程P2（剩余4）、P3（剩余9）、P4（剩余5）→選P2（4ms），完成時間8+4=12ms；12ms時可用進程P3（9）、P4（5）→選P4（5ms），完成時間12+5=17ms；最后P3（9ms），完成時間17+9=26ms。完成時間：P1=8，P2=12，P4=17，P3=26。周轉時間：P1=8，P2=12-1=11，P4=17-3=14，P3=26-2=24。平均周轉時間=(8+11+14+24)/4=57/4=14.25ms。2.內存管理（1）①頁大小4KB=212B，邏輯地址0x201F=二進制0010000000011111。頁號=前20位（32-12=20）→0x201F的高20位為0x2（即頁號2），頁內偏移=低12位0x01F。頁表中頁號2的物理塊號為3→物理地址=3×4KB+0x01F=0xC000+0x01F=0xC01F（十六進制）。②訪問0x1000時，頁號=0x1000/4KB=1（頁號1），頁表中有效位為0→缺頁中斷。操作系統(tǒng)處理步驟：-檢查頁表，確認頁號1有效位為0，觸發(fā)缺頁中斷。-查找空閑物理塊（若有），否則選擇置換算法（如LRU）淘汰一個有效頁，將其頁表有效位設為0，寫回外存（若被修改）。-將所需頁面從外存讀入空閑物理塊，更新頁表中頁號1的物理塊號和有效位為1。-重新執(zhí)行被中斷的指令，訪問物理地址。四、數(shù)據(jù)庫系統(tǒng)1.SQL編程（1）```sqlSELECTe.姓名,d.部門名稱FROM員工表eJOIN部門表dONe.部門ID=d.部門IDWHEREe.入職時間>'2023-01-01'ANDd.負責人ID=e.員工ID;```（2）```sqlSELECTd.部門名稱,COUNT(DISTINCTe.員工ID)AS人數(shù)FROM部門表dJOIN員工表eONd.部門ID=e.部門IDJOIN參與表pONe.員工ID=p.員工IDGROUPBYd.部門ID,d.部門名稱HAVINGCOUNT(DISTINCTp.項目ID)>3;```2.數(shù)據(jù)庫設計（1）R的候選鍵是(課程編號,學生編號)（能決定所有屬性）。存在部分函數(shù)依賴：課程編號→課程名稱（部分依賴于候選鍵），教師編號→教師姓名（部分依賴），學生編號→學生姓名（部分依賴）。因此R不滿足2NF（2NF要求非主屬性完全依賴于候選鍵）。分解為2NF：R1(課程編號,課程名稱)R2(教師編號,教師姓名)R3(學生編號,學生姓名)R4(課程編號,學生編號,成績)（主屬性為(課程編號,學生編號)，非主屬性成績完全依賴）。檢查3NF：R1、R2、R3、