2011年2月12日

國考資訊處理:計概重點筆記整理


 
計算機概論重點整理:2011/02/12更新

Q:說明邏輯閘的種類。
A:

AND gatetraditional OR gate symboltraditional EX-OR gate symbolNOT gate

    通用閘:可以以單一種閘實現所有閘的稱之,NAND gate 和 NOR gate 都是。

traditional NAND gate symbolNOR gate

Q:說明記憶體的高低階端與有效位元。
A:
        位元左端為高階端(high-order end),最左一位為最高有效位元(most significant bit, MSB),如下例左方紅色之 0。
        位元右端為低階端(low-order end),最右一位為最低有效位元(least significant bit, LSB),如下例右方紅色之 1。

            (高階端) 0 1 0 1 1 0 1 1 (低階端)

    Q:說明磁碟運轉的效能參數。
    A:
    1. 尋覓時間(seek time):把讀寫頭從一個磁軌移動到另一磁軌所需時間。
    2. 轉動延遲(rotation delay),或叫潛行時間(latency time):磁碟轉一整圈所需花費之時間的一半,亦即當磁頭已經置於存放資料的磁軌時,把資料所在轉置轉動至都寫頭的平均時間。
    3. 存取時間(access time):尋覓時間與轉動延遲的和。
    4. 傳輸速率(transfer rate):把資料從磁碟系統移出或移入的速率。

    Q:說明磁碟與光學系統之不同。
    A:
    1. 磁軌含等量磁區,故外側磁區較不密。光碟為等密度,故外圈資料較多。
    2. 磁碟為同心圓,適合隨機存取。光碟為螺旋狀,適合連續循序存取。
    3. 光碟每區段大小為 2 KB,可錄 1/75 秒音樂。
    4. 如 1. 因光碟外圈資料較多,故讀取時讀到外圈旋轉速度較慢,光碟的旋轉速度由電腦控制。

    Q:說明二進位與十進位之轉換。
    A:
    • 十進位轉二進位:重複將要計算的數除以二,並將餘數由最低位寫至最高位就是結果 。如 13 的二進位表示法為1101:
      1. 13/2 = 6...1 (1)
      2. 6/2 = 3...0  (01)
      3. 3/2 = 1...1  (101)
      4. 1/2 = 0...1  (1101)

    • 二進位轉十進位:將二進位的0,1乘上對應的2的冪次再相加即可。
                如 1101 : 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 13

    Q:說明一補數與二補數之正負轉換。
    A:
    • 一補數:直接將要轉換之數值的每個bit相反即可,如 6 的二進位表示法為0110,則以一補數表示 -6 為1001 。
    • 二補數:將一補數再加上 1 即可。以二補數表示 -6 為 1010。
                            同樣以 6 為例,0110 由右向左複製直到遇上第一個1,得到 10 ,其後將所有位元 (01xx) 轉換得到 1010。

    Q:說明超額表示法。
    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:
        參考連結:浮點數表示法
        二進位浮點數是以符號數值表示法格式儲存,將位元分為三個部份:
    1. 最高效位元指定為符號位元(sign bit),0 為正,1 為負。
    2. 「指數部份」,即次高效的e位元,為浮點數中經指數偏差(exponent bias)(超額表示法) 處理過後的指數;
    3. 「小數部份」,即剩下的f位元,為有效位數(significand)減掉有效位數本身的最高效位元。 (有正規表示法和隱藏位元之差別)

        三個部份所佔的位元數在單精度 (32 bit) 和倍精度 (64 bit) 分別為:
    1. 32 bit:1, 8(超127表示法), 23
    2. 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:
        以下取自參考連結:霍夫曼編碼法

    例如:
    一組簡單的的英文單字:
    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:
    1. 算術邏輯單元(arithmetic logic unit)
    2. 控制單元(control unit)
    3. 暫存器單元(register unit):又分通用和特殊用途。
        特殊暫存器:
    1. 指令暫存器(instruction register):用來儲存指令。
    2. 程式計數器(program counter)

    Q:說明CPU的指令集種類。
    A:
    1. 精簡指令集電腦(reduced instruction set computer, RISC):只使用最簡單的指令來完成工作,如Apple和IBM的PowerPC、SUN的SPARC處理器。
    2. 複雜指令集電腦(complex instruction set computer, CISC):許多簡單的指令組合成複雜的指令,如Pentium系列處理器。

    Q:說明CPU的指令分類。
    A:
    1. 資料傳送類:transfer, move, copy, clone。LOAD, STORE (I/O instructions)
    2. 算術邏輯類:AND, OR, XOR, SHIFT, ROTATE
    3. 控制類:JUMP(BRANCH),有條件和無條件跳躍

    Q:說明CPU的指令編碼。
    A:
    1. 運算碼(op-code, op=operation):SHIFT, STORE等
    2. 運算元(operand):source and destination register
        例:0011(3) 0101(5) 1010(A) 0111(7),35A7,把暫存器5的內容存入A7的位址中。

    Q:說明CPU的機器週期(machine cycle)。
    A:
    1. 提取(fetch)
    2. 解碼(decode)
    3. 執行(execute)

    Q:說明作業系統的定義。
    A:
        控制一部電腦整體運作的一套軟體。它提供各種機制讓使用者能存取檔案,提供介面讓使用者能要求程式的執行,並提供所需的環境。
        作為使用者與電腦硬體間溝通媒介的軟體。

    Q:說明作業系統發展歷史。
    A:
    1. 執行單一工作(job)
    2. 批次處理(batch processing):工作在佇列(queue)中通常為FIFO
    3. 交談式處理(interactive processing):如終端機連線
    4. 即時處理(real-time processing)
    5. 分時處理(time sharing)、多工(multitasking):多使用者
    6. 負載平衡(load balancing)、工作分割(scaling):多核

    Q:說明軟體分類。
    A:
    1. 應用軟體(application software):資料庫、會計系統……
    2. 系統軟體(system software):提供application所需之基礎設施,又分為
      • 作業系統本身
      • 公用軟體(utility software):如格式化、處理網路通訊等軟體

    Q:說明開機時作業系統啟動流程。
    A:
    1. 開機
    2. 讀取ROM中的啟動程式(bootstrap),ROM中的程式即韌體
    3. 指引CPU將磁碟特定位址上的作業系統載入主記憶體
    4. CPU jump至作業系統所在之主記憶體位址
    • BIOS 為 basic input/output system 的縮寫

    Q:說明死結的發生原因與避免及解決的方法。
    A:
        發生死結的原因有:
    1. 發生了對不可共享資源的競爭
    2. 資源的需求是部份提出的,即之後還會要求更多資源
    3. 資源分配後就不能強行取走

        只要能去除三者之一即可避免死結發生,
        前二者為避免死結的方法,如 2. 可改為要求一次就提出所有需求。
        解決 3. 的技術被歸類為 死結偵測與更正方法(deadlock detection and correction schemes)

    Q:說明網路之定義與分類。
    A:
        定義:在不同電腦之間分享資訊與資源的需求甲發了互相連結的電腦系統,其中這些電腦互相連結而使機器間能傳遞資料。
        依區域大小分:
    1. 區域網路(local area network, LAN):大廈內或大廈間,校園
    2. 都會網路(metropolitan area network, MAN):中型,跨越社區
    3. 廣域網路(wide area network, WAN):鄰近城市或世界兩端,遠距
        依內部運作或所有權分:
    1. 開放網路(open network)
    2. 封閉網路(closed network)
    3. 專屬網路(proprietary network)

    Q:說明網路拓蹼的分類。
    A:
        參考 wikipedia
    1. 環狀拓撲(Ring Topology)
    2. Mesh拓撲(Mesh Topology)
    3. 星狀拓撲(Star Topology) 
    4. 網狀拓撲(Fully Connected Topology) 
    5. 線形拓撲(Linear Topology) 
    6. 樹狀拓樸(Tree Topology)
    7. 匯流排拓撲(Bus Topology)

    Q:說明協定的定義。
    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:
    1. CSMA/CD(Carrier Sense Multiple Access with Collision Detection),譯為「載波感測多重存取/碰撞偵測」:先偵測通道是否有載波,若沒有時立刻傳送出訊框。若通道有其它訊框已經在傳送,則持續等候並偵測,直到沒有載波時送出訊框。若兩個stations同時發送訊框,就會發生碰撞。若偵測出有碰撞發生,不用等整個訊框傳完就立即停止傳送,如此可以節省通道頻寬,然後隨機等待一段時間再重新嘗試。這是乙太網路所使用的媒體存取控制(Media Access Control)方法,為IEEE 802.3標準所定義。
    2. CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance),譯為「載波感測多重存取/碰撞避免」,主要運用了兩種方法來避免碰撞:
      1. 在傳送前除了偵測頻道外還要多等一段時間,之後才可以要求頻道使用權(因無線網路傳時不能聽,或其他node之訊號到達時太弱)。channel clear -> random backoff factor -> 遞減 -> 傳!(減低碰撞機率)
      2. 資料傳送之前,傳送端與接收端先互相交換控制訊框,傳送端會送一個要求傳送的控制框(RTS, Request To Send),說明傳送的資料框長度,接收端回應(CTS, Clear To Send)後才開始傳送。資料傳送時,接收端會對每一個收到的訊框做出回應(ACK)。
                    CSMA/CA的四種等待時間:
      • DIFS:正常的等待時間(contension period)
      • SIFS:用於傳ACK, RTS, CTS
      • EIFS:用於重傳
      • PIFS:用於contension free period,即AP用polling的方式決定傳送順序時
      • SIFS < PIFS < DIFS < EIFS

    Q:說明 Hidden Node Problem。
    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 的使用時機:
    1. always:很多障礙時(因很容易造成 hidden node)
    2. never:沒什麼阻隔時,但仍可視情況選用
    3. only:傳送大封包(為了限定頻道不受干擾,因為大封包重傳很痛)

    Q:說明 Exposed Node Problem。
    A:
        Node B 要傳給 A, C 要傳 D,
    1. B, C 在對方的 sensing range中
    2. B 不在 D 的 interference range中,A 也不在 C 的中
    3. 因 B, C 會聽到對方在傳,所以另一方會被迫不能傳。但其實對接收端而言不影響

    Q:說明網路不同階層的連結設備。
    A:
    1. 接續器(repeater):單純將信號在兩個匯流排間傳送,大多有增強訊號的功能。Physical Layer
    2. 橋接器(bridge):只有訊息目的地在另一頭時才轉傳(較接續器而言更有效率)。 Data Link Layer
    3. 轉接器(switch):有多重連結的橋接器。Data Link Layer
    4. 路由器(router):連結異質網路,如Ethernet與ATM (又叫 Layer 3 switching)。 Network Layer

    Q:公開金鑰(public key)、數位簽章(digital signature)與數位信封(Digital Envelop)。
    A:
    1. 數位簽章:發送端將要傳遞的訊息hash產生訊息摘要(Message Digest),再將摘要用私用金鑰(private key)加密,此即數位簽章。之後將訊息與簽章傳送給接收端,接收端可利用發送端的公用金鑰(public key)解開數位簽章,並與訊息hash後的訊息摘要比對,一方面進行確認身份的動作,一方面可確保訊息的完整性。
    2. 數位信封:因公開金鑰加解密太慢,故傳送者先產生一把對稱式金鑰(如DES, AES等),以此對稱式金鑰加密要傳送的資料。接著將對稱式金鑰以接收端的公鑰加密,並連同加密後的資料一起傳送給接收端。接收端可用他的私鑰解開對稱式金鑰,再以此對稱式金鑰解密資料。

    Q:說明SSL與SET的不同。
    A:
    1. SSL(Secure Sockets Layer)位在TCP與應用層之間,作用是提供安全連線。SSL為網路上進行加密通訊之全球化標準,主要有三大功能:伺服器鑑別、啟動加密連線、資料完整性確認。因為它並不強制對使用者這一端做身份的認證,所以很容易的就發展成普遍使用的一種機制, 在電子商務起步階段,大部分的店家都是用這種方法來做所謂安全防護。
    2. SET(Secure Electronic Transaction)是運用安全技術的線上刷卡作業標準,規範了消費者,商店,付款閘道,收單銀行,發卡銀行的資料傳送、身分識別以及電子簽名等機制,用來讓信用卡資料與訂單在嚴密的安全設計下自動的傳輸與交換,這是兩大發卡組織(VISA和MasterCard)共同規範的標準,安全性與可信賴性都大大提高。SET主要應用於信用卡網路交易時之加密安全機制,提供資料的保密性(privacy)、交易的完整性(integrity),以及持卡人和特約商店的身分認證(authentication)

    (2012.03.31更新) 
    更多英文檢定考試、證照、國考、國營、中華電信考試的介紹與心得分享,請參考:

    關鍵字:高考、普考、國考、國家考試、資訊處理、計概、計算機概論、考古題、題目、解答、重點整理
    參考資料:
    1. 計算機概論、10/e、東華、林國平譯(Brookshear著)



    更多精選推薦文章