國考資訊處理：計概重點筆記整理
計算機概論重點整理：2011/02/12更新
通用閘：可以以單一種閘實現所有閘的稱之，NAND gate 和 NOR gate 都是。
位元右端為低階端(low-order end)，最右一位為最低有效位元(least significant bit, LSB)，如下例右方紅色之 1。
演算過程：
(一)
霍夫曼編碼是由小排到大，小的放左，大的放右。
由K.N.G.I.H.E相比，最小為I(1)，次小為N(2)，相加上去為3。
3在與剩下的K.G.H.E相比，H(3)為最小，兩者放ㄧ起，相加上去為
6，6與剩下的K.G..E相比，K.G比他小，卻比H(3)大，因此必須放在H的右邊，K.G相加為9，剩下E(7)比6大，因此放6右邊，相加為13，13在與9相加上去，便是樹狀圖的完成了。
(二)
接下來在樹狀圖的左邊線標上0，右邊線標上1。
然後照英文單字左至右，循邊線的0與1位元集合開始編碼。
便完成了。
K=10
N=0001
G=11.
I=0000
H=001
E=01
只要能去除三者之一即可避免死結發生，
關鍵字：高考、普考、國考、國家考試、資訊處理、計概、計算機概論、考古題、題目、解答、重點整理
參考資料：
Q：說明邏輯閘的種類。
A：通用閘：可以以單一種閘實現所有閘的稱之，NAND gate 和 NOR gate 都是。
Q：說明記憶體的高低階端與有效位元。
A：位元右端為低階端(low-order end)，最右一位為最低有效位元(least significant bit, LSB)，如下例右方紅色之 1。
(高階端) 0 1 0 1 1 0 1 1 (低階端)
Q：說明磁碟運轉的效能參數。
A：- 尋覓時間(seek time)：把讀寫頭從一個磁軌移動到另一磁軌所需時間。
- 轉動延遲(rotation delay)，或叫潛行時間(latency time)：磁碟轉一整圈所需花費之時間的一半，亦即當磁頭已經置於存放資料的磁軌時，把資料所在轉置轉動至都寫頭的平均時間。
- 存取時間(access time)：尋覓時間與轉動延遲的和。
- 傳輸速率(transfer rate)：把資料從磁碟系統移出或移入的速率。
Q：說明磁碟與光學系統之不同。
A：- 磁軌含等量磁區，故外側磁區較不密。光碟為等密度，故外圈資料較多。
- 磁碟為同心圓，適合隨機存取。光碟為螺旋狀，適合連續循序存取。
- 光碟每區段大小為 2 KB，可錄 1/75 秒音樂。
- 如 1. 因光碟外圈資料較多，故讀取時讀到外圈旋轉速度較慢，光碟的旋轉速度由電腦控制。
Q：說明二進位與十進位之轉換。
A：
A：
- 十進位轉二進位：重複將要計算的數除以二，並將餘數由最低位寫至最高位就是結果 。如 13 的二進位表示法為1101：
- 13/2 = 6...1 (1)
- 6/2 = 3...0 (01)
- 3/2 = 1...1 (101)
- 1/2 = 0...1 (1101)
- 二進位轉十進位：將二進位的0,1乘上對應的2的冪次再相加即可。
Q：說明一補數與二補數之正負轉換。
A：
A：
- 一補數：直接將要轉換之數值的每個bit相反即可，如 6 的二進位表示法為0110，則以一補數表示 -6 為1001 。
- 二補數：將一補數再加上 1 即可。以二補數表示 -6 為 1010。
Q：說明超額表示法。
A：
A：
二進位之數值比超額 n 表示法的數值多出 n ，若沒有特別指定 n 時則由最高位的 bit 代表的值決定，
如 111 在純二進位是 7 ，但在超額表示法 (3 bit ，要減去 100 = 4 ) 則是 3。
0111 在純二進位是 7 ，但在超額表示法 (4 bit ，要減去 1000 = 8 ) 則是 -1。
以下是 3 bit 的超額表示法：
以下是 4 bit 的超額表示法：
Q：說明浮點數表示法。
A：
A：
參考連結：浮點數表示法。
二進位浮點數是以符號數值表示法格式儲存，將位元分為三個部份：
- 最高效位元指定為符號位元（sign bit），0 為正，1 為負。
- 「指數部份」，即次高效的e位元，為浮點數中經指數偏差（exponent bias）(超額表示法) 處理過後的指數；
- 「小數部份」，即剩下的f位元，為有效位數（significand）減掉有效位數本身的最高效位元。 (有正規表示法和隱藏位元之差別)
三個部份所佔的位元數在單精度 (32 bit) 和倍精度 (64 bit) 分別為：
- 32 bit：1, 8(超127表示法), 23
- 64 bit：1, 11(超1023表示法), 52
+-+--------+-----------------------+
|S| Exp | Fraction |
+-+--------+-----------------------+
正規表示法指的是由最左邊一個 1 開始填入 Fraction 部份，如 1.0111 在 Fraction 中會是 10111……。
以下是正規表示法的例子：00111100
0：正數
011：超額 4 表示法為 -1
1100：進 -1 位後得到 .01100 ，即十進位的 3/8
再一個正規表示法的例子：01101011
0：正數
110：超額 4 表示法為 2
1011：進 2 位後得到 10.11 ，即十進位的 2又3/4
隱藏位元指的是 1.0111 在 Fraction 中會被省略為 0111……，即省去第一個1(此為IEEE 754 之標準)。
以下取浮點數表示法中的圖為例：
Q：說明霍夫曼編碼法（Huffman's Encode）。
A：
A：
以下取自參考連結：霍夫曼編碼法。
例如：
一組簡單的的英文單字：
K
|
N
|
G
|
I
|
H
|
E
|
4
|
2
|
5
|
1
|
3
|
7
|
(一)
霍夫曼編碼是由小排到大，小的放左，大的放右。
由K.N.G.I.H.E相比，最小為I(1)，次小為N(2)，相加上去為3。
3在與剩下的K.G.H.E相比，H(3)為最小，兩者放ㄧ起，相加上去為
6，6與剩下的K.G..E相比，K.G比他小，卻比H(3)大，因此必須放在H的右邊，K.G相加為9，剩下E(7)比6大，因此放6右邊，相加為13，13在與9相加上去，便是樹狀圖的完成了。
(二)
接下來在樹狀圖的左邊線標上0，右邊線標上1。
然後照英文單字左至右，循邊線的0與1位元集合開始編碼。
便完成了。
K=10
N=0001
G=11.
I=0000
H=001
E=01
Q：說明CPU的內部元件。
A：
A：
- 算術邏輯單元(arithmetic logic unit)
- 控制單元(control unit)
- 暫存器單元(register unit)：又分通用和特殊用途。
特殊暫存器：
- 指令暫存器(instruction register)：用來儲存指令。
- 程式計數器(program counter)
Q：說明CPU的指令集種類。
A：
A：
- 精簡指令集電腦(reduced instruction set computer, RISC)：只使用最簡單的指令來完成工作，如Apple和IBM的PowerPC、SUN的SPARC處理器。
- 複雜指令集電腦(complex instruction set computer, CISC)：許多簡單的指令組合成複雜的指令，如Pentium系列處理器。
Q：說明CPU的指令分類。
A：
A：
- 資料傳送類：transfer, move, copy, clone。LOAD, STORE (I/O instructions)
- 算術邏輯類：AND, OR, XOR, SHIFT, ROTATE
- 控制類：JUMP(BRANCH)，有條件和無條件跳躍
Q：說明CPU的指令編碼。
A：
A：
- 運算碼(op-code, op=operation)：SHIFT, STORE等
- 運算元(operand)：source and destination register
例：0011(3) 0101(5) 1010(A) 0111(7)，35A7，把暫存器5的內容存入A7的位址中。
Q：說明CPU的機器週期(machine cycle)。
A：
A：
- 提取(fetch)
- 解碼(decode)
- 執行(execute)
Q：說明作業系統的定義。
A：
A：
控制一部電腦整體運作的一套軟體。它提供各種機制讓使用者能存取檔案，提供介面讓使用者能要求程式的執行，並提供所需的環境。
作為使用者與電腦硬體間溝通媒介的軟體。
Q：說明作業系統發展歷史。
A：
A：
- 執行單一工作(job)
- 批次處理(batch processing)：工作在佇列(queue)中通常為FIFO
- 交談式處理(interactive processing)：如終端機連線
- 即時處理(real-time processing)
- 分時處理(time sharing)、多工(multitasking)：多使用者
- 負載平衡(load balancing)、工作分割(scaling)：多核
Q：說明軟體分類。
A：
A：
- 應用軟體(application software)：資料庫、會計系統……
- 系統軟體(system software)：提供application所需之基礎設施，又分為
- 作業系統本身
- 公用軟體(utility software)：如格式化、處理網路通訊等軟體
Q：說明開機時作業系統啟動流程。
A：
A：
- 開機
- 讀取ROM中的啟動程式(bootstrap)，ROM中的程式即韌體
- 指引CPU將磁碟特定位址上的作業系統載入主記憶體
- CPU jump至作業系統所在之主記憶體位址
- BIOS 為 basic input/output system 的縮寫
Q：說明死結的發生原因與避免及解決的方法。
A：
A：
發生死結的原因有：
- 發生了對不可共享資源的競爭
- 資源的需求是部份提出的，即之後還會要求更多資源
- 資源分配後就不能強行取走
只要能去除三者之一即可避免死結發生，
前二者為避免死結的方法，如 2. 可改為要求一次就提出所有需求。
解決 3. 的技術被歸類為 死結偵測與更正方法(deadlock detection and correction schemes)
Q：說明網路之定義與分類。
A：
A：
定義：在不同電腦之間分享資訊與資源的需求甲發了互相連結的電腦系統，其中這些電腦互相連結而使機器間能傳遞資料。
依區域大小分：
- 區域網路(local area network, LAN)：大廈內或大廈間，校園
- 都會網路(metropolitan area network, MAN)：中型，跨越社區
- 廣域網路(wide area network, WAN)：鄰近城市或世界兩端，遠距
依內部運作或所有權分：
- 開放網路(open network)
- 封閉網路(closed network)
- 專屬網路(proprietary network)
Q：說明網路拓蹼的分類。
A：
A：
參考 wikipedia。
- 環狀拓撲（Ring Topology）
- Mesh拓撲（Mesh Topology）
- 星狀拓撲（Star Topology）
- 網狀拓撲（Fully Connected Topology）
- 線形拓撲（Linear Topology）
- 樹狀拓樸（Tree Topology）
- 匯流排拓撲（Bus Topology）
Q：說明協定的定義。
A：
A：
Protocols define format, order of messages sent and received (procedure) among network entities, and actions taken on message transmission, receipt.
協定規範了：程序(procedure)、行為(action)
Q：說明CSMA/CD與CSMA/CA的不同。
A：
A：
Node A, C 都要傳資料給 B，但 A 聽不到 C，故兩者的訊號會在 B 處碰撞而失敗。此時稱 C 對 A 而言是 hidden node。
A：
- CSMA/CD(Carrier Sense Multiple Access with Collision Detection)，譯為「載波感測多重存取/碰撞偵測」：先偵測通道是否有載波，若沒有時立刻傳送出訊框。若通道有其它訊框已經在傳送，則持續等候並偵測，直到沒有載波時送出訊框。若兩個stations同時發送訊框，就會發生碰撞。若偵測出有碰撞發生，不用等整個訊框傳完就立即停止傳送，如此可以節省通道頻寬，然後隨機等待一段時間再重新嘗試。這是乙太網路所使用的媒體存取控制(Media Access Control)方法，為IEEE 802.3標準所定義。
- CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)，譯為「載波感測多重存取/碰撞避免」，主要運用了兩種方法來避免碰撞：
- 在傳送前除了偵測頻道外還要多等一段時間，之後才可以要求頻道使用權(因無線網路傳時不能聽，或其他node之訊號到達時太弱)。channel clear -> random backoff factor -> 遞減 -> 傳！(減低碰撞機率)
- 資料傳送之前，傳送端與接收端先互相交換控制訊框，傳送端會送一個要求傳送的控制框(RTS, Request To Send)，說明傳送的資料框長度，接收端回應(CTS, Clear To Send)後才開始傳送。資料傳送時，接收端會對每一個收到的訊框做出回應(ACK)。
CSMA/CA的四種等待時間：
Q：說明 Hidden Node Problem。- DIFS：正常的等待時間(contension period)
- SIFS：用於傳ACK, RTS, CTS
- EIFS：用於重傳
- PIFS：用於contension free period，即AP用polling的方式決定傳送順序時
- SIFS < PIFS < DIFS < EIFS
A：
Node A, C 都要傳資料給 B，但 A 聽不到 C，故兩者的訊號會在 B 處碰撞而失敗。此時稱 C 對 A 而言是 hidden node。
此問題可用 RTS 和 CTS 解決，若 A 傳 RTS 給 B 但 B 正與 C 傳，則 B 會等到 C 的傳送結束後才送 CTS 給 A。
RTS 與 CTS 的使用時機：
- always：很多障礙時(因很容易造成 hidden node)
- never：沒什麼阻隔時，但仍可視情況選用
- only：傳送大封包(為了限定頻道不受干擾，因為大封包重傳很痛)
Q：說明 Exposed Node Problem。
A：
Node B 要傳給 A, C 要傳 D，
A：
Node B 要傳給 A, C 要傳 D，
- B, C 在對方的 sensing range中
- B 不在 D 的 interference range中，A 也不在 C 的中
- 因 B, C 會聽到對方在傳，所以另一方會被迫不能傳。但其實對接收端而言不影響
Q：說明網路不同階層的連結設備。
A：
A：
- 接續器(repeater)：單純將信號在兩個匯流排間傳送，大多有增強訊號的功能。Physical Layer
- 橋接器(bridge)：只有訊息目的地在另一頭時才轉傳(較接續器而言更有效率)。 Data Link Layer
- 轉接器(switch)：有多重連結的橋接器。Data Link Layer
- 路由器(router)：連結異質網路，如Ethernet與ATM (又叫 Layer 3 switching)。 Network Layer
Q：公開金鑰(public key)、數位簽章(digital signature)與數位信封(Digital Envelop)。
A：
Q：說明SSL與SET的不同。
A：
A：
- 數位簽章：發送端將要傳遞的訊息hash產生訊息摘要(Message Digest)，再將摘要用私用金鑰(private key)加密，此即數位簽章。之後將訊息與簽章傳送給接收端，接收端可利用發送端的公用金鑰(public key)解開數位簽章，並與訊息hash後的訊息摘要比對，一方面進行確認身份的動作，一方面可確保訊息的完整性。
- 數位信封：因公開金鑰加解密太慢，故傳送者先產生一把對稱式金鑰(如DES, AES等)，以此對稱式金鑰加密要傳送的資料。接著將對稱式金鑰以接收端的公鑰加密，並連同加密後的資料一起傳送給接收端。接收端可用他的私鑰解開對稱式金鑰，再以此對稱式金鑰解密資料。
Q：說明SSL與SET的不同。
A：
- SSL(Secure Sockets Layer)位在TCP與應用層之間，作用是提供安全連線。SSL為網路上進行加密通訊之全球化標準，主要有三大功能：伺服器鑑別、啟動加密連線、資料完整性確認。因為它並不強制對使用者這一端做身份的認證，所以很容易的就發展成普遍使用的一種機制， 在電子商務起步階段，大部分的店家都是用這種方法來做所謂安全防護。
- SET(Secure Electronic Transaction)是運用安全技術的線上刷卡作業標準，規範了消費者，商店，付款閘道，收單銀行，發卡銀行的資料傳送、身分識別以及電子簽名等機制，用來讓信用卡資料與訂單在嚴密的安全設計下自動的傳輸與交換，這是兩大發卡組織(VISA和MasterCard)共同規範的標準，安全性與可信賴性都大大提高。SET主要應用於信用卡網路交易時之加密安全機制，提供資料的保密性(privacy)、交易的完整性(integrity)，以及持卡人和特約商店的身分認證(authentication)。
(2012.03.31更新)
更多英文檢定考試、證照、國考、國營、中華電信考試的介紹與心得分享，請參考：
參考資料：
