【正文】 的定義，非空的二叉樹(shù)可分為三部分：根結(jié)點(diǎn) D、左子樹(shù) L 和右子樹(shù) R。 二叉樹(shù)的后序遍歷（ LRD）定義為：第一步，后序遍歷左子樹(shù) L；第二步，后序遍歷右子樹(shù) R；第三步，訪問(wèn)根結(jié)點(diǎn) D。 二叉樹(shù)的中序遍歷（ LDR）定義為：第一步，中序遍歷左子樹(shù) L；第二步，訪問(wèn)根結(jié)點(diǎn) D；第三步，中序遍歷右子樹(shù) R。 因此，若一棵二叉樹(shù)的每個(gè)結(jié)點(diǎn)都沒(méi)有右子樹(shù)的話， LRD 與 LDR 都變成了 LD，即后序遍歷序列與中序遍歷序列相同。 參考答案 （ 40） A 第 1 章 程序員上午試題分析與解答 17 試題（ 41） 對(duì)長(zhǎng)度為 n 的 有序表進(jìn)行二分（折半）查找時(shí) ，無(wú)論查找指定的一個(gè)元素是否成功，最多只與表中的 （ 41） 個(gè)元素進(jìn)行比較即可。 （ 41） A． 2log 1n ????? B． 2log 1n ????? C． /2n D． n 1 試題（ 41）分析 本題考查 基本算法中的查找運(yùn)算。 對(duì)長(zhǎng)度為 n 的 有序表進(jìn)行二分（折半）查找時(shí)，其查找過(guò)程可用一棵二叉樹(shù)描述（折半查找判定樹(shù)），其高度與 n 個(gè)結(jié)點(diǎn)構(gòu)成的完全二 叉樹(shù)的高度相同（即 2log 1n ?????），查找過(guò)程中從根結(jié)點(diǎn)最多比較到二叉樹(shù)的最高層結(jié)點(diǎn)，因此參與比較的元素個(gè)數(shù)不超過(guò)2log 1n ?????。 參考答案 （ 41） B 試題（ 42） 輸入受限的雙端 隊(duì)列是指只有一端可以進(jìn)行入隊(duì)操作而從兩端都可以進(jìn)行出隊(duì)操作的隊(duì)列，如下圖所示。對(duì)于輸入序列 1 2 3 4，經(jīng)過(guò)一個(gè)初始為空且輸入受限的雙端隊(duì)列后，不能得到的輸出序列為 （ 42） 。 （ 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)中隊(duì)列的基本概念。 如題圖所示：元素 4 全部在隊(duì)列中時(shí)， 4 依次出隊(duì)列可得到序列 1 2 3 4； 1 依次出隊(duì)列可得到序列 4 3 2 1； 2 出隊(duì)列后， 4 和 3 都可以出隊(duì)列，所以可得到序列 1 2 4 3；而 4 先出隊(duì)列后，接下來(lái)只能是 1 或 3 出隊(duì)列，因此不能得到輸出序列 4 2 1 3。 參考答案 （ 42） D 試題（ 43） 對(duì) 于 具有 n 個(gè) 元 素 的 關(guān) 鍵 字 序 列 ? ?12, , , nk k k ， 當(dāng) 且 僅 當(dāng) 滿 足 關(guān) 系2 2 1i i i ik k k k ???且 ( 1,2, , )2ni ??? ????時(shí) 稱為大根堆。據(jù)此可以斷定 ， （ 43） 不是大根堆。 （ 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）分析 本題考查 排序算法。 利用完全二叉樹(shù)結(jié)構(gòu)可以容易地判斷一個(gè)序列是否為堆。在 完全二叉樹(shù)上，結(jié)點(diǎn) i的左孩子編號(hào)為 2i（若存在左孩子），右孩子編號(hào)為 2i+1（若存在右孩子），因此，只要判斷每個(gè)結(jié)點(diǎn)是否同時(shí)大于其左、右孩子即可。 將題中 A、 B、 C、 D 所表示的序列放入完全二叉樹(shù)后，結(jié)果如下圖所示，其中， B序列中 4 4 37 這三個(gè)元素不滿足大頂堆的定義。 參考答案 （ 43） B 試題（ 44） 在面向?qū)ο蟮木幊陶Z(yǔ)言中，下列正確的說(shuō)法是 （ 44） 。 （ 44） A． 對(duì)象是類的實(shí)例 B． 每個(gè)類都必須創(chuàng)建一個(gè)實(shí)例 C． 每個(gè)類只能創(chuàng)建一個(gè)實(shí)例 D． 類的實(shí)例化是指對(duì)類進(jìn)行初始化 試題 （ 44）分析 本 題 考查面向?qū)ο缶幊陶Z(yǔ)言的基本知識(shí)。 面向?qū)ο蟪绦蛟O(shè)計(jì)的實(shí)質(zhì)是選用一種面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言，采用對(duì)象、類及相關(guān)概念進(jìn)行程序設(shè)計(jì)。實(shí)現(xiàn)一個(gè)面向?qū)ο蟪绦驎r(shí)，通常首先編寫(xiě)類，類是對(duì)對(duì)象的抽象，對(duì)象表現(xiàn)為類的實(shí)例。每個(gè)類可以創(chuàng)建不同個(gè)數(shù)的實(shí)例，也可以不創(chuàng)建實(shí)例。類的實(shí)例化包括實(shí)例生成和實(shí)例消除，在實(shí)例化時(shí)可以確定實(shí)例的初始狀態(tài)，即初始化。 參考答案 （ 44） A 試題（ 45） 在統(tǒng)一建模語(yǔ)言（ UML）中， （ 45） 用于描述系統(tǒng)與外部系統(tǒng)及用戶之間的交互。 （ 45） A． 對(duì)象圖 B． 類圖 C． 用例 圖 D． 序列圖 第 1 章 程序員上午試題分析與解答 19 試題（ 45）分析 本題考查 統(tǒng)一建模語(yǔ)言（ UML）的基本知識(shí)。 中提供了多種圖形。 對(duì)象圖展現(xiàn)了一組對(duì)象以及它們之間的關(guān)系。對(duì)象圖描述了在類圖中所建立的事物的實(shí)例的靜態(tài)快照。類圖展現(xiàn)了一組對(duì)象、接口、協(xié)作和它們之間的關(guān)系。用例圖展現(xiàn)了一組用例、參與者以及它們之間的關(guān)系 ， 描述了誰(shuí)將使用系統(tǒng)以及用戶期望以什么方式與系統(tǒng)交互。序列圖是場(chǎng)景的圖形化表示，描述了在一個(gè)用例或操作的執(zhí)行過(guò)程中以時(shí)間順序組織的對(duì)象之間的交互活動(dòng)。 參考答案 （ 45） C 試題（ 46） 面向?qū)ο筌浖_(kāi)發(fā)過(guò)程中，面向?qū)?象分析階段包含一系列活動(dòng)，而 （ 46） 活動(dòng)不屬于 面向?qū)ο蠓治鲭A段。 （ 46） A． 識(shí)別分析類 B． 構(gòu)建分析模型 C． 評(píng)估分析模型 D． 確定接口規(guī)格 試題（ 46）分析 本 題 考查面向?qū)ο箝_(kāi)發(fā)過(guò)程的基本知識(shí)。 面向?qū)ο箝_(kāi)發(fā)主要分為面向?qū)ο蠓治?（ ObjectOriented Analysis， OOA） 和面向?qū)ο笤O(shè)計(jì) （ ObjectOriented Design， OOD） 兩大部分。 OOA 的目標(biāo)是建立待開(kāi)發(fā)軟件系統(tǒng)的模型。 OOA 模型描述了表示某個(gè)特定應(yīng)用領(lǐng)域中的對(duì)象、對(duì)象間的結(jié)構(gòu)關(guān)系和通信關(guān) 系，反映了現(xiàn)實(shí)世界強(qiáng)加給軟件系統(tǒng)的各種規(guī)則和約束條件。 OOA 模型還規(guī)定了對(duì)象如何協(xié)同工作和完成系統(tǒng)的職責(zé)。 通常 OOA 階段包括的活動(dòng)有識(shí)別分析類、構(gòu)建分析模型 和評(píng)估分析模型。 參考答案 （ 46） D 試題（ 47） 在面向?qū)ο箝_(kāi)發(fā)方法中， （ 47） 機(jī)制模擬現(xiàn)實(shí)世界中的遺傳現(xiàn)象，實(shí)現(xiàn) 類之間共享數(shù)據(jù)和方法 。 （ 47） A． 封裝 B． 繼承 C． 多態(tài) D． 抽象接口 試題（ 47）分析 本題考查面向?qū)ο箝_(kāi)發(fā)方法中的基本概念。 面向?qū)ο箝_(kāi)發(fā)方法中，封裝 是一種信息隱蔽技術(shù)，其目的是使對(duì)象的使用者和生產(chǎn)者分離，使對(duì)象的 定義和實(shí)現(xiàn)分開(kāi)。 繼承是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制，使得在定義一個(gè)類的時(shí)候，可以在一個(gè)已經(jīng)存在的類的基礎(chǔ)上進(jìn)行，把這個(gè)已經(jīng)存在的類所定義的內(nèi)容作為自己的內(nèi)容，并加入若干新的內(nèi)容。 多態(tài) 在 繼承的支持 下， 不同的對(duì)象收到同一消息可以產(chǎn)生完全不同的結(jié)果。 2022 上半年試題分析與解答 20 參考答案 （ 47） B 試題（ 48）、（ 49） UML 圖中， （ 48） 屬于動(dòng)態(tài)交互圖，它們關(guān)注系統(tǒng)的動(dòng)態(tài)特性； （ 49） 屬于靜態(tài)結(jié)構(gòu)視圖，它們關(guān)注系統(tǒng)的靜態(tài)結(jié)構(gòu)。 （ 48） A． 序列圖和通信圖 B． 序列圖和類圖 C． 類圖和對(duì)象圖 D． 組件圖 和 通信圖 （ 49） A． 序列圖和通信圖 B． 序列圖和類圖 C． 類圖和對(duì)象圖 D． 組件圖 和通信圖 試題（ 48）、（ 49）分析 本題考查 統(tǒng)一建模語(yǔ)言（ UML）的基本知識(shí)。 在 中提供的多種圖形中，有些圖 形 關(guān)注系統(tǒng)的靜態(tài)結(jié)構(gòu)，展現(xiàn)系統(tǒng)的靜態(tài)視圖，有些圖形關(guān)注系統(tǒng)的動(dòng)態(tài)特性，展現(xiàn)動(dòng)態(tài)視圖。 類圖展現(xiàn)了一組對(duì)象、接口、協(xié)作和它們之間的關(guān)系 ， 給出系統(tǒng)的靜態(tài)設(shè)計(jì)視圖。對(duì)象圖展現(xiàn)了一組對(duì)象以及它們之間的關(guān)系。對(duì)象圖描述了在類圖中所建立的事物的實(shí)例的靜態(tài)快照 ， 給出系統(tǒng)的靜態(tài)設(shè)計(jì)視圖。序列圖是場(chǎng)景的圖形 化表示，描述了在一個(gè)用例或操作的執(zhí)行過(guò)程中以時(shí)間順序組織的對(duì)象之間的交互活動(dòng)。通信圖強(qiáng)調(diào)收發(fā)消息的對(duì)象之間的結(jié)構(gòu)組織 ，是一種交互圖 。組件圖展現(xiàn)了一組構(gòu)件之間的組織和依賴。組件圖與類圖相關(guān)，專注于系統(tǒng)的靜態(tài)實(shí)現(xiàn)視圖。 參考答案 （ 48） A （ 49） C 試題（ 50） 在數(shù)據(jù)流圖（ DFD）中，頂層數(shù)據(jù)流圖僅包含一個(gè) （ 50） 。 （ 50） A． 數(shù)據(jù)處理 B． 數(shù)據(jù)存儲(chǔ) C． 數(shù)據(jù)流 D． 數(shù)據(jù)源或者數(shù)據(jù)匯點(diǎn) 試題（ 50）分析 本題考查 數(shù)據(jù)流圖的基本概念 。 數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度 ，以圖形的方式刻畫(huà)數(shù)據(jù)流從輸入到輸出的處理變換過(guò)程，其基礎(chǔ)是功能分解。數(shù)據(jù)流圖包括數(shù)據(jù)處理，也稱為加工，是對(duì)數(shù)據(jù)對(duì)象的處理或變換；數(shù)據(jù)源或數(shù)據(jù)匯點(diǎn)，表示圖中要處理數(shù)據(jù)的輸入來(lái)源或處理結(jié)果要送往何處，數(shù)據(jù)源或數(shù)據(jù)匯點(diǎn)不是目標(biāo)系統(tǒng)的一部分，因此也稱為外部實(shí)體；數(shù)據(jù)存儲(chǔ)，在數(shù)據(jù)流圖中起著保存數(shù)據(jù)的作用，可以是數(shù)據(jù)庫(kù)文件或任何形式的數(shù)據(jù)組織；數(shù)據(jù)流，表示數(shù)據(jù)沿著箭頭方向的流動(dòng)。 參考答案 （ 50）