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