北大軟微復(fù)試2018年之前含答案

1、1. TCP/IP 協(xié)議簇是ernet 的基礎(chǔ)，也是最流行的組網(wǎng)形式。TCP/IP 是一組協(xié)議的代名詞，包括許多別的協(xié)議，組成了 TCP/IP 協(xié)議簇。其中比較重要的有 SLIP 協(xié)議、PPP 協(xié)議、IP 協(xié)議、ICMP 協(xié)議、ARP 協(xié)議、TCP 協(xié)議、UDP 協(xié)議、FTP協(xié)議、DNS 協(xié)議、SMTP 協(xié)議等。TCP/IP 協(xié)議并不完全符合 OSI 的七層參考模型。2. ;TCP/IP 協(xié)議族中的加密協(xié)議，我說了個 ssl，她問我是哪一層的；3. SSL(Secure Sockets Layer接層),及其繼任者傳輸層安全（Transport LayerSecurity，TLS）是為網(wǎng)絡(luò)通信

2、提供安全及數(shù)據(jù)完整性的一種安全協(xié)議。TLS 與SSL 在傳輸層對網(wǎng)絡(luò)連接進行加密。4.男老師 2：說一說客戶端和服務(wù)器客戶和服務(wù)器都是指在通信中所涉及的兩個應(yīng)用進程, 他們之間是服務(wù)與被服務(wù)的關(guān)系：客戶端和服務(wù)器用英文怎么說？Cnt 客戶 klantServer 服務(wù)器s:rv(r)P2P:, P2(to)P搜索器,CS 和 BS 是什么5. 瀏覽器的英文 browser(braz)端到端指的進程到進程，通過套接字(IP 地址+端)6.7.C/S Cnt/Server 客戶/服務(wù)器模型 是雙向的通訊，任何一方都可以隨時方發(fā)送信息。B/S Browser/Server，瀏覽器/服務(wù)器模式是查詢式

3、的通訊，只有客戶端向服務(wù)器查詢時，服務(wù)器才能向客戶端發(fā)送信息.C/S 是雙向通訊，B/S 是一問一答。鏈路怎么判斷環(huán),設(shè)置兩個指針 fast 和 slow，剛開始都指向鏈表頭部，fast 每次移動兩個位置，slow 每次移動一個位置，若兩個指針相遇，說明有環(huán)。若 fast 為 null（nl）, 則無環(huán)(null 只能是地址，不能是型，表示地址為空，即不存在)在鏈表里怎么找到環(huán)的，一解： 從鏈表頭、與相遇點分別設(shè)一個指針，每次各走一步，兩個指針再次相遇點就是環(huán)的。a,是鏈表頭到的距離。 b,是從到相遇掉的距離2s= a+ b + mrS = a + b + nrS= (m-n)r=a+b+nr

4、a = ox-b二解第一問得出相遇點后，再發(fā)出一個指針，統(tǒng)計這個指針再次回到這個點的距離，也就是環(huán)的距離。然后從起點再發(fā)出兩個指針，一個指針在另一個前面，兩個指針的距離就是環(huán)的距離，當(dāng)兩個指針再次相遇的時候就是環(huán)的。8. 算法里的背包問題以及貪心算法。9. 0-1 背包用動態(tài)規(guī)劃算法10. 0-1 背包：一組物品，每種物品有自己的重量和價格，且每種物品僅一個，在限定的總重量內(nèi)，如何選擇，使得物品的總價格最高11. 動態(tài)規(guī)劃算法與分治法類似，其基本也是將待求解問題分解為若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。數(shù)據(jù)結(jié)構(gòu)12. 與分治法最大的差別是：適用于動態(tài)規(guī)劃求解，經(jīng)分解

5、后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進行進一步的求解）13. 背包問題(Knapsack problem)是一種組合優(yōu)化的 NP 完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，使得物品的總價格最高如何選擇，才能NP 完全問題：多項式復(fù)雜程度的非確定性問題。數(shù)據(jù)結(jié)構(gòu)里面編算法之前需要做什么/數(shù)據(jù)結(jié)構(gòu)三要素邏輯結(jié)構(gòu)+/物理結(jié)構(gòu)+數(shù)據(jù)運算邏輯結(jié)構(gòu)：數(shù)據(jù)之間的邏輯關(guān)系。結(jié)構(gòu)：數(shù)據(jù)的邏輯關(guān)系在計算機中的表示。問判斷算法優(yōu)劣的標(biāo)準(zhǔn)：時空 ，以為自己正確的毒瘤，才健壯。正確性：對任何合法的輸入，會得出正確的結(jié)果。1

6、2.怎么判斷環(huán)？（忘了是鏈表還是圖了）圖的遍歷就是按照某種次序圖的每一頂點一次僅且一次。實現(xiàn) bfs 和 dfs 都需要解決的一個問題就是如何接表。這里為簡單起圖。一般有兩種方法：鄰接矩陣和鄰見，均采用鄰接矩陣，說白了也就是二維數(shù)組。14.DFS: 深度優(yōu)先搜索遍歷 Depth兩個棧模擬隊列,在搜索最短路徑時，適合用 BFS，BFS 類似二叉樹層次遍歷，BFS 搜索過遇到的解一定是離根最近的，所以遇到一個解一定是最優(yōu)解在搜索全部的解時，適合用 DFS，BFS 在搜索過使用隊列搜索過的狀態(tài)，而 DFS 使用遞歸工作棧，不需要保存搜索過的狀態(tài)。BFS: 廣度優(yōu)先搜索遍歷 BreadthSearch

7、健壯性：當(dāng)輸入數(shù)據(jù)時，不會導(dǎo)致程序癱瘓?？勺x性：被理解的難易程度。時間復(fù)雜度和空間復(fù)雜度：算法運算所需要的時間，算法運算時所需要的空間常見的排序算法（了解它們的算法和時間及空間復(fù)雜度，若能手寫代碼是最好的了），樹的定義，給出一顆樹要求寫出廣度和深度優(yōu)先序列（這個簡單哈）棧是先入后出，隊列是先入先出。用兩個棧來模擬隊列。棧 1 用來入隊列，棧 2 用來出隊列。入隊列時，將元素壓入棧 1 即可。出隊列時，先看棧 2 是否為空，若不為空，棧 2 彈棧。若為空，先將棧 1 元素彈出，壓入棧2，之后棧 2 彈棧。堆棧的區(qū)別,棧區(qū)（stack） 由編譯器自動分配，存放方法調(diào)用和函數(shù)參數(shù)值和局部變量 一般速

8、度較快；地址是連續(xù)且存在有限棧容量，會出現(xiàn)溢出現(xiàn)象堆區(qū)（heap） 一般由程序員分配，通過(malloc 和 new)動態(tài)申請內(nèi)存, 一般速度較棧慢；回收地址通常是鏈?zhǔn)降?，?nèi)存較大不會溢出, 若程序員不，程序結(jié)束時可能由 OS15. 樹、二叉樹、滿二叉樹、完全二叉樹的區(qū)別1 樹(遞歸的非線性數(shù)據(jù)結(jié)構(gòu)) ：N 個結(jié)點的有限集合，N=0 時，稱為空樹 滿足有且僅有一個特定的稱為根的結(jié)點 當(dāng) N1 時，其余節(jié)點可分為 m（M0）個互不相交的有限集合，其中每個集合本身又是一棵樹,并成為根結(jié)點的.1）二叉樹：每個節(jié)點至多有兩個（二叉樹中不存在度大于 2 的結(jié)點），二叉樹有左右之分，不能相互顛倒（1）滿二

9、叉樹：一個高度為 n，并且有 2n-1 個結(jié)點的二叉樹稱為滿二叉樹（2）完全二叉樹 ：一個高度是 n 的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與高度為 n 的滿二叉樹中為 12n-1 的結(jié)點一一對應(yīng)時，此時稱完全二叉樹.可由滿二叉樹從右至左, 從下至上, 挨個刪結(jié)點形成（3）二叉排序樹：一棵二叉樹或者空二叉樹，或者具有如下性質(zhì)的二叉樹：樹上所有結(jié)點的關(guān)鍵字均小于根節(jié)點上的關(guān)鍵字，右上所有結(jié)點的關(guān)鍵字均大于根節(jié)點的關(guān)鍵字，樹和右又各是一棵二叉排序樹（4）平衡二叉樹(AVL 樹)：樹上任一結(jié)點的樹和右的深度之差不超過 12）樹轉(zhuǎn)換為二叉樹：根據(jù)左孩子，右兄弟的原則，每個節(jié)點左指針指向它的第一個孩子結(jié)點，右

10、指針指向它在樹中的相鄰兄弟節(jié)點樹二叉樹畫法: 兄弟連, 骨肉殘將同一結(jié)點的各孩子結(jié)點用線串起來, 把每個結(jié)點的分支從左往右除了第一個之外, 其余全都剪掉, 最后調(diào)整結(jié)點使之符合二叉樹的層次結(jié)構(gòu) 森林轉(zhuǎn)換為二叉樹: 先將森林中的每一棵樹轉(zhuǎn)換為二叉樹, 然后將第一個樹的根作為轉(zhuǎn)換后的二叉樹的根, 第一棵樹的樹作為轉(zhuǎn)換后二叉樹的樹, 第二棵樹作為轉(zhuǎn)換后二叉樹的右, 第三棵樹作為轉(zhuǎn)換后二叉樹的右的右, 以此類推二叉樹轉(zhuǎn)換為森林:若二叉樹非空 則二叉樹根及其樹為第一棵樹的二叉樹形式 二叉樹的右又可以看做是一個由除第一棵樹外的森林轉(zhuǎn)換后的二叉樹 應(yīng)用同樣的方法 直到最后產(chǎn)生一顆棵沒有右的二叉樹為止 這樣就

11、得到了原森林森林 $二叉樹的畫法 右下皆兄弟 排排坐 找媽咪F ）樹編碼樹 也可以 叉 又稱最優(yōu)二叉樹 帶權(quán)路徑長度最小的二叉樹 樹的帶權(quán)路徑長度 =62 KOMNZKJ VGZN RKTMZN 樹中所有葉子結(jié)點的帶權(quán)路徑長度之和結(jié)點的帶權(quán)路徑長度 結(jié)點具值 從該結(jié)點到根之間的路徑長度乘以結(jié)點的權(quán)值 樹特點 大短 人的 MM 權(quán)值越大的結(jié)點 距離根結(jié)點越近樹中沒有度為 的結(jié)點 此類樹又稱為正則 嚴(yán)格 二叉樹樹的帶權(quán)路徑長度最短編碼 是一種數(shù)據(jù)壓縮編碼 通過可變長度編碼 產(chǎn)生的是最短前綴碼 前綴碼 任一字符的編碼都不是另一字符編碼的前綴 OV 壓縮文件就用到了編碼常見排序的及其時空復(fù)雜度。 常見

12、的排序和復(fù)雜度5 RUM T歐 RGU MK 以 為底T 的對數(shù) ）排序 （ ）直接排序：將當(dāng)前的元素排到前面已經(jīng)有序的序列中（適用于基本有序和數(shù)據(jù)量不大的排序表） （ ）折半排序：用折半查找找出 元素待的位置，然后再的移動待位置之后的所有元素 （ ）排序（縮小增量排序）：先將待排序表分割成若干個形如 2A/ / J O JdddC的特殊子表，分別進行直接排序，當(dāng)整個表中元素呈現(xiàn)基本有序時，再對全體進行一次直接排序（僅適合于當(dāng)線性表為順序存貯的情況）空間復(fù)雜度為 U（ ） ）交換排序 （ ）冒泡排序：假設(shè)待排序表長為 T，從后往前（或從前往后）兩兩相鄰元素的值，若為逆序，則交換他們，直到序列比

13、較完，結(jié)果將最小的元素交換到待排序的第一個位置來 （ ）快速排序：在待排序表中選取一個元素 VOUZ 作為基準(zhǔn)，通過一趟排序?qū)⑴判虮韯澐譃楠毩⒌膬刹糠郑鞍氩糠侄夹∮?VOUZ 后半部分都大于 VOUZ 則 VOUZ 被放在了最終位置上，然后再對這兩個子序列進行劃分。 ）選擇排序 （ ）簡單選擇排序 ：假設(shè)排序表為 2A ， ，。4C，第 / 趟排序即從 2【O。4】中選擇最小的元素與 2（O）交換，每一趟排序可以確定一個元素的最終位置。叉樹的順序存貯結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)選擇最大最小元素 ）歸并排序：兩個或兩個以上的有序表組成一個新的有序表 ）基

14、數(shù)排序：基于關(guān)鍵字排序每輪排序都會確定一個最終位置：冒泡，快排，選擇排序，堆 各種鏈表的算法 幾種以及解決方法 ( 樹：多路平衡查找樹，( 樹中所有結(jié)點的孩子結(jié)點數(shù)的最大值稱為 ( 樹的階 ）樹中每個節(jié)點至多有 3 棵（即至多含有 3 個關(guān)鍵字） ）若根節(jié)點不是終端節(jié)點，則至少有兩棵 ）除根節(jié)點以外的所有非葉節(jié)點至少有【3 】棵 ）所有葉節(jié)點都出現(xiàn)在同一層( 樹是所有節(jié)點的平衡銀子都等于 的多路查找樹。( 樹的概念： ）每個分支最多有 3 棵。 ）每個非葉節(jié)點至少有兩棵，其他每個分支節(jié)點至少有【3 】棵 ）結(jié)點的個數(shù)與關(guān)鍵字個數(shù)相等 ）所有葉節(jié)點包含全部關(guān)鍵字以及指向相應(yīng)的指針，而且葉節(jié)點中將

15、關(guān)鍵字按大小順序排列，并且相鄰葉節(jié)點按照大小順序相互連接起來。 ）所有分支節(jié)點（可以看成索引的索引）中僅包含它的各個子節(jié)點中的最大值及指向子（ ）堆排序：樹形選擇排序方法，在排序過，將 2A 。4C看成是一棵完全二節(jié)點的指針。函數(shù)調(diào)用: 先定義并函數(shù)，之后再根據(jù)定義函數(shù)的格式調(diào)用函數(shù)調(diào)用模式: 函數(shù)模式,方法模式,構(gòu)造器模式,(分治)：一趟排序，用樞軸值將待排分成兩塊，（較小，樞紐值，較大記錄），分別對兩塊遞歸排序，最終，整個序列有序。平均時間復(fù)雜度：5 TRUM T 最好情況（無序列）: O(nlog2n), 此時樞軸值恰好能將待排序列從中間分開情況: O(n2), 此時待排序列有序，選擇的

16、樞軸值最終每次都在序列的兩端。分治：將復(fù)雜的原問題分解為多個規(guī)模較小且性質(zhì)相同的子問題，求出子問題的解，將其合并，就是原問題的解。如二分法，快排啊16. “簡單介紹下你使用過的數(shù)據(jù)結(jié)構(gòu)，一個是單鏈表倒置的題，新建一個鏈表，將原鏈表的從首元結(jié)點開始，依次摘下，用頭插法新鏈表即可。（每次摘結(jié)點之前，要保存其后結(jié)點的地址）1234Node* Reverse(Node* node)Node* prev = NULL; Node* tmp = NULL;/ 用于保存當(dāng)前鏈表的頭結(jié)點/ 用于保存當(dāng)前節(jié)點的 next 歸并排序, 冒泡與說一下快速排序的實現(xiàn)過程，最好情況和情況的時間復(fù)雜度。567891011

17、12131415while (node != NULL)tmp = node-_next;/保存當(dāng)前節(jié)點的 nextnode-_next = prev = node;prev;/將當(dāng)前節(jié)點到頭結(jié)點前之后將當(dāng)前節(jié)點設(shè)置為頭節(jié)點node = tmp;/next 為下次迭代的當(dāng)前節(jié)點return prev;/循環(huán)結(jié)束后，p 即為倒置后的頭結(jié)點19. 查找最大公共子序列（LCS: longest common subsequence）：常用于解決字符串的相似度，20. 個序列的，則S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長S 稱為已知序列的最長公共子序列21. 與最長公共

18、子串不同的是：子序列不一定在原序列中連續(xù)，子串要求連續(xù)。前沿C4.5 以決策樹的形式構(gòu)建了一個分類器，C4.5 算法在生成信息樹的時候使用了信息增益，決策樹最好的賣點是他們方便于翻譯和解釋The term big data often refers simply to the use of predictiveytics, user behaviorytics, or certain other advanced dataytics methodst extract value from data“大數(shù)據(jù)”一詞通常是指簡單地使用分析、用戶行為分析、或某些其他先進的數(shù)據(jù)分析方法,從數(shù)據(jù)中提取價值

19、,很少到一個特定的數(shù)據(jù)集的大小。數(shù)據(jù)挖掘算法：PageR（的搜索引擎）。為了決定一些對象和同網(wǎng)絡(luò)中的其他對象之間的相對重要程度而設(shè)計的連接分析算inkysis algorithm)。18. 求若干序列的公共子序列大 一是指數(shù)據(jù)量大 一是指數(shù)據(jù)源多 利用不同來源的龐大的數(shù)據(jù)量進行分析 來對未來進行 1.云計算是一種通過網(wǎng)絡(luò)提供高性能的計算資源的，可以彈性變化的，共享的一種服務(wù)模式。它綜合應(yīng)用了多種技術(shù)，但不是一種新技術(shù)。2.說它是“云”，因為它很難找到邊界，而且是彈性變化的，像天空的云一樣。另外，提供云計算服務(wù)的中心有一堆服務(wù)器，像 “云”一樣不易計數(shù)。計算能力和能力向互聯(lián)網(wǎng)端的遷移和抽象。遷移

20、指計算和都不在本機甚至本地服務(wù)器而遷移到了互聯(lián)網(wǎng)的服務(wù)器集群上，抽象指最終用戶無需關(guān)系真正的和計算發(fā)生在何處。云計算包含兩方面內(nèi)容，一是在網(wǎng)絡(luò)上提供的為計算服務(wù)的應(yīng)用，例如以前被稱為SaaS(Software as a Service)的那一類應(yīng)用；二是提供這些服務(wù)的在數(shù)據(jù)中心的硬件和系統(tǒng)軟件，這部分也就是通常所稱呼為“云”的東西通過網(wǎng)絡(luò)以自助服務(wù)的方式獲得所需要的 IT 資源的模式云計算就是租！將計算力作為服務(wù)進行銷售非本地計算，都可以算作云計算。小到一個程序應(yīng)用，大到整個計算架構(gòu)云計算的本質(zhì)是一種服務(wù)提供模型，通過這種模型可以隨時隨地、按需的通過網(wǎng)絡(luò)共享資源池的資源，這個資源池的資源內(nèi)容包

21、括計算資源、網(wǎng)絡(luò)資源、源能夠動態(tài)的分配和調(diào)整，在不同的用戶之間;靈活切換劃分。資源等，這些資你可以直接形象化的理解為云計算就是生活中的水電廠，之前每家每戶都需要自己買發(fā)動機自己打水井，現(xiàn)在有一個公司供水供電還便宜，這個公司就是云計算廠家。金融大數(shù)據(jù)集合海量非結(jié)構(gòu)化數(shù)據(jù)，通過對其進行實時分析，通過分析和挖掘客戶的交易和消費信息掌握客戶的消費 ，并準(zhǔn)確 客戶行為，使金融機構(gòu)在 和風(fēng)險控制方面有的放矢云計算基于 .GJUUV 分布式基礎(chǔ)構(gòu)架，開發(fā)，其 是 HDFS（分布式文件系統(tǒng) Hadoop Distributed File System）為海量的數(shù)據(jù)提供了 ，利用 SGVXKJIK 進行計算。云

22、計算：按使用量 商業(yè)計算模式。云計算是一種按使用量的模式，這種模式提供可用的、便捷的、按需的網(wǎng)絡(luò)， 進入可配置的計算資源共享池（資源包括網(wǎng)絡(luò)，服務(wù)器，應(yīng)用，服務(wù)），這些資源能夠被快速提供，只需投入很少的管理工作，或與服務(wù)供應(yīng)商進行很少的交互。云，就是互聯(lián)網(wǎng)上的提供計算服務(wù)的計算集群，提供云計算服務(wù)的中心的服務(wù)器集群。很多，像云一樣，無邊表示互聯(lián)網(wǎng)和底層基礎(chǔ)設(shè)施的抽象Cloud Computing）Refers to the proviof compuional resouron demand via a computernetwork.云計算指通過計算機網(wǎng)絡(luò)，根據(jù)需要提供計算資源。，現(xiàn)在人太多

23、了，人不能閑在這里。啪，你不會考慮一下把這些人賣出去，給別人開發(fā)項目。但是，別人只要半個人，或者幾個小時的工作量，了。一個人一個人的太多啪，你不會把一個人拆成幾個虛擬的人啊，或者按工時賣就行了。想要管理這么多機器，做這么多事情，還真不簡單，還要有人管協(xié)調(diào)分工（并行計算），有人管理誰多誰少（負載均衡），還需要容許別人生病、辭職（熱備冗余），還需要解決賣半個人，甚至十分之一個人（虛擬化）。人工智能（Artifilelligence），英文縮寫為 AI人工智能就是研究如何使計算機去做過去只有能做的智能工作云安全（Cloud Security）：通過網(wǎng)狀的大量客戶端對網(wǎng)絡(luò)中行為的異常監(jiān)測，獲取互聯(lián)網(wǎng)中

24、木馬、程序的信息，推送到 Server 端進行自動分析和處理，再把和木馬的解決方案分發(fā)到每一個客戶端。機器學(xué)習(xí) ： machine learning 在不直接針對問題進行編程的情況下，賦予計算機學(xué)習(xí)能力，讓計算機程序隨著經(jīng)驗積累自動提高性能互聯(lián)網(wǎng)金融ernet Finance（ITFIN） ：傳統(tǒng)金融機構(gòu)與互聯(lián)網(wǎng)企業(yè)利用互聯(lián)網(wǎng)技術(shù)和信息通信技術(shù)實現(xiàn)融通、支付、投資和信息中介服務(wù)的新型金融業(yè)務(wù)模式VR(virtual reality，虛擬現(xiàn)實)：可以讓用戶沉浸其中的由計算機生成的三維虛擬環(huán)境，并與現(xiàn)實環(huán)境相隔絕。AR(augmented reality，增強現(xiàn)實)：在真實環(huán)境中增添或者移除由計算

25、機實時生成的可以交互的虛擬物體或信息。MR(mixed reality，混合現(xiàn)實)：將現(xiàn)實環(huán)境與虛擬環(huán)境相互混合，也可以看成是 VR 與 AR 的混合。Blockchain ： （blk ten）用共識算法來對于新增數(shù)據(jù)達成共識，采用去中心化的分布式數(shù)據(jù)庫。學(xué)的方法來保證已有數(shù)據(jù)不可能被篡改的系統(tǒng)結(jié)構(gòu)(操作系統(tǒng)體系結(jié)構(gòu)): 微內(nèi)核和宏(大)內(nèi)核宏內(nèi)核: 將操作系統(tǒng)的主要功能模塊都作為一個整體運行在內(nèi)核態(tài), 不易于擴展，但是功能較強，效率比較高。模塊獨立程度：（1）耦合 一個結(jié)構(gòu)內(nèi)不同模塊之間互聯(lián)程度的度量 數(shù)據(jù)耦合 控制耦合 特征耦合 公共環(huán)境耦合 內(nèi)容耦合 （2）內(nèi)聚 一個模塊內(nèi)各個元素彼此

26、結(jié)合的緊密程度 偶然內(nèi)聚 邏輯內(nèi)聚 時間內(nèi)聚（必須在同一段時間內(nèi)完成）過程內(nèi)聚（順序） 通信內(nèi)聚（必須使用同一個輸入數(shù)據(jù)和產(chǎn)生同一個輸出數(shù)據(jù)） 順序內(nèi)聚（一個微內(nèi)核: 把一些必要的功能集成在內(nèi)核里，易于擴展，功能相對較弱, 效率沒有宏內(nèi)核高(要頻繁的在用戶態(tài)和態(tài)間進行切換)。windows 是微內(nèi)核系統(tǒng), Linus, unix 是宏內(nèi)核系統(tǒng)物聯(lián)網(wǎng): 即是物物相連的互聯(lián)網(wǎng). 物聯(lián)網(wǎng)是互聯(lián)網(wǎng)的基礎(chǔ)上進行擴展和延伸的網(wǎng)絡(luò), 其用戶端擴展和延伸到了任何物品與物品之間, 進行信息交換和通信.軟工開發(fā)模型(設(shè)計中的模型)：瀑布模型 前一階段的工作完成后，才能開始下一階段的工作，前一階段的輸出文檔就是后一

27、階段的輸入文檔?？焖僭湍Ｐ?快速建立起可以運行的程序，完成的功能是最終產(chǎn)品的一個子集增量模型 在各個階段并不交付一個可運行的完整產(chǎn)品，而是交付用戶滿足用戶需求的一個子集的可運行產(chǎn)品螺旋模型 結(jié)合快速原型和瀑布模型，每個階段之前都增加了風(fēng)險分析的快速原型模型噴泉模型以用戶需求為動力，以對象作為驅(qū)動的模型。具有迭代性和無間隙性模塊的輸出作為下一個模塊的輸入） 功能內(nèi)聚（所有處理元素屬于同一整體，完成單一的功能） 面象 ）客觀世界是由各種對象組成的，任何事物都是對象，復(fù)雜的對象可以由簡單的對象以某種方式組合而成 ）把所有的對象都劃分成各種對象類，每個對象類都定義了一組數(shù)據(jù)和法。 ）按照子類與父類的

28、關(guān)系，把若干個對象類組成一個層次結(jié)構(gòu)的系統(tǒng)。 ）對象之間僅能通過傳遞消息互相聯(lián)系。優(yōu)點：與人類的思維方法一致，穩(wěn)定性好，可重用性好，較易開發(fā)大型對象：由描述該對象屬性的數(shù)據(jù)以及可以對這些數(shù)據(jù)施加的所有操作封裝在一起的統(tǒng)一體特點：以數(shù)據(jù)為中心 對象是主動的 實現(xiàn)了數(shù)據(jù)封裝 本質(zhì)上具有并行性 模塊獨立性好類：具有相同數(shù)據(jù)和相同操作的一組相似對象的定義，也就是說，類是對具有相同屬性和行為的一個或多個對象的描述重載： ）函數(shù)重載是在同一作用域內(nèi)的若干個參數(shù)特征不同的函數(shù)可以使用相同的名字2）運算符重載是指同一個運算符可以施加于不同類型的操作數(shù)上面面象設(shè)計的準(zhǔn)則：模塊化，抽象 信息隱藏 弱耦合 強內(nèi)聚

29、可重用24 面象建模的三種模型1）對象模型：描述系統(tǒng)數(shù)據(jù)結(jié)構(gòu)2）動態(tài)模型：系統(tǒng)控制結(jié)構(gòu)，表示瞬時的，行為化的系統(tǒng)控制性質(zhì)，規(guī)定了對象模型中對象的合法變化序列3）功能模型：系統(tǒng)功能（數(shù)據(jù)流圖，用例圖）計算機網(wǎng)絡(luò)4 層結(jié)構(gòu), 可看做五層(TCP/IP 模型)物理層, 數(shù)據(jù)鏈路層, 網(wǎng)絡(luò)層, 傳輸層, 應(yīng)用層1 TCP/IP（TransmisControl Protocol/ernet Protocol）即傳輸控制協(xié)議/網(wǎng)間協(xié)議應(yīng)用層：層：TCP （面向連接，報文段）UDP（用戶數(shù)據(jù)報）網(wǎng)際層：IP（IP 數(shù)據(jù)報=分組）網(wǎng)絡(luò)接口層：網(wǎng)絡(luò)層：端到端 套接字 OV 地址 端 唯一標(biāo)識端口59/ 83（U

30、VKT Y_YZKSKXIUTTKIZOUT XKLKXKTIK S）開放系統(tǒng)互連基本參考模型6N_YOIGR RG_KX JGZG ROTQ RG_KX TKZUXQ RG_KX :XGTYVUXZ 2G_KX YKYRG_KX VXKYKTOUT RG_KX GVVROIGZOUT RG_KX應(yīng)用層：*.)6（動態(tài)主機配置協(xié)議 J_TGSOI NUYZ IUTLOMXGZOUT VXUZUIUR）基于 JV8/6 路由信息協(xié)議 XUZOTM OTLUXSGZOUT VXUZUIUR 距離向量 JV (-6（邊界網(wǎng)關(guān)協(xié)議 HUXJKX MGZKG_ VXUZUIUR） ZIV ,:6（文件傳

31、輸協(xié)議 LORK ZXGTYLXUZUIUR） 控制端口 數(shù)據(jù)連接 93:6 簡單郵件傳輸協(xié)議 YOSVRZXGTYLXUZUIUR 6UV 郵局協(xié)議Z ULLOIK VXUZUIUR 端 .:6 超文本傳輸協(xié)議 ._VKX:KZ :XGTYLKX 6XUZUIUR 表示層：不同的表示方法的數(shù)據(jù)和信 不同通信系統(tǒng) 之間能相互交換 數(shù)據(jù)格式轉(zhuǎn)換 會話層：允許不同主機上進程間的會話傳輸層 進程之間的邏輯通信 可同一主機 也可不同主機 一個進程一個端口/6 數(shù)據(jù)報首部中的檢驗和只檢驗首部查數(shù)據(jù)部分86（地址協(xié)議 GJJXKYY XKYURZOUT VXUZUIUR）886（逆地址協(xié)議 XKKXYK）

32、/)36（網(wǎng)際控制報文協(xié)議KXTKZ IUTZXUR SKYYGMK VXUZUIUR）允許主機或路由器差錯和異常情況/-36 網(wǎng)際組管理協(xié)議TKZ MXUV SGTGMKSKTZ VXUZUIUR /6（網(wǎng)際協(xié)議KXTKZ VXUZUIUR）AVXZQRC596, 開放最短路徑優(yōu)先 數(shù)據(jù)鏈路層：25. GJJOZOK ROTQ UTROTK NGGOO Y_YZKS )93 載波偵聽多路IGXXOKX YKTYK SRZOVRK GY )93 )* 載波偵聽多路 碰撞協(xié)議 ddOZN IURROJKIZOUT )93 )（ 碰撞避免）令牌傳遞協(xié)議（以上都屬于隨機介質(zhì)控制）.*2)666物理層

33、：協(xié)議是水平的，服務(wù)是垂直的協(xié)議數(shù)據(jù)單元 VJ VXUZUIUR JGZG TOZ 對等層次間數(shù)據(jù)單元的傳遞服務(wù)數(shù)據(jù)單元 YJ YKXOIK JGZG TOZ 層間數(shù)據(jù)的傳遞分層的好處：各層之間相互獨立，易于實現(xiàn)和復(fù)用：多個應(yīng)用層進程同時使用下面?zhèn)鬏攲拥姆?wù)分用：傳輸層把收到的信息分別交給上面應(yīng)用層中相應(yīng)的進程 :)6 與 ;*6 的區(qū)別都有 復(fù)用和分用復(fù)用：多個應(yīng)用層進程同時使用下面?zhèn)鬏攲拥姆?wù)分用：傳輸層把收到的信息分別交給上面應(yīng)用層中相應(yīng)的進程:IV 和 JV 都檢驗 首部 數(shù)據(jù):)6 （ZXGTYSOYIUTZXUR VXUZUIUR 傳輸控制協(xié)議） 使用 :)6 的應(yīng)用層協(xié)議：93:

34、64+:.:6 ,:6面向連接 每一條 ZIV 連接只能由兩個端點 提供可靠交付 全雙工面向字節(jié)流;*6 （YKX JGZGMXXUZUIUR 用戶數(shù)據(jù)報協(xié)議）使用;*6 的應(yīng)用層協(xié)議：*49 :,:6 8/6 *.)69436 /6，流式多的通信無連接 盡最大努力交付 面向報文 首部開銷小 ZIV 報文段首部#/6 數(shù)據(jù)報首部# ( ;*6 用戶數(shù)據(jù)報首部# ( 不提供流量控制 沒有擁塞控制 兩個都是連接的事 不保證順序接受支持一對一，一對多，多對一，多對多的交互通信 優(yōu)點：首部開銷小 發(fā)送之前不需建立連接，減少時延 快速 不保證可靠交付，主機不需維持復(fù)雜的連接狀態(tài)表 無擁塞控制有利于實時應(yīng)

35、用ZIV 只支持一對一 JV 支持一對多 多對一 ip 協(xié)議定義了, 數(shù)據(jù)傳送的基本單元IP 分組及其明確的數(shù)據(jù)格式。/IP 協(xié)議的作用, 就是向傳輸層提供的 IP 數(shù)據(jù)報/分組，即將各種不同類型的 MAC 幀轉(zhuǎn)換為的 IP 數(shù)據(jù)報/分組， 并將 MAC 幀的物理地址變換為全網(wǎng)的邏輯地址（IP地址）。ipv4 和 ipv6 的區(qū)別，聯(lián)系Ipv6：更大的地址空間 擴展的地址層次 支持即插即用 更小的路由表 增加了增強的組播和對流的支持 具有更高的安全性Ipv6 只有在源結(jié)點才能分片，是端到端的，傳輸路徑中不能分片 ipv6 首部是長度必須是 8B 的整數(shù)倍, 而 IPV4 是 4B 的整數(shù)倍 增

36、加了組播功能 簡化了報文頭部 對于可選項有了更大的支持Ipv6 跟 TCP UDP ICMP IGMP 等都兼容過渡采用了：雙協(xié)議棧，隧道技術(shù)簡述數(shù)據(jù)鏈路層（1）封裝成幀：在網(wǎng)絡(luò)層傳下來的 ip 數(shù)據(jù)報的前面和后面分別添加首部和尾部，首部和如何確定 udp 可靠比對目的端是否存在(UDP 首部: 源端口, 目的端口, 長度, 檢驗和)，不存在就丟棄，并由 icmp 發(fā)送端口不可達給發(fā)送方udp 檢驗和, 檢驗首部和數(shù)據(jù)部分是否正確3 ip 的作用尾部用于幀定界（ ）透明傳輸：字符，字符填充，比特填充，編碼法（數(shù)據(jù)鏈路層成幀方法）（ ）差錯檢測 無比特差錯，主要使用 )8) *49 服務(wù)器的作用

37、與原理*49 屬于客戶 服務(wù)器模型 ;*6 協(xié)議 端 作用：把轉(zhuǎn)換為 OV 地址原理：當(dāng)某個應(yīng)用進程需要把主機名為 OV 地址時，調(diào)用程序，成為 *49 的一個客戶，把待的放在請求報文中，以 ;*6 用戶數(shù)據(jù)報方式發(fā)給本地服務(wù)器，查找后，把 OV 放在響應(yīng)報文中返回，如果本地服務(wù)器不能回答，就向其他服務(wù)器發(fā)出請求，向本地查詢時使用遞歸，向根服務(wù)器，頂級服務(wù)器，權(quán)限服務(wù)器通常使用迭代*49 迭代和遞歸的區(qū)別：遞歸：如果主機所詢問的本地服務(wù)器不知道被查詢的 OV 地址，那么本地服務(wù)器就以 *49 客戶的，向根服務(wù)器繼續(xù)發(fā)出查詢請求報文（即替該主機查詢），而不是讓該主機自己進行下一步查詢迭代：當(dāng)根服

38、務(wù)器收到本地服務(wù)器發(fā)出的迭代查詢請求報文時，要么給出所要查詢的 OV 地址，要么告訴本地服務(wù)器應(yīng)該去 哪一個服務(wù)器進行下一步的查詢 電子郵件的發(fā)送過程用戶:郵箱, 163 郵箱（1）發(fā)件人發(fā)信, 調(diào)用用戶, 以 SMTP 客戶的與發(fā)送方郵件服務(wù)器建立 TCP 連接, 使用 smtp 協(xié)議（簡單郵件傳輸協(xié)議）發(fā)給郵件.（2）發(fā)送方郵件服務(wù)器收到郵件后，以 smtp 客戶的與接收方郵件服務(wù)器建立 TCP連接，使用 smtp 發(fā)送郵件(3)收件人打算收信, 調(diào)用用戶, 以 Pop3 客戶與收件方郵件服務(wù)器建立 TCP 連接，使用 pop3 接收郵件HTTP 的持久連接和非持久連接http1.0 非持

39、久連接: 傳輸一個網(wǎng)頁元素對象, 一次 TCP 連接每請求一個文檔=傳輸文檔時間+2 倍的往返時間(一個 RTT,用于 tcp 連接, 一個用于 HTTP請求和接收文檔)http1.1 持久連接: 傳輸多個網(wǎng)頁元素對象, 一次 TCP 連接網(wǎng)服務(wù)器在發(fā)送響應(yīng)后仍保持連接，使同一個客戶和該服務(wù)器可以繼續(xù)在這條連接上傳送報文簡述網(wǎng)卡的作用: 又稱網(wǎng)絡(luò)適配器（網(wǎng)絡(luò)接口卡 NIC networkerface card）, 局域網(wǎng)中連接計算機和傳輸介質(zhì)的的接口.( 一塊網(wǎng)卡包括物理層和數(shù)據(jù)鏈路層, 每塊網(wǎng)卡有唯一 MAC 地址（物理地址）)封 封裝解封 碼 編碼譯碼 路 鏈路管理 有網(wǎng)卡的放行 并串行

40、.數(shù)據(jù)的封裝與解封：發(fā)送時將上一層交下來的數(shù)據(jù)加上首部和尾部，成為以太網(wǎng)的幀。接收時將以太網(wǎng)的幀剝?nèi)ナ撞亢臀膊?，然后送交上一層；鏈路管理：主要?CSMA/CD（Carrier Sense Multiple Acs with ColliDetection ，帶檢測的載波多路）協(xié)議的實現(xiàn)；編碼與譯碼：即曼徹斯特編碼與譯碼。進行串行/并行轉(zhuǎn)換: 網(wǎng)卡和局域網(wǎng)之間通信通過電纜或雙絞線, 以串行傳輸方式進行的。網(wǎng)卡和計算機之間通信通過計算機主板上 I/O 總線, 以并行傳輸方式進行8/6 和 596,8/6 距離向量算法 收斂速度慢特點：（ ）僅和相鄰路由器交換信息（ ）路由器交換的信息是當(dāng)前路由器知

41、道的全部信息，即自己的路由表（ ）按照固定的時間間隔交換路由信息5YVL 分布式鏈路狀態(tài)路由特點：（ ）向本自治系統(tǒng)的所有路由器發(fā)送信息，法（ ）發(fā)送的信息是與本路由器相鄰的所有路由器的鏈路狀態(tài)（本路由器與哪些路由器相鄰，以及該鏈路的度量）（ ）網(wǎng)絡(luò)層協(xié)議，不使用 ZIV 或 JV 直接使用 OV 數(shù)據(jù)報傳送（OV 數(shù)據(jù)報協(xié)議字段首部 ）（ ）只有當(dāng)鏈路狀態(tài)發(fā)生變化時，才用法。更新過程收斂的快 通信的同步異步同步：通信雙方必須先建立同步，即雙方的時鐘要調(diào)到同一個頻率，收發(fā)雙方不停的發(fā)送和接收連續(xù)的同步比特流異步：所發(fā)送的字符之間的時間間隔可以是任意的，但接收方必須做好時刻接收的準(zhǔn)備 碼元傳輸率

42、 ：時間內(nèi)傳輸?shù)拇a元個數(shù)（脈沖次數(shù) 信號變化次數(shù)）信息傳輸速率：時間內(nèi)傳輸?shù)亩M制碼元個數(shù) 基帶頻帶寬帶傳輸基帶：不經(jīng)調(diào)制就在信道上直接傳輸，通常用于局域網(wǎng)頻帶：用數(shù)字信號對特定頻率的載波進行調(diào)制，將其變成適合于傳送的信號在傳輸（遠距離傳輸 或 無線傳輸）寬帶：借助頻帶傳輸，將鏈路容量分解為兩個或多個信道，每個信道可以攜帶不同的信號寬帶中所有的信道可以同時互不干擾的發(fā)送信號 NH 路由器 交換機 網(wǎng)橋等都作用 ）物理層：（ ）中繼器（轉(zhuǎn)發(fā)器）：將信號整形并放大再轉(zhuǎn)發(fā)出去，消除信號因為某些原因造成的失真和衰減，使信號的波形的強度達到要求（將衰弱的數(shù)字信號整形再生 （ ）集線器（多個端口的中繼器

43、NH ）整形放大傳送到其他端口（屬于同一個域） ）數(shù)據(jù)鏈路層：（ ）網(wǎng)橋：連接以太網(wǎng)，成為一個覆蓋范圍更大的以太網(wǎng)，原來每個以太網(wǎng)就可以成為一個網(wǎng)段（碰撞域）特點：網(wǎng)橋必須具備尋址和路徑選擇能力，以確定幀的傳輸方向從源網(wǎng)絡(luò)接收幀，以目的網(wǎng)絡(luò)的介質(zhì)控制協(xié)議向目的地轉(zhuǎn)發(fā)該幀網(wǎng)橋在不同或相同類型的 24 之間都可以存貯并轉(zhuǎn)發(fā)幀，必要時還進行協(xié)議轉(zhuǎn)換優(yōu)點：過濾通信量 擴大物理范圍 可使用不同的物理層 可互聯(lián)不同類型的局域網(wǎng) 提高了可靠性 性能得到改善缺點：增加時延 3) 層沒有流量控制功能 網(wǎng)橋只適合于用戶數(shù)不多和通信量不大的局域網(wǎng)，否則會因為過多廣播信息產(chǎn)生網(wǎng)絡(luò)擁塞（ ）局域網(wǎng)（以太網(wǎng)）交換機：多端

44、口的網(wǎng)橋：在某一時刻可以執(zhí)行多個幀的轉(zhuǎn)發(fā)操作（檢測從以太網(wǎng)端口來的數(shù)據(jù)幀的源和目的地址的 3) 介質(zhì)層 地址，然后與的動態(tài)查找表進行比較，若數(shù)據(jù)幀的 3) 地址不在查找表中，則將該地址加入查找表中，并將數(shù)據(jù)幀發(fā)送給相應(yīng)的目的端口）特點：全雙工 即插即用 獨占帶寬 的作用.:6 是無狀態(tài)的，同一個用戶多次時，服務(wù)器并不記得曾經(jīng)過的這個用戶，也不記得為該客戶服務(wù)過多少次。稱為 .:6 的無狀態(tài)特性，使得服務(wù)器更容易支持大量并發(fā)的 .:6 請求。在實際應(yīng)用中，通常使用加數(shù)據(jù)庫的方式來用戶的活動。是一個存貯在用戶主機的文本文件，=+( 服務(wù)器根據(jù)就能從數(shù)據(jù)庫中查詢到該用戶的活動，進而執(zhí)行個性化的活動。

45、 介質(zhì)控制 ）信道劃分介質(zhì)控制多路復(fù)用：通過在一條介質(zhì)上同時攜帶多個傳輸信號的方法來提高傳輸系統(tǒng)的利用率頻分多路復(fù)用（,*3）：將基帶信號調(diào)到不同的頻率載波上再進行疊加形成一個復(fù)合信號的多路復(fù)用技術(shù)（充分利用的傳輸介質(zhì)的帶寬，效率高，系統(tǒng)成熟，實現(xiàn)容易）時分多路復(fù)用（:*3）：將一條物理信路按時間分成若干個時間片，輪流的分配給多個信號使用波分多路復(fù)用（=*3）：光的頻分多路復(fù)用碼分多路復(fù)用（)*3）：不同的編碼來區(qū)分各路原始信號的一種復(fù)用方式 ）隨機介質(zhì)控制25. 協(xié)議 純 25. 當(dāng)網(wǎng)絡(luò)中的任何一個節(jié)點需要發(fā)送數(shù)據(jù)時，可以不進行任何檢測就發(fā)送數(shù)據(jù)，如果早一段時間內(nèi)沒有收到確認(rèn)，該站點就認(rèn)為傳

46、輸過程發(fā)生了，發(fā)送站點需要等待一段時間再發(fā)送數(shù)據(jù)，直到成功時隙 25. 把所有各站的時間都同步起來，分 成一段段等長的時隙，規(guī)定只能在每個時隙開始時才能發(fā)送一個幀 N)93 協(xié)議：在發(fā)送前偵聽一下共用的信道，信道空閑后再發(fā)送)93 )*（總線型 半雙工）先聽后發(fā) 邊聽邊發(fā)停發(fā) 隨機重發(fā))93 ) 無線 碰撞避免 ）輪詢介質(zhì)控制：令牌傳遞協(xié)議 :)6 /6 協(xié)議族中的加密協(xié)議 應(yīng)用層：Y NZZV，YYN，YYR，VMV；傳輸層：YYR，ZRY；網(wǎng)絡(luò)層：OVYKI；網(wǎng)絡(luò)接口層：VVZV 客戶機服務(wù)器（ITZ YKXKX ) 9）：總是有一個打開的服務(wù)器，服務(wù)于許多來自其他客戶機的主機請求 客戶機

47、一般不需要特殊的硬件和復(fù)雜的操作系統(tǒng)，而服務(wù)器上運行的軟件則是專門用來提供某種服務(wù)的程序，可同時處理多個和本地用戶的要求6 6（VKKX ZU VKKX）模型：每個結(jié)點即作為客戶其他節(jié)點的資源，也作為服務(wù)器提供資源給其他節(jié)點 VVV 和 .*2)666：串行鏈路通信的面向字節(jié)的協(xié)議 .*2)：面向比特通過撥號或?qū)＞€方式建立點對點連接發(fā)送數(shù)據(jù)，使其成為各種主機，網(wǎng)橋，路由器之間連接的一種共同解決方案。包括： 鏈路控制協(xié)議 2)6：一種擴展鏈路控制協(xié)議，用于建立，配置，測試和管理數(shù)據(jù)鏈路。 ）網(wǎng)絡(luò)控制協(xié)議 4)6：666 允許同時采用多種網(wǎng)絡(luò)層協(xié)議 ）一個將 /6 數(shù)據(jù)報封裝到串行鏈路的方法。 電

48、路交換和分組交換的聯(lián)系與區(qū)別電路交換： ） 基于位置，即在某一位置的比特經(jīng)交換后變更到另一個位置上。 ） 面向連接的電路交換必定是面向連接的，但面向連接的卻不一定是電路交換。 ） 通話過始終占用端到端的固定傳輸帶寬。分組交換： ） 采用轉(zhuǎn)發(fā)技術(shù) ）基于標(biāo)記的，將欲發(fā)送的整塊數(shù)據(jù)稱為報文 SKYYGMK ，將較長的報文劃分為一個個更小等長數(shù)據(jù)段（比如 HOZ） ，在每個數(shù)據(jù)段前面加上首部 NKGJKX ，后就一個分組 VGIQKZ ，分組又稱為包，分組的頭部稱為包頭。分組首部包含了目的地址和源地址等重要的控制信息，每一個分組才能在分組交換網(wǎng)中獨立地選擇路由。 ）無連接的 解決 OV 地址用完分類

49、的 /6 地址a網(wǎng)絡(luò)號$主機號$c分類的劃分a網(wǎng)絡(luò)號$子網(wǎng)號$主機號$c構(gòu)造超網(wǎng)a網(wǎng)絡(luò)前綴$主機號$cOV 4: 技術(shù)：將網(wǎng)絡(luò)的 /6 地址轉(zhuǎn)換為有效的外部使用的全球 OV 地址，使得整個網(wǎng)只需要一個 /6 地址就可以與因特網(wǎng)簡述 59/ 模型與 :)6 /6 模型不同” 網(wǎng)傳 簽個 協(xié)議 山雞 也可以變鳳凰 不用再 OK L POK 了 一個有 層 一個有 層一個有 個重要概念 協(xié)議服務(wù)接口 OK L POK 一個沒有區(qū)分協(xié)議服務(wù)接口一個產(chǎn)生在協(xié)議發(fā)明之前 一個產(chǎn)生在協(xié)議發(fā)生之后一個網(wǎng)絡(luò)層有面向連接和無連接, 一個網(wǎng)絡(luò)層僅有無連接一個傳輸層僅有面向連接, 一個傳輸層有面向連接和無連接奇偶校驗

50、區(qū)別奇偶都是由 n-1 位信息元和 1 位校驗元組成. 如果是奇, 在附加上一個校驗元之后, 碼長為 n 的碼字中”1”的個數(shù)為奇數(shù). 如果是偶, 在附加一個校驗元之后, 碼長為 n 的碼字中”1”的個數(shù)為偶數(shù)操作系統(tǒng)9 虛擬內(nèi)存 ：基于局部性原理，可以將程序的一部分裝入內(nèi)存，而將其余部分留在外存。程序運行時, 當(dāng)所的信息不在內(nèi)存時，可以將暫時不用的信息調(diào)出內(nèi)存, 將所需部分調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行程序，這樣，系統(tǒng)好像為用戶提供了一個比實際內(nèi)存大得多的器，稱為虛擬器。虛擬器特征：（1）多次性（2）對換性（3）虛擬性(多次對換達到虛擬)虛擬內(nèi)存實現(xiàn)方式：請求分頁管理，請求分段管理，請求段頁式管理頁

51、面置換算法：FLOC 廢棉絮要置換掉頁面分配策略：固定分配局部置換 可變分配全局置換 可變分配局部置換11 I/O 控制方式（1）程序直接控制（2）中斷驅(qū)動：允許 i/o 設(shè)備主動打斷 cpu 的運行并請求服務(wù)，解放 cpu，使得其向 I/O控制器發(fā)送讀命令后可以繼續(xù)做其他工作（3）DMA：在 i/o 和內(nèi)存之間直接開辟了一條通路，傳送數(shù)據(jù)塊（4）通道控制方式：把一個數(shù)據(jù)塊改為一組數(shù)據(jù)塊12 磁盤調(diào)度算法（1）FCFS( come service )先來先服務(wù)（2）SSTF (short seek time)最短尋道時間優(yōu)先（3）SCAN 掃描算法 電梯算法（4）C-SCAN 循環(huán)掃描13 系

52、統(tǒng)調(diào)用：用戶在程序中調(diào)用操作系統(tǒng)所提供的一些子功能。系統(tǒng)中的共享資源都由操作系統(tǒng)掌管，因此在用戶程序中，凡是與資源相關(guān)的操作（分配，進行 I/O 傳輸以及管理文件），都須通過系統(tǒng)調(diào)用方式向操作系統(tǒng)提出服務(wù)請求，并由操作系統(tǒng)代為完成.系統(tǒng)調(diào)用過程：操作系統(tǒng)接收到系統(tǒng)調(diào)用請求后，會讓處理器進入內(nèi)核模式, 而當(dāng)處理完系統(tǒng)調(diào)用內(nèi)容后，操作系統(tǒng)會讓處理器返回用戶模式，來執(zhí)行用戶代碼態(tài): 操作系統(tǒng)關(guān)系程序執(zhí)行時, 機器所處的狀態(tài), 有較高的, 可以執(zhí)行包括指令的一起指令,所有的寄存器和區(qū)用戶態(tài): 用戶程序執(zhí)行時, 機器所處的狀態(tài), 有較低的, 只能執(zhí)行規(guī)定的指令,指定的寄存器和區(qū)14 中斷過程中斷請求 中

53、斷響應(yīng) 斷點保護 執(zhí)行中斷服務(wù)程序 斷點恢復(fù) 中斷返回17 中斷隱指令(即硬件機制)：CPU 在中斷周期內(nèi)由硬件自動完成的一條指令，其功能包括關(guān)中斷, 保存 PC(斷點)，尋找中斷服務(wù)程序地址并送至 pc.系統(tǒng)調(diào)用與子程序調(diào)用區(qū)別:系統(tǒng)調(diào)用是在態(tài)(即管態(tài))下執(zhí)行，需從用戶態(tài)轉(zhuǎn)換為態(tài)，而子程序調(diào)用在用戶態(tài)(即目態(tài))下執(zhí)行的,沒有狀態(tài)變化.中斷和子程序調(diào)用的區(qū)別:硬件+處理過程處理過程有調(diào)用程序根據(jù)尋址方式得到保存 PC,通用寄存器沒有狀態(tài)變化地址:保存環(huán)境:進程狀態(tài):有中斷隱指令根據(jù)中斷向量得到,保存 PC, PSW,通用寄存器,從用戶態(tài)轉(zhuǎn)換為和心態(tài),中斷和系統(tǒng)調(diào)用的區(qū)別 中斷是由外設(shè)產(chǎn)生 無意

54、的的系統(tǒng)調(diào)用是由應(yīng)用程序請求操作系統(tǒng)提供服務(wù)產(chǎn)生有意的 主動的系統(tǒng)調(diào)用運行在態(tài) 其通過中斷機制 來完后用戶態(tài)到態(tài)的轉(zhuǎn)換 程序方式：靜態(tài) 裝入時動態(tài) 運行時動態(tài) 程序裝入：絕對裝入 可重定位裝入 動態(tài)運行裝入 內(nèi)存分配方式管理方法 單一分配 固定分區(qū)分配 動態(tài)分區(qū)分配 （ ）首次適應(yīng) （ ）循環(huán)首次適應(yīng) 最佳適應(yīng)適應(yīng) 操作系統(tǒng)的層次結(jié)構(gòu) 硬件層操作系統(tǒng)層實用程序?qū)樱河梢唤M操作系統(tǒng)控制下的實用程序組成應(yīng)用層 數(shù)據(jù)庫系統(tǒng)，操作系統(tǒng)，應(yīng)用之間關(guān)系 分頁和分段的區(qū)別： 頁是信息的物理，是系統(tǒng)的需要；段則是信息的邏輯，是為了滿足用戶的需要 頁的大小固定且有系統(tǒng)決定，而段長度可變，取決于用戶編寫的程序 分頁

55、的作業(yè)地址空間一維，單一線性地址空間；分段的作業(yè)地址空間是二維的，要給出和段內(nèi)地址 管程：一組數(shù)據(jù)以及定義在這組數(shù)據(jù)之上對這組數(shù)據(jù)的操作組成的模塊，這組操作能初始化并改變管的數(shù)據(jù)和同步進程。組成： ）局部于管程的共享結(jié)構(gòu)數(shù)據(jù)說明 ）對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程3）對局部于管程的共享數(shù)據(jù)設(shè)置初始值的語句特性：局部于管程的數(shù)據(jù)只能被局部于管程內(nèi)的過程所一個進程只能通過調(diào)用管程內(nèi)的過程才能進入管程共享數(shù)據(jù)每次僅允許一個進程在管程內(nèi)執(zhí)行某個過程。數(shù)據(jù)庫事務(wù)：一個單元的工作，要么全完成，要么全不做。2 ACID:原子性（Atomicity）整個事務(wù)中的所有操作，要么全部完成，要么全部不完成，不可能停留

56、在某個中間環(huán)節(jié)一致性（consistency）在事務(wù)開始之前和事務(wù)結(jié)束之后，數(shù)據(jù)庫的完整性約束沒有被破壞性(isolation)：兩個事務(wù)的執(zhí)行是互不干擾的，一個事務(wù)不可能看到其他事務(wù)運行時，中間某一刻的數(shù)據(jù)持久性(durablity)：在事務(wù)完成以后，該對數(shù)據(jù)庫所做的更改便持久的保存在數(shù)據(jù)庫中，并不會回滾。4 數(shù)據(jù)庫的 armstrong 定理及其應(yīng)用從已知的一些函數(shù)依賴，可以推導(dǎo)出另外一些函數(shù)依賴，這就需要一系列推理規(guī)則。這些規(guī)則常被稱作“Armstrong 公理設(shè) U 是關(guān)系模式 R 的屬性集，F(xiàn) 是R 上成立的只涉及 U 中屬性的函數(shù)依賴集。函數(shù)依賴的推理規(guī)則有以下三條：1）自反律：若

57、屬性集 Y 包含于屬性集 X，屬性集 X 包含于U，則 XY 在 R 上成立。(此處 XY 是平凡函數(shù)依賴)2）增廣律：若 XY 在R 上成立，且屬性集 Z 包含于屬性集 U，則 XZYZ 在 R 上成立。3）傳遞律：若 XY 和 YZ 在 R 上成立，則 X Z 在 R 上成立。Armstrong 公理系統(tǒng)的有效性和完備性Armstrong 公理系統(tǒng)的有效性指的是：由 R 出發(fā)根據(jù) Armstrong 公理系統(tǒng)推導(dǎo)出來的每一個函數(shù)依賴一定是 R 所邏輯蘊含的函數(shù)依賴。Armstrong 公理系統(tǒng)的完備性指的是：對于 R 所邏輯蘊含的每一函數(shù)依賴，必定可以由R 出發(fā)根據(jù) Armstrong 公

58、理系統(tǒng)推導(dǎo)出來。根據(jù)上面三條推理規(guī)則，又可推出下面三條推理規(guī)則： 合并規(guī)則：若 XY，XZ，則 XYZ 為F 所蘊含； 偽傳遞規(guī)則：若 XY，WYZ，則 XWZ 為 F 所蘊含； 分解規(guī)則：若 XY，ZY，則 XZ 為 F 所蘊含。5數(shù)據(jù)庫中的索引索引是對數(shù)據(jù)庫表中,一列或多列的值進行排序的一種結(jié)構(gòu)主鍵: 一個列或多列的組合，其值能唯一地標(biāo)識表中的每一行.數(shù)據(jù)庫索引分為，唯一索引、主鍵索引和索引。聚簇索引 按數(shù)據(jù)存放的物理位置為順序的唯一索引, 不允許其中任何兩行具有相同索引值的索引。主鍵索引(默認(rèn)索引)數(shù)據(jù)庫主鍵，一個列或多列的組合，其值能唯一地標(biāo)識表中的每一行. 主鍵索引是唯一索引的特定類

59、型。該索引要求主鍵中的每個值都唯一索引 表中行的物理順序與鍵值的邏輯（索引）順序相同。(表中行的物理順序與鍵值的邏輯順序不匹配)。與非索引相比，索引通常提供更快的數(shù)據(jù)速度優(yōu)點： 加快數(shù)據(jù)的檢索速度缺點：創(chuàng)建和索引要耗費時間, 且索引占物理空間 3 數(shù)據(jù)庫模型：關(guān)系模型 層次模型 網(wǎng)狀模型6 數(shù)據(jù)庫的模式 內(nèi)模式 外模式 模式1）模式 模式又稱概念模式或邏輯模式，對應(yīng)于概念級。它是由數(shù)據(jù)庫設(shè)計者綜合所有用戶的數(shù)據(jù)，按照的觀點構(gòu)造的全局邏輯結(jié)構(gòu)，是對數(shù)據(jù)庫中全部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的總?cè)绾谓ㄖ麈I:體描述，是所有用戶的公共數(shù)據(jù)視圖 全局視圖 ）外模式 外模式又稱子模式，對應(yīng)于用戶級。它是某個或某幾個

60、用戶所看到的數(shù)據(jù)庫的數(shù)據(jù)視圖，是與某一應(yīng)用有關(guān)的數(shù)據(jù)的邏輯表示。 ）內(nèi)模式 內(nèi)模式又稱模式，對應(yīng)于物理級，它是數(shù)據(jù)庫中全體數(shù)據(jù)的表示或底層描述，是數(shù)據(jù)庫最低一級的邏輯描述，它描述了數(shù)據(jù)在介質(zhì)上的方式翱物理結(jié)構(gòu)，對應(yīng)著實際在外介質(zhì)上的數(shù)據(jù)庫 關(guān)系數(shù)據(jù)庫都有那些操作 特點是什么% 查詢 選擇、投影、連接、除、并、交、差 數(shù)據(jù)更新、刪除、修改 關(guān)系操作的特點 集合操作方式 即操作的對象和結(jié)果都是集合。 數(shù)據(jù)庫的幾個鍵，幾個碼主碼：主關(guān)鍵字 VXOSGX_ QK_ 是表中的一個或多個字段，它的值用于惟一地標(biāo)識表中的某一條。22. 范式(NF Normal Form): 一張數(shù)據(jù)表中的表結(jié)構(gòu)所符合的某種