2026年計(jì)算機(jī)等級(jí)考試公共基礎(chǔ)知識(shí)庫及答案

2026年計(jì)算機(jī)等級(jí)考試公共基礎(chǔ)知識(shí)庫及答案1.數(shù)據(jù)結(jié)構(gòu)中，線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的本質(zhì)區(qū)別是？順序存儲(chǔ)要求內(nèi)存連續(xù)，可隨機(jī)訪問（時(shí)間復(fù)雜度O(1)），但插入/刪除需移動(dòng)元素（時(shí)間復(fù)雜度O(n)）；鏈?zhǔn)酱鎯?chǔ)內(nèi)存不連續(xù)，通過指針鏈接，插入/刪除只需修改指針（時(shí)間復(fù)雜度O(1)，若需定位則O(n)），但無法隨機(jī)訪問。2.若棧的輸入序列為3,1,4,2,5，不可能的輸出序列是？例如5,2,4,1,3不可能。因?yàn)?出棧時(shí)，1、2、3、4必須已入棧，此時(shí)棧內(nèi)順序?yàn)?（底）→1→4→2→5（頂），5出棧后棧頂是2，下一個(gè)出棧應(yīng)為2，而非4（若4要在2前出棧，需2先出棧，矛盾）。3.完全二叉樹有1023個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)是多少？完全二叉樹中，葉子結(jié)點(diǎn)數(shù)等于?n/2?。n=1023為奇數(shù)，故葉子結(jié)點(diǎn)數(shù)為(1023+1)/2=512。4.對(duì)長(zhǎng)度為n的有序數(shù)組進(jìn)行二分查找，最壞情況下的時(shí)間復(fù)雜度是？二分查找每次將區(qū)間減半，最壞需log?n次比較，時(shí)間復(fù)雜度為O(log?n)。5.冒泡排序在最好情況下（已有序）的比較次數(shù)和交換次數(shù)分別是？最好情況（正序）只需遍歷一次，比較次數(shù)為n-1次，交換次數(shù)為0次。6.隊(duì)列的“假溢出”是如何產(chǎn)生的？順序隊(duì)列中，隊(duì)尾指針到達(dá)數(shù)組末尾時(shí)，若隊(duì)頭指針之前有空閑空間，因隊(duì)尾無法后移導(dǎo)致的空間浪費(fèi)現(xiàn)象，解決方法是使用循環(huán)隊(duì)列。7.深度為5的滿二叉樹（根結(jié)點(diǎn)深度為1），其葉子結(jié)點(diǎn)數(shù)是多少？滿二叉樹第k層有2^(k-1)個(gè)結(jié)點(diǎn)，深度5的滿二叉樹葉子結(jié)點(diǎn)在第5層，數(shù)量為2^(5-1)=16。8.已知某二叉樹的前序遍歷序列為ABDCE，中序遍歷序列為BDAEC，求后序遍歷序列。前序根為A，中序中A左側(cè)B、D為左子樹，右側(cè)E、C為右子樹。左子樹前序?yàn)锽D→根B，中序B左側(cè)無，右側(cè)D→左子樹結(jié)構(gòu)B→D（右孩子）。右子樹前序?yàn)镃E→根C，中序C左側(cè)E→E為C左孩子。后序遍歷順序?yàn)镈→B→E→C→A，即DBECA。9.對(duì)關(guān)鍵字序列[5,2,7,1,3]進(jìn)行直接插入排序（升序），第三趟排序后的序列是？直接插入排序每趟將當(dāng)前元素插入已排序序列。初始：[5]；第一趟插入2→[2,5]；第二趟插入7→[2,5,7]；第三趟插入1→[1,2,5,7]；第四趟插入3→[1,2,3,5,7]。第三趟后為[1,2,5,7,3]？不，第三趟處理的是第4個(gè)元素（索引3，值1），此時(shí)已排序序列是[2,5,7]，插入1后變?yōu)閇1,2,5,7]，原序列變?yōu)閇1,2,5,7,3]。10.快速排序在平均情況下的時(shí)間復(fù)雜度是？O(nlog?n)，最壞情況（已有序或逆序）為O(n2)。11.結(jié)構(gòu)化程序設(shè)計(jì)的核心原則是？自頂向下、逐步求精、模塊化設(shè)計(jì)，使用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)，避免無條件跳轉(zhuǎn)（如goto）。12.面向?qū)ο蠓椒ㄖ校胺庋b”的含義是？將對(duì)象的屬性（數(shù)據(jù)）和方法（操作）綁定為一個(gè)整體，隱藏內(nèi)部實(shí)現(xiàn)細(xì)節(jié)，僅通過公共接口對(duì)外提供服務(wù)。13.繼承可分為單繼承和多繼承，Java語言僅支持哪種？單繼承（類只能繼承一個(gè)父類），但接口可多實(shí)現(xiàn)。14.多態(tài)的實(shí)現(xiàn)機(jī)制包括編譯時(shí)多態(tài)和運(yùn)行時(shí)多態(tài)，舉例說明。編譯時(shí)多態(tài)通過函數(shù)重載（同一類中同名不同參數(shù)的方法）實(shí)現(xiàn)；運(yùn)行時(shí)多態(tài)通過子類重寫父類的虛函數(shù)（如Java中的@Override），運(yùn)行時(shí)根據(jù)對(duì)象實(shí)際類型調(diào)用對(duì)應(yīng)方法。15.模塊的內(nèi)聚性越高，耦合性越低，軟件質(zhì)量越好。其中，“功能內(nèi)聚”是指？模塊內(nèi)所有元素共同完成一個(gè)單一功能，缺一不可，是內(nèi)聚性最高的類型。16.軟件生命周期中，“需求分析”階段的主要任務(wù)是？確定軟件的功能、性能、數(shù)據(jù)、界面等要求，提供需求規(guī)格說明書（SRS），作為后續(xù)設(shè)計(jì)的依據(jù)。17.瀑布模型的主要缺點(diǎn)是？強(qiáng)調(diào)階段間的順序性和依賴性，缺乏靈活性，后期發(fā)現(xiàn)需求錯(cuò)誤時(shí)修改成本極高。18.黑盒測(cè)試與白盒測(cè)試的主要區(qū)別是？黑盒測(cè)試（功能測(cè)試）不關(guān)注內(nèi)部代碼邏輯，僅根據(jù)需求規(guī)格驗(yàn)證功能是否正確；白盒測(cè)試（結(jié)構(gòu)測(cè)試）基于代碼結(jié)構(gòu)（如語句、分支、路徑）設(shè)計(jì)測(cè)試用例，驗(yàn)證代碼邏輯的正確性。19.軟件調(diào)試的目的是？定位并修復(fù)測(cè)試中發(fā)現(xiàn)的錯(cuò)誤（bug），而測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤。20.敏捷開發(fā)的核心實(shí)踐包括？迭代開發(fā)（短周期發(fā)布可工作軟件）、用戶故事（從用戶角度描述需求）、每日站會(huì)（快速同步進(jìn)度）、持續(xù)集成（頻繁合并代碼并測(cè)試）。21.數(shù)據(jù)模型的三要素是？數(shù)據(jù)結(jié)構(gòu)（描述數(shù)據(jù)的靜態(tài)特性）、數(shù)據(jù)操作（如查詢、更新）、數(shù)據(jù)完整性約束（如實(shí)體完整性、參照完整性）。22.關(guān)系數(shù)據(jù)庫中，“候選鍵”的定義是？能唯一標(biāo)識(shí)關(guān)系中一個(gè)元組的最小屬性集合（即其任何真子集都不能唯一標(biāo)識(shí)元組）。23.關(guān)系R(A,B,C)和S(B,D)進(jìn)行自然連接，結(jié)果包含哪些屬性？自然連接會(huì)自動(dòng)匹配相同屬性名（B），結(jié)果屬性為A,B,C,D（去重B）。24.關(guān)系模式R(學(xué)號(hào),姓名,課程號(hào),成績(jī),系別,系主任)，存在函數(shù)依賴：學(xué)號(hào)→姓名,系別；系別→系主任；(學(xué)號(hào),課程號(hào))→成績(jī)。判斷R最高符合第幾范式。1NF（屬性不可再分）；2NF要求消除非主屬性對(duì)候選鍵的部分依賴。候選鍵是(學(xué)號(hào),課程號(hào))，非主屬性為姓名、系別、系主任、成績(jī)。姓名、系別僅依賴于學(xué)號(hào)（候選鍵的部分），存在部分依賴，故R僅符合1NF。若分解為R1(學(xué)號(hào),姓名,系別,系主任)和R2(學(xué)號(hào),課程號(hào),成績(jī))，則R1中系主任傳遞依賴于學(xué)號(hào)（學(xué)號(hào)→系別→系主任），R1符合2NF但不符合3NF；R2符合3NF（無傳遞依賴）。25.E-R圖中，實(shí)體、屬性、聯(lián)系的表示符號(hào)分別是？實(shí)體用矩形，屬性用橢圓，聯(lián)系用菱形，聯(lián)系與實(shí)體間用線段連接，標(biāo)注聯(lián)系類型（1:1、1:n、m:n）。26.數(shù)據(jù)庫三級(jí)模式結(jié)構(gòu)中，“外模式”是指？用戶級(jí)模式，是數(shù)據(jù)庫用戶（如應(yīng)用程序）能看見和使用的局部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征描述，一個(gè)數(shù)據(jù)庫可有多外模式。27.數(shù)據(jù)字典的作用是？對(duì)數(shù)據(jù)流程圖（DFD）中各元素（數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲(chǔ)、處理邏輯）的詳細(xì)定義和描述，是需求分析階段的重要文檔。28.事務(wù)的ACID特性是指？原子性（Atomicity，操作要么全做要么全不做）、一致性（Consistency，事務(wù)執(zhí)行后數(shù)據(jù)保持一致狀態(tài)）、隔離性（Isolation，事務(wù)間互不干擾）、持久性（Durability，事務(wù)提交后修改永久保存）。29.索引的主要作用是？提高數(shù)據(jù)查詢效率（通過建立屬性值到記錄的映射），但會(huì)增加插入、刪除、更新的開銷。30.若關(guān)系R和S的笛卡爾積有m×n個(gè)元組，則R和S分別有多少個(gè)元組？R有m個(gè)元組，S有n個(gè)元組（笛卡爾積是所有可能的元組組合，數(shù)量為兩關(guān)系元組數(shù)的乘積）。31.線性鏈表中，刪除指定值的第一個(gè)結(jié)點(diǎn)，需修改哪些指針？需找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，將前驅(qū)的next指針指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)（若刪除的是頭結(jié)點(diǎn)，需更新頭指針）。32.一個(gè)具有n個(gè)結(jié)點(diǎn)的線性表，采用順序存儲(chǔ)時(shí)，插入一個(gè)元素的平均移動(dòng)次數(shù)是？平均需移動(dòng)(n-1)/2個(gè)元素（插入位置i的概率為1/(n+1)，移動(dòng)次數(shù)為n-i，求和后平均）。33.樹的基本遍歷方式包括先根遍歷、后根遍歷，對(duì)應(yīng)的二叉樹遍歷方式是？樹的先根遍歷對(duì)應(yīng)二叉樹的前序遍歷，后根遍歷對(duì)應(yīng)二叉樹的中序遍歷（因樹轉(zhuǎn)換為二叉樹時(shí)，兄弟結(jié)點(diǎn)變?yōu)橛易訕洌?4.對(duì)有序數(shù)組[1,3,5,7,9,11,13]進(jìn)行二分查找，查找元素7時(shí)，需要比較幾次？第一次中間值為7（索引3），直接找到，比較1次。35.希爾排序的核心思想是？將整個(gè)數(shù)組分成若干子序列（間隔為增量d），分別進(jìn)行插入排序，逐步減小增量d（如d=5,3,1），最終對(duì)整個(gè)數(shù)組進(jìn)行插入排序，利用局部有序提高效率。36.程序設(shè)計(jì)中，“對(duì)象”與“類”的關(guān)系是？類是對(duì)象的抽象（模板），對(duì)象是類的實(shí)例（具體實(shí)例化結(jié)果）。37.面向?qū)ο笤O(shè)計(jì)的“里氏替換原則”是指？子類可以替換其父類且不影響程序正確性，即子類應(yīng)保持父類的行為約定。38.軟件設(shè)計(jì)中，“扇入”和“扇出”的含義是？扇入指一個(gè)模塊被其他模塊調(diào)用的次數(shù)（越高表示復(fù)用性越好）；扇出指一個(gè)模塊直接調(diào)用的其他模塊數(shù)（過大可能導(dǎo)致復(fù)雜度高，一般建議3-5）。39.測(cè)試用例應(yīng)包括？輸入數(shù)據(jù)、預(yù)期輸出，以及測(cè)試環(huán)境、測(cè)試步驟等信息。40.數(shù)據(jù)庫設(shè)計(jì)的步驟包括？需求分析→概念設(shè)計(jì)（E-R圖）→邏輯設(shè)計(jì)（轉(zhuǎn)換為關(guān)系模式）→物理設(shè)計(jì)（存儲(chǔ)結(jié)構(gòu)、索引設(shè)計(jì)）→實(shí)施與維護(hù)。41.關(guān)系代數(shù)中，“投影”運(yùn)算的作用是？從關(guān)系中選出若干屬性列組成新關(guān)系（消除重復(fù)元組），對(duì)應(yīng)SQL中的SELECT列名。42.若關(guān)系模式R滿足3NF，則其一定滿足？1NF和2NF（3NF是在2NF基礎(chǔ)上消除傳遞函數(shù)依賴）。43.E-R圖轉(zhuǎn)換為關(guān)系模式時(shí)，多對(duì)多聯(lián)系（m:n）如何處理？創(chuàng)建一個(gè)新的關(guān)系模式，包含兩個(gè)實(shí)體的主鍵和聯(lián)系的屬性，主鍵為兩實(shí)體主鍵的組合。44.數(shù)據(jù)庫管理系統(tǒng)（DBMS）的主要功能包括？數(shù)據(jù)定義（DDL）、數(shù)據(jù)操縱（DML）、數(shù)據(jù)控制（安全性、完整性、并發(fā)控制、恢復(fù)）、數(shù)據(jù)庫維護(hù)。45.棧的典型應(yīng)用場(chǎng)景包括？函數(shù)調(diào)用棧、表達(dá)式求值（中綴轉(zhuǎn)后綴）、括號(hào)匹配、回溯算法。46.隊(duì)列的典型應(yīng)用場(chǎng)景包括？操作系統(tǒng)進(jìn)程調(diào)度（FCFS）、網(wǎng)絡(luò)數(shù)據(jù)分組緩存、廣度優(yōu)先搜索（BFS）。47.二叉排序樹（BST）的定義是？左子樹所有結(jié)點(diǎn)值小于根結(jié)點(diǎn)，右子樹所有結(jié)點(diǎn)值大于根結(jié)點(diǎn)，左右子樹也是BST。48.對(duì)二叉排序樹進(jìn)行中序遍歷，結(jié)果是？一個(gè)有序序列（升序）。49.哈希表（散列表）的沖突是指？不同關(guān)鍵字通過哈希函數(shù)映射到同一存儲(chǔ)地址的現(xiàn)象，解決方法有開放定址法（線性探測(cè)、二次探測(cè)）、鏈地址法（哈希桶）。50.軟件危機(jī)的主要表現(xiàn)是？軟件需求變更難以應(yīng)對(duì)，開發(fā)周期失控，成本超支，質(zhì)量低下，維護(hù)困難。51.結(jié)構(gòu)化分析方法（SA）的主要工具是？數(shù)據(jù)流程圖（DFD）、數(shù)據(jù)字典（DD）、判定表/判定樹。52.面向?qū)ο蠓治觯∣OA）的核心是？識(shí)別問題域中的對(duì)象，分析對(duì)象間的關(guān)系（如關(guān)聯(lián)、繼承、依賴），建立對(duì)象模型。53.數(shù)據(jù)庫的完整性約束包括？實(shí)體完整性（主鍵非空唯一）、參照完整性（外鍵要么為空，要么匹配被參照表的主鍵）、用戶定義完整性（如字段取值范圍）。54.事務(wù)的隔離級(jí)別中，“可重復(fù)讀”能解決哪些問題？解決臟讀（讀取未提交數(shù)據(jù)），但可能存在不可重復(fù)讀（同一事務(wù)兩次讀取結(jié)果不同）和幻讀（讀取到新插入數(shù)據(jù)）。55.索引分為聚集索引和非聚集索引，區(qū)別是？聚集索引決定數(shù)據(jù)的物理存儲(chǔ)順序（一個(gè)表只能有一個(gè)），非聚集索引不影響物理順序（可多個(gè)）。56.線性表的鏈?zhǔn)酱鎯?chǔ)中，頭結(jié)點(diǎn)的作用是？簡(jiǎn)化插入/刪除操作（尤其是頭結(jié)點(diǎn)的處理），使所有結(jié)點(diǎn)的操作統(tǒng)一。57.圖的遍歷方式有深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS），分別使用什么