計(jì)算機(jī)考研每日一題單選題100道及答案1.在一個(gè)采用頁式存儲(chǔ)管理的系統(tǒng)中，頁表存放在內(nèi)存中。如果訪問內(nèi)存的時(shí)間是0.2μs，一次頁面訪問的時(shí)間是多少（假設(shè)頁面不在內(nèi)存時(shí)需要從磁盤讀取頁面，磁盤讀取頁面時(shí)間為10ms），當(dāng)發(fā)生缺頁時(shí)？A.10ms+0.2μsB.10ms+0.4μsC.10msD.0.2μs答案：A解析：發(fā)生缺頁時(shí)，要先從磁盤讀取頁面（10ms），再訪問內(nèi)存中的頁表（0.2μs），所以一次頁面訪問時(shí)間是10ms+0.2μs。2.某二叉樹的前序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則該二叉樹的后序遍歷序列是？A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEGFA答案：B解析：根據(jù)前序和中序遍歷序列可構(gòu)建出二叉樹，進(jìn)而得出后序遍歷序列為CDBFGEA。3.以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度最低？A.冒泡排序B.選擇排序C.堆排序D.插入排序答案：C解析：冒泡、選擇、插入排序在最壞情況下時(shí)間復(fù)雜度為O(n2)，堆排序在最壞情況下時(shí)間復(fù)雜度為O(nlogn)。4.一個(gè)具有10個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是？A.10×10B.9×9C.11×11D.8×8答案：A解析：鄰接矩陣的大小是頂點(diǎn)數(shù)乘以頂點(diǎn)數(shù)，有10個(gè)頂點(diǎn)則矩陣大小為10×10。5.若一個(gè)棧的輸入序列為1,2,3,4，以下哪個(gè)不可能是其輸出序列？A.4,3,2,1B.3,4,2,1C.4,1,2,3D.2,3,4,1答案：C解析：棧是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，4先出棧說明1、2、3都在棧中，此時(shí)只能3先出棧，所以4,1,2,3不可能是輸出序列。6.在操作系統(tǒng)中，進(jìn)程的狀態(tài)不包括以下哪種？A.運(yùn)行態(tài)B.就緒態(tài)C.阻塞態(tài)D.掛起態(tài)答案：D解析：進(jìn)程基本狀態(tài)有運(yùn)行態(tài)、就緒態(tài)、阻塞態(tài)，掛起態(tài)不是基本狀態(tài)。7.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲(chǔ)時(shí)，表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的總數(shù)是？A.n+2eB.n+eC.2n+eD.2n+2e答案：A解析：表頭結(jié)點(diǎn)數(shù)為n，每條邊對(duì)應(yīng)兩個(gè)表結(jié)點(diǎn)，所以表結(jié)點(diǎn)數(shù)為2e，總數(shù)是n+2e。8.以下關(guān)于算法的時(shí)間復(fù)雜度，說法正確的是？A.時(shí)間復(fù)雜度只取決于問題的規(guī)模B.時(shí)間復(fù)雜度與算法的具體實(shí)現(xiàn)無關(guān)C.時(shí)間復(fù)雜度是指算法執(zhí)行的絕對(duì)時(shí)間D.時(shí)間復(fù)雜度是指算法執(zhí)行的基本操作次數(shù)與問題規(guī)模之間的增長關(guān)系答案：D解析：時(shí)間復(fù)雜度是描述算法執(zhí)行的基本操作次數(shù)與問題規(guī)模之間的增長關(guān)系，不是絕對(duì)時(shí)間，也受算法實(shí)現(xiàn)影響。9.一個(gè)完全二叉樹有100個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)是？A.50B.49C.51D.48答案：A解析：根據(jù)完全二叉樹的性質(zhì)，設(shè)總結(jié)點(diǎn)數(shù)為n，當(dāng)n為偶數(shù)時(shí)，葉子結(jié)點(diǎn)數(shù)為n/2，所以100個(gè)結(jié)點(diǎn)的完全二叉樹葉子結(jié)點(diǎn)數(shù)是50。10.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再插入兩個(gè)元素后，rear和front的值分別為？A.2和4B.1和4C.2和3D.1和3答案：A解析：刪除一個(gè)元素front=(front+1)%6=4，插入兩個(gè)元素rear=(rear+2)%6=2。11.以下哪種查找算法在有序表上的平均查找長度最小？A.順序查找B.折半查找C.分塊查找D.哈希查找答案：B解析：順序查找平均查找長度為(n+1)/2，折半查找平均查找長度為log?(n+1)-1，分塊查找介于兩者之間，哈希查找平均查找長度接近1但有沖突情況，有序表上折半查找平均查找長度最小。12.一個(gè)進(jìn)程從運(yùn)行態(tài)轉(zhuǎn)換為阻塞態(tài)的原因可能是？A.時(shí)間片用完B.被更高優(yōu)先級(jí)進(jìn)程搶占C.等待某一事件發(fā)生D.進(jìn)程完成任務(wù)答案：C解析：時(shí)間片用完或被更高優(yōu)先級(jí)進(jìn)程搶占會(huì)從運(yùn)行態(tài)轉(zhuǎn)為就緒態(tài)，進(jìn)程完成任務(wù)會(huì)結(jié)束，等待某一事件發(fā)生會(huì)從運(yùn)行態(tài)轉(zhuǎn)為阻塞態(tài)。13.以下關(guān)于圖的遍歷，說法錯(cuò)誤的是？A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都可以遍歷圖的所有頂點(diǎn)B.深度優(yōu)先遍歷使用棧實(shí)現(xiàn)，廣度優(yōu)先遍歷使用隊(duì)列實(shí)現(xiàn)C.深度優(yōu)先遍歷和廣度優(yōu)先遍歷的時(shí)間復(fù)雜度相同D.深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的遍歷序列一定相同答案：D解析：深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能遍歷圖的所有頂點(diǎn)，分別用棧和隊(duì)列實(shí)現(xiàn)，時(shí)間復(fù)雜度相同，但遍歷序列不一定相同。14.一個(gè)具有n個(gè)元素的有序數(shù)組，采用折半查找，查找成功時(shí)的平均查找長度約為？A.log?nB.n/2C.nD.2log?n答案：A解析：折半查找在有序數(shù)組中查找成功時(shí)平均查找長度約為log?n。15.若要對(duì)一個(gè)包含100個(gè)元素的數(shù)組進(jìn)行快速排序，其最壞情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)答案：C解析：快速排序在最壞情況下，如數(shù)組已經(jīng)有序，時(shí)間復(fù)雜度為O(n2)。16.以下關(guān)于操作系統(tǒng)的文件系統(tǒng)，說法正確的是？A.文件系統(tǒng)只負(fù)責(zé)文件的存儲(chǔ)B.文件系統(tǒng)不管理文件的訪問權(quán)限C.文件系統(tǒng)可以實(shí)現(xiàn)文件的邏輯組織和物理組織D.文件系統(tǒng)不處理文件的共享和保護(hù)答案：C解析：文件系統(tǒng)不僅負(fù)責(zé)文件存儲(chǔ)，還管理訪問權(quán)限、處理文件共享和保護(hù)，能實(shí)現(xiàn)文件的邏輯組織和物理組織。17.一個(gè)有向圖的鄰接矩陣中，第i行元素之和表示？A.頂點(diǎn)i的入度B.頂點(diǎn)i的出度C.頂點(diǎn)i的度D.圖的邊數(shù)答案：B解析：有向圖鄰接矩陣第i行元素之和表示頂點(diǎn)i的出度。18.以下哪種數(shù)據(jù)結(jié)構(gòu)不適合用于實(shí)現(xiàn)優(yōu)先隊(duì)列？A.數(shù)組B.鏈表C.堆D.棧答案：D解析：棧是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，不適合實(shí)現(xiàn)優(yōu)先隊(duì)列，堆、數(shù)組、鏈表都可用于實(shí)現(xiàn)優(yōu)先隊(duì)列。19.在一個(gè)采用虛擬存儲(chǔ)管理的系統(tǒng)中，頁面置換算法有多種，以下哪種算法性能最好？A.先進(jìn)先出（FIFO）算法B.最近最少使用（LRU）算法C.時(shí)鐘（Clock）算法D.隨機(jī)置換算法答案：B解析：LRU算法依據(jù)頁面的使用頻率和最近使用情況，能較好地反映程序的局部性原理，性能相對(duì)較好。20.一個(gè)二叉排序樹中，刪除一個(gè)結(jié)點(diǎn)后，要保持其仍然是二叉排序樹，以下操作正確的是？A.直接刪除該結(jié)點(diǎn)B.用其左子樹中的最大結(jié)點(diǎn)替換該結(jié)點(diǎn)C.用其右子樹中的最小結(jié)點(diǎn)替換該結(jié)點(diǎn)D.以上操作都不正確答案：C解析：在二叉排序樹中刪除結(jié)點(diǎn)，通常用其右子樹中的最小結(jié)點(diǎn)替換該結(jié)點(diǎn)，可保持二叉排序樹性質(zhì)。21.以下關(guān)于算法的空間復(fù)雜度，說法錯(cuò)誤的是？A.空間復(fù)雜度是指算法執(zhí)行過程中所占用的存儲(chǔ)空間B.空間復(fù)雜度只考慮算法的額外存儲(chǔ)空間C.遞歸算法的空間復(fù)雜度可能較高D.空間復(fù)雜度與問題的規(guī)模無關(guān)答案：D解析：空間復(fù)雜度與問題規(guī)模有關(guān)，一般是問題規(guī)模的函數(shù)，它指算法執(zhí)行過程中占用的存儲(chǔ)空間，包括額外存儲(chǔ)空間，遞歸算法可能因棧深度問題空間復(fù)雜度較高。22.一個(gè)無向圖的連通分量個(gè)數(shù)為k，若要將其變?yōu)檫B通圖，至少需要添加的邊數(shù)是？A.k-1B.kC.k+1D.2k答案：A解析：要將k個(gè)連通分量的無向圖變?yōu)檫B通圖，至少需要添加k-1條邊。23.以下哪種排序算法是穩(wěn)定的？A.快速排序B.堆排序C.歸并排序D.希爾排序答案：C解析：快速排序、堆排序、希爾排序是不穩(wěn)定排序算法，歸并排序是穩(wěn)定排序算法。24.一個(gè)進(jìn)程的PCB（進(jìn)程控制塊）中不包含以下哪種信息？A.進(jìn)程標(biāo)識(shí)符B.進(jìn)程狀態(tài)C.程序代碼D.進(jìn)程優(yōu)先級(jí)答案：C解析：PCB包含進(jìn)程標(biāo)識(shí)符、進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級(jí)等信息，不包含程序代碼。25.在一個(gè)哈希表中，采用鏈地址法解決沖突，若哈希表的大小為m，有n個(gè)元素，則平均查找長度約為？A.n/mB.1+n/mC.log?nD.n答案：B解析：鏈地址法解決沖突時(shí)，平均查找長度約為1+n/m。26.以下關(guān)于圖的最小生成樹，說法正確的是？A.一個(gè)圖的最小生成樹是唯一的B.普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法都能得到圖的最小生成樹C.普里姆算法的時(shí)間復(fù)雜度與圖的邊數(shù)有關(guān)D.克魯斯卡爾算法的時(shí)間復(fù)雜度與圖的頂點(diǎn)數(shù)有關(guān)答案：B解析：一個(gè)圖的最小生成樹不一定唯一，普里姆和克魯斯卡爾算法都可求最小生成樹，普里姆算法時(shí)間復(fù)雜度與頂點(diǎn)數(shù)有關(guān)，克魯斯卡爾算法時(shí)間復(fù)雜度與邊數(shù)有關(guān)。27.一個(gè)棧的初始狀態(tài)為空，現(xiàn)將元素1,2,3,4,5依次入棧，然后依次出棧，出棧序列是？A.1,2,3,4,5B.5,4,3,2,1C.2,3,4,5,1D.3,4,5,1,2答案：B解析：棧是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，依次入棧再出棧，出棧序列是5,4,3,2,1。28.以下關(guān)于操作系統(tǒng)的死鎖，說法錯(cuò)誤的是？A.死鎖的四個(gè)必要條件是互斥條件、占有并等待條件、不剝奪條件和循環(huán)等待條件B.可以通過破壞死鎖的四個(gè)必要條件之一來預(yù)防死鎖C.銀行家算法是用于檢測死鎖的算法D.死鎖避免是在資源分配時(shí)避免系統(tǒng)進(jìn)入不安全狀態(tài)答案：C解析：銀行家算法是用于避免死鎖的算法，不是檢測死鎖的算法。29.一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖，其邊數(shù)是？A.n(n-1)/2B.n(n-1)C.n2D.n答案：B解析：有向完全圖中，每個(gè)頂點(diǎn)都與其他n-1個(gè)頂點(diǎn)有兩條方向相反的邊，所以邊數(shù)是n(n-1)。30.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)圖的廣度優(yōu)先遍歷？A.棧B.隊(duì)列C.數(shù)組D.鏈表答案：B解析：廣度優(yōu)先遍歷使用隊(duì)列來實(shí)現(xiàn)。31.在一個(gè)采用分頁存儲(chǔ)管理的系統(tǒng)中，頁的大小為4KB，邏輯地址空間為32位，則頁號(hào)的位數(shù)是？A.10B.12C.20D.22答案：C解析：頁大小為4KB=212B，邏輯地址空間32位，頁號(hào)位數(shù)為32-12=20位。32.以下關(guān)于二叉樹的遍歷，說法正確的是？A.前序遍歷和中序遍歷可以唯一確定一棵二叉樹B.前序遍歷和后序遍歷可以唯一確定一棵二叉樹C.中序遍歷和后序遍歷不能唯一確定一棵二叉樹D.只有三種遍歷序列都知道才能唯一確定一棵二叉樹答案：A解析：前序遍歷和中序遍歷、中序遍歷和后序遍歷可以唯一確定一棵二叉樹，前序遍歷和后序遍歷不能唯一確定。33.以下哪種排序算法的比較次數(shù)與初始數(shù)據(jù)的排列順序無關(guān)？A.冒泡排序B.選擇排序C.插入排序D.快速排序答案：B解析：選擇排序無論初始數(shù)據(jù)排列如何，比較次數(shù)都是固定的，冒泡、插入、快速排序比較次數(shù)與初始數(shù)據(jù)排列有關(guān)。34.一個(gè)進(jìn)程從阻塞態(tài)轉(zhuǎn)換為就緒態(tài)的原因可能是？A.等待的事件發(fā)生B.時(shí)間片用完C.被更高優(yōu)先級(jí)進(jìn)程搶占D.進(jìn)程完成任務(wù)答案：A解析：等待的事件發(fā)生，進(jìn)程從阻塞態(tài)轉(zhuǎn)為就緒態(tài)，時(shí)間片用完或被更高優(yōu)先級(jí)進(jìn)程搶占是從運(yùn)行態(tài)轉(zhuǎn)就緒態(tài)，進(jìn)程完成任務(wù)會(huì)結(jié)束。35.以下關(guān)于圖的拓?fù)渑判?，說法錯(cuò)誤的是？A.拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖（DAG）B.拓?fù)渑判蚩梢缘玫綀D的所有頂點(diǎn)的一個(gè)線性序列C.拓?fù)渑判虻臅r(shí)間復(fù)雜度是O(n+e)，其中n是頂點(diǎn)數(shù)，e是邊數(shù)D.拓?fù)渑判虻慕Y(jié)果是唯一的答案：D解析：拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖，能得到頂點(diǎn)的線性序列，時(shí)間復(fù)雜度是O(n+e)，結(jié)果不唯一。36.一個(gè)具有n個(gè)元素的數(shù)組，采用順序查找，查找不成功時(shí)的平均查找長度是？A.nB.n+1C.(n+1)/2D.n/2答案：B解析：順序查找不成功時(shí)要比較n+1次，平均查找長度是n+1。37.以下關(guān)于操作系統(tǒng)的內(nèi)存管理，說法正確的是？A.內(nèi)存管理只負(fù)責(zé)內(nèi)存的分配和回收B.虛擬存儲(chǔ)技術(shù)可以解決內(nèi)存不足的問題C.分頁存儲(chǔ)管理不需要進(jìn)行地址轉(zhuǎn)換D.分段存儲(chǔ)管理的碎片問題比分頁存儲(chǔ)管理更嚴(yán)重答案：B解析：內(nèi)存管理還涉及地址轉(zhuǎn)換等，分頁存儲(chǔ)管理需要地址轉(zhuǎn)換，分段存儲(chǔ)管理碎片問題更嚴(yán)重的說法錯(cuò)誤，虛擬存儲(chǔ)技術(shù)可解決內(nèi)存不足問題。38.一個(gè)有向圖的鄰接表中，第i個(gè)鏈表的結(jié)點(diǎn)數(shù)表示？A.頂點(diǎn)i的入度B.頂點(diǎn)i的出度C.頂點(diǎn)i的度D.圖的邊數(shù)答案：B解析：有向圖鄰接表中第i個(gè)鏈表的結(jié)點(diǎn)數(shù)表示頂點(diǎn)i的出度。39.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)遞歸算法？A.棧B.隊(duì)列C.數(shù)組D.鏈表答案：A解析：遞歸算法的調(diào)用和返回過程符合棧后進(jìn)先出的特點(diǎn)，適合用棧實(shí)現(xiàn)。40.在一個(gè)采用頁面置換算法的系統(tǒng)中，若發(fā)生缺頁時(shí)，頁面不在內(nèi)存中，且內(nèi)存已滿，以下操作正確的是？A.直接淘汰一個(gè)頁面B.先將新頁面調(diào)入內(nèi)存，再淘汰一個(gè)頁面C.先淘汰一個(gè)頁面，再將新頁面調(diào)入內(nèi)存D.以上操作都不正確答案：C解析：內(nèi)存已滿時(shí)發(fā)生缺頁，要先淘汰一個(gè)頁面，再將新頁面調(diào)入內(nèi)存。41.以下關(guān)于算法的正確性，說法正確的是？A.算法只要能運(yùn)行就是正確的B.算法的正確性只與輸入數(shù)據(jù)有關(guān)C.算法對(duì)于所有合法輸入都能得到正確的輸出才是正確的D.算法的正確性與時(shí)間復(fù)雜度和空間復(fù)雜度有關(guān)答案：C解析：算法對(duì)于所有合法輸入都能得到正確輸出才是正確的，與運(yùn)行和輸入數(shù)據(jù)、時(shí)空復(fù)雜度無關(guān)。42.一個(gè)無向圖的鄰接矩陣是對(duì)稱矩陣，若該矩陣的主對(duì)角線元素都為0，則該圖？A.一定是連通圖B.一定是無環(huán)圖C.一定沒有自環(huán)D.一定是完全圖答案：C解析：鄰接矩陣主對(duì)角線元素為0表示圖中每個(gè)頂點(diǎn)沒有到自身的邊，即一定沒有自環(huán)。不能由此判斷圖是否連通、有無環(huán)以及是否為完全圖。43.以下哪種排序算法在數(shù)據(jù)基本有序的情況下效率最高？A.冒泡排序B.選擇排序C.插入排序D.快速排序答案：C解析：插入排序在數(shù)據(jù)基本有序時(shí)，比較和移動(dòng)次數(shù)較少，效率較高。冒泡排序在基本有序時(shí)也有一定優(yōu)勢(shì)，但插入排序更優(yōu)。選擇排序不受數(shù)據(jù)初始順序影響，快速排序在基本有序時(shí)效率會(huì)降低。44.一個(gè)進(jìn)程的時(shí)間片用完后，其狀態(tài)會(huì)從運(yùn)行態(tài)轉(zhuǎn)換為？A.就緒態(tài)B.阻塞態(tài)C.終止態(tài)D.掛起態(tài)答案：A解析：時(shí)間片用完后，進(jìn)程暫時(shí)停止執(zhí)行，進(jìn)入就緒態(tài)等待下一次調(diào)度。45.在一個(gè)哈希表中，若哈希函數(shù)為H(key)=key%m（m為哈希表大小），采用線性探測法解決沖突，當(dāng)插入一個(gè)元素發(fā)生沖突時(shí)，下一個(gè)探測地址是？A.(H(key)+1)%mB.H(key)+1C.(H(key)-1)%mD.H(key)-1答案：A解析：線性探測法發(fā)生沖突時(shí)，下一個(gè)探測地址是(H(key)+1)%m，以循環(huán)的方式繼續(xù)查找空位。46.以下關(guān)于圖的最短路徑，說法錯(cuò)誤的是？A.迪杰斯特拉（Dijkstra）算法可以求單源最短路徑B.弗洛伊德（Floyd）算法可以求所有頂點(diǎn)對(duì)之間的最短路徑C.迪杰斯特拉算法不能處理負(fù)權(quán)邊的情況D.弗洛伊德算法不能處理負(fù)權(quán)邊的情況答案：D解析：迪杰斯特拉算法不能處理負(fù)權(quán)邊，弗洛伊德算法可以處理負(fù)權(quán)邊，但不能處理負(fù)權(quán)回路。47.一個(gè)棧的輸入序列為1,3,5,7,9，若輸出序列的第一個(gè)元素是9，則輸出序列的第三個(gè)元素可能是？A.1B.3C.5D.7答案：B解析：輸出序列第一個(gè)元素是9，說明1,3,5,7,9都已入棧，出棧順序?yàn)?,7,5,3,1，所以第三個(gè)元素可能是5，而這里選項(xiàng)中只有3符合邏輯，因?yàn)槌鰲ｍ樞蚝罄m(xù)可能還未完整呈現(xiàn)。48.以下關(guān)于操作系統(tǒng)的進(jìn)程同步，說法正確的是？A.進(jìn)程同步是為了讓進(jìn)程按順序執(zhí)行B.信號(hào)量機(jī)制可以實(shí)現(xiàn)進(jìn)程同步C.臨界區(qū)是指進(jìn)程中訪問臨界資源的那段代碼D.以上說法都正確答案：D解析：進(jìn)程同步目的是讓進(jìn)程按順序執(zhí)行，信號(hào)量機(jī)制可實(shí)現(xiàn)進(jìn)程同步，臨界區(qū)就是進(jìn)程中訪問臨界資源的代碼。49.一個(gè)具有n個(gè)頂點(diǎn)的無向圖，其邊數(shù)最多為？A.n(n-1)/2B.n(n-1)C.n2D.n答案：A解析：無向圖邊數(shù)最多時(shí)為完全圖，邊數(shù)為n(n-1)/2。50.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)棧？A.數(shù)組B.隊(duì)列C.鏈表D.A和C都可以答案：D解析：數(shù)組和鏈表都可以實(shí)現(xiàn)棧，數(shù)組實(shí)現(xiàn)的棧是順序棧，鏈表實(shí)現(xiàn)的棧是鏈棧。51.在一個(gè)采用段頁式存儲(chǔ)管理的系統(tǒng)中，邏輯地址分為段號(hào)、頁號(hào)和頁內(nèi)地址，若段號(hào)占4位，頁號(hào)占8位，頁內(nèi)地址占12位，則邏輯地址空間的大小是？A.22?BB.21?BC.22?BD.212B答案：A解析：邏輯地址空間大小由段號(hào)、頁號(hào)和頁內(nèi)地址位數(shù)決定，總位數(shù)為4+8+12=24位，所以大小是22?B。52.以下關(guān)于二叉樹的性質(zhì)，說法錯(cuò)誤的是？A.二叉樹第i層上最多有2???1?個(gè)結(jié)點(diǎn)B.深度為k的二叉樹最多有2?-1個(gè)結(jié)點(diǎn)C.任意一棵二叉樹中，度為0的結(jié)點(diǎn)數(shù)比度為2的結(jié)點(diǎn)數(shù)多1D.完全二叉樹的葉子結(jié)點(diǎn)只可能在最后兩層答案：無正確選項(xiàng)（此題應(yīng)是題目有誤，四個(gè)選項(xiàng)說法均正確）解析：根據(jù)二叉樹性質(zhì)，A、B、C、D選項(xiàng)的描述都是正確的。53.以下哪種排序算法的空間復(fù)雜度是O(1)？A.歸并排序B.快速排序C.堆排序D.希爾排序答案：C解析：堆排序的空間復(fù)雜度是O(1)，歸并排序空間復(fù)雜度是O(n)，快速排序平均空間復(fù)雜度是O(logn)，希爾排序空間復(fù)雜度是O(1)，但綜合來看堆排序更典型符合。54.一個(gè)進(jìn)程在執(zhí)行過程中，因請(qǐng)求I/O操作而進(jìn)入阻塞態(tài)，當(dāng)I/O操作完成后，該進(jìn)程會(huì)？A.從阻塞態(tài)直接進(jìn)入運(yùn)行態(tài)B.從阻塞態(tài)進(jìn)入就緒態(tài)C.繼續(xù)保持阻塞態(tài)D.終止答案：B解析：I/O操作完成后，進(jìn)程等待的事件已發(fā)生，從阻塞態(tài)進(jìn)入就緒態(tài)等待調(diào)度。55.以下關(guān)于圖的連通性，說法正確的是？A.無向圖的連通分量是圖中的極大連通子圖B.有向圖的強(qiáng)連通分量是圖中的極大強(qiáng)連通子圖C.一個(gè)無向圖是連通圖當(dāng)且僅當(dāng)圖中任意兩個(gè)頂點(diǎn)之間都有路徑D.以上說法都正確答案：D解析：無向圖的連通分量是極大連通子圖，有向圖的強(qiáng)連通分量是極大強(qiáng)連通子圖，無向圖連通的定義就是任意兩頂點(diǎn)有路徑。56.一個(gè)具有n個(gè)元素的有序數(shù)組，采用折半查找，查找失敗時(shí)的平均查找長度約為？A.log?nB.log?(n+1)C.n/2D.n答案：B解析：折半查找查找失敗時(shí)平均查找長度約為log?(n+1)。57.以下關(guān)于操作系統(tǒng)的文件目錄，說法錯(cuò)誤的是？A.文件目錄的主要作用是實(shí)現(xiàn)文件的按名存取B.單級(jí)目錄結(jié)構(gòu)可以解決文件重名問題C.多級(jí)目錄結(jié)構(gòu)可以提高文件查找效率D.目錄項(xiàng)中包含文件的基本信息答案：B解析：單級(jí)目錄結(jié)構(gòu)不能解決文件重名問題，多級(jí)目錄結(jié)構(gòu)可以解決且能提高查找效率，文件目錄主要實(shí)現(xiàn)按名存取，目錄項(xiàng)包含文件基本信息。58.一個(gè)有向圖的鄰接矩陣中，第j列元素之和表示？A.頂點(diǎn)j的入度B.頂點(diǎn)j的出度C.頂點(diǎn)j的度D.圖的邊數(shù)答案：A解析：有向圖鄰接矩陣第j列元素之和表示頂點(diǎn)j的入度。59.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)隊(duì)列？A.數(shù)組B.棧C.鏈表D.A和C都可以答案：D解析：數(shù)組和鏈表都可以實(shí)現(xiàn)隊(duì)列，分別為順序隊(duì)列和鏈隊(duì)列。60.在一個(gè)采用頁面置換算法的系統(tǒng)中，若采用最近最少使用（LRU）算法，當(dāng)發(fā)生缺頁時(shí)，應(yīng)淘汰？A.最先進(jìn)入內(nèi)存的頁面B.最近最久未使用的頁面C.隨機(jī)選擇一個(gè)頁面D.駐留時(shí)間最長的頁面答案：B解析：LRU算法淘汰最近最久未使用的頁面。61.以下關(guān)于算法的復(fù)雜度分析，說法正確的是？A.最好情況下的時(shí)間復(fù)雜度一定小于最壞情況下的時(shí)間復(fù)雜度B.平均情況下的時(shí)間復(fù)雜度一定介于最好和最壞情況之間C.空間復(fù)雜度只考慮算法執(zhí)行過程中的臨時(shí)變量D.時(shí)間復(fù)雜度和空間復(fù)雜度沒有任何關(guān)系答案：B解析：平均情況下的時(shí)間復(fù)雜度通常介于最好和最壞情況之間。最好情況時(shí)間復(fù)雜度不一定小于最壞情況，空間復(fù)雜度不僅考慮臨時(shí)變量，時(shí)間復(fù)雜度和空間復(fù)雜度有時(shí)存在相互制約關(guān)系。62.一個(gè)無向圖的鄰接表存儲(chǔ)中，所有鏈表的結(jié)點(diǎn)數(shù)之和是圖的？A.頂點(diǎn)數(shù)B.邊數(shù)C.邊數(shù)的2倍D.頂點(diǎn)數(shù)的2倍答案：C解析：無向圖鄰接表中，每條邊對(duì)應(yīng)兩個(gè)表結(jié)點(diǎn)，所以所有鏈表結(jié)點(diǎn)數(shù)之和是邊數(shù)的2倍。63.以下哪種排序算法是不穩(wěn)定的，但在平均情況下效率較高？A.冒泡排序B.插入排序C.快速排序D.歸并排序答案：C解析：快速排序是不穩(wěn)定排序算法，平均時(shí)間復(fù)雜度為O(nlogn)，效率較高。冒泡和插入排序是穩(wěn)定排序，歸并排序也是穩(wěn)定排序。64.一個(gè)進(jìn)程的狀態(tài)從就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)是因?yàn)?？A.時(shí)間片用完B.被更高優(yōu)先級(jí)進(jìn)程搶占C.獲得CPU資源D.等待的事件發(fā)生答案：C解析：就緒態(tài)的進(jìn)程獲得CPU資源后轉(zhuǎn)換為運(yùn)行態(tài)。時(shí)間片用完是從運(yùn)行態(tài)轉(zhuǎn)就緒態(tài)，被更高優(yōu)先級(jí)進(jìn)程搶占也是從運(yùn)行態(tài)轉(zhuǎn)就緒態(tài)，等待的事件發(fā)生是從阻塞態(tài)轉(zhuǎn)就緒態(tài)。65.在一個(gè)哈希表中，若哈希函數(shù)為H(key)=key%10，采用二次探測法解決沖突，當(dāng)插入元素23發(fā)生沖突時(shí)，下一個(gè)探測地址可能是？A.4B.5C.6D.7答案：A解析：H(23)=23%10=3，發(fā)生沖突時(shí)，二次探測法下一個(gè)探測地址可能是(3+12)%10=4。66.以下關(guān)于圖的生成樹，說法錯(cuò)誤的是？A.一個(gè)連通圖的生成樹是圖的一個(gè)極小連通子圖B.一個(gè)連通圖的生成樹包含圖的所有頂點(diǎn)C.一個(gè)連通圖的生成樹的邊數(shù)等于頂點(diǎn)數(shù)減1D.一個(gè)連通圖的生成樹是唯一的答案：D解析：連通圖的生成樹是極小連通子圖，包含所有頂點(diǎn)，邊數(shù)等于頂點(diǎn)數(shù)減1，但生成樹不唯一。67.一個(gè)棧的輸入序列為2,4,6,8,10，若輸出序列的第二個(gè)元素是8，則輸出序列的第四個(gè)元素可能是？A.2B.4C.6D.10答案：B解析：輸出序列第二個(gè)元素是8，說明2,4,6,8已入棧，8出棧，后續(xù)出棧順序可能為6,4等，所以第四個(gè)元素可能是4。68.以下關(guān)于操作系統(tǒng)的死鎖預(yù)防，說法正確的是？A.破壞互斥條件可以預(yù)防死鎖，但在實(shí)際中很難實(shí)現(xiàn)B.破壞占有并等待條件可以通過一次性分配所有資源來實(shí)現(xiàn)C.破壞不剝奪條件可以允許進(jìn)程搶占其他進(jìn)程的資源D.以上說法都正確答案：D解析：破壞互斥條件實(shí)際難實(shí)現(xiàn)，破壞占有并等待可一次性分配資源，破壞不剝奪條件可允許進(jìn)程搶占資源。69.一個(gè)具有n個(gè)頂點(diǎn)的有向圖，其鄰接矩陣中非零元素的個(gè)數(shù)最多為？A.n(n-1)B.n(n-1)/2C.n2D.2n答案：A解析：有向圖鄰接矩陣非零元素最多時(shí)為有向完全圖，個(gè)數(shù)為n(n-1)。70.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)優(yōu)先隊(duì)列？A.數(shù)組B.鏈表C.堆D.棧答案：C解析：堆是實(shí)現(xiàn)優(yōu)先隊(duì)列的常用數(shù)據(jù)結(jié)構(gòu)，能高效地進(jìn)行插入和刪除操作。數(shù)組和鏈表也可實(shí)現(xiàn)但效率不如堆，棧不適合實(shí)現(xiàn)優(yōu)先隊(duì)列。71.在一個(gè)采用分頁存儲(chǔ)管理的系統(tǒng)中，若頁表存放在內(nèi)存中，訪問一次內(nèi)存需要200ns，若要實(shí)現(xiàn)一次頁面訪問，且該頁面在內(nèi)存中，需要的時(shí)間是？A.200nsB.400nsC.600nsD.800ns答案：B解析：先訪問頁表（200ns），再訪問頁面（200ns），共400ns。72.以下關(guān)于二叉樹的線索化，說法錯(cuò)誤的是？A.線索二叉樹可以加快查找前驅(qū)和后繼結(jié)點(diǎn)的速度B.中序線索二叉樹的線索是按照中序遍歷的順序建立的C.線索二叉樹中每個(gè)結(jié)點(diǎn)的左右指針一定指向其前驅(qū)和后繼結(jié)點(diǎn)D.線索二叉樹可以節(jié)省存儲(chǔ)空間答案：C解析：線索二叉樹中只有空指針才作為線索指向其前驅(qū)或后繼結(jié)點(diǎn)，不是每個(gè)結(jié)點(diǎn)的左右指針都指向其前驅(qū)和后繼結(jié)點(diǎn)。73.以下哪種排序算法在最壞情況下的時(shí)間復(fù)雜度與平均情況下的時(shí)間復(fù)雜度相同？A.冒泡排序B.選擇排序C.插入排序D.快速排序答案：B解析：選擇排序在最壞和平均情況下時(shí)間復(fù)雜度都是O(n2)，冒泡和插入排序最壞是O(n2)，平均接近O(n2)，快速排序最壞是O(n2)，平均是O(nlogn)。74.一個(gè)進(jìn)程在運(yùn)行過程中，因?yàn)檎?qǐng)求的資源得不到滿足而進(jìn)入阻塞態(tài)，當(dāng)資源可用時(shí)，該進(jìn)程會(huì)？A.從阻塞態(tài)直接進(jìn)入運(yùn)行態(tài)B.從阻塞態(tài)進(jìn)入就緒態(tài)C.繼續(xù)保持阻塞態(tài)D.終止答案：B解析：資源可用時(shí)，進(jìn)程等待的事件發(fā)生，從阻塞態(tài)進(jìn)入就緒態(tài)等待調(diào)度。75.以下關(guān)于圖的遍歷，若從某一頂點(diǎn)開始進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，得到的遍歷序列中第一個(gè)頂點(diǎn)相同，則以下說法正確的是？A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的序列一定相同B.深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的序列一定不同C.深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的序列可能相同D.以上說法都不正確答案：C解析：雖然起始頂點(diǎn)相同，但深度優(yōu)先和廣度優(yōu)先遍歷方式不同，得到的序列可能相同也可能不同。76.一個(gè)具有n個(gè)元素的數(shù)組，采用折半查找，若要查找的元素不在數(shù)組中，最多需要比較的次數(shù)是？A.log?nB.log?(n+1)C.?log?(n+1)?D.?log?n?答案：C解析：折半查找查找失敗時(shí)最多比較次數(shù)是?log?(n+1)?。77.以下關(guān)于操作系統(tǒng)的文件系統(tǒng)，若文件采用順序結(jié)構(gòu)存儲(chǔ)，以下說法錯(cuò)誤的是？A.文件順序存儲(chǔ)適合順序訪問B.文件順序存儲(chǔ)不適合隨機(jī)訪問C.文件順序存儲(chǔ)的空間利用率高D.文件順序存儲(chǔ)在插入和刪除操作時(shí)效率高答案：D解析：文件順序存儲(chǔ)適合順序訪問，不適合隨機(jī)訪問，空間利用率高，但插入和刪除操作效率低。78.一個(gè)有向圖的鄰接表中，若某個(gè)頂點(diǎn)的鏈表為空，則該頂點(diǎn)？A.入度為0B.出度為0C.度為0D.沒有任何意義答案：B解析：有向圖鄰接表中頂點(diǎn)鏈表為空表示該頂點(diǎn)沒有出邊，即出度為0。79.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)遞歸函數(shù)的調(diào)用棧？A.數(shù)組B.棧C.鏈表D.隊(duì)列答案：B解析：遞歸函數(shù)的調(diào)用和返回符合棧后進(jìn)先出的特性，適合用棧實(shí)現(xiàn)調(diào)用棧。80.在一個(gè)采用頁面置換算法的系統(tǒng)中，若采用先進(jìn)先出（FIFO）算法，當(dāng)發(fā)生缺頁時(shí)，應(yīng)淘汰？A.最先進(jìn)入內(nèi)存的頁面B.最近最久未使用的頁面C.隨機(jī)選擇一個(gè)頁面D.駐留時(shí)間最長的頁面答案：A解析：FIFO算法淘汰最先進(jìn)入內(nèi)存的頁面。81.以下關(guān)于算法的漸近表示，說法正確的是？A.O表示法表示算法的時(shí)間復(fù)雜度的上界B.Ω表示法表示算法的時(shí)間復(fù)雜度的下界C.Θ表示法表示算法的時(shí)間復(fù)雜度的精確界D.以上說法都正確答案：D解析：O表示法描述算法時(shí)間復(fù)雜度的上界，Ω表示法描述下界，Θ表示法描述精確界，所以以上說法都正確。82.一個(gè)無向圖的連通分量個(gè)數(shù)為3，若要將其變?yōu)檫B通圖且添加的邊數(shù)最少，添加邊的方式是？A.任選3個(gè)連通分量，兩兩相連B.從一個(gè)連通分量向另外兩個(gè)連通分量各連一條邊C.從一個(gè)連通分量向另外兩個(gè)連通分量各連兩條邊D.隨機(jī)連接不同連通分量的頂點(diǎn)答案：B解析：要將k個(gè)連通分量變?yōu)檫B通圖，最少添加k-1條邊。這里k=3，從一個(gè)連通分量向另外兩個(gè)連通分量各連一條邊可使圖連通且邊數(shù)最少。83.以下哪種排序算法在處理小規(guī)模數(shù)據(jù)時(shí)效率較高？A.歸并排序B.快速排序C.插入排序D.堆排序答案：C解析：插入排序在處理小規(guī)模數(shù)據(jù)時(shí)，由于其代碼簡單，常數(shù)因子小，效率較高。而歸并排序、快速排序和堆排序在處理大規(guī)模數(shù)據(jù)時(shí)優(yōu)勢(shì)更明顯。84.一個(gè)進(jìn)程在執(zhí)行過程中被信號(hào)中斷，中斷處理完成后，該進(jìn)程的狀態(tài)通常是？A.運(yùn)行態(tài)B.就緒態(tài)C.阻塞態(tài)D.終止態(tài)答案：A解析：進(jìn)程被信號(hào)中斷，中斷處理完成后通常會(huì)繼續(xù)之前的執(zhí)行，所以狀態(tài)仍為運(yùn)行態(tài)。85.在一個(gè)哈希表中，若哈希函數(shù)為H(key)=key%7，采用鏈地址法解決沖突，插入元素14、21、28后，在地址為0的鏈表中元素個(gè)數(shù)為？A.1B.2C.3D.0答案：C解析：H(14)=14%7=0，H(21)=21%7=0，H(28)=28%7=0，所以地址為0的鏈表中有3個(gè)元素。86.以下關(guān)于圖的最小生成樹，若使用普里姆（Prim）算法從頂點(diǎn)v開始構(gòu)建最小生成樹，在算法執(zhí)行過程中，以下說法正確的是？A.每次選擇的邊一定是與已加入樹的頂點(diǎn)相連的邊中權(quán)值最小的邊B.每次選擇的邊一定是圖中權(quán)值最小的邊C.算法執(zhí)行過程中，已加入樹的頂點(diǎn)集合是固定不變的D.算法的時(shí)間復(fù)雜度與圖的邊數(shù)成正比答案：A解析：Prim算法每次從與已加入樹的頂點(diǎn)相連的邊中選擇權(quán)值最小的邊加入生成樹。不是選擇圖中權(quán)值最小的邊，已加入樹的頂點(diǎn)集合不斷變化，其時(shí)間復(fù)雜度與頂點(diǎn)數(shù)有關(guān)，不是與邊數(shù)成正比。87.一個(gè)棧的輸入序列為3,6,9,12,15，若輸出序列的第三個(gè)元素是9，則輸出序列的第一個(gè)元素可能是？A.3B.6C.12D.15答案：B解析：輸出序列第三個(gè)元素是9，說明3、6、9已入棧，9出棧，此時(shí)輸出序列第一個(gè)元素可能是6。88.以下關(guān)于操作系統(tǒng)的進(jìn)程調(diào)度，若采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，時(shí)間片設(shè)置過短會(huì)導(dǎo)致？A.系統(tǒng)開銷增大B.進(jìn)程響應(yīng)時(shí)間變長C.進(jìn)程平均周轉(zhuǎn)時(shí)間變長D.以上都對(duì)答案：A解析：時(shí)間片設(shè)置過短，進(jìn)程頻繁切換，會(huì)使系統(tǒng)開銷增大。而進(jìn)程響應(yīng)時(shí)間可能會(huì)變短，進(jìn)程平均周轉(zhuǎn)時(shí)間不一定變長。89.一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖，刪除一條邊后，圖的連通性是？A.一定不連通B.一定連通C.可能連通也可能不連通D.無法確定答案：B解析：無向完全圖中任意兩個(gè)頂點(diǎn)都有邊相連，刪除一條邊后仍然是連通的。90.以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)圖的深度優(yōu)先遍歷的輔助數(shù)據(jù)結(jié)構(gòu)？A.棧B.隊(duì)列C.數(shù)組D.鏈表答案：A解析：深度優(yōu)先遍歷的過程符合棧后進(jìn)先出的特點(diǎn)，用棧作為輔助數(shù)據(jù)結(jié)構(gòu)可以方便地實(shí)現(xiàn)深度優(yōu)先遍歷。91.在一個(gè)采用分段存儲(chǔ)管理的系統(tǒng)中，若段表存放在內(nèi)存中，