下午題

試題一

黑洞：加工有輸入無(wú)輸出
白洞(奇跡)：加工有輸出無(wú)輸入
灰洞：數(shù)據(jù)流輸入的加工不足以產(chǎn)生輸出

結(jié)構(gòu)化語(yǔ)言：
IF ***
THEN

---

ELSE IF ***
THEN
*******
END IF
END IF

1. 數(shù)據(jù)流的父子圖平衡，如果父子圖平衡就不會(huì)產(chǎn)生實(shí)體到加工的數(shù)據(jù)流
2. 數(shù)據(jù)流的文字平衡
3. 一個(gè)數(shù)據(jù)流的起點(diǎn)和終點(diǎn)至少有一個(gè)是加工p
4. 加工至少有一個(gè)輸入一個(gè)輸出

試題二

1. 在一對(duì)多關(guān)系中，需要將一方的主鍵寫(xiě)入多方關(guān)系中做外鍵
2. 在一對(duì)一關(guān)系中，需要將任意一方的主鍵歸并到另外一方
3. 在多對(duì)多關(guān)系中則需要單獨(dú)抽出一個(gè)關(guān)系模式，這里的主鍵和外鍵可能相同
4. 三個(gè)實(shí)體相關(guān)聯(lián)的er圖中，可以單獨(dú)抽取一個(gè)關(guān)系模式
5. 題目表述的某個(gè)意為一個(gè)或多個(gè)，而*可以表示一個(gè)或多個(gè)
6. 關(guān)系模式的表示 例子：銷售（編號(hào)，日期，數(shù)量） 主鍵：下滑橫線 外鍵：下滑虛線 實(shí)體也許抽成關(guān)系模式

試題三

先看題目文字表述最后一行，確定是什么樣的UML圖 一般都是用例圖（有參與者 人） 和類圖

1. 用例名一般是 名詞+動(dòng)詞 類名一般使用文字描述用到的詞匯
2. 依賴關(guān)系：A------>B A依賴B B改變會(huì)引起A改變
3. 關(guān)聯(lián)關(guān)系：A——B 多重度（位于橫線上方）0…1（含義：） 0…*（含義：）
4. 組合關(guān)系：A——◆B 表示整體與部分的關(guān)系 整體消失 部分也消失
5. 聚合關(guān)系：A——◇B 表示整體與部分的關(guān)系 整體消失 部分不消失
6. 用例與用例之間的三種關(guān)系 包含 擴(kuò)展 泛化

包含關(guān)系：include A------>B 關(guān)鍵字include位于虛線上方
當(dāng)一個(gè)用例包含另一個(gè)用例時(shí)，當(dāng)基本用例執(zhí)行是，被包含用例一定會(huì)被執(zhí)行，包含關(guān)系由基本用例指向被包含用例關(guān)系是一條帶箭頭虛線上有<>
擴(kuò)展關(guān)系：extend A------>B 關(guān)鍵字extend 位于虛線上方
當(dāng)一個(gè)用例執(zhí)行，可能會(huì)出現(xiàn)特殊情況和可選情況，這時(shí)會(huì)執(zhí)行擴(kuò)展用例，關(guān)系是一條帶箭頭虛線上有<>
泛化關(guān)系：generalize A——?B
泛化關(guān)系是一種繼承關(guān)系，子用例繼承父用例所有屬性和行為，并且父用例出現(xiàn)的地方子用例也可能出現(xiàn)，關(guān)系是實(shí)線空心箭頭、

7. 實(shí)現(xiàn)關(guān)系：A-------?B A：類 B：接口

試題四 算法

算法的思想

分治法

將一個(gè)復(fù)雜問(wèn)題分解為若干規(guī)模較小且結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，然后遞歸解決這些子問(wèn)題，最后將子問(wèn)題的解合并得到原問(wèn)題的解。

動(dòng)態(tài)規(guī)劃法

將原問(wèn)題分解為若干重疊子問(wèn)題，通過(guò)求解子問(wèn)題的最優(yōu)解得到原問(wèn)題的最優(yōu)解。使用一個(gè)表格來(lái)存儲(chǔ)子問(wèn)題的最優(yōu)解，避免重復(fù)計(jì)算

貪心法

每一步都選擇當(dāng)前看起來(lái)的最優(yōu)解，不考慮未來(lái)，通過(guò)一系列的局部最優(yōu)解，希望得到全局最優(yōu)解。

回溯法

通過(guò)逐步構(gòu)建解的集合，當(dāng)發(fā)現(xiàn)當(dāng)前候選解不能滿足問(wèn)題的約束條件時(shí)，回溯到上一步進(jìn)行其他選擇，直到找到滿足問(wèn)題的解或者遍歷完所有可能的選擇（深度優(yōu)先遍歷）

拿分技巧

時(shí)間復(fù)雜度，關(guān)鍵字

歸并排序，快速排序，分組 使用分治法
時(shí)間復(fù)雜度：通常為O(nlogn)

0-1背包，公共子序列，全局最優(yōu)解 不一定看具體算代碼
時(shí)間復(fù)雜度：通常為O(n^2)或O(n3)

霍夫曼編碼、最小生成樹(shù)（如Prim算法和Kruskal算法），背包問(wèn)題（部分），任務(wù)調(diào)度
時(shí)間復(fù)雜度：通常為O(n)，因?yàn)樨澬乃惴ㄖ恍枰淮伪闅v即可得到解

N皇后，迷宮問(wèn)題
時(shí)間復(fù)雜度：取決于問(wèn)題的規(guī)模和解的數(shù)量，通常為指數(shù)級(jí)別的復(fù)雜度。

時(shí)間復(fù)雜度

試題六 Java

1. 接口里要填的，看實(shí)現(xiàn)了接口的方法里的方法（實(shí)現(xiàn)了一個(gè)接口就要實(shí)現(xiàn)這個(gè)接口里所有的方法）
2. 接口不能直接實(shí)例化，要通過(guò)實(shí)現(xiàn)他的接口來(lái)實(shí)現(xiàn)實(shí)例化
3. 根據(jù)返回值的類型推斷方法的返回值類型，也可以根據(jù)方法的返回類型推斷返回值的類型
4. 在父子類繼承關(guān)系extend中，補(bǔ)充父類方法時(shí) 一定需要加關(guān)鍵字abstract（父類抽象方法被繼承）
5. 在繼承關(guān)系中，子類引用父類成員關(guān)鍵字super 例super.drawCircle = drawCircle;
6. 在組合模式（類圖）中 （+ 代表 public;- 代表 private ; # 代表 protected ; ~ 代表 package）
7. 在觀察者模式中，需要將觀察者添加到觀察者列表中區(qū)，目標(biāo)需要更新?tīng)顟B(tài)