計(jì)算機(jī)入學(xué)考試題目及答案一、單項(xiàng)選擇題（每題2分，共20分）1.以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（）。A.隊(duì)列B.二叉樹C.棧D.線性表答案：B2.冒泡排序在最壞情況下（數(shù)組逆序）的時(shí)間復(fù)雜度為（）。A.O(n)B.O(n2)C.O(nlogn)D.O(1)答案：B3.操作系統(tǒng)中，進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)的原因通常是（）。A.時(shí)間片用完B.被調(diào)度程序選中C.等待I/O操作完成D.進(jìn)程創(chuàng)建完成答案：C4.在TCP/IP模型中，HTTP協(xié)議屬于（）。A.網(wǎng)絡(luò)接口層B.網(wǎng)絡(luò)層C.傳輸層D.應(yīng)用層答案：D5.關(guān)系數(shù)據(jù)庫中，第二范式（2NF）要求消除（）。A.傳遞函數(shù)依賴B.部分函數(shù)依賴C.多值依賴D.完全函數(shù)依賴答案：B6.深度為5的滿二叉樹（根節(jié)點(diǎn)深度為1）的節(jié)點(diǎn)總數(shù)為（）。A.15B.31C.32D.63答案：B（滿二叉樹節(jié)點(diǎn)數(shù)為2?1=31）7.以下排序算法中，不穩(wěn)定的是（）。A.冒泡排序B.歸并排序C.快速排序D.插入排序答案：C8.虛擬內(nèi)存的主要作用是（）。A.提高CPU訪問內(nèi)存的速度B.擴(kuò)展物理內(nèi)存的容量C.存儲(chǔ)系統(tǒng)緩存D.加速文件讀寫答案：B9.以下不屬于對(duì)稱加密算法的是（）。A.AESB.DESC.RSAD.3DES答案：C（RSA是非對(duì)稱加密）10.編譯過程中，詞法分析的主要任務(wù)是（）。A.檢查語法錯(cuò)誤B.將源程序轉(zhuǎn)換為目標(biāo)代碼C.識(shí)別單詞（如標(biāo)識(shí)符、關(guān)鍵字）D.優(yōu)化中間代碼答案：C二、填空題（每題2分，共20分）1.計(jì)算多項(xiàng)式f(x)=a?+a?x+a?x2+…+a?x?的秦九韶算法的時(shí)間復(fù)雜度為____。答案：O(n)2.對(duì)有序數(shù)組進(jìn)行二分查找，最壞情況下的時(shí)間復(fù)雜度為____。答案：O(logn)3.TCP建立連接的過程稱為____，需要經(jīng)過____次握手。答案：三次握手；34.數(shù)據(jù)庫實(shí)體聯(lián)系（ER）模型的三個(gè)基本元素是____、____、____。答案：實(shí)體；屬性；聯(lián)系5.操作系統(tǒng)中，進(jìn)程的三種基本狀態(tài)是____、____、____。答案：就緒；運(yùn)行；阻塞6.深度為5的完全二叉樹（根節(jié)點(diǎn)深度為1）最少有____個(gè)節(jié)點(diǎn)。答案：16（完全二叉樹最少節(jié)點(diǎn)數(shù)為2?=16）7.HTTP請(qǐng)求中，GET方法通常用于____，POST方法通常用于____。答案：獲取資源；提交數(shù)據(jù)8.快速排序的平均時(shí)間復(fù)雜度為____，最壞時(shí)間復(fù)雜度為____。答案：O(nlogn)；O(n2)9.計(jì)算機(jī)內(nèi)存地址的編址單位通常是____。答案：字節(jié)10.結(jié)構(gòu)化程序設(shè)計(jì)的三種基本控制結(jié)構(gòu)是____、____、____。答案：順序；選擇；循環(huán)三、簡(jiǎn)答題（每題10分，共40分）1.解釋虛擬內(nèi)存的定義、作用及實(shí)現(xiàn)方式。虛擬內(nèi)存是操作系統(tǒng)為進(jìn)程提供的一個(gè)邏輯地址空間，其容量不受物理內(nèi)存限制。作用：解決物理內(nèi)存不足的問題，允許進(jìn)程使用比物理內(nèi)存更大的地址空間；通過內(nèi)存換頁（或換段）實(shí)現(xiàn)進(jìn)程間內(nèi)存隔離，提高系統(tǒng)安全性。實(shí)現(xiàn)方式：分頁機(jī)制：將虛擬內(nèi)存劃分為固定大小的頁（Page），物理內(nèi)存劃分為頁框（PageFrame），通過頁表記錄虛擬頁與物理頁框的映射關(guān)系。缺頁中斷：當(dāng)進(jìn)程訪問的頁不在物理內(nèi)存時(shí)，觸發(fā)缺頁中斷，將所需頁從磁盤調(diào)入內(nèi)存（若內(nèi)存不足則置換出部分頁）。交換空間：磁盤中預(yù)留的空間用于存儲(chǔ)暫時(shí)不使用的頁。2.比較歸并排序與快速排序的異同點(diǎn)（從時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性、適用場(chǎng)景角度）。時(shí)間復(fù)雜度：歸并排序平均和最壞均為O(nlogn)；快速排序平均O(nlogn)，最壞O(n2)（如數(shù)組已有序時(shí)）。空間復(fù)雜度：歸并排序需要O(n)的額外空間（合并時(shí)臨時(shí)存儲(chǔ)）；快速排序需要O(logn)的棧空間（遞歸調(diào)用）。穩(wěn)定性：歸并排序是穩(wěn)定排序（相等元素的相對(duì)順序不變）；快速排序不穩(wěn)定（分區(qū)過程可能打亂順序）。適用場(chǎng)景：歸并排序適用于外排序（處理大文件）或?qū)Ψ€(wěn)定性有要求的場(chǎng)景；快速排序適用于內(nèi)存充足、平均情況性能好的場(chǎng)景（如通用排序）。3.說明關(guān)系數(shù)據(jù)庫中1NF、2NF、3NF的定義，并舉例說明。1NF（第一范式）：要求關(guān)系中的每個(gè)屬性不可再分（原子性）。例如，若“學(xué)生”表包含“聯(lián)系方式”字段（存儲(chǔ)電話+郵箱），則違反1NF，需拆分為“電話”和“郵箱”兩個(gè)字段。2NF（第二范式）：在1NF基礎(chǔ)上，消除非主屬性對(duì)候選鍵的部分函數(shù)依賴。例如，表（學(xué)號(hào)，課程號(hào)，姓名，成績）中，候選鍵為（學(xué)號(hào)，課程號(hào)），姓名僅依賴于學(xué)號(hào)（部分依賴），需拆分為（學(xué)號(hào)，姓名）和（學(xué)號(hào)，課程號(hào)，成績）。3NF（第三范式）：在2NF基礎(chǔ)上，消除非主屬性對(duì)候選鍵的傳遞函數(shù)依賴。例如，表（學(xué)號(hào)，系號(hào)，系主任）中，學(xué)號(hào)→系號(hào)，系號(hào)→系主任（傳遞依賴），需拆分為（學(xué)號(hào)，系號(hào)）和（系號(hào)，系主任）。4.描述TCP三次握手的過程，并說明每一步的作用。三次握手是TCP建立連接的過程，步驟如下：第一步（SYN）：客戶端向服務(wù)端發(fā)送SYN包（同步序列號(hào)），標(biāo)識(shí)自己的初始序列號(hào)x，并請(qǐng)求建立連接。作用：客戶端通知服務(wù)端準(zhǔn)備連接。第二步（SYN+ACK）：服務(wù)端收到SYN后，回復(fù)SYN+ACK包，包含自己的初始序列號(hào)y，以及對(duì)客戶端序列號(hào)的確認(rèn)（x+1）。作用：服務(wù)端確認(rèn)客戶端請(qǐng)求，并同步自己的序列號(hào)。第三步（ACK）：客戶端收到SYN+ACK后，發(fā)送ACK包，確認(rèn)服務(wù)端的序列號(hào)（y+1）。作用：客戶端確認(rèn)服務(wù)端已準(zhǔn)備好，連接建立完成。三次握手的目的是防止歷史連接的重復(fù)請(qǐng)求，確保雙方通信能力正常，并同步初始序列號(hào)。四、編程題（共20分）題目：給定一個(gè)整數(shù)數(shù)組nums和一個(gè)整數(shù)目標(biāo)值target，找出所有滿足兩數(shù)之和等于target的不重復(fù)二元組。要求：輸出結(jié)果中每個(gè)二元組按升序排列（如[2,7]而非[7,2]）。整個(gè)結(jié)果數(shù)組按二元組的第一個(gè)元素升序排列。時(shí)間復(fù)雜度不超過O(nlogn)。示例：輸入nums=[2,7,11,15,7,2]，target=9；輸出[[2,7]]（因[2,7]重復(fù)出現(xiàn)但需去重）。Python實(shí)現(xiàn)代碼：```pythondeftwo_sum_unique_pairs(nums,target):nums.sort()排序，時(shí)間復(fù)雜度O(nlogn)n=len(nums)result=[]left,right=0,n1雙指針whileleft<right:current_sum=nums[left]+nums[right]ifcurrent_sum==target:result.append([nums[left],nums[right]])跳過左側(cè)重復(fù)元素whileleft<rightandnums[left]==nums[left+1]:left+=1跳過右側(cè)重復(fù)元素whileleft<rightandnums[right]==nums[right1]:right=1left+=1移動(dòng)左指針right=1移動(dòng)右指針elifcurrent_sum<target:left+=1和過小，左指針右移else:right=1和過大，右指針左移returnresult測(cè)試用例print(two_sum_unique_pairs([2,7,11,15,7,2],9))輸出[[2,7]]print(two_sum_unique_pairs([3,2,4,2,3],6))輸出[[2,4],[3,3]]```代碼說明：1.首先對(duì)數(shù)組排序（O(nlogn)），