2025年計算機學科水平模擬測試考試時間：______分鐘總分：______分姓名：______一、選擇題（每題2分，共20分）1.下列關于算法時間復雜度T(n)=O(f(n))的描述中，正確的是（）。A.算法執(zhí)行時間隨輸入規(guī)模n的增長而無限增長B.算法執(zhí)行時間隨輸入規(guī)模n的增長有界C.任何T(n)=O(f(n))的算法都是高效的算法D.當n趨向無窮大時，T(n)/f(n)的極限存在且為正數(shù)2.在線性表L=(a1,a2,...,an)中，刪除ai元素（假設位置唯一）的最少比較次數(shù)是（）。A.1B.2C.n-1D.n3.下列數(shù)據(jù)結構中，適合用來表示稀疏矩陣的是（）。A.順序表B.鏈棧C.稀疏矩陣壓縮存儲（如三元組表）D.二叉排序樹4.設棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e依次進入棧S。若每個元素出棧后立即進入隊列Q，則Q中的元素序列為（）。A.abcdeB.dcbaeC.acbedD.ebcda5.下列關于樹的說法中，正確的是（）。A.樹是一種非線性結構，其中每個節(jié)點最多有一個前件，可以有多個后件B.樹是一種非線性結構，其中每個節(jié)點最多有一個后件，可以有多個前件C.樹是一種線性結構，其中每個節(jié)點最多有一個前件，可以有多個后件D.樹是一種線性結構，其中每個節(jié)點最多有一個后件，可以有多個前件6.在下列排序算法中，平均時間復雜度最低的是（）。A.冒泡排序B.選擇排序C.插入排序D.快速排序7.下列關于操作系統(tǒng)的敘述中，錯誤的是（）。A.操作系統(tǒng)是計算機系統(tǒng)中最核心的系統(tǒng)軟件B.操作系統(tǒng)提供了用戶與計算機硬件之間的接口C.操作系統(tǒng)的主要目標是提高資源利用率和方便用戶使用D.操作系統(tǒng)可以脫離應用程序獨立運行8.在TCP/IP協(xié)議簇中，負責在網(wǎng)絡層提供可靠數(shù)據(jù)傳輸?shù)膮f(xié)議是（）。A.IP協(xié)議B.ICMP協(xié)議C.UDP協(xié)議D.TCP協(xié)議9.采用分頁存儲管理方式時，地址空間是（）。A.連續(xù)的B.不連續(xù)的C.既有連續(xù)的也有不連續(xù)的D.以上都不對10.關系數(shù)據(jù)庫中的“元組”指的是（）。A.表中的屬性B.表中的記錄C.屬性的值域D.關系的鍵二、填空題（每空2分，共20分）1.在深度為k的滿二叉樹中，含有的節(jié)點總數(shù)為_______。2.冒泡排序在最壞情況下的時間復雜度為_______。3.在SQL查詢語句中，用于選擇數(shù)據(jù)的子句是_______。4.計算機網(wǎng)絡按照傳輸介質可分為有線網(wǎng)和_______。5.CPU響應中斷后，將中斷源的中斷號放入_______寄存器中。6.數(shù)據(jù)的壓縮編碼方式分為無損壓縮和有損壓縮兩種，其中_______壓縮能完全恢復原始數(shù)據(jù)。7.將n個元素插入一個空堆中，構建大根堆的時間復雜度為_______。8.在多道程序設計系統(tǒng)中，進程的基本狀態(tài)包括運行、就緒和_______。9.IP地址202.115.51.34屬于_______類地址。10.關系R和關系S進行笛卡爾積運算，記作_______。三、簡答題（每題5分，共20分）1.簡述棧和隊列的主要區(qū)別。2.解釋什么是“死鎖”，并列舉產生死鎖的四個必要條件。3.簡述TCP協(xié)議三次握手的過程及其目的。4.什么是數(shù)據(jù)庫的規(guī)范化？為什么要對數(shù)據(jù)庫進行規(guī)范化？四、算法設計題（10分）設計一個算法，查找無向圖中是否存在一條從頂點u到頂點v的路徑。輸入為圖的鄰接矩陣`graph`（`graph[i][j]`表示頂點i和j之間是否有邊，1表示有，0表示無），以及頂點`u`和`v`。請用C或Java偽代碼描述該算法，并簡要說明其時間復雜度。五、編程題（30分）編寫一個函數(shù)`removeDuplicates`，接受一個由整數(shù)組成的數(shù)組`arr`和它的大小`size`作為參數(shù)。該函數(shù)的功能是：刪除數(shù)組中重復的元素，只保留一個。例如，輸入`[1,2,2,3,4,4,5]`和`size=7`，處理后數(shù)組應變?yōu)閌[1,2,3,4,5]`，實際保留的元素個數(shù)為5。要求：不能使用額外的數(shù)組空間（即只能通過修改原數(shù)組實現(xiàn)），可以假設數(shù)組有足夠的空間來存放結果。請用C或Java偽代碼實現(xiàn)該函數(shù)。試卷答案一、選擇題1.B2.C3.C4.B5.A6.D7.D8.D9.B10.B二、填空題1.2^k-12.O(n^2)3.SELECT4.無線網(wǎng)5.程序計數(shù)器(PC)或標志寄存器(PSW)的某部分(具體取決于中斷處理機制，PC更常見)6.無損7.O(nlogn)8.等待9.B10.R×S三、簡答題1.棧是后進先出(LIFO)的線性結構，只允許在棧頂進行插入和刪除操作；隊列是先進先出(FIFO)的線性結構，允許在隊頭進行刪除操作，在隊尾進行插入操作。2.死鎖是指兩個或兩個以上的進程在執(zhí)行過程中，因爭奪資源而造成的一種相互等待的現(xiàn)象，若無外力作用，這些進程都將無法向前推進。產生死鎖的四個必要條件是：互斥、占有并等待、非搶占、循環(huán)等待。3.TCP三次握手過程如下：①主機A向主機B發(fā)送SYN=1的連接請求報文段，同步序列號seq=x。②主機B收到SYN報文段后，向主機A發(fā)送SYN=1,ACK=1的確認報文段，同步序列號seq=y，確認號ack=x+1。③主機A收到確認報文段后，向主機B發(fā)送ACK=1的確認報文段，確認號ack=y+1。目的在于雙方確認彼此都具備發(fā)送和接收數(shù)據(jù)的能力，并同步初始序列號。4.數(shù)據(jù)庫規(guī)范化是將一個關系模式分解為多個更小的關系模式，以消除數(shù)據(jù)冗余、減少數(shù)據(jù)修改異常（插入、刪除、更新異常）、保證數(shù)據(jù)一致性。進行規(guī)范化的主要目的是建立合理的數(shù)據(jù)庫邏輯結構，提高數(shù)據(jù)存儲效率和查詢效率，保證數(shù)據(jù)的完整性。四、算法設計題```c//偽代碼示例(BFS)boolhasPath(intgraph,intn,intu,intv){if(u==v)returntrue;boolvisited[n];for(inti=0;i<n;i++)visited[i]=false;intqueue[n];//隊列intfront=0,rear=0;visited[u]=true;queue[rear++]=u;//入隊while(front<rear){intcurrent=queue[front++];//出隊for(inti=0;i<n;i++){if(graph[current][i]==1&&!visited[i]){//有邊且未訪問if(i==v)returntrue;//找到vvisited[i]=true;queue[rear++]=i;//入隊}}}returnfalse;//未找到路徑}//時間復雜度：O(n^2)，其中n是頂點數(shù)。在最壞情況下，需要遍歷整個鄰接矩陣。```解析思路：可以使用深度優(yōu)先搜索(DFS)或廣度優(yōu)先搜索(BFS)來查找路徑。此處采用BFS，利用隊列實現(xiàn)。初始化訪問標記數(shù)組visited和一個隊列。將起始點u標記為已訪問并入隊。然后循環(huán)，每次從隊列頭部取出一個頂點current，檢查其所有鄰接點。若鄰接點i未被訪問且是目標頂點v，則返回true。否則，若鄰接點i未被訪問，則將其標記為已訪問并入隊。若隊列為空仍未找到v，則不存在路徑。五、編程題```c//偽代碼示例(雙指針法)voidremoveDuplicates(int*arr,intsize){if(size==0||size==1)return;intj=0;//指向下一個不重復元素應放置的位置for(inti=1;i<size;i++){//如果當前元素與前一個元素不同if(arr[i]!=arr[j]){j++;//j移動到下一個位置arr[j]=arr[i];//將當前元素放到新位置}}//數(shù)組中不重復元素的實際個數(shù)是j+1//可以根據(jù)需要返回j+1或修改函數(shù)接口}//解析思路：使用兩個指針（或索引）i和j。i遍歷數(shù)組，j指向當前已找到的不重復元素的末尾。//初始時，j=0，將第一