【正文】 (nlogn)不穩(wěn)后往前找小交換 （ 6）、 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不穩(wěn) （ 7）、 歸并排序 O(nlogn) O(nlogn)O(nlogn) O(1) 穩(wěn)定 兩兩排序歸并 （ 8）、 基數(shù)排序 O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd) 穩(wěn)定 r=10,d 位數(shù) 操作系統(tǒng) 四個特征：并發(fā)、共享、虛擬性、不確定性。 引起阻塞的原因：啟動某個 IO操作、新數(shù)據(jù)尚未到底、無新工作可作。 P（－ 1） V（＋ 1）。 調(diào)度方式：先來先服務(wù)、時間片輪轉(zhuǎn)、優(yōu)先級調(diào)度、多級反饋調(diào)度算法。 死鎖的處理：鴕鳥政策、預(yù)防政策（靜態(tài)分配法、資 源有序分配法）、避免政策（安全狀態(tài)和銀行家算法）、檢測與解除死鎖。 存儲管理的功能：主存的分配和回收、提高主存的利用率、存儲保護(hù)、主存擴充。可重定位分區(qū)是解決碎片問題的簡單有效的方法。兩級頁表機制：外層頁表即頁目錄存放頁表的物理地址，內(nèi)層頁表頁的物理塊號。請求分頁的硬件支持：缺頁中斷特點：在指令執(zhí)行期間產(chǎn)生和處理（一般中斷在后）、返回時回到該指令的開始重新執(zhí)行該指令（一般中斷回到下一條）、一條指令可產(chǎn)生多次缺頁中斷。 I/O 系統(tǒng)組成：設(shè)備、控制器、通道、總線、 I/O 軟件。 設(shè)備管理的主要技術(shù)：中斷技術(shù)、 DMA、通道、緩沖技術(shù)。字節(jié)多路通道、數(shù)組選擇通道、數(shù)組多路通道。磁盤調(diào)度目標(biāo)是使平均尋道時間最短。磁盤分配表是外存空閑空間管理的數(shù)據(jù)結(jié)構(gòu)。作業(yè)的四種狀態(tài)：提交、后備、執(zhí)行、完成。嵌入式操作系統(tǒng)：微型化、可定制、實時性、可靠性、易移植性（硬件抽象層 HAL屏蔽了 硬件平臺的差異），常見： Win CE 、 VxWorks、 pSOS、 Palm OS 、C/OS Unix 采用三級索引、四種尋址方式。采用分頁式虛擬存儲機制，二次機會頁面替換算法。 Win2020 系統(tǒng)：用戶態(tài)即目態(tài)只能執(zhí)行特權(quán)指令，核心態(tài)即管態(tài)可執(zhí)行任何指令并改變狀態(tài)。進(jìn)程對象屬性包括進(jìn)程標(biāo)識、資源訪問令牌、進(jìn)程的基本優(yōu)先級。 數(shù)據(jù)庫 DBMS 特點：①數(shù)據(jù)結(jié)構(gòu)化且統(tǒng)一管理，②有較高的數(shù)據(jù)獨立性，③數(shù)據(jù)控制功能：安全性、完整性、并發(fā)控制（帶來的數(shù)據(jù)不一致性有三類：丟失更新、不可重復(fù)讀、讀臟數(shù)據(jù)）、故障恢復(fù)（事務(wù)內(nèi)部故障、系統(tǒng)、介質(zhì)、病 毒） 三級模式：①、內(nèi)模式 存儲模式：數(shù)據(jù)物理格式存儲方式描述、②、模式 概念模式：數(shù)據(jù)邏輯結(jié)構(gòu)及聯(lián)系描述、③、外模式即用戶模式 子模式。 ALTER TABLE tbname [ADD 列名 完整性約束條件 ] [DROP 完整性約束名 ] [MODIFY 列名 類型 ] CREATE [UNIQUE][CLUSTER]INDEX idname ON tbname 列名 ASC/DSC CREATE VIEW viewname 列名 AS SELEC 子句 [WITH CHECK OPTION] SELECT [ALL|DISTINCT]列表名 FROM tbname/vname WHERE [GROUP BY 列名 HAVING 條件表達(dá)式 ][ORDER BY 列名 ASC/DESC] INSERT INTO tbname (字段名 ) VALUES（常量 /查詢子句） UPDATE tbname SET 列名＝值 (,) WHERE GRANT 權(quán)限 ,ON對象類型 對象名 TO用戶 WITH GRANT OPTION REVOKE 權(quán)限 , ON 對象類型 對象名 FROM 用戶 grant all privileges on table tbname to user1 grant insert on table tbname to user2 grant createtab on database dbname to user3 revoke update(sno) on table tbname from user4 SELECT 語句： 求選修了課程名 J的姓名： select sname from s where sno IN select sno from sc where o IN select o from c where ame=39。) 求選修了全部課程的姓名 :select sname from S where NOT EXISTS (select * from C where NOT EXISTS (select * from SC where sno= and o=) ) 求至少選修了學(xué)生 S2 所修課程的學(xué)生姓名： select DISTINCT SNO from SC x where NOT EXIST (select * from SC y where =39。 and SNO IN select SNO from sc y where =39。圖書的用戶定購的其他圖書 (表 orders orderlist)： select bid from orderlist A where NOT exists (select * from orders B where = and NOT IN (select cid from orderlist C,orders D where =39。 08 年軟考需要做什么？ 如何快捷通過軟考？ 軟考時間安排： 軟考視頻教程： 軟考各科指定教材： 軟考考試大綱匯總： 軟考過關(guān)完全攻略： 軟考?xì)v年試題匯總： 軟考資料下載： 提交資料賺希賽幣： 免費賺取希賽幣： 規(guī)范化 1NT:沒有表中表， 2NT 消除了 1NT 中非主屬性對碼的 部分函數(shù)依賴即每一個非主屬性完全依賴于全部的碼（ XY即 Y依賴 X）、 3NT 消除了非主屬性對碼傳遞依賴、 BCNF 消除了主屬性對碼的部分和傳遞依賴、 4NT 表中沒有多值依賴 事務(wù)的四個特征：原子性、一致性（數(shù)據(jù)不會因事務(wù)而破壞）、隔離性（事務(wù)獨立運行）、持久性（事務(wù)一旦提交）。 。 COMMIT。 and =)) 08 年軟考需要做什么？ 如何快捷通過軟考？ 軟考時間安排： 軟考視頻教程： 軟考各科指定教材： 軟考考試大綱匯總： 軟考過關(guān)完全攻略： 軟考?xì)v年試題匯總： 軟考資料下載： 提交資料賺希賽幣： 免費賺取希賽幣： 按學(xué)號給出每個學(xué)生選修課程的門數(shù)： select sno,count(CNO) from sc group by SNO 查某工程至少用了 3 家供應(yīng)商供應(yīng)零件的平均數(shù)（表 S、 P、 J、 SPJ） （三個實體一個聯(lián)系） ： select JNO,avg(QTY) avg(QTY)子句僅對分組 JNO 作計算 from SPJ group by JNO having count(distinct(SNO))=3 order by JNO DESC （查詢某工程至少用了 3 家供應(yīng)商（包含 3 家）供應(yīng)的零件的平均數(shù)量，并按工程號的降序排列） 分組查詢： GROUP BY 子句 SELECT 子句中使用的聚集操作符僅用在每個分組上。 求定購了 bid=39。 and NOT EXISTS ( select * from sc z ehere = and =)) 求選修了 C2 課程的學(xué)生選修的其他課程號： select o from SC x where CNO39。 求不選 C3課程的姓名： select sname from S where NOT EXISTS (select * from sc where = and o=39。 數(shù)據(jù)模型的三要素：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作、數(shù)據(jù)的約束條件。 IO 設(shè)備虛擬界面，將所有讀寫數(shù)據(jù)看成送往虛擬文件的字節(jié)流。子系統(tǒng)動 態(tài)鏈接庫是服務(wù)進(jìn)程和應(yīng)用進(jìn)程和系統(tǒng)交互的憑借。正則表達(dá)式符號： .任意字符 *前一字符的多次出現(xiàn) []選一個 ^否定 $行尾 \轉(zhuǎn)義符 “”忽視特殊字符 \字首匹配 \字尾匹配。 08 年軟考需要做什么？ 如何快捷通過軟考？ 軟考時間安排： 軟考視頻教程： 軟考各科指定教材： 軟考考試大綱匯總： 軟考過關(guān)完全攻略： 軟考?xì)v年試題匯總： 軟考資料下載： 提交資料賺希賽幣： 免費賺取希賽幣： 進(jìn)程控制語句： Fork 創(chuàng)建、 Exec 執(zhí)行、 Exit 結(jié)束、 Signal相應(yīng)事件、 Kill發(fā)送軟中斷信號。 網(wǎng)絡(luò)操作系統(tǒng)：有三類集中式、客戶服務(wù)器模式、對等模式。文件共享：硬鏈接 ln 名 新名、軟鏈接 ls – s。文件控制塊 FCB是由基本信息（名、物理地址）、存取控制信息、使用信息組