2023年下半年軟件設計師真題+答案解析〔上午選擇+下午案例完整版〕1、在程序運行過程中，CPU需要將指令從內存中取出并加以分析和執行。CPU依據〔〕來區分在內存中以二進制編碼形式存放的指令和數據。A.指令周期的不同階段B.指令和數據的尋址方式C.指令操作碼的譯碼結果D.指令和數據所在的存儲單元答案：A指令和數據是都存儲在內存中，傳統計算機CPU在執行過程中根據指令周期的不同階段來區分是指令還是數據，取指周期取出的是指令，執行周期取出的是數據。2、計算機在一個指令周期的過程中，為從內存讀取指令操作碼，首先要將〔〕的內容送到地址總線上。A.指令存放器〔IR〕B.通用存放器〔GR〕C.程序計數器〔PC〕D.狀態存放器〔PSW〕答案：CPC〔程序計數器〕是用于存放下一條指令所在單元的地址。當執行一條指令時，處理器首先需要從PC中取出指令在內存中的地址，通過地址總線尋址獲取。3、設16位浮點數，其中階符1位、階碼值6位、數符1位、尾數8位。假設階碼用移碼表示，尾數用補碼表示，那么該浮點數所能表示的數值范圍是〔〕。A.-264～〔1-2-8〕264B.-263～〔1-2-8〕263C.-264～〔1-2-〔1-2-8〕264～〔1-2-8〕264D.-〔1-2-8〕263～〔1-2-8〕263答案：B如果浮點數的階碼(包括1位階符)用R位的移碼表示，尾數(包括1位數符)用M位的補碼表示，那么浮點數表示的數值范圍如下。4、數據信息為16位，最少應附加〔〕位校驗位，以實現海明碼糾錯。A.3B.4C.5D.6答案：C海明碼的構造方法是：在數據位之間插入k個校驗位，通過擴大碼距來實現檢錯和糾錯。設數據位是n位，校驗位是k位，那么n和k的必須滿足以下的關系。2K-1≥n+k數據為16位時，至少需要5位校驗位。25-1≥16+55、將一條指令的執行過程分解為取址、分析和執行三步，按照流水方式執行，假設取指時間t取址=4△t、分析時間t分析=2△t、執行時間t執行=3△t，那么執行完100條指令，需要的時間為〔〕△t。A.200B.300C.400D.405答案：D第一條指令執行時間+(指令數-1)*各指令段執行時間中最大的執行時間。4△t+3△t+2△t+〔100-1〕X4△t=405△t6、以下關于Cache與主存間地址映射的表達中，正確的是〔〕。A.操作系統負責管理Cache與主存之間的地址映射B.程序員需要通過編程來處理Cache與主存之間的地址映射C.應用軟件對Cache與主存之間的地址映射進行調度D.由硬件自動完成Cache與主存之間的地址映射答案：D在程序的執行過程中，Cache與主存的地址映射是由硬件自動完成的7、可用于數字簽名的算法是〔〕。A.RSAB.IDEAC.RC4D.MD5答案：AIDEA算法和RC4算法都對稱加密算法，只能用來進行數據加密。MD5算法是消息摘要算法，只能用來生成消息摘要無法進行數字簽名。RSA算法是典型的非對稱加密算法，主要具有數字簽名和驗簽的功能。8、〔〕不是數字簽名的作用。A.接收者可驗證消息來源的真實性B.發送者無法否認發送過該消息C.接收者無法偽造或篡改消息D.可驗證接收者合法性答案：D數字簽名是信息的發送者才能產生的別人無法偽造的一段數字串，這段數字串同時也是對信息的發送者發送信息真實性的一個有效證明。不能驗證接收者的合法性。9、在網絡設計和實施過程中要采取多種平安措施，其中〔〕是針對系統平安需求的措施。A.設備防雷擊B.入侵檢測C.漏洞發現與補丁管理D.流量控制答案：C10、〔〕的保護期限是可以延長的。A.專利權B.商標權C.著作權D.商業秘密權答案：B根據?中華人民共和國商標法?第三十八條：注冊商標有效期滿，需要繼續使用的，應當在期滿前六個月內申請續展注冊。專利權和著作權到期后都無法延長，而商業秘密權無期限限制。11、甲公司軟件設計師完成了一項涉及計算機程序的創造。之后，乙公司軟件設計師也完成了與甲公司軟件設計師相同的涉及計算機程序的創造。甲、乙公司于同一天向專利局申請創造專利。此情形下，〔〕是專利權申請人。A.甲公司B.甲、乙兩公司C.乙公司D.由甲、乙公司協商確定的公司答案：D專利審查指南的規定：在審查過程中，對于不同的申請人同日〔指申請日，有優先權的指優先權日〕就同樣的創造創造分別提出專利申請，并且這兩件申請符合授予專利權的其他條件的，應當根據專利法實施細那么第四十一條第一款的規定，通知申請人自行協商確定申請人。12、甲、乙兩廠生產的產品類似，且產品都使用“B"商標。兩廠于同一天向商標局申請商標注冊，且申請注冊前兩廠均未使用“B"商標。此情形下，〔〕能核準注冊。A.甲廠B.由甲、乙廠抽簽確定的廠C.乙廠D.甲、乙兩廠答案：B按照商標法的規定，第29條，以及實施條例19條規定，同一天申請的，初步審定并公告使用在先的。駁回其他人的申請。均未使用獲無法證明的，各自協商，不愿協商或者協商不成的，抽簽決定，不抽簽的，視為放棄。13、在FM方式的數字音樂合成器中，改變數字載波頻率可以改變樂音的〔13〕，改變它的信號幅度可以改變樂音的〔14〕。A.音調B.音色C.音高D.音質答案：A14、在FM方式的數字音樂合成器中，改變數字載波頻率可以改變樂音的〔13〕，改變它的信號幅度可以改變樂音的〔14〕。A.音調B.音域C.音高D.帶寬答案：C15、結構化開發方法中，〔〕主要包含對數據結構和算法的設計。A.體系結構設計B.數據設計C.接口設計D.過程設計答案：D16、在敏捷過程的開發方法中，〔〕使用了迭代的方法，其中，把每段時間〔30天〕一次的迭代稱為一個“沖刺〞，并按需求的優先級別來實現產品，多個自組織和自治的小組并行地遞增實現產品。A.極限編程XPB.水晶法C.并列爭球法D.自適應軟件開發答案：C極限編程〔xp〕：由價值觀、原那么、實踐和行為四個局部組成。水晶法：每一個不同的工程都需要一套不同的策略、約定和方法論。并列爭球法：使用了迭代的方法，其中，把每段時間〔30天〕一次的迭代稱為一個“沖刺〞，并按需求的優先級別來實現產品，多個自組織和自治的小組并行地遞增實現產品。17、某軟件工程的活動圖如以下列圖所示，其中頂點表示工程里程碑，連接頂點的邊表示包含的活動，邊上的數字表示相應活動的持續時間〔天〕，那么完成該工程的最少時間為〔17〕天。活動BC和BF最多可以晚開始〔18〕天而不會影響整個工程的進度。A.11B.15C.16D.18答案：D18、A.0和7B.0和11C.2和7D.2和11答案：A19、本錢估算時，〔〕方法以規模作為本錢的主要因素，考慮多個本錢驅動因子。該方法包括三個階段性模型，即應用組裝模型、早期設計階段模型和體系結構階段模型。A.專家估算B.WolvertonC.COCOMOD.COCOMOⅡ答案：D20、邏輯表達式求值時常采用短路計算方式。“&&"、“||〞、“！〞分別表示邏輯與、或、非運算，“&&〞、“||〞為左結合，“！〞為右結合，優先級從高到低為“！〞、“&&〞、“||〞。對邏輯表達式“x&&〔yII!z〕〞進行短路計算方式求值時，〔〕。A.x為真，那么整個表達式的值即為真，不需要計算y和z的值B.x為假，那么整個表達式的值即為假，不需要計算y和z的值C.x為真，再根據z的值決定是否需要計算y的值D.x為假，再根據y的值決定是否需要計算z的值答案：B在進行邏輯與“&&〞運算時，只有當兩個操作數的值為真，最后的結果才會為真。因此一旦x的值為假，整個運算表達式的值那么為假。21、常用的函數參數傳遞方式有傳值與傳引用兩種。〔〕。A.在傳值方式下，形參與實參之間互相傳值B.在傳值方式下，實參不能是變量C.在傳引用方式下，修改形參實質上改變了實參的值。D.在傳引用方式下，實參可以是任意的變量和表達式。答案：C傳值調用最顯著的特征就是被調用的函數內部對形參的修改不影響實參的值。引用調用是將實參的地址傳遞給形參，使得形參的地址就是實參的地址。22、二維數組a[1..N，1..N]可以按行存儲或按列存儲。對于數組元素a[i,j]〔1<=i,j<=N〕，當〔〕時，在按行和按列兩種存儲方式下，其偏移量相同。A.i≠jB.i=jC.i>jD.i<j答案：B23、實時操作系統主要用于有實時要求的過程控制等領域。實時系統對于來自外部的事件必須在〔〕。A.一個時間片內進行處理B.一個周轉時間內進行處理C.一個機器周期內進行處理D.被控對象規定的時間內做出及時響應并對其進行處理答案：D實時操作系統是保證在一定時間限制內完成特定功能的操作系統。實時操作系統有硬實時和軟實時之分，硬實時要求在規定的時間內必須完成操作，這是在操作系統設計時保證的；軟實時那么只要按照任務的優先級，盡可能快地完成操作即可。24、假設某計算機系統中只有一個CPU、一臺輸入設備和一臺輸出設備，假設系統中有四個作業T1、T2、T3和T4，系統采用優先級調度，且T1的優先級>T2的優先級>T3的優先級>T4的優先級。每個作業Ti具有三個程序段：輸入Ii、計算Ci和輸出Pi〔i=1，2，3，4〕，其執行順序為Ii→Ci→Pi。這四個作業各程序段并發執行的前驅圖如下所示。圖中①、②分別為〔24〕，③、④、⑤分別為〔25〕。A.l2、P2B.l2、C2C.C1、P2D.C1、P3答案：C25、A.C2、C4、P4B.l2、l3、C4C.I3、P3、P4D.l3、C4、P4答案：D題目告訴我們一共有3個設備，分別是一個CPU、一臺輸入設備和一臺輸出設備，其實輸入設備對應程序段輸入Ii，而CPU對應程序段計算Ci，輸出設備對應程序段輸出Pi。而每個作業都分為這三段，各段間有個順序關系。再結合圖中已經給出的結點，我們不難發現，第一行是輸入，第二行是計算，而第三行的結點數輸出結點。因此可以知道①、②分別為C1、P3，③、④、⑤分別為I3、C4、P4。26、假設段頁式存儲管理系統中的地址結構如以下列圖所示，那么系統〔〕。A.最多可有256個段，每個段的大小均為2048個頁，頁的大小為8KB.最多可有256個段，每個段最大允許有2048個頁，頁的大小為8KC.最多可有512個段，每個段的大小均為1024個頁，頁的大小為4KD.最多可有512個段，每個段最大允許有1024個頁，頁的大小為4K答案：B頁內地址為13位，頁號地址為11位，段號地址為8位。根據公式，可以分別計算段號，頁號以及頁內地址最大的尋址空間。存儲管理系統中的地址長度均表示為最大的尋址空間。27、假設系統中有n個進程共享3臺掃描儀，并采用PV操怍實現進程同步與互斥。假設系統信號量S的當前值為-1，進程P1、P2又分別執行了1次P〔S〕操作，那么信號量S的值應為〔〕。A.3B.-3C.1D.-1答案：B當有進程運行時，其他進程訪問信號量，信號量就會減1。S=-1-2。28、某字長為32位的計算機的文件管理系統采用位示圖〔bitmap〕記錄磁盤的使用情況。假設磁盤的容量為300GB，物理塊的大小為1MB，那么位示圖的大小為〔〕個字。A.1200B.3200C.6400D.9600答案：D磁盤的容量為300GB，物理塊的大小為1MB，那么磁盤共300×1024/1個物理塊，位示圖的大小為300×1024/〔32〕=9600個字。29、某開發小組欲為一公司開發一個產品控制軟件，監控產品的生產和銷售過程，從購置各種材料開始，到產品的加工和銷售進行全程跟蹤。購置材料的流程、產品的加工過程以及銷售過程可能會發生變化。該軟件的開發最不適宜采用〔29〕模型，主要是因為這種模型〔30〕。A.瀑布B.原型C.增量D.噴泉答案：A30、某開發小組欲為一公司開發一個產品控制軟件，監控產品的生產和銷售過程，從購置各種材料開始，到產品的加工和銷售進行全程跟蹤。購置材料的流程、產品的加工過程以及銷售過程可能會發生變化。該軟件的開發最不適宜采用〔29〕模型，主要是因為這種模型〔30〕。A.不能解決風險B.不能快速提交軟件C.難以適應變化的需求D.不能理解用戶的需求答案：C對于較大型軟件系統的需求往往難以在前期確定，所以瀑布模型最不適合。對于較大型軟件系統的需求往往難以在前期確定，所以瀑布模型最不適合。31、〔〕不屬于軟件質量特性中的可移植性。A.適應性B.易安裝性C.易替換性D.易理解性答案：D可移植性包含：適應性、易安裝性、共存性和易替換性四個特性。32、對以下列圖所示流程圖采用白盒測試方法進行測試，假設要滿足路徑覆蓋，那么至少需要〔32〕個測試用例。采用McCabe度量法計算該程序的環路復雜性為〔33〕。A.3B.4C.6D.8答案：C33、A.1B.2C.3D.4答案：D環形復雜度V(G)=E-N+2，其中，E是流圖中邊的條數，N是結點數。V(G)=E-N+2=10-8+2=4。34、計算機系統的〔〕可以用MTBF/〔1+MTBF〕來度量，其中MTBF為平均失效間隔時間。A.可靠性B.可用性C.可維護性D.健壯性答案：A35、以下關于軟件測試的表達中，不正確的是〔〕。A.在設計測試用例時應考慮輸入數據和預期輸出結果B.軟件測試的目的是證明軟件的正確性C.在設計測試用例時，應該包括合理的輸入條件D.在設計測試用例時，應該包括不合理的輸入條件答案：B軟件測試的目的在于希望以最少的人力和時間發現潛在的各種錯誤和缺陷。36、某模塊中有兩個處理A和B，分別對數據結構X寫數據和讀數據，那么該模塊的內聚類型為〔〕內聚。A.邏輯B.過程C.通信D.內容答案：C如果一個模塊的所有成分都操作同一數據集或生成同一數據集，那么稱為通信內聚。內聚有一下幾種：功能內聚：完成一個單一功能，各個局部協同工作，缺一不可。順序內聚：處理元素相關，而且必須順序執行。通信內聚：所有處理元素集中在一個數據結構的區域上。過程內聚：處理元素相關，而且必須按特定的次序執行。瞬時內聚：所包含的任務必須在同一時間間隔內執行〔如初始化模塊〕。邏輯內聚：完成邏輯上相關的一組任務。偶然內聚：完成一組沒有關系或松散關系的任務。37、在面向對象方法中，不同對象收到同一消息可以產生完全不同的結果，這一現象稱為〔〕。在使用時，用戶可以發送一個通用的消息，而實現的細節那么由接收對象自行決定。A.接口B.繼承C.覆蓋D.多態答案：D此題考察面向對象多態的概念。多態實質上是將子類的指針對象或者引用對象傳遞給父類指針對象后，通過這個父類指針對象調用的函數〔此函數在父類中聲明為虛函數，且在各個子類中重寫這個函數〕，不是父類中定義的，而是傳遞進來的子類對象中重寫的函數。38、在面向對象方法中，支持多態的是〔〕。A.靜態分配B.動態分配C.靜態類型D.動態綁定答案：D動態綁定是實現多態的根底。39、面向對象分析的目的是為了獲得對應用問題的理解，其主要活動不包括〔〕。A.認定并組織對象B.描述對象間的相互作用C.面向對象程序設計D.確定基于對象的操作答案：C面向對象分析的任務是了解問題域所涉及的對象、對象間的關系和操作，然后構造問題的對象模型。40、如下所示的UML狀態圖中，〔〕時，不一定會離開狀態B。A.狀態B中的兩個結束狀態均到達B.在當前狀態為B2時，事件e2發生C.事件e2發生D.事件e1發生答案：C當e2發生時，如果當前狀態是B2，那么會離開B；如果當前狀態不是B2，那么不會離開。41、以下關于UML狀態圖中轉換〔transition〕的表達中，不正確的是〔〕。A.活動可以在轉換時執行也可以在狀態內執行B.監護條件只有在相應的事件發生時才進行檢查C.一個轉換可以有事件觸發器、監護條件和一個狀態D.事件觸發轉換答案：C轉換的五要素：源狀態：即受轉換影響的狀態目標狀態：當轉換完成后對象的狀態觸發事件：用來為轉換定義一個事件，包括調用、改變、信號、時間四類事件監護條件：布爾表達式，決定是否激活轉換、動作：轉換激活時的操作42、以下列圖①②③④所示是UML〔42〕。現有場景：一名醫生〔Doctor〕可以治療多位病人〔Patient〕，一位病人可以由多名醫生治療，一名醫生可能屢次治療同一位病人。要記錄哪名醫生治療哪位病人時，需要存儲治療〔Treatment〕的日期和時間。以下①②③④圖中〔43〕。是描述此場景的模型。A.用例圖B.對象圖C.類圖D.協作圖答案：C類圖描述的是類與類之間的關系對象圖描述的是某個具體的對象。本圖描述的是類與類之間的關系。43、A.①B.②C.③D.④答案：C44、〔44〕模式定義一系列的算法，把它們一個個封裝起來，并且使它們可以相互替換，使得算法可以獨立于使用它們的客戶而變化。以下〔45〕情況適合選用該模式。①一個客戶需要使用一組相關對象②一個對象的改變需要改變其它對象③需要使用一個算法的不同變體④許多相關的類僅僅是行為有異A.命令〔Command〕B.責任鏈〔ChainofResponsibility〕C.觀察者〔Observer〕D.策略〔Strategy〕答案：D45、A.①②B.②③C.③④D.①④答案：C策略模式定義了一系列的算法，并將每一個算法封裝起來，而且使它們還可以相互替換。策略模式讓算法獨立于使用它的客戶而獨立變化。應用場景：1、多個類只區別在表現行為不同，可以使用Strategy模式，在運行時動態選擇具體要執行的行為。2、需要在不同情況下使用不同的策略(算法)，或者策略還可能在未來用其它方式來實現。3、對客戶隱藏具體策略(算法)的實現細節，彼此完全獨立。46、〔46〕模式將一個復雜對象的構建與其表示別離，使得同樣的構建過程可以創建不同的表示。以下〔47〕情況適合選用該模式。①抽象復雜對象的構建步驟②基于構建過程的具體實現構建復雜對象的不同表示③一個類僅有一個實例④一個類的實例只能有幾個不同狀態組合中的一種A.生成器〔Builder〕B.工廠方法〔FactoryMethod〕C.原型〔Prototype〕D.單例〔Singleton〕答案：A47、A.①②B.②③C.③④D.①④答案：A生成器模式將一個復雜對象的構建與它的表示別離，使得同樣的構建過程可以創立不同的表示。實用范圍1當創立復雜對象的算法應該獨立于該對象的組成局部以及它們的裝配方式時。2當構造過程必須允許被構造的對象有不同表示時。48、由字符a、b構成的字符串中，假設每個a后至少跟一個b，那么該字符串集合可用正規式表示為〔〕。A.〔b|ab〕*B.〔ab*〕*C.〔a*b*〕*D.〔a|b〕*答案：A規式(a｜b)*表示字符a和b組成的任何長度的字符串(a和b的位置任意)。a*｜b*表示由假設干個a組成的字符串，或者是由假設干個b組成的任何長度的字符串。a*b*薩表示由假設干個a后跟假設干個b所組成的任何長度的字符串(a在b前面)。(ab)*表示每個ab所組成的任何長度的字符串(ab不能別離)。(a*b*)*表示由字符a和b組成的任何長度的字符串(假設干個a后面跟假設干個b，b后面再跟假設干個a)。只有(a*b*)*與(a｜b)*含義相同，因此正規式(a｜b)*與(a*b*)*是等價的。49、喬姆斯基〔Chomsky〕將文法分為4種類型，程序設計語言的大多數語法現象可用其中的〔〕描述。A.上下文有關文法B.上下文無關文法C.正規文法D.短語結構文法答案：B上下文無關文法：形式語言理論中一種重要的變換文法，用來描述上下文無關語言，在喬姆斯基分層中稱為2型文法。由于程序設計語言的語法根本上都是上下文無關文法，因此應用十分廣泛。50、運行下面的C程序代碼段，會出現〔〕錯誤。intk=0;for(;k<100;);{k++;}A.變量未定義B.靜態語義C.語法D.動態語義答案：D在此題中，for語句后有“;〞號，說明該循環語句的語句體為空，此時，循環會是一個死循環，所以存在語義錯誤51、在數據庫系統中，一般由DBA使用DBMS提供的授權功能為不同用戶授權，其主要目的是為了保證數據庫的〔〕。A.正確性B.平安性C.一致性D.完整性答案：BDBMS是數據庫管理系統，主要用來保證數據庫的平安性和完整性。而DBA通過授權功能為不同用戶授權，主要的目的是為了保證數據的平安性。52、給定關系模式R〔U,F〕，其中：U為關系模式R中的屬性集，F是U上的一組函數依賴。假設U={A1，A2，A3，A4}，F={A1→A2，A1A2→A3，A1→A4，A2→A4}，那么關系R的主鍵應為〔52〕。函數依賴集F中的〔53〕是冗余的。A.A1B.A1A2C.A1A3D.A1A2A3答案：A53、A.A1→A2B.A1A2→A3C.A1→A4D.A2→A4答案：C此題中U1={A1、A2、A3、A4}，構造出依賴關系圖之后，A1是入度為0的結點，且從A1出發能遍歷全圖，因此A1為主鍵。A1→A2，A2→A4利用傳遞率：A1→A4，因此A1→A4是冗余。54、給定關系R〔A，B，C，D〕和關系S〔A，C，E，F〕，對其進行自然連接運算R?S后的屬性列為〔54〕個；與σR.B>S.E(R?S)等價的關系代數表達式為〔55〕。A.4B.5C.6D.8答案：C55、A.B.C.D.答案：B關系R〔A,B,C,D〕和S〔A,C,E,F〕做自然連接時，會以兩個關系公共字段做等值連接，然后將操作結果集中重復列去除，所以運算后屬性列有6個56、以下查詢B=“大數據〞且F=“開發平臺〞，結果集屬性列為A、B、C、F的關系代數表達式中，查詢效率最高的是〔〕。A.π1,2,3,8〔σ2='大數據'^1=5^3=6^8='開發平臺'〔R×S〕〕B.π1,2,3,8〔σ1=5^3=6^8='開發平臺'〔σ2='大數據'〔R〕×S〕〕C.π1,2,3,8〔σ2='大數據'^1=5^3=6〔R×σ4='開發平臺'〔S〕〕D.π1,2,3,8〔σ1=5^3=6〔σ2='大數據'〔R〕×σ4='開發平臺'〔S〕〕〕答案：D57、拓撲序列是有向無環圖中所有頂點的一個線性序列，假設有向圖中存在弧<v，w>或存在從頂點v到w的路徑，那么在該有向圖的任一拓撲序列中，v一定在w之前。下面有向圖的拓撲序列是〔〕。A.41235B.43125C.42135D.41325答案：A拓撲排序通俗一點來講，其實就是依次遍歷沒有前驅結點的結點。而某一時刻沒有前驅結點的結點有可能存在多個，所以一個圖的拓撲排序可能有多個。4號結點沒有前戲，所以拓撲排序的第一個元素是4。當4訪問完了就可以訪問1，1號訪問完了就可以訪問2，2號訪問完了就可以訪問3或5。所以拓撲排序結果為：412(35)58、設有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，假設采用順序存儲結構，那么平均需要移動〔58〕個元素；假設采用單鏈表存儲，那么平均需要移動〔59〕個元素。A.1B.(n-1)/2C.lognD.n答案：B假設用順序表存儲，那么最好情況是刪除最后一個元素，此時不用移動任何元素，直接刪除，最差的情況是刪除第一個元素，此時需要移動n-1個元素，所以平均狀態是移動(n-1)/2。假設用鏈表存儲，直接將需要刪除元素的前趨next指針指向后繼元素即可，不需要移動元素，所以移動元素個數為0。59、設有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，假設采用順序存儲結構，那么平均需要移動〔58〕個元素；假設采用單鏈表存儲，那么平均需要移動〔59〕個元素。A.0B.1C.(n-1)/2D.n/2答案：A假設用順序表存儲，那么最好情況是刪除最后一個元素，此時不用移動任何元素，直接刪除，最差的情況是刪除第一個元素，此時需要移動n-1個元素，所以平均狀態是移動(n-1)/2。假設用鏈表存儲，直接將需要刪除元素的前趨next指針指向后繼元素即可，不需要移動元素，所以移動元素個數為0。60、具有3個節點的二叉樹有〔〕種形態。A.2B.3C.5D.7答案：C61、以下關于二叉排序樹〔或二叉查找樹、二叉搜索樹〕的表達中，正確的是〔〕。A.對二叉排序樹進行先序、中序和后序遍歷，都得到結點關鍵字的有序序列B.含有n個結點的二叉排序樹高度為〔log2n〕+1C.從根到任意一個葉子結點的路徑上，結點的關鍵字呈現有序排列的特點D.從左到右排列同層次的結點，其關鍵字呈現有序排列的特點答案：D62、下表為某文件中字符的出現頻率，采用霍夫曼編碼對以下字符編碼，那么字符序列“bee〞的編碼為〔62〕；編碼“〞的對應的字符序列為〔63〕。C.001100100D.110011011答案：A63、A.badB.beeC.faceD.bace答案：C64、兩個矩陣Am*n和Bn*p相乘，用根本的方法進行，那么需要的乘法次數為m*n*p。多個矩陣相乘滿足結合律，不同的乘法順序所需要的乘法次數不同。考慮采用動態規劃方法確定Mi，M(i+1)，…，Mj多個矩陣連乘的最優順序，即所需要的乘法次數最少。最少乘法次數用m[i,j]表示，其遞歸式定義為：其中i、j和k為矩陣下標，矩陣序列中Mi的維度為〔pi-1〕*pi采用自底向上的方法實現該算法來確定n個矩陣相乘的順序，其時間復雜度為〔64〕。假設四個矩陣M1、M2、M3、M4相乘的維度序列為2、6、3、10、3，采用上述算法求解，那么乘法次數為〔65〕。A.O〔n2〕B.O〔n2lgn〕C.O〔n3〕D.O〔n3lgn〕答案：C四個矩陣分別為：2*66*33*1010*3先計算：M1*M2 及M3*M4，計算次數分別為：2*6*3=36，3*10*3=90。然后結果相乘，計算次數為：2*3*3=18。36+90+18=144。65、A.156B.144C.180D.360答案：B四個矩陣分別為：2*66*33*1010*3先計算：M1*M2 及M3*M4，計算次數分別為：2*6*3=36，3*10*3=90。然后結果相乘，計算次數為：2*3*3=18。36+90+18=144。66、以下協議中屬于應用層協議的是〔66〕，該協議的報文封裝在〔67〕。A.SNMPB.ARPC.ICMPD.X.25答案：AARP和ICMP是網絡層協議，X.25是數據鏈路層協議，只有SNMP是應用層協議。SNMP協議的報文是封裝在UDP協議中傳送。67、以下協議中屬于應用層協議的是〔66〕，該協議的報文封裝在〔67〕。A.TCPB.IPC.UDPD.ICMP答案：CARP和ICMP是網絡層協議，X.25是數據鏈路層協議，只有SNMP是應用層協議。SNMP協議的報文是封裝在UDP協議中傳送。68、某公司內部使用wb.xyz作為訪問某效勞器的地址，其中wb是〔〕。A.主機名B.協議名C.目錄名D.文件名答案：A69、如果路由器收到了多個路由協議轉發的關于某個目標的多條路由，那么決定采用哪條路由的策略是〔〕。A.選擇與自己路由協議相同的B.選擇路由費用最小的C.比較各個路由的管理距離D.比較各個路由協議的版本答案：C對于多種不同的路由協議到一個目的地的路由信息，路由器首先根據管理距離決定相信哪一個協議70、與地址2匹配的路由表的表項是〔〕。答案：D地址2中179的二制碼為10110011，假設網絡號采用22位，與該地址匹配的路由表項那么為4/22。Softwareentitiesaremorecomplexfortheirsizethanperhapsanyotherhumanconstruct,becausenotwopartsarealike(atleastabovethestatementlevel).Iftheyare,wemakethetwosimilarpartsintoone,a〔71〕,openorclosed.Inthisrespectsoftwaresystemsdifferprofoundlyfromcomputers,buildings,orautomobiles,whererepeatedelementsabound.Digitalcomputersarethemselvesmorecomplexthanmostthingspeoplebuild;theyhaveverylargenumbersofstates.Thismakesconceiving,describing,andtestingthemhard.Softwaresystemshaveordersofmagnitudemore〔72〕thancomputersdo.Likewise,ascaling-upofasoftwareentityisnotmerelyarepetitionofthesameelementsinlargersize;itisnecessarilyanincreaseinthenumberofdifferentelements.Inmostcases,theelementsinteractwitheachotherinsome〔73〕fashion,andthecomplexityofthewholeincreasesmuchmorethanlinearly.Thecomplexityofsoftwareisa(an)〔74〕property,notanaccidentalone.Hencedescriptionsofasoftwareentitythatabstractawayitscomplexityoftenabstractawayitsessence.Mathematicsandthephysicalsciencesmadegreatstridesforthreecenturiesbyconstructingsimplifiedmodelsofcomplexphenomena,derivingpropertiesfromthemodels,andverifyingthosepropertiesexperimentally.Thisworkedbecausethecomplexities〔75〕inthemodelswerenottheessentialpropertiesofthephenomena.Itdoesnotworkwhenthecomplexitiesaretheessence.Manyoftheclassicalproblemsofdevelopingsoftwareproductsderivefromthisessentialcomplexityanditsnonlinearincreaseswithsize.Notonlytechnicalproblemsbutmanagementproblemsaswellcomefromthecomplexity.71、A.taskB.jobC.subroutineD.program答案：C72、A.statesB.partsC.conditionsD.expressions答案：A73、A.linearB.nonlinearC.parallelD.additive答案：B74、A.surfaceB.outsideC.exteriorD.essential答案：D75、A.fixedB.includedC.ignoredD.stabilized答案：C下午試卷案例第1題閱讀以下說明，答復以下問題1至問題4，將解答填入答題紙的對應欄內。【說明】某證券交易所為了方便提供證券交易效勞，欲開發一證券交易平臺，該平臺的主要功能如下：〔1〕開戶。根據客戶效勞助理提交的開戶信息，進行開戶，并將客戶信息存入客戶記錄中，賬戶信息〔余額等〕存入賬戶記錄中；〔2〕存款。客戶可以向其賬戶中存款，根據存款金額修改賬戶余額；〔3〕取款。客戶可以從其賬戶中取款，根據取款金額修改賬戶余額；〔4〕證券交易。客戶和經紀人均可以進行證券交易〔客戶通過在線方式，經紀人通過〕，將交易信息存入交易記錄中；〔5〕檢查交易。平臺從交易記錄中讀取交易信息，將交易明細返回給客戶。現采用結構化方法對該證券交易平臺進行分析與設計，獲得如圖1-1所示的上下文數據流圖和圖1-2所示的0層數據流圖。問題：1.1〔3分〕使用說明中的詞語，給出圖1-1中的實體E1-E3的名稱。問題：1.2〔3分〕使用說明中的詞語，給出圖1-2中的數據存儲D1-D3的名稱。問題：1.3〔4分〕根據說明和圖中的術語，補充圖1-2中缺失的數據流及其起點和終點。問題：1.4〔5分〕實際的證券交易通常是在證券交易中心完成的，因此，該平臺的“證券交易〞功能需將交易信息傳遞給證券交易中心。針對這個功能需求，需要對圖1-1和圖1-2進行哪些修改，請用200字以內的文字加以說明。答案解析：E1：客戶效勞助理，E2：客戶，E3：經紀人。此題要求識別E1-E3具體為哪個外部實體，通讀試題說明，可以了解到適合充當外部實體的包括：客戶、客戶效勞助理、經記人。具體的對應關系，可以通過將頂層圖與題目說明進行匹配得知。如：從圖中可看出E1會向交易平臺發出數據流開戶信息;；而從試題說明根據客戶效勞助理提交的開戶信息，進行開戶，并將客戶信息存入客戶記錄中，賬戶信息存入賬戶記錄中可以看出，E1對應是客戶效勞助理。E2、E3同理可得。答案解析：D1：客戶記錄，D2：賬戶記錄，D3：交易記錄。此題要求識別存儲，解決這類問題，以圖的分析為主，配合說明給存儲命名，因為存儲相關的數據流一般展現了這個存儲中到底存了些什么信息，如從圖中可以看到D1中有客戶信息，而D2中有賬戶信息，題目說明中又有根據客戶效勞助理提交的開戶信息，進行開戶，并將客戶信息存入客戶記錄中，賬戶信息存入賬戶記錄中。自然D1應為客戶記錄，D2應為賬戶記錄。同理，D3為交易記錄。答案解析：數據流名稱：修改賬戶余額，起點：存款，終點：D2。數據流名稱：修改賬戶余額，起點：取款，終點：D2。數據流名稱：交易信息存入交易記錄，起點：證券交易，終點：D3。缺失數據流1名稱：修改賬戶余額，起點：存款，終點：D2。理由：從試題說明客戶可以向其賬戶中存款，根據存款金額修改賬戶余額可以看出，這個功能有操作根據存款金額修改賬戶余額。據此可以了解到從該功能應有數據流存款至D2，而0層圖沒有。缺失數據流2:名稱：修改賬戶余額，起點：取款，終點：D2。理由：從試題說明客戶可以從其賬戶中取款，根據取款金額修改賬戶余額可以看出，這個功能有操作根據取款金額修改賬戶余額。據此可以了解到從該功能應有數據流取款至D2，而0層圖沒有。缺失數據流3名稱：交易信息存入交易記錄，起點：證券交易，終點：D3。理由：從試題說明客戶和經紀人均可以進行證券交易，將交易信息存入交易記錄中可以看出，這個功能有操作將交易信息存入交易記錄中。據此可以了解到從該功能應有數據流證券交易至D3，而0層圖沒有。答案解析：增加外部實體證券交易中心，原來證券交易中的交易信息的數據流終點改為證券交易中心，數據流檢測交易中的起點改為證券交易中心。此題強調實際的證券交易通常是在證券交易中心完成，這個證券交易中心屬于典型的外部實體，所以需要增加外部實體證券交易中心。由于該平臺的證券交易功能需將交易信息傳遞給證券交易中心，因此將原來證券交易中的交易信息的數據流終點改為證券交易中心，數據流檢測交易中的起點改為證券交易中心。第2題【說明】某賓館為了有效地管理客房資源，滿足不同客戶需求，擬構建一套賓館信息管理系統，以方便賓館管理及客房預訂等業務活動。【需求分析結果】該系統的局部功能及初步需求分析的結果如下：〔1〕賓館有多個部門，部門信息包括部門號、部門名稱、、經理。每個部門可以有多名員工，每名員工只屬于一個部門；每個部門只有一名經理，負責管理本部門。〔2〕員工信息包括員工號、姓名、崗位、、工資，其中，員工號唯一標識員工關系中的一個元組，崗位有經理、業務員。〔3〕客房信息包括客房號〔如1301、1302等〕、客房類型、收費標準、入住狀態〔已入住／未入住〕，其中客房號唯一標識客房關系中的一個元組，不同客房類型具有不同的收費標準。〔4〕客戶信息包括客戶號、單位名稱、聯系人、聯系、，其中客戶號唯一標識客戶關系中的一個元組。〔5〕客戶預訂客房時，需要填寫預訂申請。預訂申請信息包括申請號、客戶號、入住時間、入住天數、客房類型、客房數量，其中，一個申請號唯一標識預訂申請中的一個元組；一位客戶可以有多個預訂申請，但一個預訂申請對應唯一的一位客戶。〔6〕當客戶入住時，業務員根據客戶的預訂申請負責安排入住客房事宜。安排信息包括客房號、姓名、性別、身份證號、入住時間、天數、，其中客房號、身份證號和入住時間唯一標識一次安排。一名業務員可以安排多個預訂申請，一個預訂申請只由一名業務員安排，而且可安排多間同類型的客房。【概念模型設計】根據需求階段收集的信息，設計的實體聯系圖如圖2-1所示。【關系模式設計】部門〔部門號，部門名稱，經理，〕員工〔員工號，〔a〕，姓名，崗位，，工資〕客戶〔〔b〕，聯系人，聯系，〕客房〔客房號，客房類型，收費標準，入住狀態〕預訂申請〔〔c〕，入住時間，天數，客房類型，客房數量〕安排〔申請號，客房號，姓名，性別，〔d〕，天數，，業務員〕問題：2.1〔4分〕根據問題描述，補充四個聯系，完善圖2-1，的實體聯系圖。聯系名可用聯系1、聯系2、聯系3和聯系4代替，聯系的類型為1:1、1:n和m:n〔或1:1，和1:*和*:*〕。問題：2.2〔8分〕〔1〕根據題意，將關系模式中的空〔a〕～〔d〕補充完整，并填入答題紙對應的位置上。〔2〕給出“預訂申請〞和“安排〞關系模式的主鍵和外鍵。問題：2.3〔3分〕【關系模式設計】中的“客房〞關系模式是否存在標準性問題，請用100字以內文字解釋你的觀點〔假設存在問題，應說明如何修改“客房〞關系模式〕。答案解析：1、經理與部門之間存在1:1的聯系。2、部門與員工之間存在1:n的聯系。3、客戶與預訂申請之間存在1:n的聯系。4、業務員、客房、預訂申請之間存在1:m:n的聯系。答案解析：〔a〕部門號。〔b〕客戶號、單位名稱〔c〕申請號、客戶號。〔d〕身份證號、入住時間。預訂申請關系模式中的主鍵是申請號，外鍵是申請號、客戶號。安排關系模式中的主鍵是：〔客房號、身份證號、入住時間〕，外鍵是：申請號、客房號、業務員。答案解析：根據試題中的描述，客房信息中客房號是唯一標識客房關系的一個元組，即可以作為唯一的主鍵。在客房關系模式中，不存在其他局部依賴關系，但客房號->類型->收費標準，存在傳遞函數依賴，所以冗余，添加異常，修改異常，刪除異常均存在。第3題【說明】某種出售罐裝飲料的自動售貨機．〔VendingMachine〕的工作過程描述如下：〔1〕顧客選擇所需購置的飲料及數量。〔2〕顧客從投幣口向自動售貨機中投入硬幣〔該自動售貨機只接收硬幣〕。硬幣器收集投入的硬幣并計算其對應的價值。如果所投入的硬幣足夠購置所需數量的這種飲料且飲料數量足夠，那么推出飲料，計算找零，顧客取走飲料和找回的硬幣；如果投入的硬幣不夠或者所選購的飲料數量缺乏，那么提示用戶繼續投入硬幣或重新選擇飲料及數量。〔3〕一次購置結束之后，將硬幣器中的硬幣移走〔清空硬幣器〕，等待下一次交易。自動售貨機還設有一個退幣按鈕，用于退還顧客所投入的硬幣。已經成功購置飲料的錢是不會被退回的。采用面向對象方法分析和設計該自動售貨機的軟件系統，得到如圖3-1所示的用例圖，其中，用例“購置飲料〞的用例規約描述如下。參與者：顧客。主要事件流：1．顧客選擇需要購置的飲料和數量，投入硬幣；2．自動售貨機檢查顧客是否投入足夠的硬幣；3．自動售貨機檢查飲料儲存倉中所選購的飲料是否足夠；4．自動售貨機推出飲料；5．自動售貨機返回找零。各選事件流：2a．假設投入的硬幣缺乏，那么給出提示并退回到1；3a．假設所選購的飲料數量缺乏，那么給出提示并退回到1。根據用例“購置飲料〞得到自動售貨機的4個狀態：“空閑〞狀態、“準備效勞〞狀態、“可購置〞狀態以及“飲料出售〞狀態，對應的狀態圖如圖3-2所示。所設計的類圖如圖3-3所示。問題：3.1〔6分〕根據說明中的描述，使用說明中的術語，給出圖3-2中的S1～S4所對應的狀態名。問題：3.2〔4分〕根據說明中的描述，使用說明中的術語，給出圖3-2中的E1～E4所對應的事件名問題：3.3〔5分〕根據說明中的描述，使用說明中的術語，給出圖3-3中C1～C5所對應的類名。答案解析：S1：空閑，S2：準備效勞，S3：飲料出售，S4：可購置。此題系統中的狀態圖，是對狀態轉換的圖形化表達。從題目的說明局部可知，在狀態轉換過程中，涉及到的狀態一共有四種：空閑、準備效勞、可購置、飲料出售。從狀態圖涉及的轉換可知S1~S4分別為：空閑、準備效勞、飲料出售、可購置。關于狀態轉換的分析如下：〔1〕清空硬幣器后，自動售貨機等待下一次交易，進入空閑狀態。此時可任意的進行飲料選擇數量，一旦顧客投入硬幣，自動售貨機便進入準備效勞狀態。〔2〕當自動售貨機進行準備效勞狀態時，開始計算硬幣價值，如果硬幣不夠那么提示顧客繼續投入硬幣。如果硬幣足夠，那么進入可購置狀態。〔3〕進行可購置狀態后，自動售貨機判斷飲料數量。如果數量不夠，那么返回準備效勞狀態提示用戶重新選擇飲料。如果數量足夠，那么推出飲料進入飲料出售狀態。〔4〕進行飲料出售狀態后，自動售貨機計算找零，并返回進入空閑狀態等待下一次交易。答案解析：E1：飲料數量缺乏，E2：硬幣數量足夠，E3：推出飲料，E4：返回找零。答案解析：C1：自動售貨機，C2：硬幣器，C3：飲料儲存倉，C4：硬幣，C5：飲料。第4題閱讀以下說明和C代碼，答復以下問題1至問題3，將解答寫在答題紙的對應欄內。【說明】模式匹配是指給定主串t和子串s，在主串t中尋找子串s的過程，其中s稱為模式。如果匹配成功，返回s在t中的位置，否那么返回-1。KMP算法用next數組對匹配過程進行了優化。KMP算法的偽代碼描述如下：1．在串t和串s中，分別設比較的起始下標i=j=0。2．如果串t和串s都還有字符，那么循環執行以下操作：〔1〕如果j=-l或者t[i]=s[j]，那么將i和j分別加1，繼續比較t和s的下一個字符；〔2〕否那么，將j向右滑動到next[j]的位置，即j=next[j]。3．如果s中所有字符均已比較完畢，那么返回匹配的起始位置〔從1開始〕；否那么返回-1．其中，next數組根據子串s求解。求解next數組的代碼已由get_next函數給出。【C代碼】〔1〕常量和變量說明t，s：長度為憫鉑Is的字符串next:next數組，長度為Is〔2〕C程序#include<stdio.h>#include<stdlib.h>#include<string.h>/*求next[]的值*/voidget_next(int*next,char*s,intIs){inti=0，j=-1;next[0]=-1;/*初始化next[0]*/while(i<ls){/*還有字符*/if(j==-1lls[i]==s[j]){/*匹配*/j++;i++;if(s[i]==s[j])next[i]=next[j];elseNext[i]=j;}elsej=next[j];}}intkmp(int*next,char*t,char*s,intlt,intIs){Inti=0,j=0;while(i<lt&&〔1〕){if(j==-1||〔2〕){i++;j++;}else〔3〕;}if(j>=ls)return〔4〕;elsereturn-1;}問題：4.1〔8分〕根據題干說明，填充C代碼中的空〔1〕～〔4〕.問題：4.2〔2分〕根據題干說明和C代碼，分析出kmp算法的時間復雜度為〔5〕〔主串和子串的長度分別為It和Is，用O符號表示〕。問題：4.3〔5分〕根據C代碼，字符串“BBABBCAC〞的next數組元素值為〔6〕〔直接寫素值，之間用逗號隔開〕。假設主串為“AABBCBBABBCACCD〞，子串為“BBABBCAC〞，那么函數Kmp的返回值是〔7〕。答案解析：〔1〕：j<ls〔2〕：t[i]==s[j];〔3〕：get_next(next,s,ls);j=next[j]〔4〕：i+1-ls答案解析：(5)O(ls+lt)答案解析：〔6〕[-1,-1,1,-1,-1,2,0,0]〔7〕6第5題閱讀以下說明和C++-代碼，將應填入〔n〕處的字句寫在答題紙的對應欄內。【說明】某發票〔lnvoice〕由抬頭〔Head〕局部、正文局部和腳注〔Foot〕局部構成。現采用裝飾〔Decorator〕模式實現打印發票的功能，得到如圖5-1所示的類圖。問題：5.1【C++代碼】#include<iostream>usingnamespacestd;classInvoice{public:〔1〕{cout<<"Thisisthecontentoftheinvoice!"<<endl;}};classDecorator:publicInvoice{Invoice*ticket;public:Decorator(