軟件學(xué)院面試題.pdf

School of Software Engineering University of Science and Technology of China 2012 年參加中國(guó)科大軟件學(xué)院復(fù)試前 收集了一些前幾屆的面試題目 和大家分享一下 希望對(duì)大家有所幫助 獨(dú)上高樓 望盡天涯路 衣帶漸寬終不悔 為伊消的人憔悴 眾里尋她千百度 驀然回首 伊人卻在燈火闌珊處 turinglife 2013 03 09 關(guān)于版本號(hào) 主版本號(hào) 次版本號(hào) 修訂號(hào) 版本號(hào)修改內(nèi)容修改時(shí)間修改人 1 0 000第一版本發(fā)布2013 03 09turinglife 1 0 001增加 2013 年第一批 面試真題 2013 03 24turinglife 1 0 002追加 2013 年第一批 面試真題 2013 03 26turinglife 1 0 003追加 2013 年第一批 面試真題 添加部分 題目答案 2013 03 29turinglife 1 好多人會(huì)問(wèn)到時(shí)間復(fù)雜度 6 2 各種排序的時(shí)間復(fù)雜度和性能比較 7 3 什么叫堆排序 與快速排序有神馬不同 10 4 循環(huán)隊(duì)列的順序表示中 為什么要空一個(gè)位置 10 5 什么是二叉查找樹(shù) 原理 11 6 排序算法最優(yōu)的時(shí)間復(fù)雜度 11 13 11 7 哈夫曼樹(shù) 11 12 13 11 8 什么是哈希沖突 及如何解決 13 11 9 深度 廣度搜索的過(guò)程 12 10 圖的深度優(yōu)先遍歷序列是否唯一 為什么 13 13 11 迪杰斯克拉算法的過(guò)程 13 12 鏈表查詢某個(gè)元素 平均時(shí)間復(fù)雜度是多少 13 13 圖的存儲(chǔ)方式 12 13 13 14 圖的深度遍歷是否唯一 14 15 圖相關(guān)概念 14 16 連通圖的概念 12 13 14 17 解釋下最小生成樹(shù) 15 18 n 個(gè)節(jié)點(diǎn)的圖的最小生成樹(shù)有幾個(gè)節(jié)點(diǎn) 幾條邊 15 19 平衡二叉樹(shù) 15 20 二叉樹(shù)怎么存儲(chǔ) 15 21 單鏈表就地逆置 15 22 各種查找總結(jié) 16 23 m 階的 B 樹(shù)和 m 階的 B 樹(shù)主要區(qū)別 19 24 折半查找 適用范圍和時(shí)間復(fù)雜度 19 25 計(jì)算機(jī)和計(jì)算器的區(qū)別 19 26 線程 進(jìn)程空間是什么 20 27 硬實(shí)時(shí)和軟實(shí)時(shí) 11 12 13 20 28 進(jìn)程和程序的區(qū)別 20 29 進(jìn)程和線程的區(qū)別 11 13 20 30 什么是微內(nèi)核 11 12 13 21 31 call 和 return 具體做了哪些工作 21 32 什么是 DMA 什么是中斷 DMA 和中斷有什么區(qū)別 12 13 21 33 硬中斷和軟中斷是什么 區(qū)別是什么 21 34 什么是內(nèi)存 13 22 35 頁(yè)面置換算法有哪些 什么是 LRU 22 36 操作系統(tǒng)中磁盤(pán)調(diào)度算法 23 37 操作系統(tǒng)中的信號(hào)量 24 38 什么是 Pv 操作 24 39 什么是操作系統(tǒng) 25 40 簡(jiǎn)述操作系統(tǒng)中系統(tǒng)調(diào)用過(guò)程 25 41 虛擬存儲(chǔ)器 虛存 問(wèn)有啥相關(guān)算法 12 13 26 42 存儲(chǔ)器管理應(yīng)具有的功能 26 43 什么是 TLB 27 44 程序連接方式有哪些 27 45 程序的裝入方式有哪些 27 46 什么是交換技術(shù) 什么是覆蓋技術(shù) 及其區(qū)別 28 47 內(nèi)存連續(xù)分配管理方式有哪幾種 28 48 動(dòng)態(tài)分區(qū)分配算法有哪些 28 49 什么是拼接技術(shù) 29 51 什么內(nèi)部碎片 什么是外部碎片 29 52 常用存儲(chǔ)保護(hù)方法有哪些 29 53 連續(xù)分區(qū)分配 vs 非連續(xù)分區(qū)分配 29 54 什么是頁(yè)面 什么是塊或物理塊 30 55 什么是頁(yè)表 及頁(yè)表的作用 12 13 30 56 段寄存器 30 57 進(jìn)程線程樹(shù)圖 31 58 作業(yè)與進(jìn)程的區(qū)別 31 59 進(jìn)程的三種狀態(tài) 以及之間轉(zhuǎn)換的過(guò)程 11 12 13 31 60 進(jìn)程調(diào)度算法 32 61 死鎖 32 62 分頁(yè)和分段的區(qū)別 11 12 13 33 63 死鎖及死鎖原因 33 64 介紹下銀行家算法 33 65 RAID 34 66 數(shù)據(jù)庫(kù)里面的 什么分級(jí) 什么是 ER 圖 35 67 數(shù)據(jù)庫(kù)的三級(jí)模式結(jié)構(gòu) 36 68 視圖在數(shù)據(jù)庫(kù)的第幾層 37 69 數(shù)據(jù)庫(kù)的兩級(jí)映像是什么 作用 37 70 數(shù)據(jù)庫(kù) ER 模型轉(zhuǎn)換成關(guān)系模型是數(shù)據(jù)庫(kù)設(shè)計(jì)的第幾個(gè)階段 38 71 數(shù)據(jù)庫(kù) 數(shù)據(jù)模型有哪幾種 說(shuō)出至少兩種的特征 38 72 數(shù)據(jù)庫(kù)中什么叫主碼 39 73 關(guān)系操作有哪些 13 39 74 數(shù)據(jù)庫(kù)的表怎樣分級(jí) 39 75 事務(wù)是什么 及其四個(gè)特征 11 12 13 39 76 數(shù)據(jù)庫(kù)操縱語(yǔ)言 定義語(yǔ)言 定義 操作 查詢 控制 39 77 數(shù)據(jù)庫(kù)中怎樣預(yù)防死鎖 40 78 并發(fā)控制是為了保證事務(wù)的什么性質(zhì) 11 13 40 79 在數(shù)據(jù)庫(kù)中什么是關(guān)系 它和普通二維表啥區(qū)別 40 80 視圖 索引 40 81 還有個(gè)根本沒(méi)見(jiàn)過(guò)的說(shuō)是什么標(biāo)準(zhǔn) 在數(shù)據(jù)庫(kù)中的那一層 41 82 數(shù)據(jù)庫(kù)里的讀鎖 寫(xiě)鎖 41 83 數(shù)據(jù)庫(kù)里 如何解決數(shù)據(jù)冗余問(wèn)題 41 84 關(guān)系范式 41 85 斷點(diǎn)之類(lèi)的問(wèn)題 42 86 關(guān)于顯卡的 顯卡作用 原理 42 87 VGA 43 88 FPGA 43 89 算數(shù)移位 邏輯移位 循環(huán)移位 43 90 386 的保護(hù)模式是什么 44 91 什么是實(shí)模式 44 92 芯片組是什么 45 93 介紹下南橋和北橋芯片 45 94 cache 和虛擬存儲(chǔ)的功能不同 46 95 接口芯片使用 8259A8251 46 96 組成總線里的異步通信 47 97 PC 機(jī)的串口是同步的還是異步的 13 47 98 512 4 的芯片 要組成 4M 的存儲(chǔ)空間要用幾個(gè)芯片級(jí)聯(lián) 具體用多少引腳 13 47 99 兩個(gè)時(shí)鐘不同步的設(shè)備怎么通信 47 100 X86 尋址方式有哪些 2013 年第一批 47 101 編譯 如何把一個(gè)機(jī)器的語(yǔ)言拿到另一臺(tái)機(jī)器語(yǔ)言機(jī)器上執(zhí)行 48 102 編譯原理語(yǔ)法分析句法分析 48 103 編譯的過(guò)程 48 104 路由協(xié)議有哪些 49 105 通信的同步異步定義及其相關(guān) 11 13 50 106 比特率波特率 50 107 網(wǎng)絡(luò)服務(wù)質(zhì)量包括哪些方面 50 108 什么是信道 51 109 信道分類(lèi) 51 110 什么是模擬信號(hào) 什么是數(shù)字信號(hào) 51 111 什么是基帶信號(hào) 什么是寬帶信號(hào) 51 112 局部變量和全局變量在內(nèi)存中是如何存儲(chǔ)的 13 51 113 java 與 C 區(qū)別他說(shuō)他想問(wèn)的是地址方面的 52 114 傳送介質(zhì)和無(wú)線網(wǎng)絡(luò)協(xié)議 54 115 什么是 SHELL 11 13 54 116 網(wǎng)絡(luò)里的時(shí)延 帶寬 55 117 滑動(dòng)窗口協(xié)議是什么 13 55 118 網(wǎng)絡(luò)擁塞 55 119 CSMA CD 的原理 12 13 56 120 數(shù)據(jù)緩存 cache 的基本概念 56 121 應(yīng)用層有什么協(xié)議 作用 57 122 網(wǎng)絡(luò)各層的設(shè)備是什么和工作原理 12 13 57 123 傳統(tǒng)的搜索引擎基本原理 基于內(nèi)容的搜索 原理及實(shí)現(xiàn) 57 124 客機(jī)被迫降到水面上 什么姿勢(shì)才能保證平穩(wěn)不栽倒水里面 57 125 數(shù)據(jù)傳輸方式 57 126 數(shù)據(jù)鏈路層有哪些協(xié)議 舉 1 2 例 58 127 電路交換和分組交換的區(qū)別及聯(lián)系 58 128 電路交換 報(bào)文交換 分組交換主要的區(qū)別 58 129 什么是 PN 結(jié) 模電數(shù)電 59 130 CDMA 全稱(chēng)及原理 59 131 ICMP 59 132 問(wèn)我什么是非對(duì)稱(chēng)加密 什么是數(shù)據(jù)安全的特征 60 133 保護(hù)頻帶 60 134 問(wèn)到 PPP 協(xié)議 60 135 流量控制在哪些層實(shí)現(xiàn) 61 136 二層交換機(jī)是哪一層的設(shè)備 與三層交換機(jī)之間的區(qū)別 61 137 三網(wǎng) 指哪三網(wǎng) 61 138 分組交換的優(yōu)點(diǎn)及缺點(diǎn) 61 139 組成網(wǎng)絡(luò)協(xié)議的三個(gè)要素 62 140 DNS and DHCP 62 141 網(wǎng)絡(luò)安全有哪些方面 63 142 P2P 協(xié)議 63 143 停止等待協(xié)議 63 144 ipv4 地址匱乏解決辦法 64 145 單工 半雙工 全雙工 12 13 65 146 TCP IP 模型分層 11 12 13 66 147 IPv4 和 IPv6 怎么相互通信 66 148 IPv4 的替代方案 66 149 從網(wǎng)絡(luò)的作用范圍進(jìn)行分類(lèi) 67 150 從網(wǎng)絡(luò)的使用范圍分類(lèi) 67 151 從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分類(lèi) 67 152 信道劃分 及其典型應(yīng)用 67 153 復(fù)用的相關(guān)概念 頻分 時(shí)分 碼分等 68 154 計(jì)算機(jī)網(wǎng)絡(luò)中使用的信道共享技術(shù)有哪些 13 68 155 自控問(wèn)的是時(shí)域和頻域的穩(wěn)定性判據(jù)分別是什么 13 69 156 反饋系統(tǒng)中偏差信號(hào)是指什么信號(hào)的偏差 13 69 157 中國(guó)科大軟件學(xué)院 2012 2013 學(xué)年 部分開(kāi)課老師 70 158 中國(guó)科大軟件學(xué)院 蘇州 美景 74 159 中國(guó)科大軟件學(xué)院 合肥 美景 77 160 Reference 78 1 1 1 1 好多人會(huì)問(wèn)到時(shí)間復(fù)雜度好多人會(huì)問(wèn)到時(shí)間復(fù)雜度 按數(shù)量級(jí)遞增排列 常見(jiàn)的時(shí)間復(fù)雜度有 常數(shù)階 O 1 對(duì)數(shù)階 O log2n 線性階 O n 線性對(duì)數(shù)階 O nlog2n 平方階 O n 2 立方階 O n 3 k 次方階 O n k 指數(shù)階 O 2 n 隨著問(wèn)題規(guī)模問(wèn)題規(guī)模 n n n n 的不斷增大 上述時(shí)間復(fù)雜度不斷增大 算法的執(zhí)行效率越低 2 2 2 2 各種排序的時(shí)間復(fù)雜度和性能比較各種排序的時(shí)間復(fù)雜度和性能比較 排序類(lèi)別排序類(lèi)別基本思路基本思路詳細(xì)詳細(xì) 分類(lèi)分類(lèi) 時(shí) 間 復(fù) 雜時(shí) 間 復(fù) 雜 度度 空 間 復(fù) 雜空 間 復(fù) 雜 度度 特點(diǎn)特點(diǎn)注意注意 插入排序每 一 趟 將 一 個(gè) 待 排 序的元素 按 其 關(guān) 鍵 字 值 的 大 小 插 入 到 已 經(jīng) 排 序 的 有 序 區(qū) 中 的 適 當(dāng) 位置上 直 到 全 部 插 入完成 直接插入排序最 好 正 序 O n O 1 需要 一 個(gè) 監(jiān) 視 哨 穩(wěn) 定穩(wěn) 定 排序 直接插入排序所產(chǎn)生的有序區(qū) 不一定是全局有序不一定是全局有序的 有序區(qū) 中的關(guān)鍵字并不一定大于或小 于無(wú)序區(qū)中所有元素的關(guān)鍵 字 這樣每一趟排序并不一定 將一個(gè)元素放置在最終的位置 上 插入排序與待排序數(shù)據(jù)的 順序有關(guān) 當(dāng)正序正序時(shí)效率最高效率最高 當(dāng)反序反序時(shí)效率最低效率最低 最 壞 逆 序 O n 2 平均 O n 2 折半插入平均 O n 2 O 1 折半插入排序僅減少了關(guān)鍵字 間的比較次數(shù) 而元素的移動(dòng) 次數(shù)不變 希爾排序平均 O n 1 3 O 1 不 穩(wěn)不 穩(wěn) 定定 排 序 希爾排序每一趟并不產(chǎn)生有序 區(qū) 也不一定將一個(gè)元素放置 在最終的位置上 希爾排序和 待排序數(shù)據(jù)的順序有關(guān) 正序正序 時(shí)最高最高 逆序逆序時(shí)效率最低最低 交換排序基本思想 兩 兩 比 較 待 排 序 元 素 的 關(guān) 鍵 字 發(fā)現(xiàn)兩 個(gè) 元 素 的 次 序 相 反 時(shí) 即 進(jìn) 行 交換 直到 沒(méi) 有 反 序 的 元 素 為 止 起泡排序最壞 O n2 平均 O n2 O 1 穩(wěn) 定穩(wěn) 定 排序 起泡排序中所產(chǎn)生的有序區(qū)一 定是全局有序的全局有序的 有序區(qū)中的 所有元素的關(guān)鍵字一定大于或 小于無(wú)序區(qū)中所有元素的關(guān)鍵 字 每一趟排序都將一個(gè)元素 放置到最終位置上 起泡排序 與待排序數(shù)據(jù)的順序有關(guān) 正正 序序效率最高最高 逆序逆序效率最低最低 快速排序 在待排序的 n 個(gè)元素中任取一個(gè)元素 通常取第一個(gè)元素 作 為基準(zhǔn) 把該元素放入最 終的位置上 歸為一個(gè)元 素 數(shù)據(jù)序列被此元素劃 不 穩(wěn)不 穩(wěn) 定定 排 序 在快速排序算法中 并不產(chǎn)生不產(chǎn)生 有序區(qū)有序區(qū) 但每一趟歸位一個(gè)元 素 快速排序與待排序數(shù)據(jù)的 順序有關(guān) 當(dāng)正序正序和逆序逆序時(shí)效效 率都低率都低 只有當(dāng)數(shù)據(jù)隨機(jī)分布 每次劃分的子區(qū)間長(zhǎng)度大致相 分成兩部分 所有關(guān)鍵字 比該元素關(guān)鍵字小的元素 放置在前一部分 所有比 他大的元素放置在后一部 分 這個(gè)過(guò)程稱(chēng)為一趟快 速排序 以后對(duì)所有的兩 部分分別重復(fù)上述過(guò)程 直至每部分內(nèi)只有一個(gè)元 素或空為止 等時(shí)效率最高 選擇排序基本思想 每 一 趟 從 待 排 序 的 元 素 序 列 中 選 出 關(guān) 鍵 字 最 大 或最小 的元素 按 順 序 放 在 已 排 序 的 元 素 序 列 的 最 后 面 或 最 前 面 直到 全 部 拍 完 為止 簡(jiǎn)單選擇排序 在無(wú)序區(qū) 中選擇關(guān)鍵字最小的元素 放在有序區(qū)的最后 形成 新的有序區(qū)和新的無(wú)序 區(qū) O 1 O n 2 不 穩(wěn)不 穩(wěn) 定定 排 序 有序區(qū)全局有序有序區(qū)全局有序 有序區(qū)中的 所有元素關(guān)鍵字要么全部大于 無(wú)序區(qū) 要么全部小于無(wú)序區(qū) 每趟排序歸為一個(gè)元素 時(shí)間 復(fù)雜度與待排序數(shù)據(jù)序列的順順 序無(wú)關(guān)序無(wú)關(guān) 堆排序 一種樹(shù)形選擇排 序 在排序過(guò)程中 將 R 1 n 看成是完全二叉樹(shù) 的順序存儲(chǔ)結(jié)構(gòu) 利用完 全二叉樹(shù)中的雙親和孩子 結(jié)點(diǎn)之間的關(guān)系來(lái)找到當(dāng) 前序列中關(guān)鍵最大 小的元 素 O 1 O nlog 2 n 不 穩(wěn)不 穩(wěn) 定定 排 序 建初始堆所需要的比較次數(shù)較 多 所以堆排序不適宜于元素 較少的表 所產(chǎn)生的有序區(qū)一定全局有有序區(qū)一定全局有 序序 有序區(qū)要么全部大于或小 于無(wú)序區(qū)中的關(guān)鍵字 每趟排 序歸為一個(gè)元素 時(shí)間復(fù)雜度 與待排序數(shù)據(jù)順序無(wú)關(guān)待排序數(shù)據(jù)順序無(wú)關(guān) 歸并排序 基數(shù)排序 各種排序方法的綜合比較 一 時(shí)間性能 1 按平均的時(shí)間性能來(lái)分 有三類(lèi)排序方法 時(shí)間復(fù)雜度為 O nlogn 的方法有 快速排序 堆排序和歸并排序 其中以快速排序?yàn)樽詈?直接插入算法 折半插入算法 3 3 3 3 什么叫堆排序 與快速排序有神馬不同 什么叫堆排序 與快速排序有神馬不同 答案請(qǐng)參加上面答案請(qǐng)參加上面 4 4 4 4 循環(huán)隊(duì)列的順序表示中 為什么要空一個(gè)位置 循環(huán)隊(duì)列的順序表示中 為什么要空一個(gè)位置 循環(huán)隊(duì)列那個(gè)空位置為了便于辨別對(duì)空和隊(duì)滿 5 5 5 5 什么是二叉查找樹(shù) 原理什么是二叉查找樹(shù) 原理 二叉排序樹(shù) Binary Sort Tree 又稱(chēng)二叉查找樹(shù) 它或者是一棵空樹(shù) 或者是具有下列性質(zhì)的二叉樹(shù) 1 若左子樹(shù)不空 則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值 2 若右子樹(shù)不空 則右子樹(shù)上所有 結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值 3 左 右子樹(shù)也分別為二叉排序樹(shù) 步驟 若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字 成功 否則 若小于根結(jié)點(diǎn)的關(guān)鍵字值 遞歸查左子樹(shù) 若大于根結(jié)點(diǎn)的關(guān)鍵字值 遞歸查右子樹(shù) 若子樹(shù)為空 查找不成功 6 6 6 6 排序算法最優(yōu)的時(shí)間復(fù)雜度排序算法最優(yōu)的時(shí)間復(fù)雜度 11 1311 1311 1311 13 基于比較的排序算法中最好時(shí)間復(fù)雜度為 O nlogn 7 7 7 7 哈夫曼樹(shù)哈夫曼樹(shù) 11 12 1311 12 1311 12 1311 12 13 給定 n 個(gè)權(quán)值作為 n 個(gè)葉子結(jié)點(diǎn) 構(gòu)造一棵二叉樹(shù) 若帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度達(dá)到最小最小 稱(chēng)這樣的二叉樹(shù)為最優(yōu)二最優(yōu)二 叉樹(shù)叉樹(shù) 也稱(chēng)為哈夫曼樹(shù)哈夫曼樹(shù) Huffman Huffman Huffman Huffman tree tree tree tree 構(gòu)造方法構(gòu)造方法 假設(shè)有 n 個(gè)權(quán)值 則構(gòu)造出的哈夫曼樹(shù)有 n 個(gè)葉子結(jié)點(diǎn) n 個(gè)權(quán)值分別設(shè)為 w1 w2 wn 則 哈夫曼樹(shù)的構(gòu)造規(guī)則為 1 將 w1 w2 wn 看成是有 n 棵樹(shù)的森林 每棵樹(shù)僅有一個(gè)結(jié)點(diǎn) 2 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并 作為一棵新樹(shù)的左 右子樹(shù) 且新樹(shù)的根結(jié)點(diǎn)權(quán) 值為其左 右子樹(shù)根結(jié)點(diǎn)權(quán)值之和 3 從森林中刪除選取的兩棵樹(shù) 并將新樹(shù)加入森林 4 重復(fù) 2 3 步 直到森林中只剩一棵樹(shù)為止 該樹(shù)即為所求得的哈夫曼樹(shù) 2 8 8 8 8 什么是哈希沖突 及如何解決什么是哈希沖突 及如何解決 13131313 哈希表哈希表 散列表 Hash table 也叫哈希表 是根據(jù)關(guān)鍵碼值 Key value 而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu) 也就是說(shuō) 它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄 以加快查找的速度 這個(gè)映射函數(shù)叫做散散 列函數(shù)列函數(shù) 存放記錄的數(shù)組叫做散列表 常用散列函數(shù)常用散列函數(shù) 1 直接尋址法 2 數(shù)字分析法 3 平方取中法 4 折疊法 5 隨機(jī)數(shù)法 6 除留余數(shù)法 處理沖突的方法處理沖突的方法 1 開(kāi)放尋址法 2 再散列法 3 鏈地址法 4 建立一個(gè)公共溢出區(qū) 散列因子散列因子 散列表的裝填因子定義為 填入表中的元素個(gè)數(shù) 散列表的長(zhǎng)度 是散列表裝滿程度的標(biāo)志因子 由于表長(zhǎng)是定值 與 填入表中的元素個(gè)數(shù) 成正比 所以 越大 填入表中的元素較多 產(chǎn)生沖突的可能性就越大 越小 填入表中的元素較少 產(chǎn)生沖突的可能性就越小 9 9 9 9 深度 廣度搜索的過(guò)程深度 廣度搜索的過(guò)程 圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷 假設(shè)給定圖 G 的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò) 在 G 中任選一頂點(diǎn) v 為初始出發(fā)點(diǎn) 源點(diǎn) 則深度優(yōu) 先遍歷可定義如下 首先訪問(wèn)出發(fā)點(diǎn) v 并將其標(biāo)記為已訪問(wèn)過(guò) 然后依次從 v 出發(fā)搜索 v 的每個(gè)鄰接點(diǎn) w 若 w 未曾訪問(wèn)過(guò) 則以 w 為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷 直至圖中所有和源點(diǎn) v 有路徑相通的頂點(diǎn) 亦稱(chēng)為從源點(diǎn)可達(dá)的頂點(diǎn) 均已被訪問(wèn)為止 若此時(shí)圖中仍有未訪問(wèn)的頂點(diǎn) 則另選一個(gè)尚未訪問(wèn)的頂點(diǎn) 作為新的源點(diǎn)重復(fù)上述過(guò)程 直至圖中所有頂點(diǎn)均已被訪問(wèn)為止 圖的深度優(yōu)先遍歷類(lèi)似于樹(shù)的前序遍歷圖的深度優(yōu)先遍歷類(lèi)似于樹(shù)的前序遍歷 采用的搜索方法的特點(diǎn)特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索 這 種搜索方法稱(chēng)為深度優(yōu)先搜索 Depth First Search 相應(yīng)地 用此方法遍歷圖就很自然地稱(chēng)之為圖的深度 優(yōu)先遍歷 使用數(shù)據(jù)結(jié)構(gòu)使用數(shù)據(jù)結(jié)構(gòu) 堆棧 圖的廣度優(yōu)先遍歷圖的廣度優(yōu)先遍歷 設(shè) x 是當(dāng)前被訪問(wèn)頂點(diǎn) 在對(duì) x 做過(guò)訪問(wèn)標(biāo)記后 選擇一條從 x 出發(fā)的未檢測(cè)過(guò)的邊 x y 若發(fā)現(xiàn) 頂點(diǎn) y 已訪問(wèn)過(guò) 則重新選擇另一條從 x 出發(fā)的未檢測(cè)過(guò)的邊 否則沿邊 x y 到達(dá)未曾訪問(wèn)過(guò)的 y 對(duì) y 訪問(wèn)并將其標(biāo)記為已訪問(wèn)過(guò) 然后從 y 開(kāi)始搜索 直到搜索完從 y 出發(fā)的所有路徑 即訪問(wèn)完所有從 y 出 發(fā)可達(dá)的頂點(diǎn)之后 才回溯到頂點(diǎn) x 并且再選擇一條從 x 出發(fā)的未檢測(cè)過(guò)的邊 上述過(guò)程直至從 x 出發(fā) 的所有邊都已檢測(cè)過(guò)為止 此時(shí) 若 x 不是源點(diǎn) 則回溯到在 x 之前被訪問(wèn)過(guò)的頂點(diǎn) 否則圖中所有和源 點(diǎn)有路徑相通的頂點(diǎn) 即從源點(diǎn)可達(dá)的所有頂點(diǎn) 都已被訪問(wèn)過(guò) 若圖 G 是連通圖 則遍歷過(guò)程結(jié)束 否則 繼續(xù)選擇一個(gè)尚未被訪問(wèn)的頂點(diǎn)作為新源點(diǎn) 進(jìn)行新的搜索過(guò)程 使用數(shù)據(jù)結(jié)構(gòu)使用數(shù)據(jù)結(jié)構(gòu) 隊(duì)列 10 10 10 10 圖的圖的深度深度優(yōu)先遍歷序列是否唯一 為什么 優(yōu)先遍歷序列是否唯一 為什么 13131313 不一定唯一 當(dāng)從某頂點(diǎn) x 出發(fā)搜索時(shí) 若 x 的鄰接點(diǎn)有多個(gè)尚未訪問(wèn)過(guò) 則我們可任選一個(gè)訪問(wèn)之 11 11 11 11 迪杰斯克拉算法的過(guò)程迪杰斯克拉算法的過(guò)程 Dijkstra 迪杰斯特拉 算法是典型的單源最短路徑算法單源最短路徑算法 用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路 徑 主要特點(diǎn)主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展 直到擴(kuò)展到終點(diǎn)為止 Dijkstra 算法是很有代表性的最短路 徑算法 在很多專(zhuān)業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹 如數(shù)據(jù)結(jié)構(gòu) 圖論 運(yùn)籌學(xué)等等 Dijkstra 一般 的表述通常有兩種方式 一種用永久和臨時(shí)標(biāo)號(hào)方式 一種是用 OPEN CLOSE 表的方式 這里均采用永 久和臨時(shí)標(biāo)號(hào)的方式 注意該算法要求圖中不存在負(fù)權(quán)邊 算法步驟如下算法步驟如下 1 初使時(shí)令 S V0 T 其余頂點(diǎn) T 中頂點(diǎn)對(duì)應(yīng)的距離值若存在 d V0 Vi 為弧上的權(quán) 值若不存在 d V0 Vi 為 2 從 T 中選取一個(gè)其距離值為最小的頂點(diǎn) W 且不在 S 中 加入 S 3 對(duì) T 中頂點(diǎn)的距離值進(jìn)行修改 若加進(jìn) W 作中間頂點(diǎn) 從 V0 到 Vi 的距離值比不加 W 的路徑要短 則修改此距離值重復(fù)上述步驟 2 3 直到 S 中包含所有頂點(diǎn) 即 S T 為止 12 12 12 12 鏈表查詢某個(gè)元素 平均時(shí)間復(fù)雜度是多少 鏈表查詢某個(gè)元素 平均時(shí)間復(fù)雜度是多少 O n 13 13 13 13 圖的存儲(chǔ)方式圖的存儲(chǔ)方式 12 13 12 13 12 13 12 13 圖沒(méi)有沒(méi)有順序映像的存儲(chǔ)結(jié)構(gòu) 1 鄰接矩陣鄰接矩陣 用兩個(gè)數(shù)組分別存儲(chǔ)數(shù)據(jù)元素?cái)?shù)據(jù)元素 頂點(diǎn)頂點(diǎn) 的信息的信息和數(shù)據(jù)元素之間的關(guān)系關(guān)系 邊或 弧 的信息 圖的鄰接矩陣表示是唯一唯一的 且無(wú)向圖的鄰接矩陣一定是一個(gè)對(duì)稱(chēng)矩陣 2 鄰接表鄰接表 是圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3 十字鏈表十字鏈表 有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 4 鄰接多重表鄰接多重表 無(wú)向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 14 14 14 14 圖的深度遍歷是否唯一圖的深度遍歷是否唯一 不唯一不唯一 15 15 15 15 圖相關(guān)概念圖相關(guān)概念 有向圖有向圖無(wú)向圖無(wú)向圖 弧弧 弧頭弧頭 弧尾弧尾邊邊 有向完全圖有向完全圖 n n 1 條弧的有向圖完全圖完全圖 1 2 n n 1 條邊的無(wú)向圖 稀疏圖稀疏圖 很少條邊或弧 如 enlogn 權(quán)權(quán) 有時(shí)圖的邊或弧具有與它相關(guān)的數(shù) 這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)權(quán) 網(wǎng)網(wǎng) 帶權(quán)圖稱(chēng)為網(wǎng) 子圖子圖 假設(shè)有兩個(gè)圖 G V E 和 G V E 如果 V 是 V 的子集 E 是 E 的子集 則稱(chēng) G 為 G 的子 圖 路徑路徑 頂點(diǎn)序列 路徑的長(zhǎng)度就是路徑上的邊或弧的數(shù)目 回路回路 環(huán)環(huán) 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱(chēng)為回路 環(huán) 簡(jiǎn)單路徑簡(jiǎn)單路徑 序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱(chēng)為簡(jiǎn)單路徑 簡(jiǎn)單回路簡(jiǎn)單回路 簡(jiǎn)單環(huán)簡(jiǎn)單環(huán) 除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外 其余頂點(diǎn)不重復(fù)出現(xiàn)的回路 稱(chēng)為簡(jiǎn)單回路 簡(jiǎn)單 環(huán) 出度出度 入度入度 度度 連通 連通 無(wú)向圖中從頂點(diǎn) A 到頂點(diǎn) B 有路徑 則稱(chēng)兩 個(gè)頂點(diǎn)連通 強(qiáng)連通圖強(qiáng)連通圖 有向圖中任意兩個(gè)不同頂點(diǎn) A B 從頂 點(diǎn) A 到頂點(diǎn) B 和從頂點(diǎn) B 到頂點(diǎn) A 都存在路徑 則 稱(chēng)為強(qiáng)連通圖 連同圖連同圖 圖中任意兩個(gè)頂點(diǎn)都是連通的 則稱(chēng)為連 通圖 強(qiáng)連通分量強(qiáng)連通分量 有向圖中的極大強(qiáng)連通子圖連通分量連通分量 無(wú)向圖中的極大極大連通子圖 生成森林生成森林 一個(gè)有向圖的生成森林由若干棵有向樹(shù) 組成 含有圖中全部頂點(diǎn) 但只有足以構(gòu)成若干棵 不相交的有向樹(shù)的弧 生成樹(shù)生成樹(shù) 極小連通子圖 含有圖中全部頂點(diǎn) 但只 有足以構(gòu)成一棵樹(shù)的 n 1 條邊 如果在一棵生成 樹(shù)上添加一條邊 必定構(gòu)成一個(gè)環(huán) 有向樹(shù)有向樹(shù) 如果一個(gè)有向圖恰好有一個(gè)頂點(diǎn)的入度為 0 其余頂點(diǎn)的入度均為 1 則是一棵有向樹(shù) 16 16 16 16 連通圖的概念連通圖的概念 12 1312 1312 1312 13 在圖論中 連通圖基于連通的概念 在一個(gè)無(wú)向圖 G 中 若從頂點(diǎn) vi 到頂點(diǎn) vj 有路徑相連 當(dāng)然從 vj 到 vi 也一定有路徑 則稱(chēng) vi 和 vj 是連通的 如果 G 是有向圖 那么連接 vi 和 vj 的路徑中所有的邊都 必須同向 如果圖中任意兩點(diǎn)都是連通的 那么圖被稱(chēng)作連通圖 如果圖中任意兩點(diǎn)都是連通的 那么圖被稱(chēng)作連通圖 圖的連通性是圖的基本性質(zhì) 17 17 17 17 解釋下最小生成樹(shù)解釋下最小生成樹(shù) 極小連通子圖 含有圖中全部頂點(diǎn) 但只有足以構(gòu)成一棵樹(shù)的 n 1 條邊 如果在一棵生成樹(shù)上添 加一條邊 必定構(gòu)成一個(gè)環(huán) 18 18 18 18 n n n n 個(gè)節(jié)點(diǎn)的圖的最小生成樹(shù)有幾個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)的圖的最小生成樹(shù)有幾個(gè)節(jié)點(diǎn) 幾條邊 幾條邊 n 個(gè)頂點(diǎn) n 1 條邊 19 19 19 19 平衡二叉樹(shù)平衡二叉樹(shù) 平衡二叉樹(shù) Balanced Binary Tree 又被稱(chēng)為 AVL 樹(shù) 有別于 AVL 算法 且具有以下性質(zhì) 它是一 棵 空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 1 0 1 并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù) AVL 樹(shù)是最先發(fā)明的自平衡二叉查找樹(shù) AVL 樹(shù)得名于它的發(fā)明者 G M Adelson Velsky 和 E M Landis 他們?cè)?1962 年的論文 An algorithm for the organization of information 中發(fā)表了它 查找 插入和刪除在平均和最壞情況下都是 O logn 增加和刪除可能需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新 平衡這個(gè)樹(shù) 20 20 20 20 二叉樹(shù)怎么存儲(chǔ)二叉樹(shù)怎么存儲(chǔ) 1 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元依次自上而下 自左向右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)信息 這 種順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹(shù) 否則其他形式的二叉樹(shù)用順序存儲(chǔ) 會(huì)浪費(fèi)不少存儲(chǔ)空間 2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表 三叉鏈表 含有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中有 n 1 個(gè)空鏈域 21 21 21 21 單鏈表單鏈表就地逆置就地逆置 所謂 就地就地 是指算法的輔助空間為 O 1 思路 用指針 p 掃描原單鏈表 先將頭節(jié)點(diǎn) L 的 next 域設(shè)置為 NULL 而變成一個(gè)空鏈表 然后將 p 節(jié)點(diǎn) 采用頭插法插入到 L 中 L an a1 P 算法 22 22 22 22 各種查找總結(jié)各種查找總結(jié) 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 若在查找的同時(shí)還對(duì)表做修改運(yùn)算 如插入或刪除 則相應(yīng)的表稱(chēng)之為動(dòng)態(tài)查找表 靜態(tài)查找表靜態(tài)查找表 反之稱(chēng)為靜態(tài)查找表 查找類(lèi)型查找類(lèi)型平均查找長(zhǎng)度平均查找長(zhǎng)度時(shí)間復(fù)雜度時(shí)間復(fù)雜度適用存儲(chǔ)結(jié)構(gòu)適用存儲(chǔ)結(jié)構(gòu)原理原理 順序查找 靜態(tài)查 找 成功 n 1 2O n 線性表的順序存儲(chǔ)順序存儲(chǔ) 和鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)都可以 從表的一端開(kāi)始 順序掃描線性表 依次將掃描到的關(guān) 失敗 n 鍵字和給定值 k 相 比較 若當(dāng)前掃描 到記錄的關(guān)鍵字與 k 相等 則查找成 功 若掃描結(jié)束后 仍未找到關(guān)鍵字等 于 k 的記錄 則查 找失敗 折半查找 靜態(tài)查 找 成功 查找過(guò)程恰 好走了一條從判定 樹(shù)的根到被查記錄 的路徑 經(jīng)歷比較 的關(guān)鍵字次數(shù)恰為 該記錄在樹(shù)中的層 次 在最壞的情況下查 找成功和查找不成 功的比較次數(shù)均不 超 過(guò) 判 定 樹(shù) 的 高 度 即 log2 n 1 O log2n 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)且 要求元素按關(guān)鍵字 有序排列有序排列 首先用要查找的關(guān) 鍵字 k 與中間位置 的節(jié)點(diǎn)的關(guān)鍵字相 比較 這個(gè)中間記 錄把線性表分成了 兩個(gè)子表 若比較 結(jié)果相等則查找成 功 若不相等 再 根據(jù) k 與該中間記 錄關(guān)鍵字的比較大 小確定下一步查找 哪個(gè)子表 這樣遞 歸進(jìn)行下去 注意注意 折半查找的 過(guò)程可用二叉樹(shù)來(lái) 描述 把當(dāng)前查找 區(qū)的中間位置上得 記錄作為根 左子 表和右子表中的記 錄作為根的左子樹(shù) 和右子樹(shù) 由此得 到的二叉樹(shù)稱(chēng)為描 述折半查找的判定判定 樹(shù)樹(shù)或比較樹(shù)比較樹(shù) 失敗 比較過(guò)程經(jīng) 理了一條從判定樹(shù) 根到某個(gè)外部節(jié)點(diǎn) 的路徑 所需關(guān)鍵 字比較次數(shù)不超過(guò) 判定樹(shù)的高度 B 樹(shù) 多路平衡查 找樹(shù) 動(dòng)態(tài)查找 特點(diǎn) 1 所有葉子節(jié)點(diǎn) 都在同一層 且不帶任何信 息 2 若根節(jié)點(diǎn)不是 終端節(jié)點(diǎn) 則 應(yīng)該同二叉查找樹(shù) O log2n 查找過(guò)程查找過(guò)程 B 樹(shù)查 找過(guò)程類(lèi)似于二叉 查找樹(shù)上的查找過(guò) 程 不同的是在每 個(gè)記錄確定向下查 找的路徑不一定是 二路的 因?yàn)橐粋€(gè) 節(jié)點(diǎn)內(nèi)的關(guān)鍵字有 序 故節(jié)點(diǎn)內(nèi)可以 采用順序查找或折 半查找 根節(jié)點(diǎn)至少有 兩棵子樹(shù) 3 樹(shù)中每個(gè)節(jié)點(diǎn) 至多有 m 棵樹(shù) 4 所有內(nèi)部每個(gè) 節(jié)點(diǎn)至少 m 2 棵子樹(shù) 插入過(guò)程插入過(guò)程 插入過(guò) 程分兩步 定位定位和 插入插入 定位過(guò)程利 用 上 面 的 查 找 算 法 插入過(guò)程分為 不分裂不分裂和分裂分裂兩種 情況 分裂插入有 可能導(dǎo)致 B 樹(shù)增高 一層 刪除過(guò)程刪除過(guò)程 兩大類(lèi) 第一類(lèi)在非最底層 的非葉子節(jié)點(diǎn)上刪 除關(guān)鍵字 第二類(lèi)在最底層非 葉子節(jié)點(diǎn)刪除關(guān)鍵 字 這類(lèi)型又分三 種情況 情況一 直接刪除關(guān)鍵字 情況二 兄弟夠借 情況三 兄弟不夠 借 合并 情況三 有可能導(dǎo)致 B 樹(shù)減 少一層 B 樹(shù)如果是從根節(jié)點(diǎn)開(kāi) 始進(jìn)行隨機(jī)查找的 話 應(yīng)該同二叉查 找樹(shù) O log2n 查找過(guò)程查找過(guò)程 兩種查 找方法 第一種 直接從最小關(guān)鍵字 開(kāi) 始 進(jìn) 行 順 序 查 找 第二種 從 B 樹(shù)的根節(jié)點(diǎn)開(kāi)始進(jìn) 行隨機(jī)查找 插入過(guò)程插入過(guò)程 僅在葉 子節(jié)點(diǎn)中插入關(guān)鍵 字 刪除過(guò)程刪除過(guò)程 僅在葉 子節(jié)點(diǎn)中刪除節(jié)點(diǎn) 23 23 23 23 mmmm 階的階的 B B B B 樹(shù)和樹(shù)和 mmmm 階的階的 B B B B 樹(shù)主要區(qū)別樹(shù)主要區(qū)別 mmmm 階的階的 B B B B 樹(shù)和樹(shù)和 mmmm 階的階的 B B B B 樹(shù)主要區(qū)別樹(shù)主要區(qū)別 1 B 樹(shù)所有有效數(shù)據(jù)全在葉子節(jié)點(diǎn) 而 B 樹(shù)所有節(jié)點(diǎn)分散在樹(shù)中 B 樹(shù)中的關(guān)鍵字不重復(fù) 2 B 樹(shù)種有幾個(gè)關(guān)鍵字就有幾個(gè)子樹(shù) B 樹(shù)中具有 n 個(gè)關(guān)鍵字的節(jié)點(diǎn)含有 n 1 棵子樹(shù) 3 B 樹(shù)有兩個(gè)指針 根指針和只想最小節(jié)點(diǎn)的指針 葉子節(jié)點(diǎn)連接成一個(gè)不定長(zhǎng)的線性鏈表 4 B 樹(shù)中 每個(gè)節(jié)點(diǎn) 除根節(jié)點(diǎn)外 中的關(guān)鍵字個(gè)數(shù) n 的取值范圍是 m 2 n m 根節(jié)點(diǎn) n 的取值 范圍是 2 n m B 樹(shù)中 每個(gè)節(jié)點(diǎn) 除根節(jié)點(diǎn)外的所有最底層非葉子節(jié)點(diǎn) 中的關(guān)鍵字取值范圍是 m 2 1 n m 1 根節(jié)點(diǎn) n 的取值范圍是 1 n m 1 5 B 樹(shù)中的所有非葉子節(jié)點(diǎn)僅僅起到索引的作用 節(jié)點(diǎn)中的每個(gè)索引項(xiàng)只包含對(duì)應(yīng)子樹(shù)的最大關(guān)鍵字和 指向該子樹(shù)的指針 不含有該關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)地址 而在 B 樹(shù)中 每個(gè)關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ) 地址 24 24 24 24 折半折半查找 適用范圍和時(shí)間復(fù)雜度查找 適用范圍和時(shí)間復(fù)雜度 適用范圍 順序存儲(chǔ)結(jié)構(gòu)適用范圍 順序存儲(chǔ)結(jié)構(gòu)且要求元素按關(guān)鍵字有序排列有序排列 時(shí)間復(fù)雜度 時(shí)間復(fù)雜度 o log 2 n 25 25 25 25 計(jì)算機(jī)和計(jì)算器的區(qū)別計(jì)算機(jī)和計(jì)算器的區(qū)別 計(jì)算器 具有簡(jiǎn)單計(jì)算功能 有些具有簡(jiǎn)單存儲(chǔ)功能 不能自動(dòng)工作 而計(jì)算機(jī)可以通過(guò)編程實(shí)現(xiàn)程序自 動(dòng)運(yùn)行 價(jià)位便宜 計(jì)算機(jī) 高速計(jì)算的電子計(jì)算機(jī) 可進(jìn)行數(shù)值計(jì)算 邏輯計(jì)算 還具有存儲(chǔ)記憶功能 自動(dòng)化程度高于計(jì) 算器 實(shí)際上二者還有另一個(gè)本質(zhì)性的區(qū)別 計(jì)算器使用的是固化的處理程序 只能完成特定的計(jì)算任務(wù) 而計(jì)算機(jī)借助操作系統(tǒng)平臺(tái)和各類(lèi)應(yīng)用軟硬件 可以無(wú)限擴(kuò)展其應(yīng)用領(lǐng)域 也就是說(shuō) 是否具有擴(kuò)展性是 二者的本質(zhì)區(qū)別 26 26 26 26 線程線程 進(jìn)程空間是什么進(jìn)程空間是什么 線程運(yùn)行所需要的內(nèi)存空間 比如線程程序的存儲(chǔ)空間 數(shù)據(jù)空間 運(yùn)行空間等 邏輯地址和物理地址之間的切換 是由 CPU 的內(nèi)存管理單元 MMU 完成 Linux 內(nèi)核維護(hù)每個(gè)進(jìn)程的邏輯地 址到物理地址的對(duì)照表 當(dāng)用戶空間進(jìn)程切換時(shí) 內(nèi)核會(huì)更新對(duì)照表 用戶空間也跟隨變 每個(gè)進(jìn)程的用戶空間都是相互獨(dú)立的 把同一個(gè)程序同時(shí)運(yùn)行 10 次 會(huì)看到 10 個(gè)進(jìn)程使用的線性地址一 模一樣但物理內(nèi)存不一樣 27 27 27 27 硬實(shí)時(shí)和軟實(shí)時(shí)硬實(shí)時(shí)和軟實(shí)時(shí) 11 12 1311 12 1311 12 1311 12 13 在實(shí)時(shí)操作系統(tǒng)中 系統(tǒng)必須在特定的時(shí)間內(nèi)完成指定的應(yīng)用 具有較強(qiáng)的 剛性 而分時(shí)操作系 統(tǒng)則注重將系統(tǒng)資源平均地分配給各個(gè)應(yīng)用 不太在意各個(gè)應(yīng)用的進(jìn)度如何 什么時(shí)間能夠完成 不過(guò) 就算是實(shí)時(shí)操作系統(tǒng) 其 剛性 和 柔性 的程度也有所不同 就好像是系統(tǒng)的 硬度 有所不同 因 而有了所謂的 硬實(shí)時(shí) hard real time 和 軟實(shí)時(shí) soft real time 硬實(shí)時(shí)硬實(shí)時(shí)系統(tǒng)有一個(gè)剛性的 不可改變的時(shí)間限制 它不允許任何超出時(shí)限的錯(cuò)誤 超時(shí)錯(cuò)誤會(huì)帶來(lái)?yè)p 害甚至導(dǎo)致系統(tǒng)失敗 或者導(dǎo)致系統(tǒng)不能實(shí)現(xiàn)它的預(yù)期目標(biāo) 軟實(shí)時(shí)軟實(shí)時(shí)系統(tǒng)的時(shí)限是一個(gè)柔性靈活的 它可以容忍偶然的超時(shí)錯(cuò)誤 失敗造成的后果并不嚴(yán)重 例如 在網(wǎng)絡(luò)中僅僅是輕微地降低了系統(tǒng)的吞吐量 28 28 28 28 進(jìn)程和程序的區(qū)別進(jìn)程和程序的區(qū)別 進(jìn)程進(jìn)程 程序的一次執(zhí)行過(guò)程 一個(gè)動(dòng)態(tài)的過(guò)程 存在生命周期 包括進(jìn)程的創(chuàng)建 進(jìn)程運(yùn)行 進(jìn)程掛起 進(jìn)程結(jié)束 程序程序 代碼 數(shù)據(jù)的一個(gè)集合 一個(gè)靜態(tài)的表示 29 29 29 29 進(jìn)程和線程的區(qū)別進(jìn)程和線程的區(qū)別 11 1311 1311 1311 13 進(jìn)程 資源分配和調(diào)度的基本單位 進(jìn)程切換耗費(fèi)資源比線程切換大 進(jìn)程有獨(dú)立的進(jìn)程地址空間 線程 線程是進(jìn)程中的一個(gè)實(shí)體 是 CPU 調(diào)度的基本單位 是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位 線程 自己不擁有系統(tǒng)資源 只擁有運(yùn)行中必不可少的資源 如程序計(jì)數(shù)器 寄存器 棧 在同一個(gè)線程內(nèi) 可 以有多個(gè)線程 多個(gè)線程共享同一個(gè)進(jìn)程的資源 每個(gè)線程具有自己的線程棧 線程沒(méi)有獨(dú)立的線程地址 空間 多個(gè)線程共享同一個(gè)進(jìn)程地址空間 30 30 30 30 什么是微內(nèi)核什么是微內(nèi)核 11 12 1311 12 1311 12 1311 12 13 微內(nèi)核是一種能夠提供必要服務(wù)的操作系統(tǒng)內(nèi)核 其中這些必要的服務(wù)包括任務(wù) 線程 交互進(jìn)程通信 IPC Inter Process Communication 以及內(nèi)存管理等等 所有服務(wù) 包括設(shè)備驅(qū)動(dòng) 在用戶模式下運(yùn) 行 而處理這些服務(wù)同處理其他的任何一個(gè)程序一樣 因?yàn)槊總€(gè)服務(wù)只是在自己的地址空間運(yùn)行 所以這 些服務(wù)之間彼此之間都受到了保護(hù) 微內(nèi)核是提供操作系統(tǒng)核心功能的內(nèi)核的精簡(jiǎn)版本 如 Windows Linux 是一個(gè)單內(nèi)核 也就是說(shuō) Linux 內(nèi)核運(yùn)行在單獨(dú)的內(nèi)核地址空間 不過(guò) Linux 汲取了微內(nèi)核的精華 其引以為豪的是模塊化設(shè)計(jì) 搶占式內(nèi)核 支持內(nèi)核線程已經(jīng)動(dòng)態(tài)裝載內(nèi)核模塊的能力 31 31 31 31 callcallcallcall 和和 returnreturnreturnreturn 具體做了哪些工作具體做了哪些工作 call 參數(shù)壓棧 返回地址壓棧 保護(hù)現(xiàn)場(chǎng) return 返回地址 恢復(fù)現(xiàn)場(chǎng) 32 32 32 32 什么是什么是 DMADMADMADMA 什么是中斷 什么是中斷 DMADMADMADMA 和中斷有什么區(qū)別和中斷有什么區(qū)別 12 1312 1312 1312 13 DMADMADMADMA Direct Memory Access 直接內(nèi)存訪問(wèn) 為了實(shí)現(xiàn)外設(shè)CPU存儲(chǔ)器之間的不足 從而實(shí)現(xiàn) 存儲(chǔ)器 CPU 釋放總線 由 DMA 控制器管理 中斷中斷 是指在 CPU 正常運(yùn)行程序時(shí) 由于內(nèi)部 外部事件引起 CPU 暫時(shí)停止正在運(yùn)行的程序 轉(zhuǎn)而去執(zhí)行 請(qǐng)求 CPU 服務(wù)的內(nèi)部事件或外部事件的服務(wù)子程序 待該服務(wù)子程序處理完畢后又返回到被中止的程序繼 續(xù)運(yùn)行 這一過(guò)程叫做中斷 區(qū)別區(qū)別 首先概念功能就不一樣 另外在 DMA 的過(guò)程中需要用到中斷系統(tǒng) 33 33 33 33 硬中斷和軟中斷是什么 區(qū)別是什么 硬中斷和軟中斷是什么 區(qū)別是什么 軟中斷軟中斷 1 編程異常通常叫做軟中斷 2 軟中斷是通訊進(jìn)程之間用來(lái)模擬硬中斷的 一種信號(hào)通訊方式 3 中斷源發(fā)中斷請(qǐng)求或軟中斷信號(hào)后 CPU 或接收進(jìn)程在適當(dāng)?shù)臅r(shí)機(jī)自動(dòng)進(jìn)行中斷處理或完成軟中斷信號(hào) 對(duì)應(yīng)的功能 4 軟中斷是軟件實(shí)現(xiàn)的中斷 也就是程序運(yùn)行時(shí)其他程序?qū)λ闹袛?而硬中斷是硬件實(shí)現(xiàn)的中斷 是程序運(yùn) 行時(shí)設(shè)備對(duì)它的中斷 硬中斷硬中斷 1 硬中斷是由外部事件引起的因此具有隨機(jī)性和突發(fā)性 軟中斷是執(zhí)行中斷指令產(chǎn)生的 無(wú)外部施加中斷 請(qǐng)求信號(hào) 因此中斷的發(fā)生不是隨機(jī)的而是由程序安排好的 2 硬中斷的中斷響應(yīng)周期 CPU 需要發(fā)中斷回合信號(hào) NMI 不需要 軟中斷的中斷響應(yīng)周期 CPU 不 需發(fā)中斷回合信號(hào) 3 硬中斷的中斷號(hào)是由中斷控制器提供的 NMI 硬中斷中斷號(hào)系統(tǒng)指定為 02H 軟中斷的中斷號(hào)由指 令直接給出 無(wú)需使用中斷控制器 4 硬中斷是可屏蔽的 NMI 硬中斷不可屏蔽 軟中斷不可屏蔽 區(qū)別區(qū)別 1 軟中斷發(fā)生的時(shí)間是由程序控制的 而硬中斷發(fā)生的時(shí)間是隨機(jī)的 2 軟中斷是由程序調(diào)用發(fā)生的 而硬中斷是由外設(shè)引發(fā)的 3 硬件中斷處理程序要確保它能快速地完成它的任務(wù) 這樣程序執(zhí)行時(shí)才不會(huì)等待較長(zhǎng)時(shí)間 34 34 34 34 什么是內(nèi)存 什么是內(nèi)存 13131313 內(nèi)存是計(jì)算機(jī)中重要的部件之一 它是與 CPU 進(jìn)行溝通的橋梁 計(jì)算機(jī)中所有程序的運(yùn)行 都是在內(nèi)存中進(jìn)行的 因此內(nèi)存的性能對(duì)計(jì)算機(jī)的影響非常大 內(nèi)存 Memory 也被稱(chēng)為內(nèi) 存儲(chǔ)器 其作用是用于暫時(shí)存放 CPU 中的運(yùn)算數(shù)據(jù) 以及與硬盤(pán)等外部存儲(chǔ)器交換的數(shù)據(jù) 只要計(jì)算機(jī)在運(yùn)行中 CPU就會(huì)把需要運(yùn)算的數(shù)據(jù)調(diào)到內(nèi)存中進(jìn)行運(yùn)算 當(dāng)運(yùn)算完成后CPU 再將結(jié)果傳送出來(lái) 內(nèi)存的運(yùn)行也決定了計(jì)算機(jī)的穩(wěn)定運(yùn)行 內(nèi)存是由內(nèi)存芯片 電路板 金手指等部分組成的 35 35 35 35 頁(yè)面置換算法有哪些 什么是頁(yè)面置換算法有哪些 什么是 LRULRULRULRU 在地址映射過(guò)程中 若在頁(yè)面中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)面不再內(nèi)存中 則產(chǎn)生缺頁(yè)中斷缺頁(yè)中斷 當(dāng) 發(fā)生缺頁(yè)中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存 以便為即將調(diào)入的頁(yè)面讓 出空間 而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法頁(yè)面置換算法 常見(jiàn)的置換算法有 01 最佳置換算法 OPT 理想置換算法 02 先進(jìn)先出置換算法 FIFO 03 最近最久未使用 LRU 算法 04 Clock 置換算法 LRU 算法的近似實(shí)現(xiàn) 05 最少使用 LFU 置換算法 06 工作集算法 07 工作集時(shí)鐘算法 08 老化算法 非常類(lèi)似 LRU 的有效算法 09 NRU 最近未使用 算法 10 第二次機(jī)會(huì)算法 LRU 是 Least Recently Used 最近最少使用算法 為了盡量減少與理想算法的差距 產(chǎn)生了各種精妙的算法 最近最少使用頁(yè)面置換算法 便是其中一個(gè) LRU 算法的提出 是基于這樣一個(gè)事實(shí) 在前面幾條指令中使用頻繁的頁(yè) 面很可能在后面的幾條指令中頻繁使用 反過(guò)來(lái)說(shuō) 已經(jīng)很久沒(méi)有使用的頁(yè)面很可能在未來(lái) 較長(zhǎng)的一段時(shí)間內(nèi)不會(huì)被用到 這個(gè) 就是著名的局部性原理局部性原理 比內(nèi)存速度還要快的 cache 也是基于同樣的原理運(yùn)行的 因此 我們只需要在每次調(diào)換時(shí) 找到最近最少使用 的那個(gè)頁(yè)面調(diào)出內(nèi)存 這就是 LRU 算法的全部?jī)?nèi)容 36 36 36 36 操作系統(tǒng)中磁盤(pán)調(diào)度算法操作系統(tǒng)中磁盤(pán)調(diào)度算法 磁盤(pán)調(diào)度的目標(biāo)是 使磁盤(pán)的平均尋道時(shí)間最少 磁盤(pán)調(diào)度的目標(biāo)是 使磁盤(pán)的平均尋道時(shí)間最少 調(diào)度算法名稱(chēng)調(diào)度算法名稱(chēng)基本原理基本原理特點(diǎn)特點(diǎn) 先來(lái)先服務(wù) FCFS First Come First Serve 僅適用于請(qǐng)求磁盤(pán)僅適用于請(qǐng)求磁盤(pán) IOIOIOIO 的進(jìn)程的進(jìn)程 數(shù)目較少的場(chǎng)合數(shù)目較少的場(chǎng)合 最簡(jiǎn)單的一種磁盤(pán)調(diào)度算法 根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先 后次序進(jìn)行調(diào)度 優(yōu)點(diǎn)優(yōu)點(diǎn) 簡(jiǎn)單 公平 每一個(gè)請(qǐng) 求的進(jìn)程都能夠得到處理 不 會(huì)出現(xiàn)長(zhǎng)期得不到處理的進(jìn) 程 缺點(diǎn)缺點(diǎn) 未對(duì)尋道進(jìn)行優(yōu)化 致 使平均尋道時(shí)間可能較長(zhǎng) 最短尋道時(shí)間優(yōu)先 SSTF Shorted Seek Time First 該算法選擇這樣的進(jìn)程 其要 求訪問(wèn)的磁道 與當(dāng)前磁頭所 在的磁道距離最近 以使每次 的尋道時(shí)間最短 但這種算法 不能保證平均尋道時(shí)間最短 優(yōu)點(diǎn)優(yōu)點(diǎn) 較 FCFS 有更好的尋道 性能 缺點(diǎn)缺點(diǎn) 可能導(dǎo)致老進(jìn)程饑餓饑餓 可能會(huì)出現(xiàn)磁臂黏著磁臂黏著 掃描算法 SCAN 電梯調(diào)度電梯調(diào)度 算法算法 該算法不僅考慮到被訪問(wèn)磁 道和當(dāng)前磁頭之間的距離 更 優(yōu)點(diǎn)優(yōu)點(diǎn) 磁頭雙向移動(dòng) 不會(huì)產(chǎn) 生饑餓 平均尋道時(shí)間短 在在 SSTSSTSSTSSTF F F F 算法基礎(chǔ)上優(yōu)化而得算法基礎(chǔ)上優(yōu)化而得 到 可以防止老進(jìn)程饑餓 到 可以防止老進(jìn)程饑餓 優(yōu)先考慮的是磁頭當(dāng)前的移 動(dòng)方向 應(yīng)該選取同方向且距 離最近的磁道訪問(wèn) 缺點(diǎn)缺點(diǎn) 可能會(huì)出現(xiàn)磁臂黏著磁臂黏著 循環(huán)掃描算法 CSCAN 為了減少延遲 CSCAN 規(guī)定 磁頭單向移動(dòng) 當(dāng)從里到最外 后 磁頭立即返回到最里的欲 訪問(wèn)磁道 然后繼續(xù)向外 優(yōu)點(diǎn)優(yōu)點(diǎn) 磁頭單向移動(dòng) 不會(huì)產(chǎn) 生饑餓 平均尋道時(shí)間短 N Step SCAN 算法 對(duì) SCAN 算法的優(yōu)化 將磁盤(pán)請(qǐng)求隊(duì)列分成若干個(gè) 長(zhǎng)度為 N 的子隊(duì)列 磁盤(pán)調(diào)度 將按照 FCFS 依次處理這些子 隊(duì)列 而每處理一個(gè)隊(duì)列時(shí)又 是按照 SCAN 算法 對(duì)一個(gè)隊(duì) 列處理后再處理其他隊(duì)列 將 新請(qǐng)求隊(duì)列放入新隊(duì)列 優(yōu)點(diǎn)優(yōu)點(diǎn) 無(wú)磁臂黏著磁臂黏著 FSCAN 算法 對(duì) SCAN 算法 的優(yōu)化 將請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列 將新出現(xiàn)請(qǐng)求磁盤(pán) IO 的進(jìn)程 放入另一個(gè)子隊(duì)列 優(yōu)點(diǎn)優(yōu)點(diǎn) 無(wú)磁臂黏著磁臂黏著 37 37 37 37 操作系統(tǒng)中的信號(hào)量操作系統(tǒng)中的信號(hào)量 信號(hào)量是一種實(shí)現(xiàn)進(jìn)程同步同步和互斥互斥的工具 1 整型信號(hào)量整型信號(hào)量 所謂整型信號(hào)量就是一個(gè)用于表示資源個(gè)數(shù)的整型量 2 記錄性信號(hào)量記錄性信號(hào)量 就是用一個(gè)結(jié)構(gòu)體實(shí)現(xiàn) 里面包含了表示資源個(gè)數(shù)的整型量和一個(gè)等待 隊(duì)列 Linux 內(nèi)核代碼對(duì) semaphore 的實(shí)現(xiàn) struct semaphore raw spinlock t lock unsigned int count struct list head wait list 38 38 38 38 什么是什么是 PvPvPvPv 操作操作 P V 操作以原語(yǔ)形式實(shí)現(xiàn) 信號(hào)量的值僅能由這兩條原語(yǔ)加以改變 P 操作相當(dāng)于申請(qǐng)資源申請(qǐng)資源 V 操作相當(dāng)于釋放資源釋放資源 39 39 39 39 什么是操作系統(tǒng)什么是操作系統(tǒng) 操作系統(tǒng)是管理電腦硬件與軟件資源的程序 同時(shí)也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石 操作系統(tǒng)是控制其他程 序運(yùn)行 管理系統(tǒng)資源并為用戶提供操作界面的系統(tǒng)軟件的集合 操作系統(tǒng)身負(fù)諸如管理與配置內(nèi)存 決 定系統(tǒng)資源供需的優(yōu)先次序 控制輸入與輸出設(shè)備 操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù) 操作系統(tǒng)的型 態(tài)非常多樣 不同機(jī)器安裝的 OS 可從簡(jiǎn)單到復(fù)雜 可從手機(jī)的嵌入式系統(tǒng)到超級(jí)電腦的大型操作系統(tǒng) 目前微機(jī)上常見(jiàn)的操作系統(tǒng)有 DOS OS 2 UNIX XENIX LINUX Windows Netware 等 40 40 40 40 簡(jiǎn)述操作系統(tǒng)中系統(tǒng)調(diào)用過(guò)程簡(jiǎn)述操作系統(tǒng)中系統(tǒng)調(diào)用過(guò)程 系統(tǒng)調(diào)用把應(yīng)用程序的請(qǐng)求傳給內(nèi)核 調(diào)用相應(yīng)的的內(nèi)核函數(shù)完成所需的處理 將處理結(jié)果返回給應(yīng)用程 序 如果沒(méi)有系統(tǒng)調(diào)用和內(nèi)核函數(shù) 用戶將不能編寫(xiě)大型應(yīng)用程序 Linux 系統(tǒng)調(diào)用 包含了大部分常用系統(tǒng)調(diào)用和由系統(tǒng)調(diào)用派生出的的函數(shù) 41 41 41 41 虛擬存儲(chǔ)器 虛存 問(wèn)有啥相關(guān)算法虛擬存儲(chǔ)器 虛存 問(wèn)有啥相關(guān)算法 12 1312 1312 1312 13 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 由于常規(guī)內(nèi)存的一次性一次性 要求將作業(yè)全部裝入內(nèi)存后才能運(yùn)行 和駐留性駐留性 作業(yè)裝入內(nèi)存后 就一直駐留在內(nèi)存中 直到作業(yè)運(yùn)行結(jié)束 特點(diǎn) 難以滿足作業(yè)很大和有大量作業(yè)要求運(yùn)行的情況 虛 擬存儲(chǔ)器是一種借助于外存空間 從而允許一個(gè)進(jìn)程在其運(yùn)行過(guò)程中部分地裝入內(nèi)存的技術(shù) 之所以引入虛擬存儲(chǔ)管理方式 是因?yàn)槌绦驁?zhí)行時(shí)呈現(xiàn)局部性規(guī)律 局部性原理局部性原理 1 時(shí)間局部性 一條指令的一次執(zhí)行和下次執(zhí)行 一個(gè)數(shù)據(jù)的一次執(zhí)行和下次執(zhí)行 都集中在一個(gè)較短 時(shí)間內(nèi) 2 空間局部性 指當(dāng)前指令和鄰近的幾條指令 當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的數(shù)據(jù) 都集中在一個(gè)較小區(qū)域 實(shí)現(xiàn)虛擬存儲(chǔ)器的硬件支持實(shí)現(xiàn)虛擬存儲(chǔ)器的硬件支持 1 相當(dāng)數(shù)量的外存 2 相當(dāng)數(shù)量的內(nèi)存 3 地址變換機(jī)構(gòu) 以動(dòng)態(tài)實(shí)現(xiàn)虛擬地址到實(shí)地址的地址變換 替換算法替換算法 替換規(guī)則用來(lái)確定替換主存中哪一部分 以便騰空部分主存 存放來(lái)自輔存要調(diào)入的那部分內(nèi) 容 1 隨機(jī)算法 用軟件或硬件隨機(jī)數(shù)產(chǎn)生器確定替換的頁(yè)面 2 先進(jìn)先出 先調(diào)入主存的頁(yè)面先替