省考軟件設計師考試模擬題及答案從業(yè)資格考試測試題(4)

1、 軟件設計師考試模擬題及答案-試題一 閱讀以下說明和圖，回答問題1至問題4，將解答填入對應欄內?！菊f明】 某音像制品出租商店欲開發(fā)一個音像管理信息系統(tǒng)，管理音像制品的租借業(yè)務。需求如下： 1系統(tǒng)中的客戶信息文件保存了該商店的所有客戶的用戶名、密碼等信息。對于首次來租借的客戶，系統(tǒng)會為其生成用戶名和初始密碼。 2系統(tǒng)中音像制品信息文件記錄了商店中所有音像制品的詳細信息及其庫存數(shù)量。 3根據(jù)客戶所租借的音像制品的品種，會按天收取相應的費用。音像制品的最長租借周期為1周，每位客戶每次最多只能租借6件音像制品。 4客戶租借某種音像制品的具體流程如下。 1根據(jù)客戶提供的用戶名和密碼，驗證客戶身份。 2若

2、該客戶是合法客戶，查詢音像制品信息文件，查看商店中是否還有這種音像制品。 3若還有該音像制品，且客戶所要租借的音像制品數(shù)小于等于6個，就可以將該音像制品租借給客戶。這時，系統(tǒng)給出相應的租借確認信息，生成一條新的租借記錄并將其保存在租借記錄文件中。 4系統(tǒng)計算租借費用，將費用信息保存在租借記錄文件中并告知客戶。 5客戶付清租借費用之后，系統(tǒng)接收客戶付款信息，將音像制品租借給該客戶。 5當庫存中某音像制品數(shù)量不能滿足客戶的租借請求數(shù)量時，系統(tǒng)可以接受客戶網上預約租借某種音像制品。系統(tǒng)接收到預約請求后，檢查庫存信息，驗證用戶身份，創(chuàng)建相應的預約記錄，生成預約流水號給該客戶，并將信息保存在預約記錄文件

3、中。 6客戶歸還到期的音像制品，系統(tǒng)修改租借記錄文件，并查詢預約記錄文件和客戶信息文件，判定是否有客戶預約了這些音像制品。若有，則生成預約提示信息，通知系統(tǒng)履行預約服務，系統(tǒng)查詢客戶信息文件和預約記錄文件，通知相關客戶前來租借音像制品。 1、【問題1】 圖(a)中只有一個外部實體E1。使用【說明】中的詞語，給出E1的名稱。2、【問題2】 使用【說明】中的詞語，給出圖(b)中的數(shù)據(jù)存儲D1D4的名稱。3、【問題3】 數(shù)據(jù)流圖(b)缺少了3條數(shù)據(jù)流，根據(jù)說明及數(shù)據(jù)流圖(a)提供的信息，分別指出這3條數(shù)據(jù)流的起點和終點。起點終點4、【問題4】 在進行系統(tǒng)分析與設計時，面向數(shù)據(jù)結構的設計方法(如Jac

4、kson方法)也被廣泛應用。簡要說明面向數(shù)據(jù)結構設計方法的基本思想及其適用場合。試題二 閱讀下列說明，回答問題1至問題3，將解答填入對應欄內?！菊f明】 某地區(qū)舉行籃球比賽，需要開發(fā)一個比賽信息管理系統(tǒng)來記錄比賽的相關信息。【需求分析結果】 1登記參賽。球隊的信息。記錄球隊的名稱、代表地區(qū)、成立時間等信息。系統(tǒng)記錄球隊每個隊員的姓名、年齡、身高、體重等信息。每個球隊有一個教練負責管理球隊，一個教練僅負責一個球隊。系統(tǒng)記錄教練的姓名、年齡等信息。 2安排球隊的訓練信息。比賽組織者為球隊提供了若干塊場地，供球隊進行適應性訓練。系統(tǒng)記錄現(xiàn)有的場地信息，包括：場地名稱、場地規(guī)模、位置等信息。系統(tǒng)可為每個

5、球隊安排不同的訓練場地，如下表所示。系統(tǒng)記錄訓練場地安排的信息。球隊名稱場地名稱訓練時間解放軍一號球場2008-06-0914:00-18:00解放軍一號球場2008-06-1209:00-12:00解放軍二號球場2008-06-1114:00-1800山西一號球場2008-06-1009:00-12:00 3安排比賽。該賽事聘請專職裁判，每場比賽只安排一個裁判。系統(tǒng)記錄裁判的姓名、年齡、級別等信息。系統(tǒng)按照一定的規(guī)則，首先分組，然后根據(jù)球隊、場地和裁判情況，安排比賽(每場比賽的對陣雙方分別稱為甲隊和乙隊)。記錄參賽球隊名稱、比賽時間、比分、比賽場地等信息，如下表所示。 A組： 甲隊乙隊場地名

6、稱比賽時間裁判比分解放軍北京一號球場2008-06-17 15:00 李大明天津山西一號球場2008-06-17 19:00 胡學梅 B組： 甲隊乙隊場地名稱比賽時間裁判比分上海安徽二號球場2008-06-17 15:00 丁鴻平山東遼寧二號球場2008-06-17 19:00郭愛琪4所有球員、教練和裁判可能出現(xiàn)重名情況?！靖拍钅Ｐ驮O計】 根據(jù)需求階段收集的信息，設計的實體聯(lián)系圖和關系模式(不完整)如下： 1實體聯(lián)系圖(圖2-1) 2關系模式 教練(教練編號，姓名，年齡) 隊員(隊員編號，姓名，年齡，身高，體重， (a) ) 球隊(球隊名稱，代表地區(qū)，成立時間， (b) ) 場地(場地名稱，場

7、地規(guī)模，位置) 訓練記錄( (c) ) 裁判(裁判編號，姓名，年齡，級別) 比賽記錄( (d) )5、【問題1】 根據(jù)問題描述，補充聯(lián)系及其類型，完善實體聯(lián)系圖2-1。(聯(lián)系及其類型的書寫格式參照教練與球隊之間的聯(lián)系描述，聯(lián)系名稱也可使用聯(lián)系1、聯(lián)系2、)6、【問題2】 根據(jù)實體聯(lián)系圖，填充關系模式中的a.、b.、c.和d.，并給出訓練記錄和比賽記錄關系模式的主鍵和外鍵。7、【問題3】 如果考慮記錄一些特別資深的熱心球迷的情況，每個熱心球迷可能支持多個球隊。熱心球迷包括：姓名、住址和喜歡的俱樂部等基本信息。根據(jù)這一要求修改上圖的實體聯(lián)系圖，給出修改后的關系模式(僅給出增加的關系模式描述)。試題

8、三 閱讀下列說明和圖，回答問題1至問題4，將解答填入對應欄內?！菊f明】 某汽車停車場欲建立一個信息系統(tǒng)，已經調查到的需求如下： 1在停車場的入口和出口分別安裝一個自動欄桿、一臺停車卡打印機、一臺讀卡器和一個車輛通過傳感器，示意圖如下： 2當汽車到達入口時，駕駛員按下停車卡打印機的按鈕獲取停車卡。當駕駛員拿走停車卡后，系統(tǒng)命令欄桿自動抬起；汽車通過入口后，入口處的傳感器通知系統(tǒng)發(fā)出命令，欄桿自動放下。 3在停車場內分布著若干個付款機器。駕駛員將在入口處獲取的停車卡插入付款機器，并繳納停車費。付清停車費之后，將獲得一張出場卡，用于離開停車場。 4當汽車到達出口時，駕駛員將出場卡插入出口處的讀卡器。

9、如果這張卡是有效的，系統(tǒng)命令欄桿自動抬起；汽車通過出口后，出口傳感器通知系統(tǒng)發(fā)出命令，欄桿自動放下。若這張卡是無效的，系統(tǒng)不發(fā)出欄桿抬起命令而發(fā)出告警信號。 5系統(tǒng)自動記錄停車場內空閑的停車位的數(shù)量。若停車場當前沒有車位，系統(tǒng)將在入口處顯示“車位已滿”信息。這時，停車卡打印機將不再出卡，只允許場內汽車出場。 根據(jù)上述描述，采用面向對象方法對其進行分析與設計，得到了如下表所示的類/用例/狀態(tài)列表、下圖(a)所示的用例圖、圖(b)所示的初始類圖以及圖(c)所示的描述入口自動欄桿行為的UML狀態(tài)圖。 類/用例/狀態(tài)列表 8、【問題1】 根據(jù)說明中的描述，使用上頁表給出的用例名稱，給出圖(a)中U1、

10、U2和U3所對應的用例。9、【問題2】 根據(jù)說明中的描述，使用上頁表給出的類的名稱，給出圖(b)中的，AD所對應的類。10、【問題3】 根據(jù)說明中的描述，使用上頁表給出的狀態(tài)名稱，給出圖(c)中S1S4所對應的狀態(tài)。11、【問題4】 簡要解釋圖(a)中用例U1和U3之間的extend關系的內涵。試題四 閱讀下列說明，回答問題1至問題3，將解答填入對應欄內。【說明】 快速排序是一種典型的分治算法。采用快速排序對數(shù)組Ap.r排序的3個步驟如下。 1分解：選擇一個樞軸(pivot)元素劃分數(shù)組。將數(shù)組Ap.r劃分為兩個子數(shù)組 (可能為空)Ap.q-1和Aq+1.r，使得Aq大于等于Ap.q-1)中的

11、每個元素，小于 Aq+1.r中的每個元素。q的值在劃分過程中計算。 2遞歸求解：通過遞歸的調用快速排序，對子數(shù)組Ap.q-1和Aq+1.r分別排序。 3合并：快速排序在原地排序，故不需合并操作。12、【問題1】 下面是快速排序的偽代碼，請?zhí)钛a其中的空缺；偽代碼中的主要變量說明如下。 A：待排序數(shù)組 p，r: 數(shù)組元素下標，從p到r q: 劃分的位置 x：樞軸元素 i：整型變量，用于描述數(shù)組下標。下標小于或等于i的元素的值小于或等于樞軸元素的值 j：循環(huán)控制變量，表示數(shù)組元素下標 QUICKSORT (A，p，r) if (p r) q=PARTITION(A，p，r) ； QUICKSORT(

12、A，p，q-1)； QUICKSORT(A，q+1，r)； PARTITION(A，p，r) x=Ar；i=p-1； for(j=p；jr-1；j+) if (Ajx) i=i+1； 交換Ai和Aj 交 (1) 和 (2) /注：空(1)和空(2)答案可互換，但兩空全部答對方可得分 return (3) 13、【問題2】 (1)假設要排序包含n個元素的數(shù)組，請給出在各種不同的劃分情況下，快速排序的時間復雜度，用O記號。最佳情況為 (4) ，平均情況為 (5) ，最壞情況為 (6) 。 (2)假設要排序的n個元素都具有相同值時，快速排序的運行時間復雜度屬于哪種情況? (7) 。(最佳，平均、最壞

13、)14、【問題3】 (1)待排序數(shù)組是否能被較均勻地劃分對快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機地取出一個元素作為樞軸元素，下面是隨機化快速排序劃分的偽代碼利用原有的快速排序的劃分操作，請?zhí)畛淦渲械目杖碧?。其中，RANDOM(i，j)表示隨機取i到j之間的一個數(shù)，包括i和j。 RANDOMIZED- PARTITION(A，p，r) i=RANDOM(p，rl)； 交換 (8) 和 (9) ；/注：空(8)和空(9)答案可互換，但兩空全部答對方可得分 return PARTITION (A，p，r)； (2)隨機化快速排序是否能夠消除最壞情況的發(fā)

14、生? (10) 。(是或否)試題五 閱讀下列說明和C代碼，將應填入 處的字句寫在對應欄內。15、【說明】 棧(Stack)結構是計算機語言實現(xiàn)中的一種重要數(shù)據(jù)結構。對于任意棧，進行插入和刪除操作的一端稱為棧頂(Stock Top)，而另一端稱為棧底(Stock Bottom)。棧的基本操作包括：創(chuàng)建棧(NewStack)、判斷棧是否為空(IsEmpty)、判斷棧是否已滿(IsFull)、獲取棧頂數(shù)據(jù)(Top)、壓棧/入棧(Push)、彈棧/出棧(Pop)。 當設計棧的存儲結構時，可以采取多種方式。其中，采用鏈式存儲結構實現(xiàn)的棧中各數(shù)據(jù)項不必連續(xù)存儲(如下圖所示)。 以下C代碼采用鏈式存儲結構實

15、現(xiàn)一個整數(shù)棧操作?！綜代碼】 typedef struct List int data； /棧數(shù)據(jù) struct List* next； /上次入棧的數(shù)據(jù)地址 List； typedef struct Stack List* pTop； /當前棧頂指針 Stack； Stack* NewStack() return (Stack*) calloc(1/sizeof(Stack)； int IsEmpty(Stack* S)/判斷棧S是否為空棧 if( (1) )return 1; return 0; int Top(Stack* s)/獲取棧頂數(shù)據(jù)。若棧為空，則返回機器可表示的最小整數(shù) if(

16、IsEmpty(S)return INT_ MIN； return (2) ； void Push(Stack* S，int theData) /將數(shù)據(jù)theData壓棧 List* newNode； newNode=(List*)calloc(1/sizeof (List)； newNode-data=theData； newNode-next=S-pTop； S-pTop= (3) ； void Pop(Stack* S) /彈棧 List* lastTop； if(IsEmpty(S) ) return； lastTop=S-pTop； S-pTop= (4) ； free(lastTo

17、p)； #define MD(a) a2 int main() int i; Stack* myStack； myStack= NewStack()； Push(myStack，MD(1)； Push(myStack，MD(2)； Pop(myStack)； Push(myStack，MD(3)+1)； while( !IsEmpty(myStack) ) printf(%d，Top(myStack)； Pop(myStack)； return 0； 以上程序運行時的輸出結果為： (5) 試題六 閱讀下列說明和C+代碼，將應填入 (n) 處的字句寫在對應欄內。16、【說明】 已知某企業(yè)欲開發(fā)一

18、家用電器遙控系統(tǒng)，即用戶使用一個遙控器即可控制某些家用電器的開與關。遙控器如左下所示。該遙控器共有4個按鈕，編號分別是0至3，按鈕0和2能夠遙控打開電器1和電器2，按鈕1和3則能遙控關閉電器1和電器2。由于遙控系統(tǒng)需要支持形式多樣的電器，因此，該系統(tǒng)的設計要求具有較高的擴展性。現(xiàn)假設需要控制客廳電視和臥室電燈，對該遙控系統(tǒng)進行設計所得類圖如右下所示。 右上圖中，類RomoteController的方法onPressButton(int button)表示當遙控器按鍵按下時調用的方法，參數(shù)為按鍵的編號；Command接口中on和off方法分別用于控制電器的開與關；Light中turnLight(

19、int degree)方法用于調整電燈燈光的強弱，參數(shù) degree值為0時表示關燈，值為100時表示開燈并且將燈光亮度調整到最大；TV中 setChannel(int channel)方法表示設置電視播放的頻道，參數(shù)channel值為0時表示關閉電視，為1時表示開機并將頻道切換為第1頻道?！綜+代碼】class Light /電燈類public： void trunLight(int degree)/調整燈光亮度，0表示關燈，100表示亮度最大)；class TV/電視機類public：vold setChannel(int channel/調整電視頻道，0表示關機，1表示開機并切換到1頻道

20、；class Command/抽象命令類public： virtual void on()=0； virtual void off()=0；class RemoteController /遙控器類protected： Command* commands 4；/遙控器有4個按鈕，按照編號分別對應4個Command對象public： void onPressButton(int button) /按鈕被按下時執(zhí)行命令對象中的命令 if(button % 2=0)commandsbutton-on()； else commandsbutton-off()； void setCommand(int b

21、utton，Command* command) (1) =command；/設置每個按鈕對應的命令對象；class LightCommand：public Command /電燈命令類protected： Light* light； /指向要控制的電燈對象public： void On()light-trunLight(100)；)； void off()light- (2) ；)； LightCommand(Light * light)this-light=light；)；class TVCommand：public Command/電視機命令類protected： TV*tv； /指向要控

22、制的電視機對象public： void on()tv- (3) ； void off()tv-setChannel(0)；)； TVCommand(TV *tv)this-tv=tv；)；void main() Light light； TV tv；/創(chuàng)建電燈和電視對象 LightCommand lightCommand (&light)； TVCommand tVCommand(&tv)； RemoteController remoteController； remoteController. setCommand(0， (4) )； /設置按鈕0的命令對象 /此處省略設置按鈕1、按鈕2和按

23、鈕3的命令對象代碼 本題中，應用命令模式能夠有效讓類 (5) 和類 (6) 、類 (7) 之間的耦合性降至最小。試題七 閱讀下列說明和Java代碼，將應填入 (n) 處的字句寫在對應欄內。17、【說明】 已知某企業(yè)欲開發(fā)一家用電器遙控系統(tǒng)，即用戶使用一個遙控器即可控制某些家用電器的開與關。遙控器如下圖(a)所示。該遙控器共有4今按鈕，編號分別是0至3，按鈕0和2能夠遙控打開電器1和電器2，按鈕1和3則能遙控關閉電器1和電器2。由于遙控系統(tǒng)需要支持形式多樣的電器，因此，該系統(tǒng)的設計要求具有較高的擴展性。現(xiàn)假設需要控制客廳電視和臥室電燈，對該遙控系統(tǒng)進行設計所得類圖如下圖(b)所示。 圖(b)中，

24、類RomoteController的方法onPrcssButton(int button)表示當遙控器按鍵按下時調用的方法，參數(shù)為按鍵的編號；command接口中on和off方法分別用于控制電器的開與關；Light中turnLight(int degree)方法用于調整電燈燈光的強弱，參數(shù) degree值為0時表示關燈，值為100時表示開燈并且將燈光亮度調整到最大；TV中 sctChannel(int channel)方法表示設置電視播放的頻道，參數(shù)channel值為0時表示關閉電視，為1時表示開機并將頻道切換為第1頻道?！綣ava代碼】class Light /電燈類public void

25、trunLight(int degree)/調整燈光亮度，0表示關燈，100表示亮度最大；class TV/電視機類 public void setChannel(int channel)/0表示關機，1表示開機并切換到1頻道；interface Command/抽象命令類 void on()； void off()；class RemoteController /遙控器類protected Command commands=new Command4；/遙控器有4個按鈕，按照編號分別對應4個Command對象public void onPressButton(int button)/按鈕被按下

26、時執(zhí)行命令對象中的命令 if(button % 2 = 0)commandsbutton. on()； else commandsbutton. off()；public void setCommand(int button， Command command) (1) =command；/設置每個按鈕對應的命令對象 ；class LightCommand implements Command /電燈命令類 protected Light light； /指向要控制的電燈對象 public void on()light. trunLight(100)；)； public void off()li

27、ght. (2) ；)； public LightCommand(Light light)this. light= light；)；class TVCommand implements Command/電視機命令類 protected Tv tv； /指向要控制的電視機對象 public void on()tv. (3) ； public void off()tv. setChanne1(0)； public TVCommand(TV tv)this. tv= tv；public class rs public static void main(String args) Light light

28、= new Light()； TV tv=new TV()；/創(chuàng)建電燈和電視對象 LightCommand lightCommand= new LightCommand(light)； TVCommand tvCommand=new TVCommand(tv)； RemoteController remoteController=new RemoteController()； /設置按鈕和命令對象 remoteController. setCommand(0， (4) )； . /此處省略設置按鈕1、按鈕2和按鈕3的命令對象代碼 本題中，應用命令模式能夠有效讓類 (5) 和類 (6) 、類 (

29、7) 之間的耦合性降至最小。答案:試題一1、E1：客戶 2、D1：客戶信息文件 D2：音像制品信息文件 D3：租借記錄文件 D4：預約記錄文件 3、起點終點E1或客戶4或創(chuàng)建新客戶 5或創(chuàng)建預約記錄E1或客戶6或歸還音像制品7或履行預約服務注意：3條數(shù)據(jù)流無前后順序區(qū)分。 4、面向數(shù)據(jù)結構的設計方法以數(shù)據(jù)結構作為設計的基礎，它根據(jù)輸入/輸出數(shù)據(jù)結構導出程序的結構。 面向數(shù)據(jù)結構的設計方法用于規(guī)模不大的數(shù)據(jù)處理系統(tǒng)。解析 本題考查數(shù)據(jù)流圖的設計和應用。 根據(jù)題目說明，本系統(tǒng)的外部實體僅僅涉及到客戶，因此系統(tǒng)的頂層數(shù)據(jù)流圖中E1應該對應為客戶。 題目的第二個問題在于識別系統(tǒng)中的數(shù)據(jù)文件D1D4，根

30、據(jù)0層數(shù)據(jù)流圖中的數(shù)據(jù)文件與處理之間的關系分析可以得知： D1為創(chuàng)建新客戶加工的輸出，并且為加工1、6和7的輸入，再根據(jù)題目中的描述，客戶信息文件與創(chuàng)建客戶信息、預約、歸還和履行預約都相關，因此D1便是客戶信息文件。同理可分析出D2為音像制品信息文件、D3為租借記錄文件、D4為預約記錄文件。 圖(b)中缺少了3條數(shù)據(jù)流，我們先檢查頂層數(shù)據(jù)流圖和。層數(shù)據(jù)流是否一致。首先，從頂層數(shù)據(jù)流圖中可以看出，與E1直接相關的數(shù)據(jù)流共有9條，而在0層數(shù)據(jù)流圖中與E1直接關聯(lián)的只有7條，因此可以直接斷定，圖(b)中至少缺少直接與E1相關的兩條數(shù)據(jù)流：新客戶創(chuàng)建請求和預約流水號。新客戶創(chuàng)建請求通過創(chuàng)建新客戶加工將

31、客戶的信息寫入客戶信息文件中，因此其起點和終點分別為：E1和4。同理，預約流水號的起點和終點為5和E1。在說明中，客戶歸還到期的音像制品，系統(tǒng)修改租借記錄文件，并查詢預約記錄文件和客戶信息文件，判定是否有客戶預約了這些音像制品。若有，則生成預約提示信息，通知系統(tǒng)履行預約服務，系統(tǒng)查詢客戶信息文件和預約記錄文件，通知相關客戶前來租借音像制品。因此，在客戶歸還和履行預約服務之間存在著數(shù)據(jù)上的聯(lián)系。 面向數(shù)據(jù)結構的設計方法以數(shù)據(jù)結構作為設計的基礎，它根據(jù)輸入/輸出數(shù)據(jù)結構導出程序的結構。面向數(shù)據(jù)結構的設計方法用于規(guī)模不大的數(shù)據(jù)處理系統(tǒng)。試題二5、(對聯(lián)系名稱不做要求，但不能出現(xiàn)重名，圖中的M、N、P

32、也可表示為。) 6、 (1)球隊名稱 (2)教練編號 (3)球隊名稱，場地名稱，開始時間，結束時間 (4)甲隊，乙隊，比賽時間，場地名稱，比分，裁判，分組訓練記錄主鍵(球隊，開始時間)或(場地名稱，開始時間) 或(球隊，結束時間)或(場地名稱，結束時間)外鍵球隊名稱，場地名稱比賽記錄主鍵(甲隊，比賽時間)或(場地名稱，比賽時間) 或 (裁判，比賽時間)或(乙隊，比賽時間)外鍵甲隊，乙隊，場地名稱，裁判 7、 關系模式： 熱心球迷(球迷編號，姓名，住址，俱樂部) 支持球隊(球迷編號，球隊)解析 本題考查數(shù)據(jù)庫概念結構設計及向邏輯結構轉換的基本方法。 此類題目要求認真閱讀題目對現(xiàn)實問題的描述，經過

33、分類、聚集、概括等方法，從中確定實體及其聯(lián)系。題目已經給出了4個實體，需要根據(jù)需求描述，給出實體間的聯(lián)系。 由“每個球隊有一個教練負責管理球隊，一個教練僅負責一個球隊?！敝蜿犈c教練間為1：1聯(lián)系；球隊與隊員之間應為1：N聯(lián)系；多個球隊使用多個訓練場地，球隊與場地之間為M：M聯(lián)系；比賽是球隊、場地與裁判之間的聯(lián)系，一個球隊會與同組的其他多個隊之間比賽，有多個場地和裁決，一位裁判會對多場比賽判罰，一個場地會有多場比賽，涉及多個球隊和裁判，因此球隊、場地與裁判之間的比賽關系為M：N：P聯(lián)系。 根據(jù)補充后的E-R圖，球隊與球員之間的1：N聯(lián)系應通過將1端實體(球員)的主碼(球隊名稱)加入到N端實體(

34、球員)對應的關系中來表達。這類聯(lián)系也可通過獨立的一個關系來表達，如球隊球員(球隊名稱，隊員編號)，這樣會對查詢增加多余的連接操作，因此一般不采用這種方法。 同樣，球隊與教練之間的1：1聯(lián)系也應通過將一方的主碼增加到另一方實體對應的關系中，來表達聯(lián)系。 訓練和比賽為多對多聯(lián)系，只能獨立成一個關系模式，取與該聯(lián)系相關聯(lián)的各實體的碼及聯(lián)系自有的屬性構成。例如，比分和分組應該是比賽的屬性，再加上球隊、裁判、場地的碼，即構成“比賽記錄”的關系模式。 同理，訓練是球隊和場地的多對多聯(lián)系，訓練開始時間和結束時間為訓練的屬性，加上球隊的碼和場地的碼，構成“訓練記錄”關系模式。 球迷與球隊之間為多對多聯(lián)系，需新

35、增球迷實體和球迷與球隊之間的支持聯(lián)系。試題三8、U1：Car entry U2：Car exit U3：Car entry when full 9、A：CarPark B：Barrier C：EntryBarrier D：ExiBarrier 其中，C、D的答案可以互換 10、S1：Idle S2：Await Ticket Take S3：Await Enable S4：Await Entry 11、用例之間的延伸關系用于對被用戶看作是可選系統(tǒng)行為的用例的一部分建模。通過這種方式，可以把可選行為從必需的行為中分離出來。解析 本題考查面向對象設計基本知識和方法。 題目給出了4個用例，在4個用例中

36、，兩個用例表示汽車進入停車場，一個用例表示汽車退出停車場，另一個用例表示記錄停車場相關信息。經分析得出，前3個用例的參與者都是駕駛員，因此U1、U2和U3對應進入和退出停車場。U1和U3之間存在擴展關系，而用例之間的延伸關系用于對被用戶看作是可選系統(tǒng)行為的用例的一部分建模通過這種方式，可以把可選行為從必需的行為中分離出來。Car entry when full和Car entry之間就可以使用extend關系進行建模。 類圖問題的回答比較容易，因為首先可以判斷Barrier、EntryBarrier和ExitBarrier之間存在繼承關系，而類圖中表示繼承關系的部分只有一處，因此這3個類分別對

37、應B、C和D，而剩下的空A只有選擇類CarPark了。 在狀態(tài)圖中，Idle表示有空閑車位，Disable表示沒有空閑車位，因此在其之間存在雙向的狀態(tài)遷移，因此狀態(tài)圖上的狀態(tài)31為Idle狀態(tài)。當停車場存在空閑車位時，汽車請求進入停車場，根據(jù)說明描述“當汽車到達入口時，駕駛員按下停車卡打印機的按鈕獲取停車卡”，可知在該動作正對應于狀態(tài)圖上的S1和狀態(tài)S2之間的遷移，因此，狀態(tài)S2表示的含義應該是按下按鈕后狀態(tài)，此時，駕駛員等待打印停車卡，所以，狀態(tài)日2為Await Ticket Take。同理可分析出狀態(tài)S3和狀態(tài)S4。試題四12、(1)Ai+1 (2)Ar (3)i+1注：空(1)和空(2)

38、答案可以互換 13、(4)O(nlgn)或O(log2n) (5)O(nlgn)或O(nlog2n) (6)O(n2) (7)最壞 14、Ai (9)Ar (10)否注；空(8)和空(9)答案可以互換試題四分析 本題考查算法的設計與分析技術。 問題1考查快速排序算法的偽代碼，快速排序最核心的處理是進行劃分，即 PARTITION操作，根據(jù)樞軸元素的值，把一個較大的數(shù)組分成兩個較小的子數(shù)組，一個子數(shù)組的所有元素的值小于等于樞軸元素的值，一個子數(shù)組的所有元素的值大于樞軸元素的值，而子數(shù)組內的元素不排序。劃分時，以最后一個元素為樞軸元素，從左到右依次訪問數(shù)組的每一個元素，判斷其與樞軸元素的大小關系，

39、并進行元素的交換，如圖4-1所示： 在問題1給出的偽代碼中，當循環(huán)結束后，Ap.i中的值應小于等于樞軸元素值x，而Ai+1.r-1中的值應大于樞軸元素值x。此時Ai+1)是第一個比Ar大的元素，因此 A閉與Ai+1交換，得到劃分后的兩個子數(shù)組。PARTITION操作返回樞軸元素的位置，因此返回值為i+1。 問題2考查的是快速排序算法的時間復雜度分析。當每次能作均勻劃分時，算法為最佳情況，此時時間復雜度可以通過計算遞歸式T(n)=2T(n/2)+O(n)，得到時間復雜度為O(nlgn)：當每次為極端不均勻劃分時，即長度為n的數(shù)組劃分后一個子數(shù)組為n-1，一個為0，算法為最壞情況，此時時間復雜度可

40、以通過計算遞歸式T(n)=T(n-1)+O(n)，得到時間復雜度為O(n2)；平均情況的分析較為復雜，我們可以假設數(shù)組每次劃分為 9/10：1/10，此時時間復雜度可以通過計算遞歸式T(n)=T(9/10)+T(1/10)+O(n)，得到時間復雜度為O(nlgn)，因此在平均情況下快速排序仍然有較好的性能，時間復雜度為 O(nlgn)。當所有的n個元素具有相同的值時，可以認為數(shù)組已經有序，此時每次都劃分為長度為n-1和0的兩個子數(shù)組，屬于最壞情況。 問題3中，由于隨機化的快速排序的劃分調用了傳統(tǒng)的快速排序算法的PARTITION操作，而傳統(tǒng)的劃分每次以數(shù)組的最后一個元素作為樞軸元素，因此，隨機

41、化的劃分操作中每次先隨機獲得一個元素，將其與最后一個元素交換。隨機化的快速排序消除了輸入數(shù)據(jù)的不同排列對算法性能的影響，降低了極端不均勻劃分的概率，但不能保證不會導致最壞情況的發(fā)生。試題五15、S=NULLS-pTop=NULL (2)S-pTop-data (3)newNode (4)S-pTop-next，或lastTop-next (5)244解析 本題考查基本程序設計能力。 堆棧是軟件設計中常使用的一種經典數(shù)據(jù)結構，題目給出的操作都是任何堆棧都具有的基本操作。堆棧的存儲結構通常采用數(shù)組或鏈表形式，但無論采用哪種存儲結構，整體上呈現(xiàn)的是后進先出的特點，即后進入堆棧的元素先出棧。題目中給出

42、的結構體 Stack僅包含一個指向棧頂元素的指針(棧頂指針)，當且僅當堆棧中沒有元素時，該指針應為NULL。當向堆棧中增加元素時，首先需要動態(tài)創(chuàng)建該元素的存儲區(qū)，并且棧頂指針指向該元素。當元素出棧時，棧頂指針則指向出棧元素的緊前一個元素。結構體List表示棧中元素，包含對應的數(shù)據(jù)和指向緊上次入棧的元素指針next，對于第1個入棧的元素，指針next為NULL,而其他元素中的指針next一定不為NULL。 C語言中，如果用一個整數(shù)型表達式表示條件判定語句的話，該表達式的值為。則表示假，非0表示真。從給定程序代碼可以看出，對于函數(shù)IsEmpty，若其返回值為0則表示堆棧非空，否則表示堆棧為空。因此，對于空(1)，必須填寫可表示堆棧為空的判定語句：S=NULLS-p)Top=NULL，這2個條件中只要有1個條件滿足，則表明堆棧S為空。對于空(2)，此時需要返回棧頂元素中的數(shù)據(jù)，而棧頂元素為S-pTop，所以對應的數(shù)據(jù)應該為S-pTop-data。 對于壓棧操作Push，在為新元素獲取存儲空間后，必須調整堆棧