2024年計(jì)算機(jī)408統(tǒng)考真題考試時(shí)間：______分鐘總分：______分姓名：______一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分。在每小題列出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)字母填在題后的括號(hào)內(nèi)。）1.下列數(shù)據(jù)結(jié)構(gòu)中，適合表示稀疏矩陣的是（）。A.隊(duì)列B.棧C.線(xiàn)性表D.稀疏矩陣壓縮存儲(chǔ)（三元組表）2.設(shè)棧S的初始狀態(tài)為空，經(jīng)過(guò)一系列入棧和出棧操作后，得到棧的狀態(tài)為abc-1-2d-3，其中“-”表示出棧操作。那么，完成這一系列操作的具體入棧序列是（）。A.cbaedB.acbedC.dabcD.bcdae3.在深度為5的二叉樹(shù)中，最多有多少個(gè)結(jié)點(diǎn)？（）A.32B.31C.64D.634.下列關(guān)于哈希表的描述中，錯(cuò)誤的是（）。A.哈希表的沖突解決方法主要有插入法、開(kāi)放地址法、鏈地址法B.哈希表的裝填因子越大，發(fā)生沖突的可能性越小C.哈希表的平均查找長(zhǎng)度與裝填因子有關(guān)D.哈希表是一種通過(guò)計(jì)算關(guān)鍵字來(lái)直接確定數(shù)據(jù)存儲(chǔ)地址的數(shù)據(jù)結(jié)構(gòu)5.若一棵二叉樹(shù)的前序遍歷序列為ABCD，中序遍歷序列為CBAD，則其后序遍歷序列為（）。A.DCBAB.CBADC.CDABD.ADCB6.下列關(guān)于B樹(shù)的描述中，正確的是（）。A.B樹(shù)是一種平衡的多路搜索樹(shù)B.B樹(shù)的插入和刪除操作不需要進(jìn)行結(jié)點(diǎn)合并或分裂C.B樹(shù)的每個(gè)結(jié)點(diǎn)存儲(chǔ)的鍵值數(shù)量是固定的D.B樹(shù)適用于頻繁進(jìn)行插入和刪除操作的場(chǎng)景，但查詢(xún)效率不如二叉搜索樹(shù)7.在下列排序算法中，最壞情況下的時(shí)間復(fù)雜度不是O(n^2)的是（）。A.插入排序B.選擇排序C.快速排序D.堆排序8.設(shè)有長(zhǎng)度為n的線(xiàn)性表，分別采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在表尾插入一個(gè)元素時(shí)，其平均時(shí)間復(fù)雜度分別為（）。A.O(1)和O(1)B.O(1)和O(n)C.O(n)和O(1)D.O(n)和O(n)9.計(jì)算機(jī)硬件能夠直接識(shí)別和執(zhí)行的指令代碼是（）。A.匯編語(yǔ)言指令B.高級(jí)語(yǔ)言源程序C.機(jī)器語(yǔ)言指令D.符號(hào)語(yǔ)言指令10.在馮·諾依曼計(jì)算機(jī)體系結(jié)構(gòu)中，指令和數(shù)據(jù)都存儲(chǔ)在（）中，并以相同的方式在總線(xiàn)上傳輸。A.寄存器B.運(yùn)算器C.存儲(chǔ)器D.控制器11.組成計(jì)算機(jī)存儲(chǔ)器的半導(dǎo)體器件按其功能可分為（）。A.RAM和ROMB.Cache和主存C.內(nèi)存儲(chǔ)器和外存儲(chǔ)器D.DRAM和SRAM12.Cache的命中率主要取決于（）。A.Cache塊的大小B.主存塊的大小C.Cache的容量D.程序的局部性原理13.采用異步總線(xiàn)傳輸方式的主要目的是（）。A.提高總線(xiàn)傳輸速率B.減少總線(xiàn)傳輸延遲C.增強(qiáng)總線(xiàn)的負(fù)載能力D.實(shí)現(xiàn)多個(gè)設(shè)備的同時(shí)訪(fǎng)問(wèn)14.在TCP/IP協(xié)議簇中，負(fù)責(zé)將IP地址轉(zhuǎn)換為物理地址的協(xié)議是（）。A.IP協(xié)議B.TCP協(xié)議C.UDP協(xié)議D.ARP協(xié)議15.下列關(guān)于HTTP協(xié)議的描述中，正確的是（）。A.HTTP協(xié)議是一種無(wú)連接的、無(wú)狀態(tài)的協(xié)議B.HTTP協(xié)議是一種面向連接的、有狀態(tài)的協(xié)議C.HTTP協(xié)議只支持單向數(shù)據(jù)傳輸D.HTTP協(xié)議只支持文本數(shù)據(jù)的傳輸二、綜合應(yīng)用題（本大題共5小題，共120分。）16.（20分）已知一個(gè)線(xiàn)性表L采用順序存儲(chǔ)結(jié)構(gòu)表示，其存儲(chǔ)空間為elem[1..n]，其中n為線(xiàn)性表的當(dāng)前長(zhǎng)度。請(qǐng)寫(xiě)出以下算法的Python實(shí)現(xiàn)代碼：(1)設(shè)計(jì)一個(gè)函數(shù)`insert_element(L,i,x)`，用于在線(xiàn)性表L的第i個(gè)位置（1≤i≤n+1）插入元素x。若i不合法，則不進(jìn)行插入。(2)設(shè)計(jì)一個(gè)函數(shù)`delete_element(L,i)`，用于在線(xiàn)性表L中刪除第i個(gè)元素（1≤i≤n）。若i不合法，則不進(jìn)行刪除。17.（25分）假設(shè)有一個(gè)二叉搜索樹(shù)，其結(jié)點(diǎn)包含的數(shù)據(jù)域?yàn)檎麛?shù)。請(qǐng)回答以下問(wèn)題：(1)寫(xiě)出該二叉搜索樹(shù)的前序遍歷的遞歸算法。(2)假設(shè)二叉搜索樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)定義如下（用C語(yǔ)言描述）：```ctypedefstructTreeNode{intdata;structTreeNode*left;structTreeNode*right;}TreeNode;```請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)`search_bst(root,key)`，用于在二叉搜索樹(shù)中查找值為key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的指針，否則返回NULL。(3)分析在含有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中，查找一個(gè)元素的最壞情況時(shí)間復(fù)雜度。18.（25分）操作系統(tǒng)的內(nèi)存管理部分：(1)簡(jiǎn)述連續(xù)分配方式和分頁(yè)存儲(chǔ)管理方式的主要區(qū)別。(2)什么是虛擬內(nèi)存？它有哪些優(yōu)點(diǎn)？(3)設(shè)一個(gè)計(jì)算機(jī)的物理內(nèi)存大小為256MB，邏輯地址空間為1GB，采用分頁(yè)機(jī)制，頁(yè)大小為4KB。請(qǐng)計(jì)算：a.物理地址需要幾位二進(jìn)制數(shù)表示？b.邏輯地址需要幾位二進(jìn)制數(shù)表示？c.頁(yè)表需要多少個(gè)頁(yè)表項(xiàng)？19.（20分）計(jì)算機(jī)網(wǎng)絡(luò)部分：(1)解釋TCP協(xié)議三次握手過(guò)程，并說(shuō)明其目的是什么。(2)某主機(jī)A要發(fā)送一個(gè)1000字節(jié)的數(shù)據(jù)報(bào)文給主機(jī)B，經(jīng)過(guò)的路由器R1、R2、R3，假設(shè)每個(gè)路由器的處理時(shí)間（包括轉(zhuǎn)發(fā)延遲）為1ms，端到端的傳播延遲為10ms。如果TCP窗口大小為4096字節(jié)，請(qǐng)計(jì)算主機(jī)A發(fā)送數(shù)據(jù)的速率（假設(shè)不考慮頭部開(kāi)銷(xiāo)和重傳等因素）。(3)簡(jiǎn)述HTTPGET請(qǐng)求和POST請(qǐng)求的主要區(qū)別，并說(shuō)明在什么場(chǎng)景下更傾向于使用POST請(qǐng)求。20.（30分）計(jì)算機(jī)組成原理部分：(1)什么是CPU的CPI（每條指令執(zhí)行周期數(shù)）？簡(jiǎn)述影響CPI的主要因素。(2)假設(shè)某計(jì)算機(jī)的指令集包含LOAD（取數(shù)）、STORE（存數(shù)）、ADD（加法）、SUB（減法）四條指令，其CPI分別為3、3、1、1周期。若某程序包含100條LOAD指令、80條STORE指令、60條ADD指令和40條SUB指令，請(qǐng)計(jì)算該程序的平均CPI。(3)簡(jiǎn)述中斷響應(yīng)過(guò)程的主要步驟。假設(shè)某CPU的中斷請(qǐng)求優(yōu)先級(jí)由高到低依次為中斷1、中斷2、中斷3，當(dāng)前CPU正在執(zhí)行中斷1的處理程序。若此時(shí)中斷2和中斷3同時(shí)請(qǐng)求中斷，請(qǐng)問(wèn)CPU將如何響應(yīng)？（請(qǐng)說(shuō)明理由）---試卷答案一、單項(xiàng)選擇題1.D解析：稀疏矩陣壓縮存儲(chǔ)（如三元組表）能有效節(jié)省存儲(chǔ)空間，適用于表示稀疏矩陣。2.B解析：根據(jù)棧的LIFO特性，從后往前分析操作序列：-3出棧，d入棧且出棧，-2出棧，...，a入棧且出棧，b入棧且出棧，c入棧且出棧。得到入棧序列acbed。3.D解析：深度為k的二叉樹(shù)最多有2^k-1個(gè)結(jié)點(diǎn)。當(dāng)深度為5時(shí)，最多有2^5-1=31個(gè)結(jié)點(diǎn)。4.B解析：哈希表的裝填因子越大，發(fā)生沖突的可能性越大。5.A解析：根據(jù)前序遍歷ABCD和中序遍歷CBAD，可確定樹(shù)的結(jié)構(gòu)為：根結(jié)點(diǎn)為A，左子樹(shù)為CB，右子樹(shù)為D。后序遍歷為左子樹(shù)后序（DCB）+右子樹(shù)后序（D）=DCBA。6.A解析：B樹(shù)是一種平衡的多路搜索樹(shù)，保證查找路徑長(zhǎng)度不超過(guò)log_m(n+1)（m為B樹(shù)的階數(shù)，n為結(jié)點(diǎn)數(shù)）。7.D解析：插入排序和選擇排序的最壞情況時(shí)間復(fù)雜度均為O(n^2)?？焖倥判蜃顗那闆r為O(n^2)，但平均為O(nlogn)。堆排序的最壞情況時(shí)間復(fù)雜度為O(nlogn)。8.A解析：順序存儲(chǔ)結(jié)構(gòu)，在表尾插入只需在末尾添加元素，時(shí)間復(fù)雜度為O(1)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，找到表尾后插入，時(shí)間復(fù)雜度為O(1)。9.C解析：機(jī)器語(yǔ)言指令是計(jì)算機(jī)硬件能夠直接識(shí)別和執(zhí)行的二進(jìn)制代碼。10.C解析：在馮·諾依曼計(jì)算機(jī)體系結(jié)構(gòu)中，指令和數(shù)據(jù)都存儲(chǔ)在存儲(chǔ)器中。11.A解析：組成計(jì)算機(jī)存儲(chǔ)器的半導(dǎo)體器件按其功能可分為RAM（隨機(jī)存取存儲(chǔ)器）和ROM（只讀存儲(chǔ)器）。12.D解析：Cache的命中率主要取決于程序的局部性原理，即程序訪(fǎng)問(wèn)數(shù)據(jù)的集中趨勢(shì)。13.A解析：異步總線(xiàn)傳輸方式允許不同設(shè)備以自身速度傳輸數(shù)據(jù)，可以提高總線(xiàn)傳輸速率。14.D解析：ARP協(xié)議（地址解析協(xié)議）負(fù)責(zé)將IP地址轉(zhuǎn)換為物理地址（MAC地址）。15.A解析：HTTP協(xié)議是一種無(wú)連接的、無(wú)狀態(tài)的協(xié)議，每次請(qǐng)求-響應(yīng)獨(dú)立。二、綜合應(yīng)用題16.```pythondefinsert_element(L,i,x):n=len(L)ifi<1ori>n+1:return#i不合法，不插入ifn==len(L):#存儲(chǔ)空間已滿(mǎn)return#無(wú)法插入forjinrange(n,i,-1):#從后往前移動(dòng)元素L[j]=L[j-1]L[i-1]=x#在第i個(gè)位置插入xdefdelete_element(L,i):n=len(L)ifi<1ori>n:return#i不合法，不刪除forjinrange(i,n):#從i位置往后移動(dòng)元素L[j-1]=L[j]#刪除最后一個(gè)元素，釋放空間L.pop()#或者L[n-1]=None```解析：順序存儲(chǔ)結(jié)構(gòu)的插入需要在插入位置后所有元素都向后移動(dòng)。刪除則需要將刪除位置后的所有元素向前移動(dòng)。注意邊界條件檢查。17.(1)```pythondefpreorder_traversal(root):ifrootisNone:returnprint(root.data,end='')#訪(fǎng)問(wèn)根結(jié)點(diǎn)preorder_traversal(root.left)#遍歷左子樹(shù)preorder_traversal(root.right)#遍歷右子樹(shù)```解析：前序遍歷遵循“根-左-右”的順序。遞歸實(shí)現(xiàn)時(shí)，先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遞歸遍歷左子樹(shù)，最后遞歸遍歷右子樹(shù)。(2)```cTreeNode*search_bst(TreeNode*root,intkey){if(root==NULL||root->data==key){returnroot;//找到或到達(dá)葉子結(jié)點(diǎn)}if(key<root->data){returnsearch_bst(root->left,key);//在左子樹(shù)查找}else{returnsearch_bst(root->right,key);//在右子樹(shù)查找}}```解析：利用二叉搜索樹(shù)的性質(zhì)“左結(jié)點(diǎn)<根結(jié)點(diǎn)<右結(jié)點(diǎn)”，進(jìn)行遞歸查找。若當(dāng)前結(jié)點(diǎn)為空或其值等于key，則返回。否則，根據(jù)key與當(dāng)前結(jié)點(diǎn)值的比較結(jié)果，決定向左子樹(shù)或右子樹(shù)繼續(xù)查找。(3)解析：最壞情況發(fā)生在二叉搜索樹(shù)退化成鏈表時(shí)，例如輸入序列有序。此時(shí)查找時(shí)間復(fù)雜度為O(n)，與線(xiàn)性搜索相同。18.(1)解析：連續(xù)分配方式將內(nèi)存劃分成連續(xù)塊，分配效率高，但易產(chǎn)生碎片，不便于動(dòng)態(tài)擴(kuò)展。分頁(yè)存儲(chǔ)管理方式將內(nèi)存和邏輯地址都劃分成固定大小的頁(yè)，通過(guò)頁(yè)表進(jìn)行地址映射，解決了碎片問(wèn)題，支持虛擬內(nèi)存，但需要額外的頁(yè)表空間和管理開(kāi)銷(xiāo)。(2)解析：虛擬內(nèi)存是利用硬盤(pán)空間擴(kuò)展物理內(nèi)存容量的一種技術(shù)。它將內(nèi)存分為虛擬地址空間和物理地址空間，通過(guò)頁(yè)表等機(jī)制實(shí)現(xiàn)邏輯地址到物理地址的映射。優(yōu)點(diǎn)包括：克服物理內(nèi)存限制，支持更大程序運(yùn)行；實(shí)現(xiàn)內(nèi)存保護(hù)，提高系統(tǒng)安全性；通過(guò)頁(yè)面置換算法提高內(nèi)存利用率。(3)a.物理地址需要28位二進(jìn)制數(shù)表示。解析：256MB=256*1024*1024Bytes=2^28Bytes，需要28位二進(jìn)制數(shù)表示。b.邏輯地址需要30位二進(jìn)制數(shù)表示。解析：1GB=1024*1024*1024Bytes=2^30Bytes，需要30位二進(jìn)制數(shù)表示。c.頁(yè)表需要2^16=65536個(gè)頁(yè)表項(xiàng)。解析：頁(yè)表大小=邏輯地址空間大小/頁(yè)大小=2^30Bytes/2^12Bytes=2^18個(gè)頁(yè)表項(xiàng)。或者，若頁(yè)表項(xiàng)數(shù)用n表示，頁(yè)表大小為n*(頁(yè)內(nèi)地址位數(shù)+有效位)，設(shè)頁(yè)表大小為N，N=n*(12+4)=16n，則n=N/16。此處題干信息不足以直接計(jì)算n，但通常大地址空間會(huì)對(duì)應(yīng)大頁(yè)表，假設(shè)頁(yè)表項(xiàng)數(shù)為2^16（即65536），則頁(yè)表大小為65536*(12+4)=1228800位=1524KB。這與256MB/4KB=65536頁(yè)相符。假設(shè)頁(yè)表項(xiàng)數(shù)為2^18=262144，則頁(yè)表大小為262144*(12+4)=4194304位=5120KB。若按2^16計(jì)算更合理。19.(1)解析：TCP三次握手過(guò)程為：1.主機(jī)A向主機(jī)B發(fā)送SYN=1，seq=x的報(bào)文。2.主機(jī)B向主機(jī)A發(fā)送SYN=1，ACK=1，seq=y，ack=x+1的報(bào)文。3.主機(jī)A向主機(jī)B發(fā)送ACK=1，seq=x+1，ack=y+1的報(bào)文。目的是雙方確認(rèn)彼此的發(fā)送和接收能力，并同步初始序列號(hào)，建立可靠的連接。(2)解析：總端到端延遲=傳播延遲+處理延遲=10ms+3*1ms=13ms。數(shù)據(jù)總長(zhǎng)度=1000字節(jié)+TCP頭部長(zhǎng)度（假設(shè)20字節(jié)）=1020字節(jié)。主機(jī)A發(fā)送速率為數(shù)據(jù)長(zhǎng)度/延遲=1020字節(jié)/0.013秒=78461.54字節(jié)/秒≈78.5KB/s。(3)解析：HTTPGET請(qǐng)求用于獲取資源，請(qǐng)求負(fù)載通常在URL中或請(qǐng)求體（POST/PUT）中，無(wú)狀態(tài)。