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

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

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

3、中。 6客戶歸還到期的音像制品，系統(tǒng)修改租借記錄文件，并查詢預(yù)約記錄文件和客戶信息文件，判定是否有客戶預(yù)約了這些音像制品。若有，則生成預(yù)約提示信息，通知系統(tǒng)履行預(yù)約服務(wù)，系統(tǒng)查詢客戶信息文件和預(yù)約記錄文件，通知相關(guān)客戶前來租借音像制品。 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è)計時，面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法(如Jac

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

5、球隊安排不同的訓(xùn)練場地，如下表所示。系統(tǒng)記錄訓(xùn)練場地安排的信息。球隊名稱場地名稱訓(xùn)練時間解放軍一號球場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 胡學(xué)梅 B組： 甲隊乙隊場地名稱比賽時間裁判比分上海安徽二號球場2008-06-17 15:00 丁鴻平山東遼寧二號球場2008-06-17 19:00郭愛琪4所有球員、教練和裁判可能出現(xiàn)重名情況。【概念模型設(shè)計】 根據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖和關(guān)系模式(不完整)如下： 1實體聯(lián)系圖(圖2-1) 2關(guān)系模式 教練(教練編號，姓名，年齡) 隊員(隊員編號，姓名，年齡，身高，體重， (a) ) 球隊(球隊名稱，代表地區(qū)，成立時間， (b) ) 場地(場地名稱，場

7、地規(guī)模，位置) 訓(xùn)練記錄( (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)系圖，填充關(guān)系模式中的a.、b.、c.和d.，并給出訓(xùn)練記錄和比賽記錄關(guān)系模式的主鍵和外鍵。7、【問題3】 如果考慮記錄一些特別資深的熱心球迷的情況，每個熱心球迷可能支持多個球隊。熱心球迷包括：姓名、住址和喜歡的俱樂部等基本信息。根據(jù)這一要求修改上圖的實體聯(lián)系圖，給出修改后的關(guān)系模式(僅給出增加的關(guān)系模式描述)。試題

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

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

10、U2和U3所對應(yīng)的用例。9、【問題2】 根據(jù)說明中的描述，使用上頁表給出的類的名稱，給出圖(b)中的，AD所對應(yīng)的類。10、【問題3】 根據(jù)說明中的描述，使用上頁表給出的狀態(tài)名稱，給出圖(c)中S1S4所對應(yīng)的狀態(tài)。11、【問題4】 簡要解釋圖(a)中用例U1和U3之間的extend關(guān)系的內(nèi)涵。試題四 閱讀下列說明，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)?！菊f明】 快速排序是一種典型的分治算法。采用快速排序?qū)?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遞歸求解：通過遞歸的調(diào)用快速排序，對子數(shù)組Ap.q-1和Aq+1.r分別排序。 3合并：快速排序在原地排序，故不需合并操作。12、【問題1】 下面是快速排序的偽代碼，請?zhí)钛a其中的空缺；偽代碼中的主要變量說明如下。 A：待排序數(shù)組 p，r: 數(shù)組元素下標(biāo)，從p到r q: 劃分的位置 x：樞軸元素 i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值小于或等于樞軸元素的值 j：循環(huán)控制變量，表示數(shù)組元素下標(biāo) 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)假設(shè)要排序包含n個元素的數(shù)組，請給出在各種不同的劃分情況下，快速排序的時間復(fù)雜度，用O記號。最佳情況為 (4) ，平均情況為 (5) ，最壞情況為 (6) 。 (2)假設(shè)要排序的n個元素都具有相同值時，快速排序的運行時間復(fù)雜度屬于哪種情況? (7) 。(最佳，平均、最壞

13、)14、【問題3】 (1)待排序數(shù)組是否能被較均勻地劃分對快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機地取出一個元素作為樞軸元素，下面是隨機化快速排序劃分的偽代碼利用原有的快速排序的劃分操作，請?zhí)畛淦渲械目杖碧帯Ｆ渲?，RANDOM(i，j)表示隨機取i到j(luò)之間的一個數(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代碼，將應(yīng)填入 處的字句寫在對應(yīng)欄內(nèi)。15、【說明】 棧(Stack)結(jié)構(gòu)是計算機語言實現(xiàn)中的一種重要數(shù)據(jù)結(jié)構(gòu)。對于任意棧，進行插入和刪除操作的一端稱為棧頂(Stock Top)，而另一端稱為棧底(Stock Bottom)。棧的基本操作包括：創(chuàng)建棧(NewStack)、判斷棧是否為空(IsEmpty)、判斷棧是否已滿(IsFull)、獲取棧頂數(shù)據(jù)(Top)、壓棧/入棧(Push)、彈棧/出棧(Pop)。 當(dāng)設(shè)計棧的存儲結(jié)構(gòu)時，可以采取多種方式。其中，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧中各數(shù)據(jù)項不必連續(xù)存儲(如下圖所示)。 以下C代碼采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實

15、現(xiàn)一個整數(shù)棧操作?！綜代碼】 typedef struct List int data； /棧數(shù)據(jù) struct List* next； /上次入棧的數(shù)據(jù)地址 List； typedef struct Stack List* pTop； /當(dāng)前棧頂指針 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； 以上程序運行時的輸出結(jié)果為： (5) 試題六 閱讀下列說明和C+代碼，將應(yīng)填入 (n) 處的字句寫在對應(yīng)欄內(nèi)。16、【說明】 已知某企業(yè)欲開發(fā)一

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

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

20、；class Command/抽象命令類public： virtual void on()=0； virtual void off()=0；class RemoteController /遙控器類protected： Command* commands 4；/遙控器有4個按鈕，按照編號分別對應(yīng)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；/設(shè)置每個按鈕對應(yīng)的命令對象；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) )； /設(shè)置按鈕0的命令對象 /此處省略設(shè)置按鈕1、按鈕2和按

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

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

25、trunLight(int degree)/調(diào)整燈光亮度，0表示關(guān)燈，100表示亮度最大；class TV/電視機類 public void setChannel(int channel)/0表示關(guān)機，1表示開機并切換到1頻道；interface Command/抽象命令類 void on()； void off()；class RemoteController /遙控器類protected Command commands=new Command4；/遙控器有4個按鈕，按照編號分別對應(yīng)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；/設(shè)置每個按鈕對應(yīng)的命令對象 ；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()； /設(shè)置按鈕和命令對象 remoteController. setCommand(0， (4) )； . /此處省略設(shè)置按鈕1、按鈕2和按鈕3的命令對象代碼 本題中，應(yīng)用命令模式能夠有效讓類 (5) 和類 (6) 、類 (

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

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

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

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

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

34、球員)對應(yīng)的關(guān)系中來表達。這類聯(lián)系也可通過獨立的一個關(guān)系來表達，如球隊球員(球隊名稱，隊員編號)，這樣會對查詢增加多余的連接操作，因此一般不采用這種方法。 同樣，球隊與教練之間的1：1聯(lián)系也應(yīng)通過將一方的主碼增加到另一方實體對應(yīng)的關(guān)系中，來表達聯(lián)系。 訓(xùn)練和比賽為多對多聯(lián)系，只能獨立成一個關(guān)系模式，取與該聯(lián)系相關(guān)聯(lián)的各實體的碼及聯(lián)系自有的屬性構(gòu)成。例如，比分和分組應(yīng)該是比賽的屬性，再加上球隊、裁判、場地的碼，即構(gòu)成“比賽記錄”的關(guān)系模式。 同理，訓(xùn)練是球隊和場地的多對多聯(lián)系，訓(xùn)練開始時間和結(jié)束時間為訓(xùn)練的屬性，加上球隊的碼和場地的碼，構(gòu)成“訓(xùn)練記錄”關(guā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、用例之間的延伸關(guān)系用于對被用戶看作是可選系統(tǒng)行為的用例的一部分建模。通過這種方式，可以把可選行為從必需的行為中分離出來。解析 本題考查面向?qū)ο笤O(shè)計基本知識和方法。 題目給出了4個用例，在4個用例中

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

37、應(yīng)B、C和D，而剩下的空A只有選擇類CarPark了。 在狀態(tài)圖中，Idle表示有空閑車位，Disable表示沒有空閑車位，因此在其之間存在雙向的狀態(tài)遷移，因此狀態(tài)圖上的狀態(tài)31為Idle狀態(tài)。當(dāng)停車場存在空閑車位時，汽車請求進入停車場，根據(jù)說明描述“當(dāng)汽車到達入口時，駕駛員按下停車卡打印機的按鈕獲取停車卡”，可知在該動作正對應(yīng)于狀態(tài)圖上的S1和狀態(tài)S2之間的遷移，因此，狀態(tài)S2表示的含義應(yīng)該是按下按鈕后狀態(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)答案可以互換試題四分析 本題考查算法的設(shè)計與分析技術(shù)。 問題1考查快速排序算法的偽代碼，快速排序最核心的處理是進行劃分，即 PARTITION操作，根據(jù)樞軸元素的值，把一個較大的數(shù)組分成兩個較小的子數(shù)組，一個子數(shù)組的所有元素的值小于等于樞軸元素的值，一個子數(shù)組的所有元素的值大于樞軸元素的值，而子數(shù)組內(nèi)的元素不排序。劃分時，以最后一個元素為樞軸元素，從左到右依次訪問數(shù)組的每一個元素，判斷其與樞軸元素的大小關(guān)系，

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

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

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

42、的結(jié)構(gòu)體 Stack僅包含一個指向棧頂元素的指針(棧頂指針)，當(dāng)且僅當(dāng)堆棧中沒有元素時，該指針應(yīng)為NULL。當(dāng)向堆棧中增加元素時，首先需要動態(tài)創(chuàng)建該元素的存儲區(qū)，并且棧頂指針指向該元素。當(dāng)元素出棧時，棧頂指針則指向出棧元素的緊前一個元素。結(jié)構(gòu)體List表示棧中元素，包含對應(yīng)的數(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，所以對應(yīng)的數(shù)據(jù)應(yīng)該為S-pTop-data。 對于壓棧操作Push，在為新元素獲取存儲空間后，必須調(diào)整堆棧