1．棧和隊列Queue：
后進先出
先進先出

循環隊列 空隊列 隊列滿了 元素入隊、出隊
隊列鏈式存儲
串：字符串 存儲結構（順序存儲結構、鏈式存儲）

2．數組：
(1)定長線行表 維數 拓展，即線性表中的元素又是一個線性表
N 維數組是一種“同構”的數據結構，每個元素 類型相同、結構一致。

(2)數組結構特點：
1.數目固定 定義數組結構，不再元素個數的增減變化
2.數據元素具有相同的類型
3．下標關系具有上下界的約束且下標有序
4．兩個基本運算：
①　存取相應的數據元素
②　修改相應的數據元素中某個數據項的值
3．矩陣：
在數據結構中，目的為了節省存儲控件的情況下使矩陣的各種運算能高效地執行
稀疏矩陣：值相同的元素或0元素在矩陣中的分布有一定的規律，則稱此類為特殊矩陣，否則稱其為稀疏矩陣。

4．廣義表：
由0個單素表或者多個子表組成的而有限序列
查找、插入、刪除等操作
基本操作：取表頭，取表尾

5．樹：
非線性結構，一個數據元素有兩個或兩個以上的而直接后繼元素，描述客觀世界中廣泛存在的層次結構關系
基本概念：
雙親、孩子和兄弟
結點的度
葉子結點
內部結點
結點的層次
樹的高度
有序（無序）樹

樹的存儲結構：雙親、孩子、孩子兄弟表示法

樹和森林遍歷：
先根、后根遍歷
先序、中序遍歷森林

樹、森林和二叉樹的相互轉換：
任何一個森林或一棵樹可以對應表示為一顆二叉樹，而任何一顆二叉樹也可能對應到一個森林或一棵樹上。

6．遍歷二叉樹：
訪問特點是無論按照哪種次序遍歷，對于含有n個結點的二叉樹，遍歷算法的時間復雜度都是O（n）。
過程：實質上是按一定的規則將樹中的結點排程一個線性序列的過程，遍歷得到的是樹中結點的一個線性序列。

7．線索二叉樹：
實質是對一個非線性結構進行線性化的過程
左孩子，右孩子

8．最優二叉樹：哈夫曼樹，一類帶權路徑長度最短的書
9．哈夫曼編碼：
長編碼：對每個字符編制相同長度的二進制的統稱（缺點電文的碼串過長，不利于提高通信效率，因此希望縮短碼串的總長度）

10．死鎖：產生、解決的方式（預防，避免，檢測，解除）
11．線程：
三個狀態：就緒，運行和阻塞
兩個類型：用戶級線程，內核支持線程
12．存儲器：
13．虛擬地址，地址空間和存儲空間
14．分區存儲管理：固定分區，可變分區（四個算法：最佳適應法，最差適應法，首次適應法，循環首次適應法），可重定位分區。

15．分頁存儲管理：
純分頁存儲管理（分頁管理，地址結構，頁表）
16．快表：
地址映射機構中新增一個小容量的聯想存儲器，聯想存儲器由一組高速存儲器組成，稱為快表。

17．軟件過程模型：
瀑布模型（需求分析-設計-編碼-測試-運行與維護）

18．需求分析：
功能需求、性能需求、用戶或人的因素、環境需求、界面需求、文檔需求、資源使用需求、安全保密要求、可靠性要求、軟件成本消耗和開發進度需求、其他非功能性要求。
系統測試：
1.單元測試：
(1)模塊接口
(2)測試模塊的輸入參數的形參在個數、屬性和單位上是否一致
(3)調用其他模塊，所給出的實際采納數和被調參數在個數、屬性是否一致
(4)調用標準函數時，所用的參數在屬性、數目和順序上是否正確
(5)全局變量在各模塊中的定義和用法是否一致
(6)輸入是否僅改變了形式參數
(7)開/關的語句是否正確
(8)規定的I/O格式是否與輸入/輸出語句一致
(9)在使用文件之前是否已經打開文件或使用文件之后是否已經關閉文件

2.局部數據結構（常見錯誤）：
(1)變量的說明是否合適
(2)是否使用了尚未賦值或尚未初始化的變量
(3)變量的初始值或默認值是否正確
(4)變量名是否有錯（例如拼寫錯）

3.重要執行路徑：計算方面的錯誤，比較和控制流的錯誤，出錯處理，邊界條件

19．測試web應用：
質量維度（內容、功能、結構、可用性、導航性、性能、兼容性、安全性）

20．黑盒子測試：
也稱為功能測試
①　是否有錯誤的功能或遺漏的功能
②　界面是否有無？輸入是否正確接收？輸入是否正確？
③　是否有數據結構或外部數據庫訪問錯誤？
④　性能是否能夠接受？
⑤　是否有初始化或終止性錯誤？

測試技術的劃分：等價類劃分

調試方法：試探法，回溯法，對分查找法，歸納法，演繹法

21．系統維護應執行步驟：
①　提出維護或修改要求
②　領導審查并作出答復
③　領導分配任務，維護人員執行修改
④　驗收維護成果并登記修改信息

22．項目管理：
(1)明確目標及過程
(2)保持動力
(3)跟蹤進展
(4)做出明智的決策
(5)進行事后分析

23．進度管理：劃分，相互依賴，時間分配，工作量確認，確定責任，明確輸出結果，確認里程碑

24．甘特圖：

25．有向圖：

26．軟件配置項：
①　系統規格說明書
②　軟件項目實施計劃
③　軟件需求規格說明書
④　設計規格說明書（數據設計、體系結構設計、模塊設計、接口設計、對象描述（使用面向對象技術時））
⑤　源代碼清單
⑥　測試計劃和過程、測試用例和測試結果記錄
⑦　操作和安裝手冊
⑧　可執行程序（可執行程序模塊、連接模塊）
⑨　數據庫描述（模式和文件結果、初始內容）
⑩　用戶手冊
?　維護文檔（軟件問題報告、維護請求、工程變更次序）
?　軟件工程標準
?　項目開發小結

27．軟件質量：

28．面向對象軟件測試：
算法層，類層，模板層，系統層

29．用例圖：

30．交互圖：用于對系統的動態方面進行建模

窮舉算法：
題目：從67**8 中找出能整除67 和78的數
For(let i = 67008; i < 67998; i++){
If(i % 67 == 0 && i % 78 == 0)
Console.log(i);
}

31．算法設計與分析：
算法特性：有窮性，去定性，可行性，輸入，輸出

32．算法分析
算法的表示：自然語言，流程圖，程序設計語言，偽代碼
時間復雜度
空間復雜度

33．遞歸樹：

34．遞歸兩要素：邊界條件（遞歸出口），遞歸模式（遞歸體）
35．階乘函數
36．分治法：
與遞歸像一堆孿生兄弟
經常出現在算法設計中，由此產生許多高效算法
設計思想： 將一個難以直接解決的大問題分解成一些規模較小的相同問題，以便各個擊破，分而治之。
分治算法在每一層遞歸上有三個步驟： 分解，求解，合并
歸并排序：將待排序的元素分成大致相同的兩個子序列，分別對這兩個子序列進行排序，最終將分好序的自序合并為所要求的序列。

37．動態規劃算法：
與分治算法類似，但經過分解得到的子問題往往不是獨立的，通常用于求解具有某種最優質的的問題。在這類問題中，可能會有許多可行解，每個解都對應一個值，我們希望找到具有最優值（最大值最小值）的那個解。
設計步驟：
(1)找出最優解的性質，并刻畫其結構特征
(2)遞歸地定義最優解的值
(3)以自底向上的方式計算出最優解
(4)根據計算最優值時得到的信息，構造一個最優解

動態規劃法是一個非常有效的算法設計技術。兩大性質：最優子結構，重疊子問題

38．貪心算法：最簡單

解決最優化問題，局部最優化

39．回溯法：
通用的解題法。可以系統地搜索一個問題的所有解或者任意解
步驟：
(1)針對所給問題，定義問題的解空間
(2)確定易于搜索的解空間結構
(3)以深度優先的方式搜索解空間

兩種算法框架：遞歸和非遞歸

回溯法的界限函數：（回溯法的可新問題，也是難問題）
問題的解空間往往很大，為了有效滴進行搜索，需要再搜索的過程中對某些結點進行剪枝，而對哪些結點進行剪枝，需要設計限界函數來判斷。

40．分支限界法：
求解目標是找出滿足約束條件的一個解
如何設計銜接函數來有效的減小搜索空間是應用分支限界法要考慮的問題
類型：隊列式分支限界法、優先隊列分支限界法

41．概率算法：
(1)基本特征：
①　輸入包括兩部分：一部分是原問題的輸入，另一部分是一共供算法進行隨機選擇的隨機數序列
②　運行中，包括一處或多處隨機選擇，根據隨機值來決定算法的運行路徑
③　結果不能保證一定是正確的，但能限制其出錯概率
④　在不同的運行過程中，對于相同的輸入實例可以有不同額結果，因此對于相同的輸入實例，概率算法的執行時間可能不同

(2)四大類：
①　數值概率算法：數值問題
②　蒙特卡羅算法：求問題的精確解
③　拉斯維加斯算法：不會得到不正確的解
④　舍伍德算法：總能求得問題的一個解，切所求得的解總是正確

42．近似算法：
解決難解問題
基本思想是放棄求最優解，近似最優解代替最優解
衡量標準：算法的時間復雜度、解的近似程度

43．數據挖掘算法
功能：分類、回歸、關聯規則和聚類

44．數據模型：
層次模型，網狀模型，關系模型和面向對象模型

45．關系代數
關系數據庫

46．屬性：
描述一個事務常常取若干特征來表示，這些特征稱為屬性

47．關系的完整性分類：
實體完整性、參照完整性（引用完整性）和用戶定義完整性

48．關系代數運算符：
集合運算符、專門的關系運算符、算數比較符合邏輯運算符

49．5種基本的關系代數運算：
并、差、笛卡爾積、投影和選擇

拓展的關系代數運算：
選擇、投影、連接（0連接、等值連接和自然連接）、觸發、廣義笛卡爾積和外連接

50．數據庫技術基礎

(1)聚集函數：

(2)關系型數據庫設計：
設計滿足適當范式的模式，可以通過判斷分解后的模式達到幾范式來評價模式規范化的程度。
(3)1NF（第一范式）：
若關系模式R的誒個分量是不可再分的數據項，則關系模式R屬于第一范式。
問題：
①　冗余度大
②　引起修改操作的不一致性
③　插入異常
④　刪除異常
(4)2NF（第二范式）：
當1NF消除了非主屬性對碼的部分函數依賴，則稱為2NF
(5)3NF（第三范式）：
2NF消除了非主屬性對碼的傳遞函數依賴

51．數據庫備份與恢復：
①　故障類型：事務內部故障、系統故障、介質故障及計算機病毒。
②　備份方法：簡歷數據冗余（重復存儲），進行數據轉儲（靜態轉儲、海量轉儲和增量轉儲、日志文件）和登記日志文件

52．并發控制：
(1)帶來的數據不一致性有三類：丟失修改、不可重復度和讀臟數據
(2)并發控制技術：
①　封鎖：
排它鎖。（若事務T對數據對象A加上X鎖，則只允許T讀取和修改A，其他事務都不能再對A加任何類型的鎖，知道T釋放A上的鎖）
共享鎖。（若事務T對數據對象A加上S鎖，則只允許T讀取A，但不能修改A，其他事務只能再對A加S鎖，知道T釋放A上的S鎖。這就保證了其他事務讀A，但在T釋放A上的S鎖不能對A進行任何修改）。
②　三級封鎖協議：防止丟失修改和不讀“臟”數據歪，還進一步防止不可重復度
③　活鎖與死鎖：活鎖-永遠等待鎖釋放，死鎖-兩個以上的事務分別請求封鎖對方已經封鎖的數據，導致長期等待而無法繼續運行下去的現象。

53．并發調度的可串行性：
多個事務的并發執行是整錯的，當且僅當其結果與某一次序串行滴執行他們時的結果相同，稱這種調度策略是可串行化的調度。

54．兩端分鎖協議：
事務必須分兩個階段對數據項枷鎖和解鎖。
即事務分兩個階段：第一，獲得封鎖，不能釋放。第二階段是蜂房封鎖，但不能申請

55．封鎖的粒度：
封鎖對象的大小。
封鎖的對象：邏輯單元（如屬性、元組、關系、索引項、整個索引甚至整個數據庫），也可以是物理單元（如數據頁或索引頁）

網絡與信息安全基礎知識
56．計算機網絡的主要功能：
①　數據通信
②　資源共享
③　負載均衡：
④　當網絡中的某臺計算機任務過重時，可將任務分派給其他空閑的多臺計算機，使多臺計算機相互協作，均衡負載，共同完成任務。
⑤　高可靠性： 備用機，解決計算機出現故障而導致系統癱瘓的現象，從而大提高了系統的可靠性

57．計算機網絡的分類：
通信距離：廣域網、局域網和城域網
信息交換方式：電路交換網、分組交換網和總和交換網
網絡拓撲結構：星型網、樹形網和總線網
通訊截止：雙絞線網、同軸電纜網、光纖網和衛星網
傳輸帶寬：基帶網和寬帶網
使用范圍：公用網和專用網
速率：高速網、中速網和低速網
通信傳播：廣播式和點到點式

局域網：
①　傳輸距離有限
②　傳輸速度較高
③　數據傳輸可靠，誤碼率低
④　拓撲結構簡單、簡介，大多采用總線、星線和環型等，系統容易配置和管理。網上計算機一般采用多路控制訪問技術或令牌技術訪問信道。
⑤　網絡的控制一般趨向于分布式，從而減少對某個結點的依賴，避免并減小了一個結點故障對整個網絡的影響。
⑥　網絡歸單一組織鎖擁有和使用，不受任何公共網絡管理機構得到規定約束，容易進行設備的更新和新技術的應用，以不斷增強網絡功能。

58．城域網：
規模介于局域網和廣域網的一種較大范圍的高速網絡，一般覆蓋臨近的多個單位和城市，從而為介入網絡的企業、機關、公司及社會單位提供文字、聲音和圖像的集成服務。城域網規范由IEEE802.6協議定義。

59．廣域網：
①　又稱遠程網，覆蓋范圍廣、傳輸速率相對較低、以數據通信網誒主要目的地額數據通信網。
②　主要特點：
③　分布范圍廣
④　數據傳輸率低
⑤　數據傳輸的可靠性隨著傳輸介質的不同而不同
⑥　借用傳統的公共傳輸網來實現（因為單獨建造一個廣域網極其昂貴）
⑦　拓撲結構較為復雜，大多采用“分布式網絡”

60．網絡的拓撲結構：
①　總星線結構
②　星型結構
③　環形結構
④　樹形結構
⑤　分布式結構

61．ISO/OSI網絡體系結構：
①　物理層
②　數據鏈路層
③　網絡層傳輸層
④　會話層
⑤　表示層
⑥　應用層

特性：
A.異構系統互連的分層結構
B.提供了控制互連系統交互規則的標準框架
C.定義了一種抽象結構，而并非具體實現的描述
D.不同系統上相同層的實體稱為同等層實體
E.同等層實體之間的通信由改層的協議管理
F.相鄰層間的接口通信由該層的協議管理
G.相鄰層間的接口定義了原語操作和底層向高層提供的服務
H.鎖提供的公共服務是面向連接到或無連接的數據服務
I.直接的數據傳送僅在最低層實現
J.每層完成所定義的功能，修改本層的功能并不影響其他層

OSI/RM 1~3層 負責通信子網層 5~7層 資源子網層 傳輸層起著銜接上、下層的作用

62．互連設備：
物理層：中繼器和集線器
數據鏈路層：網橋和交換機
網絡層：路由器
應用層：網關

63．網絡的傳輸介質：
有線介質：雙絞線、同軸電纜
無線介質：微波、紅外線和衛星通信等

64．組建網絡：
服務器（server核心）
客戶端（client 用戶工作站）
網絡設備：硬件設備，如網卡，收發器、中繼器、集線器、網橋和路由器等
通信介質：數據的傳輸媒體
網絡軟件：底層協議軟件，網絡操作系統NOS等

65．TCP/IP 協議族：
Internet的核心協議

主要特性：
①　邏輯編址
②　路由選擇
③　域名解析
④　錯誤檢測和流量控制

66．TCP/IP分層模型

TCP/IP分層模型： 應用層、傳輸層、網絡層和網絡接口層

67．傳輸層協議–TCP：
TCP/IP協議族中最中最重要協議之一
在IP提供的不可靠數據服務的基礎上為應用程序提供了一個可靠的、面向連接的、全雙工的數據傳輸服務
三次握手確認簡歷和管理是否成功

68．傳輸層協議—UDP：
用戶數據報協議：不可靠的、無連接的協議，可以保證應用程序進程間的通信。
網絡十分可靠的情況下，則采用UDP，通信量的浪費就會很小

69．應用層協議：
NFS、Telnet、SMTP、DNS、SNMP和FTP等

70．域名：
用戶所在主機的名字或地址。
域名格式：由若干部分組成，每個部分又稱子域名，之間用“.”分開
一個完整、通用的層次性主機域名組才能：計算機主機名，本地名，組名，最高層域名（www.baidu.com）

71．IP地址：
Internet地址是按名字來描述，這種地址表示方式易于理解和記憶
主機IP地址來唯一標識
每個IP由4個小于256的數字組成

72．域名服務
DNS是一種分布式地址信息數據庫熊，服務器包含整個數據庫的某部分信息，并供客戶查詢。
DNS允許局部控制整個數據庫的某些部分，但數據庫的每一部分都可通過全網查詢得到
域名服務器可以分為主服務器、Caching Only服務器和轉發服務器

一個用戶A在查找另一用戶B時，域名的工作過程如下：
(1)解析向本地域名服務器發出請求查閱用戶B的域名
(2)本地域名服務器向最高層域名服務器發出查詢地址的請求
(3)最高層域名服務器返回給本地域名服務器一個IP地址
(4)本地域名服務器向組域名服務器發出查詢地址的請求
(5)組域名服務器返回給本地域名服務器一個IP地址
(6)本地服務器返回的域名服務器發出查詢域名地址請求
(7)IP地址返回給本地域名服務器
(8)本地域名服務器將改地址返回給解析器

73．WWW（World Wide Web，萬維網）服務：
①　交互式圖形界面 Internet服務，具有強大的信息連接功能
②　最受歡迎的、增長速度最快的一種多媒體信息服務系統
③　分布的超文本，這些信息結點可以是文本、子目錄或信息指針
④　WWW瀏覽程序為用戶提供基于超文本傳輸協議的用戶界面
⑤　數據文件由超文本標記語言描述，html利用統一資源定位器（URL）的指標是超媒體連接，并在文本內指向網絡資源。

74．Scheme指定服務連接的方式（協議）：

75．文本傳輸協議：
①　匿名（anonymous）FTP服務，提供公眾使用，共享主機對公眾開房的資源。匿名FTP服務特殊的用戶名—anonymous。
②　FTP在客戶端與服務器的內部建立兩條TCP連接：
控制連接：主要用于出書命令和參數（端口為21）
數據連接：用于傳送文件（端口為20）

信息安全基礎知識：
機密性、完整性、可用性、可控性和可審查性

信息的存儲安全包括信息使用的安全（如用戶的標識與驗證、用戶存取權限限制、安全問題跟蹤等）、系統安全監控、計算機病毒防止、數據的加密和防止非法的攻擊等。

數據加密：

總結

以上是生活随笔為你收集整理的软件设计师备考-软件设计师教程第五版的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。