計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)專接本入學(xué)考試試題及答案一、單項(xiàng)選擇題（每題2分，共30分）1.在C語言中，若定義inta=3,b=4;則表達(dá)式(a||b)&&(a^b)的值為A.0??B.1??C.3??D.4答案：B解析：a||b為真(1)，a^b為7(二進(jìn)制011^100=111)，7非零即真，故1&&1得1。2.下列關(guān)于進(jìn)程與線程的描述，錯(cuò)誤的是A.線程切換開銷小于進(jìn)程切換B.同一進(jìn)程的線程共享地址空間C.線程是CPU調(diào)度的基本單位D.進(jìn)程間通信一定比線程間通信快答案：D解析：進(jìn)程間通信需內(nèi)核介入，線程共享內(nèi)存即可通信，故D錯(cuò)誤。3.對(duì)長度為n的順序表執(zhí)行刪除第i個(gè)元素(1≤i≤n)，需移動(dòng)元素次數(shù)為A.n-i??B.n-i+1??C.i??D.n答案：A解析：刪除第i個(gè)元素后，i+1到n共n-i個(gè)元素前移一位。4.在IPv4中，子網(wǎng)掩碼92可劃分的主機(jī)數(shù)為A.62??B.126??C.30??D.14答案：A解析：192=11000000，主機(jī)位6位，2^6-2=62。5.下列排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)且穩(wěn)定的是A.快速排序??B.堆排序??C.歸并排序??D.希爾排序答案：C解析：歸并排序穩(wěn)定，平均O(nlogn)。6.在關(guān)系數(shù)據(jù)庫中，若屬性集X→Y，Y→Z，則X→Z屬于A.自反律??B.增廣律??C.傳遞律??D.合并律答案：C解析：函數(shù)依賴的傳遞律。7.若一棵二叉樹的后序遍歷為DBEFCA，中序遍歷為DBAECF，則先序遍歷為A.ABCDEF??B.ABDCEF??C.ABDECF??D.ACBDFE答案：C解析：后序最后為根A，中序分左子樹DB，右子樹ECF；遞歸可得先序ABDECF。8.在OSI七層模型中，負(fù)責(zé)端到端可靠傳輸?shù)氖茿.網(wǎng)絡(luò)層??B.傳輸層??C.會(huì)話層??D.數(shù)據(jù)鏈路層答案：B解析：傳輸層提供端到端服務(wù)。9.若浮點(diǎn)數(shù)采用IEEE754單精度格式，指數(shù)域全1且尾數(shù)非0，則表示A.0??B.無窮大??C.NaN??D.規(guī)格化數(shù)答案：C解析：指數(shù)全1尾數(shù)非0為NaN。10.在Linux中，命令chmod4755file的作用是A.設(shè)置SUID位??B.設(shè)置SGID位??C.設(shè)置粘滯位??D.僅改權(quán)限為755答案：A解析：4為SUID，7為rwx，故設(shè)置SUID且權(quán)限755。11.下列關(guān)于TCP擁塞控制的描述，正確的是A.慢啟動(dòng)閾值初始為0??B.擁塞避免階段cwnd線性增長C.快速重傳后直接進(jìn)入慢啟動(dòng)??D.超時(shí)發(fā)生時(shí)cwnd減半答案：B解析：擁塞避免階段每RTTcwnd加1，線性增長。12.對(duì)n個(gè)頂點(diǎn)e條邊的無向圖，采用鄰接矩陣存儲(chǔ)時(shí)，空間復(fù)雜度為A.O(n+e)??B.O(n^2)??C.O(e)??D.O(n)答案：B解析：鄰接矩陣n×n。13.在Python中，表達(dá)式[1,2]*3的值是A.[3,6]??B.[1,2,1,2,1,2]??C.報(bào)錯(cuò)??D.[1,2,3]答案：B解析：列表乘號(hào)為重復(fù)拼接。14.若Cache采用2路組相聯(lián)映射，主存地址32位，塊大小64B，Cache容量32KB，則組數(shù)為A.256??B.512??C.128??D.64答案：A解析：32KB/(64B×2)=256組。15.在公鑰密碼體系中，用于數(shù)字簽名的是A.接收方公鑰??B.接收方私鑰??C.發(fā)送方公鑰??D.發(fā)送方私鑰答案：D解析：簽名用發(fā)送方私鑰，驗(yàn)證用發(fā)送方公鑰。二、填空題（每空2分，共20分）16.若某算法時(shí)間復(fù)雜度為T(n)=4T(n/2)+O(n^2)，則根據(jù)主定理，T(n)=________。答案：Θ(n^2logn)解析：a=4,b=2,f(n)=n^2，滿足主定理情形2。17.在IPv6中，地址長度為________位。答案：12818.若關(guān)系模式R(A,B,C)的函數(shù)依賴集F={A→B,B→C}，則R的候選碼為________。答案：A解析：A的閉包為ABC。19.在操作系統(tǒng)中，頁面置換算法Belady異?？赡艹霈F(xiàn)在________算法。答案：FIFO解析：FIFO可能出現(xiàn)Belady異常。20.若某磁盤塊大小為4KB，磁盤地址指針占4B，則采用二級(jí)間接索引可支持的最大文件為________KB。答案：4KB/4B=1024，二級(jí)1024×1024×4KB=4GB，即4096×1024KB。21.在HTTP/1.1中，持久連接默認(rèn)使用________機(jī)制判斷消息邊界。答案：Content-Length或分塊傳輸編碼(chunked)22.若某二叉樹度為2的節(jié)點(diǎn)有10個(gè)，則葉子節(jié)點(diǎn)數(shù)為________。答案：11解析：n0=n2+1。23.在MySQL中，事務(wù)的隔離級(jí)別________可避免幻讀。答案：可串行化(Serializable)24.若某無向圖有20條邊，則其生成樹有________條邊。答案：19解析：生成樹邊數(shù)=頂點(diǎn)數(shù)-1，頂點(diǎn)數(shù)=20+1=21，生成樹20-1=19。25.在RSA算法中，若p=3,q=11，則歐拉函數(shù)φ(n)=________。答案：20解析：φ(n)=(p-1)(q-1)=2×10=20。三、判斷題（每題1分，共10分，正確打“√”，錯(cuò)誤打“×”）26.哈希表的裝載因子越大，沖突概率越高?！?7.在TCP三次握手中，SYN=1且ACK=1的報(bào)文一定由客戶端發(fā)出?！?8.關(guān)系數(shù)據(jù)庫中，外碼允許取空值?！?9.快速排序的最壞時(shí)間復(fù)雜度為O(n^2)?！?0.在Linux中，硬鏈接可以跨文件系統(tǒng)?！?1.采用補(bǔ)碼表示的整數(shù)，0的表示唯一?！?2.在OSI模型中，路由器工作在網(wǎng)絡(luò)層?！?3.在Python中，元組是可變對(duì)象?！?4.對(duì)任意二叉樹，后序遍歷的逆序即為拓?fù)渑判蛐蛄??！?5.在分頁管理中，頁內(nèi)偏移量位數(shù)由頁面大小決定?！趟?、簡答題（每題8分，共40分）36.簡述虛擬內(nèi)存的工作原理，并說明頁面置換算法LRU的實(shí)現(xiàn)思路。答案：虛擬內(nèi)存通過將邏輯地址空間與物理內(nèi)存分離，使程序可使用比實(shí)際內(nèi)存更大的地址空間。操作系統(tǒng)為每個(gè)進(jìn)程建立頁表，記錄邏輯頁到物理幀的映射。訪問時(shí)，MMU將邏輯地址拆分為頁號(hào)和偏移，查頁表若存在且有效位為1則直接訪問；若缺頁，則觸發(fā)缺頁異常，操作系統(tǒng)選擇一頁換出，調(diào)入所需頁，更新頁表后重新執(zhí)行指令。LRU（LeastRecentlyUse）實(shí)現(xiàn)思路：維護(hù)一個(gè)按訪問時(shí)間排序的鏈表，每次訪問某頁將其移至鏈表頭；缺頁時(shí)淘汰鏈表尾。實(shí)際可用雙向鏈表+哈希表，哈希表存頁號(hào)到鏈表節(jié)點(diǎn)指針，訪問/插入均為O(1)。37.描述TCP流量控制與擁塞控制的區(qū)別，并給出各自的核心機(jī)制。答案：流量控制解決發(fā)送方與接收方速率匹配，防止接收方緩沖區(qū)溢出，核心機(jī)制為滑動(dòng)窗口，接收方通過rwnd字段通告窗口大小，發(fā)送方發(fā)送數(shù)據(jù)不超過min(cwnd,rwnd)。擁塞控制解決網(wǎng)絡(luò)容量限制，防止網(wǎng)絡(luò)擁塞，核心機(jī)制包括慢啟動(dòng)、擁塞避免、快速重傳、快速恢復(fù)。慢啟動(dòng)階段cwnd指數(shù)增長至ssthresh；之后線性增長；收到3個(gè)重復(fù)ACK觸發(fā)快速重傳，ssthresh=cwnd/2，cwnd=ssthresh+3，進(jìn)入快速恢復(fù)；超時(shí)則ssthresh=cwnd/2，cwnd=1，重新慢啟動(dòng)。38.給定關(guān)系模式R(學(xué)號(hào)，姓名，課程號(hào)，課程名，成績，教師號(hào)，教師名)，函數(shù)依賴集F={學(xué)號(hào)→姓名，課程號(hào)→課程名，教師號(hào)→教師名，(學(xué)號(hào)，課程號(hào))→成績，(課程號(hào))→教師號(hào)}，求R的候選碼及最高范式，若不屬于3NF，請(qǐng)分解。答案：候選碼：(學(xué)號(hào)，課程號(hào))。存在非主屬性對(duì)碼的部分依賴與傳遞依賴，如課程號(hào)→教師號(hào)→教師名，故僅1NF。分解：R1(課程號(hào)，課程名，教師號(hào)，教師名)候選碼：課程號(hào)，存在傳遞依賴，再分：R11(課程號(hào)，課程名，教師號(hào))，R12(教師號(hào)，教師名)R2(學(xué)號(hào)，課程號(hào)，成績)R3(學(xué)號(hào)，姓名)最終：R11,R12,R2,R3均達(dá)3NF。39.說明HTTPS建立連接的全過程，并指出與HTTP的主要區(qū)別。答案：HTTPS在HTTP與TCP之間加入TLS/SSL層。過程：1.TCP三次握手；2.ClientHello：客戶端發(fā)送支持的TLS版本、隨機(jī)數(shù)、加密套件列表；3.ServerHello：服務(wù)端選加密套件、發(fā)送隨機(jī)數(shù)、證書（含公鑰）；4.客戶端驗(yàn)證證書，生成預(yù)主密鑰，用服務(wù)端公鑰加密發(fā)送；5.雙方根據(jù)隨機(jī)數(shù)+預(yù)主密鑰生成會(huì)話密鑰；6.握手完成，后續(xù)數(shù)據(jù)用對(duì)稱加密傳輸。與HTTP區(qū)別：HTTPS默認(rèn)端口443，HTTP為80；HTTPS提供加密、完整性、身份認(rèn)證，HTTP明文傳輸；HTTPS需數(shù)字證書，HTTP無需。40.解釋死鎖產(chǎn)生的四個(gè)必要條件，并給出銀行家算法的基本思想。答案：四個(gè)必要條件：1.互斥：資源一次只能被一個(gè)進(jìn)程占用；2.占有且等待：進(jìn)程已占部分資源，又申請(qǐng)新資源而被阻塞；3.非搶占：已分配給進(jìn)程的資源不能被強(qiáng)制剝奪；4.循環(huán)等待：存在進(jìn)程-資源的循環(huán)等待鏈。銀行家算法思想：系統(tǒng)在分配資源前，先模擬分配，檢查是否仍存在安全序列（即所有進(jìn)程都能順利完成）。若存在則分配，否則拒絕申請(qǐng)，使系統(tǒng)始終處于安全狀態(tài)，避免死鎖。需維護(hù)Available、Max、Allocation、Need矩陣。五、算法與程序設(shè)計(jì)題（每題15分，共30分）41.給定一個(gè)長度為n的整數(shù)數(shù)組，找出其中出現(xiàn)次數(shù)超過?n/2?的元素（假設(shè)一定存在）。要求時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。答案：采用摩爾投票法。初始化candidate=任意值，count=0；遍歷數(shù)組：若count==0，則candidate=當(dāng)前元素；若當(dāng)前元素==candidate，count++，否則count--；最終candidate即為答案。C語言實(shí)現(xiàn)：intmajority(int*nums,intn){intc,cnt=0;for(inti=0;i<n;i++){if(cnt==0)c=nums[i];if(nums[i]==c)cnt++;elsecnt--;}returnc;}解析：每次不同元素相互抵消，剩余即為多數(shù)。42.實(shí)現(xiàn)一個(gè)函數(shù)，判斷兩棵二叉樹是否互為鏡像。函數(shù)原型boolisMirror(TreeNoderoot1,TreeNoderoot2)。答案：遞歸思路：1.若兩樹皆空，返回true；2.若一為空另一非空，返回false；3.若根值不等，返回false；4.遞歸判斷左子樹與右子樹是否鏡像，右子樹與左子樹是否鏡像。C++實(shí)現(xiàn)：boolisMirror(TreeNodea,TreeNodeb){if(!a&&!b)returntrue;if(!a||!b)returnfalse;return(a->val==b->val)&&isMirror(a->left,b->right)&&isMirror(a->right,b->left);}時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(h)，h為樹高。六、綜合應(yīng)用題（每題20分，共40分）43.某高校選課系統(tǒng)采用B/S架構(gòu)，數(shù)據(jù)庫MySQL，Web服務(wù)器Nginx+PHP-FPM，高峰期并發(fā)量約5000。近期出現(xiàn)“數(shù)據(jù)庫連接耗盡”與“頁面響應(yīng)慢”問題。請(qǐng)從數(shù)據(jù)庫、Web服務(wù)器、應(yīng)用層給出完整優(yōu)化方案，并說明如何驗(yàn)證效果。答案：數(shù)據(jù)庫層：1.開啟連接池，使用PDO長連接，限制最大連接數(shù)=CPU核數(shù)×2+磁盤數(shù)；2.對(duì)高頻查詢?nèi)纭罢n程余量”建立聯(lián)合索引(課程號(hào),狀態(tài))，避免SELECT*；3.引入Redis緩存，將課程余量、課程詳情緩存30s，寫操作采用先寫庫再刪緩存策略；4.分庫分表：按學(xué)期哈希分表，減少單表數(shù)據(jù)量；5.開啟慢查詢?nèi)罩?，分析超過100ms的SQL，強(qiáng)制使用索引。Web服務(wù)器層：1.Nginx開啟gzip壓縮，靜態(tài)資源緩存1天；2.調(diào)整php-fpmpm=static，子進(jìn)程數(shù)=CPU核數(shù)×4，max_requests=10000防止內(nèi)存泄漏；3.使用UnixSocket連接php-fpm，減少TCP開銷；4.配置Nginx限流，限制單IP10r/s，防止惡意刷接口。應(yīng)用層：1.采用異步消息隊(duì)列(RabbitMQ)處理選課高峰，將選課請(qǐng)求先入隊(duì)，后臺(tái)消費(fèi)者串行扣減庫存，避免行鎖沖突；2.前端按鈕置灰+JS節(jié)流，減少重復(fù)提交；3.引入本地緩存(APCu)緩存配置信息，減少Redis穿透；4.使用預(yù)編譯語句防止SQL注入，減少解析開銷。驗(yàn)證：1.使用sysbench模擬5000并發(fā)，觀察QPS、響應(yīng)時(shí)間、錯(cuò)誤率；2.通過Prometheus+Grafana監(jiān)控連接數(shù)、CPU、IO；3.對(duì)比優(yōu)化前后95分位響應(yīng)時(shí)間，目標(biāo)從3s降至500ms以內(nèi)；4.進(jìn)行48h壓力測(cè)試，無連接耗盡報(bào)錯(cuò)。44.設(shè)計(jì)一個(gè)基于區(qū)塊鏈的學(xué)歷存證系統(tǒng)，要求防止學(xué)校私自篡改、支持第三方快速驗(yàn)證、保護(hù)學(xué)生隱私。請(qǐng)給出系統(tǒng)架構(gòu)、關(guān)鍵數(shù)據(jù)結(jié)構(gòu)、智能合約核心函數(shù)、隱私保護(hù)方案及攻擊防御措施。答案：系統(tǒng)架構(gòu)：1.聯(lián)盟鏈(HyperledgerFabric)，由教育部、高校、用人單位組成組織；2.每個(gè)組織部署Peer節(jié)點(diǎn)，Orderer節(jié)點(diǎn)由教育部主導(dǎo)；3.前端DApp提供學(xué)生上傳、企業(yè)驗(yàn)證界面；4.鏈下存儲(chǔ)加密后的學(xué)歷PDF，鏈上僅存哈希與索引。關(guān)鍵數(shù)據(jù)結(jié)構(gòu)：區(qū)塊頭：前一區(qū)塊哈希、Merkle根、時(shí)間戳、組織MSP簽名；交易：學(xué)歷哈希、學(xué)生學(xué)號(hào)密文、學(xué)校ID、學(xué)位類型、授予時(shí)間、狀態(tài)(有效/撤銷)。智能合約(鏈碼)：1.issueDegree(ctx,studentIDHash,degreeHash,schoolMSP,encryptPubKey