【正文】 g() int f(int x) a = 2。 return a * x。 （ 36） A． base+(4*8+4)*4 B． base+(5*8+5)*4 C． base+(4*6+4)*4 D． base+(5*6+5)*4 試題 （ 36） 分析 本題考查 數(shù)組元素的存儲。若用鏈地址法解決沖突（即將相互沖突的元素存儲在同一個單鏈表中）構(gòu)造散列 表，則散列表中與哈希地址 （ 37） 對應(yīng)的單鏈表最長。 （ 38） A． nmab? B． 1nab? C． 11ab? D． 1 mab? 第 1 章 程序員上午試題分析與解答 15 圖 11 試題（ 38）分析 本題考查 歸并排序算法。 反之，若 1b 1a ， 2b 1a ， ? ， mb 1a ，則歸并過程中共進行 m 次比較（ 1a 與序列 B的每個元素都比較 1 次）。 根據(jù)題圖中的鄰接表，可知對應(yīng)的圖如下所示： 顯然，圖中的弧數(shù)為 9。 二叉樹的后序遍歷（ LRD）定義為：第一步，后序遍歷左子樹 L；第二步，后序遍歷右子樹 R；第三步，訪問根結(jié)點 D。 （ 41） A． 2log 1n ????? B． 2log 1n ????? C． /2n D． n 1 試題（ 41）分析 本題考查 基本算法中的查找運算。 （ 42） A． 1 2 3 4 B． 4 3 2 1 C． 1 2 4 3 D． 4 2 1 3 試題（ 42）分析 本題考查 數(shù)據(jù)結(jié)構(gòu)中隊列的基本概念。 （ 43） A． 59, 53, 48, 46, 37, 31, 25 B． 59, 46, 53, 48, 37, 31, 25 2022 上半年試題分析與解答 18 C． 59, 37, 53, 25, 31, 46, 48 D． 59, 53, 48, 31, 25, 46, 37 試題（ 43）分析 本題考查 排序算法。 參考答案 （ 43） B 試題（ 44） 在面向?qū)ο蟮木幊陶Z言中，下列正確的說法是 （ 44） 。每個類可以創(chuàng)建不同個數(shù)的實例，也可以不創(chuàng)建實例。 中提供了多種圖形。用例圖展現(xiàn)了一組用例、參與者以及它們之間的關(guān)系 ， 描述了誰將使用系統(tǒng)以及用戶期望以什么方式與系統(tǒng)交互。 面向?qū)ο箝_發(fā)主要分為面向?qū)ο蠓治?（ ObjectOriented Analysis， OOA） 和面向?qū)ο笤O(shè)計 （ ObjectOriented Design， OOD） 兩大部分。 通常 OOA 階段包括的活動有識別分析類、構(gòu)建分析模型 和評估分析模型。 繼承是父類和子類之間共享數(shù)據(jù)和方法的機制，使得在定義一個類的時候，可以在一個已經(jīng)存在的類的基礎(chǔ)上進行，把這個已經(jīng)存在的類所定義的內(nèi)容作為自己的內(nèi)容，并加入若干新的內(nèi)容。 在 中提供的多種圖形中，有些圖 形 關(guān)注系統(tǒng)的靜態(tài)結(jié)構(gòu)，展現(xiàn)系統(tǒng)的靜態(tài)視圖，有些圖形關(guān)注系統(tǒng)的動態(tài)特性，展現(xiàn)動態(tài)視圖。序列圖是場景的圖形 化表示，描述了在一個用例或操作的執(zhí)行過程中以時間順序組織的對象之間的交互活動。 參考答案 （ 48） A （ 49） C 試題（ 50） 在數(shù)據(jù)流圖（ DFD）中，頂層數(shù)據(jù)流圖僅包含一個 （ 50） 。 參考答案 （ 50） A 。 數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度 ，以圖形的方式刻畫數(shù)據(jù)流從輸入到輸出的處理變換過程，其基礎(chǔ)是功能分解。組件圖展現(xiàn)了一組構(gòu)件之間的組織和依賴。對象圖展現(xiàn)了一組對象以及它們之間的關(guān)系。 2022 上半年試題分析與解答 20 參考答案 （ 47） B 試題（ 48）、（ 49） UML 圖中， （ 48） 屬于動態(tài)交互圖，它們關(guān)注系統(tǒng)的動態(tài)特性； （ 49） 屬于靜態(tài)結(jié)構(gòu)視圖，它們關(guān)注系統(tǒng)的靜態(tài)結(jié)構(gòu)。 （ 47） A． 封裝 B． 繼承 C． 多態(tài) D． 抽象接口 試題（ 47）分析 本題考查面向?qū)ο箝_發(fā)方法中的基本概念。 OOA 模型描述了表示某個特定應(yīng)用領(lǐng)域中的對象、對象間的結(jié)構(gòu)關(guān)系和通信關(guān) 系，反映了現(xiàn)實世界強加給軟件系統(tǒng)的各種規(guī)則和約束條件。 參考答案 （ 45） C 試題（ 46） 面向?qū)ο筌浖_發(fā)過程中，面向?qū)?象分析階段包含一系列活動，而 （ 46） 活動不屬于 面向?qū)ο蠓治鲭A段。對象圖描述了在類圖中所建立的事物的實例的靜態(tài)快照。 參考答案 （ 44） A 試題（ 45） 在統(tǒng)一建模語言（ UML）中， （ 45） 用于描述系統(tǒng)與外部系統(tǒng)及用戶之間的交互。 面向?qū)ο蟪绦蛟O(shè)計的實質(zhì)是選用一種面向?qū)ο蟪绦蛟O(shè)計語言，采用對象、類及相關(guān)概念進行程序設(shè)計。在 完全二叉樹上，結(jié)點 i的左孩子編號為 2i（若存在左孩子），右孩子編號為 2i+1（若存在右孩子），因此，只要判斷每個結(jié)點是否同時大于其左、右孩子即可。 參考答案 （ 42） D 試題（ 43） 對 于 具有 n 個 元 素 的 關(guān) 鍵 字 序 列 ? ?12, , , nk k k ， 當(dāng) 且 僅 當(dāng) 滿 足 關(guān) 系2 2 1i i i ik k k k ???且 ( 1,2, , )2ni ??? ????時 稱為大根堆。 參考答案 （ 41） B 試題（ 42） 輸入受限的雙端 隊列是指只有一端可以進行入隊操作而從兩端都可以進行出隊操作的隊列，如下圖所示。 因此，若一棵二叉樹的每個結(jié)點都沒有右子樹的話， LRD 與 LDR 都變成了 LD，即后序遍歷序列與中序遍歷序列相同。 （ 40） A． B． C． D． 試題（ 40）分析 本題考查 二叉樹的遍歷運算。 參考答案 （ 38） B 試題（ 39） 已知某帶權(quán)有向圖 G（頂點數(shù)為 6，頂點編號為 1～ 6）的鄰接表如下所示，其中表結(jié)點的結(jié)構(gòu)為： 鄰接頂點編號 邊 上的權(quán)值 指向下一個鄰接頂點的指針 2022 上半年試題分析與解答 16 則圖 G 中含有的弧數(shù)為 （ 39） 。因此，當(dāng)一個序列的全部元素都小于另一個序列的全部元素時，歸并過程中的比較次數(shù)最少。 根據(jù)所設(shè)置的哈希函數(shù)，計算各關(guān)鍵字對應(yīng)的哈希地址如下： H(59)=59 MOD 7 = 3 H(53)=53 MOD 7 = 4 H(46)=46 MOD 7 = 4 H(48)=48 MOD 7 = 6 H(37)=37 MOD 7 = 2 H(31)=31 MOD 7 = 3 H(25)=25 MOD 7 = 4 用拉 鏈法解決沖突構(gòu)造的哈希表如圖 11 所示： 從 圖 中可以看出，與哈希地址 4 對應(yīng)的單鏈表最長。 綜上，元素 arr[5, 5]在該數(shù)組空間的地址為 base+(4*8+4)*4。 由于是 引用調(diào)用 ，因此可以理解為在函數(shù) f 中， a 與 x 引用的是同一個對象，都是全局變量 a； 即“ a = a + 1”將 a 的值由 2 改為 3，“ x = x + 2”將 a 的值由 3 改為 5，函數(shù)返回值“ a * x”的值為 25。 a = a + 1。 參考答案 （ 33） B 試題（ 34） 、 （ 35） 函數(shù) g 和 f 的定義如下所示，其中， a 是全局變量。 HTML（ Hyper Text Markup Language） 是目前網(wǎng)絡(luò)上應(yīng)用最為廣泛的語言，也是構(gòu)成網(wǎng)頁文檔的主要語言。 它雖然不是 Linux 系統(tǒng)內(nèi)核的一部分，但它調(diào)用了系統(tǒng)內(nèi)核的大部分功能來執(zhí)行程序、創(chuàng)建文檔并以并行的方式協(xié)調(diào)各個程序的運行。 在 Linux 中， Shell 就是一個 命令行解釋器 ，它的作用就是遵循一定的語法將輸入的命令加以解釋并傳給系統(tǒng)。 高級語言程序需要經(jīng)過編輯、編譯、鏈接處理形成可執(zhí)行程序后才能運行。 編輯是指編寫和修改源程序的文本內(nèi)容；編譯是指將源程序翻譯為目標程序；鏈接是將目標程序與所需要的庫函數(shù)（代碼）鏈接在一起，以形成可執(zhí)行代碼。系統(tǒng)常將內(nèi)存區(qū)域劃分為代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)等，其中代碼區(qū)存放執(zhí)行的指令序列，在程序運行過程中該區(qū)域中的內(nèi)容用戶不能修改，因此不能將變量映射到內(nèi)存代碼區(qū)的存儲單元。 當(dāng)賦值表達式右邊的表達式的求值結(jié)果類型與左邊變量的類型不同時，也有可能需要進行強制數(shù)據(jù)類型轉(zhuǎn)換。 第 1 章 程序員上午試題分析與解答 11 ① 訪問數(shù)組元素 ② 進行賦值運算 ③ 對算術(shù)表達式求值 ④ 進行遞歸調(diào)用 （ 28） A． ②③ B． ①② C． ①③ D． ②④ 試題（ 28）分析 本題考查 程序語言基礎(chǔ)知識。 （ 26） A． 2 B． 3 C． 4 D． 5 （ 27） A． 5 B． 6 C． 8 D． 9 試題（ 26） 、 （ 27）分析 本題考查操作系統(tǒng)進程管理方面的基礎(chǔ)知識。 為了實現(xiàn) 文件“ 按名存取 ” ，必須為