三級數據庫技術1三級數據庫技術1開篇話學習建議以教材和背誦資料為綱，內容多，理解記憶，記關鍵詞、關鍵句作好預習，進行標注課程結構知識點考點歷年真題教材上的內容占90%2開篇話學習建議教材上的內容占90%233三級數據庫技術第1章計算機基礎知識4三級數據庫技術第1章計算機基礎知識4本章考點約為10％計算機系統的組成計算機網絡基礎信息安全基礎5本章考點約為10％51.1計算機系統組成與應用領域61.1計算機系統組成與應用領域6考點1計算機系統組成計算機系統硬件系統軟件系統運算器控制器存儲器輸入、輸出設備計算機語言系統軟件應用軟件機器語言匯編語言高級語言OS語言程序處理程序數據庫管理系統診斷程序算術和邏輯運算指令解釋、執行存放數據和程序模數轉換、數模轉換、磁盤、磁帶7考點1計算機系統組成計硬件系統軟件系統運算器控制器存儲器輸CPU馮.諾依曼計算機以

為基礎，由

五大部分組成

存儲程序原理接口8CPU馮.諾依曼計算機以為基礎，模數轉換器為輸入設備，而數/模轉換器為輸出設備。有些設備隊有輸入功能又有輸出如磁盤機、磁帶機9模數轉換器為輸入設備，而數/模轉換器為輸出設備。有些設備隊指令系統復雜指令系統（CISCcomplexinstructionsetcomputer)精簡指令系統(RISCreducedinstructionsetcomputer)指令類型數據傳送指令算術邏輯指令判定控制指令10指令系統復雜指令系統（CISCcomplexinstru指令系統的尋址方式：立即尋址（立即數尋址），指令中直接給出操作數。寄存器尋址：操作數在寄存器中。直接尋址：指令中直接給出操作數地址。寄存器間接尋址：寄存器給出操作數地址。寄存器相對尋址：指令中給出操作數的地址偏移量。11指令系統的尋址方式：立即尋址（立即數尋址），指令中直接給出操微型處理器分類：通用微處理器、嵌入式微處理器和數字信號處理器（如通信設備、雷達、數字圖像處理設備、數字音頻設備）總線

PCI：不依附具體處理器的局部總線。

USB：通用串行總線。1394總線：FireWire，為家用電器研制的一種高速串行總線。1394總線在數字視頻設備（數字攝像機）中廣泛應用。12微型處理器分類：通用微處理器、嵌入式微處理器和數字信號處理器考點2計算機的應用領域科學和工程計算科學計算，計算量大、邏輯簡單數據和信息處理過程控制（實時、靈敏性、可靠性、抗干擾性、封閉性）輔助設計（CAD,CAM,CAT,CAI)(computeraidedManufacturing)人工智能13考點2計算機的應用領域科學和工程計算13考題為了改變指令系統計算機指令過多的狀態而設計的一種計算機系統結構稱為精簡指令系統計算機，其英文縮寫為

數字信號處理器由于在其內部設計了能夠高速處理多路數字信號的電路，可以用在需要快速處理大量復雜信息的領域。下列哪一個設備不需要數字信號處理器？

A)雷達

B)彩色電視機

C)數字音視頻設備

D)數字圖像處理設備

B2009.914考題為了改變指令系統計算機指令過多的狀態而設計的一種計算機系考題下列哪一個不是指令系統中包含的指令類型A存儲控制類指令B數據傳送類指令C算術邏輯類指令D判定控制類指令A15考題下列哪一個不是指令系統中包含的指令類型15（1）馮·諾依曼奠定了現代計算機工作原理的基礎。下列敘述中，哪個（些）是正確的？

I．程序必須裝入內存才能執行

II．計算機按照存儲的程序逐條取出指令，分析后執行指令所規定的操作

III.計算機系統由運算器、存儲器、控制器、輸入設備、輸出設備等五大部件組成

A）僅I

B）僅I和II

C）僅II和III

D）都正確

（2）關于指令系統的尋址方式，如果在指令中給出操作數所在的地址，該方式稱為

A）立即尋址

B）直接尋址

C）寄存器尋址

D）寄存器間接尋址

16（1）馮·諾依曼奠定了現代計算機工作原理的基礎。下列敘述中，1下列哪一項指標在實時控制系統時不需要滿足？A、可靠性B、實時性C、交互性D、抗干擾性答案C2用計算機進行導彈飛行軌道的計算，屬于下列哪一個計算機應用領域？A．人工智能B．過程控制C．輔助設計D．科學和工程計算

D171下列哪一項指標在實時控制系統時不需要滿足？173通常一臺計算機系統的存儲介質包括Cache、內存、磁帶和硬盤，其中訪問速度最慢的是

A．Cache

B．磁帶

C．硬盤D．內存

B4下列關于計算機系統工作原理的敘述中，哪一條是正確的？

A．中央處理器直接對存儲器中的數據進行處理

B．運算器完成解釋和執行指令的工作

C．中央處理器可以從輸入設備中得到控制指令

D．程序和數據均存放在存儲器中

D183通常一臺計算機系統的存儲介質包括Cache、內存、磁帶和5計算機硬件系統中，完成解釋指令、執行指令的部件是______。A）運算器B）控制器C）存儲器D）輸入輸出設備B6下列哪一種設備不是輸入設備？A鍵盤B光筆C數/模轉換器D聲音識別器C195計算機硬件系統中，完成解釋指令、執行指令的部件是____填空題1將文本、音頻、視頻、動畫、圖形和圖像等各種媒體綜合起來的技術稱為【1】技術多媒體2計算機是由運算器、

【1】

、存儲器、輸入設備和輸出設備這5個主要功能部件組成的，它們被稱為計算機的五大硬件控制器20填空題1將文本、音頻、視頻、動畫、圖形和圖像等各種媒體綜合1.2計算機軟件211.2計算機軟件21考點1計算機語言機器語言依賴于硬件0，1二進制代碼，運行速度快不易被人識別（最初級語言）匯編語言

助記符表示指令的語言，易于理解和記憶，計算機不能識別，經過匯編程序翻譯成機器語言執行（仍然依賴機器，低級語言）22考點1計算機語言機器語言222323高級語言人工設計語言，接近人的理解，對算法描述特點：獨立硬件、可移植和通用性好Basic:普及性會話語言Fortran:科學及工程計算Pascal:教學語言C語言：系統開發C++：面向對象語言Cobol:商業事務處理和金融Prolog:人工智能語言

24高級語言24高級語言程序機器語言編譯編譯程序運行結果運行編譯過程25高級語言程序機器語言編譯編譯程序運行結果運行編譯過程25考點2系統軟件操作系統，系統軟件的核心語言處理程序（解釋程序和編譯程序）數據庫管理系統服務性程序（調試程序、糾錯程序、診斷程序）26考點2系統軟件操作系統，系統軟件的核心26考點3應用軟件27考點3應用軟件27計算機系統技術指標運算速度MIPS(MillionInstructionsPerSecond)主頻GHZ字長：一次處理的二進制位數存儲容量GMKB（1024）數據傳輸率1Kb1Mb1Gb的關系（1000）28計算機系統技術指標運算速度MIPS(MillionInst計算機中的信息表示進制轉換10-2進制轉換：除2取余2-8進制：從右到左每三位一組，轉換為8進制數2-16進制：從右到左每四位一組，轉換為16進制數小數部分從左到右每三位或四位一組29計算機中的信息表示進制轉換29（10）10-()2(10.1)2->()10或8進制到10進制（10001001.10）2->（）830（10）10-()230原碼、反碼和補碼正整數，原碼、反碼和補碼一樣，都是正數本身。負整數，原碼的符號位為1，數值部分取絕對值反碼的符號位為1，其他位是原碼取反補碼的符號位為1，其他位原碼取反，加1.如：29-2931原碼、反碼和補碼31服務程序是一類輔助性程序，它提供各種軟件運行時所需的服務，下列哪一個屬于服務程序？A)語言處理程序B）調試程序C）操作系統D）數據庫管理系統32服務程序是一類輔助性程序，它提供各種軟件運行時所需的服務，下八進制數1507轉換成十進制數是多少2009.1033八進制數1507轉換成十進制數是多少33考題1、完成輔助診斷疾病的軟件屬于下列哪一類計算機軟件？

A）系統軟件B、科學計算軟件

C）人工智能軟件D、數據和信息處理軟件C2、下列有關高級語言的敘述中，哪一個是不正確的？A）高級語言又稱為算法語言B）高級語言獨立于計算機硬件C）高級語言程序可以直接在計算機上執行D）用高級語言編寫的程序其通用性和移植性好C34考題1、完成輔助診斷疾病的軟件屬于下列哪一類計算機軟件？33、計算機軟件分為系統軟件和應用軟件兩大類，其中處于系統軟件核心地位的是

A)操作系統B）編譯程序

C）數據庫管理系統

D）網絡通信軟件

A4、下列有關程序設計語言的敘述中，哪一個是不正確的？

A．機器語言是最初級的計算機語言

B．機器語言程序的形式是二進制代碼

C．機器語言需要編譯后才可以被計算機執行

D．用機器語言編寫程序比較困難C353、計算機軟件分為系統軟件和應用軟件兩大類，其中處于系統軟件5、計算機軟件分為系統軟件和應用軟件兩大類，其中處于系統軟件核心地位的是

A．操作系統

B．編譯程序

C．數據庫管理系統

D．網絡通信軟件A6、匯編語言是一種符號語言，通常用指令功能的英文詞縮寫代替操作碼。助記符MOV表示的指令是______。A）加法B）中斷C）空操作D）傳送D365、計算機軟件分為系統軟件和應用軟件兩大類，其中處于系統軟件7、下列關于系統軟件的敘述中，哪個不正確？A)操作系統管理系統的軟硬件資源B)解釋程序將源程序轉換為目標程序，邊解釋邊執行C）Informix是一種數據庫管理系統D）故障診斷程序是一類服務程序B377、下列關于系統軟件的敘述中，哪個不正確？37填空題1、語言處理程序應屬于【1】軟件系統38填空題1、語言處理程序應屬于【1】軟件38過關練習1、下列哪一項不屬于系統軟件？

A)調試程序B)計算機輔助設計程序

C)編譯程序D)數據庫管理系統

2、下列敘述中，錯誤的是

A．系統軟件是在應用軟件基礎上開發的

B．系統軟件應提供友好的人機界面

C．系統軟件與硬件密切相關

D．系統軟件與具體應用領域無關

3、目前常用的辦公軟件Office應屬于

A)應用軟件B）系統軟件C）工具軟件D）管理軟件

BAA39過關練習1、下列哪一項不屬于系統軟件？

A)調試程序B)1.3計算機網絡基礎（4分）重點401.3計算機網絡基礎（4分）重點40考點1計算機網絡概述計算機網絡是通信技術與計算機技術緊密結合的產物．計算機網絡的發展歷史(1)具有通信功能的單機系統階段(2)具有通信功能的多機系統階段(3)計算機網絡階段計算機網絡特征1、資源共享：硬件共享、軟件共享、數據共享2、自治計算機3、共同網絡協議：語法（結構和格式）、語義（意義）、時序（事件的執行順序）41考點1計算機網絡概述計算機網絡是通信技術與計算機技術緊密考點2計算機網絡分類分類方法（1）根據傳輸技術分類：廣播式網絡與點-點網絡(2)根抓網絡的覆蓋范圍與規模分類：局域網（LAN）、城域問（MAN)及廣域網(WAN）局域網：（以太網、令牌總線和令牌環）決定局域網特性主要技術要素為網絡拓撲、傳輸介質與介質訪問控制方法（共享式和交換式局域網）局域網常用的傳輸介質有：同軸電纜、雙絞線、光纖與無線通信信道。42考點2計算機網絡分類分類方法42城域網：早期城域網主要采用光纖分布式數據接口FDDI具有雙環結構，容錯能力具有動態分配帶寬能力共同特點：傳輸介質采用光纖，交換接點采用基于IP交換的高速路由交換機或ATM交換機，在體系結構上采用核心交換層，業務匯聚層與接入層三層模式。城域網MAN介于廣域網與局域網之間的一種高速網絡。廣域網（分組交換技術）（X.25,幀中繼、ISDN,ATM)

大容量與突發性通信要求綜合業務服務要求

開放設備接口與規范化的協議完善的通信服務和網絡管理43城域網：43X．25：建立在速率低、誤碼率高的電纜介質上，X.25協議包括差錯控制、流量控制和擁塞控制等，由通信子網完成。FR（幀中繼）：建立在速率高、誤碼率低的光纖上，對X.25協議進行簡化，差錯控制由用戶終端完成。B-ISDN（寬帶綜合業務數字網）、N-ISDN（窄帶綜合業務數字網）ATM（異步傳輸模式，一種數據傳輸與分組交換技術，能滿足多媒體應用的高速率與低延遲的要求，具有線路交換實時性好和分組交換靈活性好的雙重優點。44X．25：建立在速率低、誤碼率高的電纜介質上，X.25協議包考點3Internet基礎1、Internet的形成和發展（1）TCP/IP協議與ARPnet結合，使ARPnet成為Internet的主干網（2）NSFnet是第一個使用TCP/IP的廣域網（3）Internet實現了TCP/IP參考模型與協議的結合，TCP/IP協議不受主機、操作系統的限制45考點3Internet基礎1、Internet的形成和發2、Internet結構與組成Internet是通過網絡互聯設備-路由器連接起來的大型廣域網（通信線路、路由器、主機、信息資源）462、Internet結構與組成46路由器：為數據包選擇路徑。47路由器：為數據包選擇路徑。474848

3、TCP/IP協議、域名與IP地址（重點）TCP/IP協議組的四個層次應用層傳輸層網絡層物理層TCPUDPIP493、TCP/IP協議、域名與IP地址（重點）應用層傳輸層網應用層協議：網絡終端協議TELNET,實現遠程登錄文件傳送協議FTP域名服務協議DNS，實現域名到IP地址映射路由信息協議RIP，交換路由信息電子郵件協議SMTP

HTTP協議，WWW服務50應用層協議：50域名與IP地址域名和IP地址是Internet上的兩種地址表示形式IP地址由網絡地址和機器地址組成IP地址長度為32位，X.X.X.X表示，X為8為，表示0-255,(點分十進制地址）51域名與IP地址51A類：7位24位B類：14位16位C類：21位8位網絡地址機器地址010110---52A類：7位24位B類：14位16位C類：21位8位網絡地址機域名IP地址數字，難記憶，出現字符型主機名即域名格式主機名.組名.網點名域名與IP地址一一對應53域名53考點4Internet提供的主要服務WWW服務：超文本和超媒體是WWW信息組織形式（鏈接）使用的協議HTTP（Hypertexttransferprotocol)54考點4Internet提供的主要服務WWW服務：超文本和超HTML(超文本標記語言)和HTTP（超文本傳輸協議）是WWW工作的基礎55HTML(超文本標記語言)和HTTP（超文本傳輸協議）是WWURL:統一資源定位器（uniformResourceLocator),定位頁面56URL:統一資源定位器（uniformResourceL電子郵件服務（E-Mail)由郵件服務器、電子郵箱組成，并規定電子郵件書寫規則工作原理發送方郵件服務器發送方接收方郵件服務器接收方SMTP簡單郵件傳輸協議POP3、IMAP郵局協議交互式郵件存取協議FTP郵箱57電子郵件服務（E-Mail)工作原理發送方發送方接收方接收方電子郵件內容協議MIME(MultipurposeInternetMailExtensions)，可以傳送圖像、聲音等多媒體信息58電子郵件內容協議MIME(MultipurposeIn考點5Internet基本接入方式局域網接入數據通信網（X.25,DDN,ADSL,ISDN）

ISP（InternetServiceProvider，ISP）Internet服務提供商，為用戶提供接入和提供信息服務59考點5Internet基本接入方式局域網接入數據通信網（X電話網接入60電話網接入60ADSL(AsymmetricalDigitalSubscriberLoop)非對稱數字用戶環路。用戶通過電信接入Internet，普遍采用ADSL方式。基于電話線，上、下行傳輸速率不同，上行（從用戶到網絡）為低速，可達1Mbps；下行（從網絡到用戶）為高速，可達8Mbps。傳輸距離有限制：3-5km61ADSL(AsymmetricalDigitalSubs下列關于ADSL技術的敘述中，哪些是正確的？

Ⅰ.它是在普通電話線上的一種新的高速寬帶技術

Ⅱ.它為用戶提供上、下行對稱的傳輸速率

Ⅲ.ADSL寬帶接入方式可用于網絡互聯業務

A)僅Ⅰ和Ⅱ

B)僅Ⅱ和Ⅲ

C)僅Ⅰ和Ⅲ

D)全部

C2009.962下列關于ADSL技術的敘述中，哪些是正確的？

Ⅰ.它是在（3）用于實現Internet中文件傳輸功能所采用的應用層協議是

A）FTP

B）DNS

C）SMTP

D）HTTP

（4）WWW能夠提供面向Internet服務的、一致的用戶界面的信息瀏覽功能，其使用的基礎協議是

A）FTP

B）DNS

C）SMTP

D）HTTP

63（3）用于實現Internet中文件傳輸功能所采用的應用層協數據包要求從源主機出發，最終到目的主機。下列哪一個設備可為數據包選擇輸出路徑，將它從一個網絡傳送到另一個網絡？

A)通信線路

B)路由器

C)WWW服務器

D)調制解調器

當電子郵件軟件從郵件服務器讀取郵件時，可以使用下列哪一個（些）協議？

Ⅰ.簡單郵件傳輸協議SMTP

Ⅱ.郵局協議POP3

Ⅲ.交互式郵件存取協議IMAP

A)僅Ⅰ

B)僅Ⅱ

C)僅Ⅱ和Ⅲ

C)僅Ⅰ和Ⅲ

CB2009.964數據包要求從源主機出發，最終到目的主機。下列哪一個設備可為數下列哪個不屬于廣域網技術？A、X.25B、FDDIC、ISDND、ATMB2009.03下列關于廣域網技術的敘述，哪個不正確？A、X.25執行過程復雜，增加了網絡傳輸延遲B、幀中繼的產生為了保證數據傳輸的質量C、ATM技術采用異步傳輸與分組交換技術D、建立綜合業務數字網的目的之一為用戶提供標準接口B2008.0465下列哪個不屬于廣域網技術？65考題1、IP地址是Internet賴以工作的基礎，它由網絡地址和主機地址兩部分組成，其中C類網絡的主機地址數最多為A）64個B）128個C）256個D）512個C（2007.04）2、電子郵件服務程序從郵件服務器中讀取郵件時可以使用郵局協議，下列哪個是郵局協議（2007.04）A）POP3B）IMAPC）HTTPD）SMTPA66考題1、IP地址是Internet賴以工作的基礎，它由網絡地3、下列哪一項不屬于郵件服務器的主要功能？(2007.04)A）接收用戶發送來的郵件B）為收件人定期清理郵箱C）根據收件人地址將郵件發送到對方服務器中D）根據收件人地址將其他郵件服器發送來的郵件分發到相應的電子郵箱B4、TCP/IP參考模型在下列哪一層定義了用戶數據報協議（UDP）？(2006.04)

A．鏈路層

B．網絡層

C．傳輸層

D．應用層C673、下列哪一項不屬于郵件服務器的主要功能？(2007.04)5、下列關于異步傳輸模式ATM技術的敘述中，哪一條是不正確的？

A．ATM技術可以滿足用戶對數據傳輸的服務質量的要求

B．ATM是B-ISDN選擇的數據傳輸技術

C．ATM技術的實時性好，但靈活性不夠

D．采用ATM技術可滿足網絡中突發性的通信量C(2005.09)6、電子郵件軟件向郵件服務器發送郵件時使用的協議是

(2005.09)A．SMTP

B．POP3

C．IMAP

D．MIMEA685、下列關于異步傳輸模式ATM技術的敘述中，哪一條是不正確的7、______不是網絡協議的要素。(2005.04)A）語法B）語義C）時態D）時序C8、若想在本地機上顯示Internet上的各種信息，要安裝運行一個軟件，該軟件是______。(2005.04)A）搜索引擎B）WWW瀏覽器C）電子郵件服務D）遠程登錄服務B697、______不是網絡協議的要素。(2005.04)6910、IP地址由網絡地址和主機地址組成，C類網絡的主機地址長度為

(2007.09)A、4B、6C、8D、12C

7010、IP地址由網絡地址和主機地址組成，C類網絡的主機地址長填空題1、Internet服務提供商（ISP）是用戶接入Intemet的入口點，一般用戶計算機接入Internet有兩種方式：一種是通過電話網，另一種是通過【2】

局域網2、針對采用TCP/IP協議聯網的主機數量增多情況，可以用【1】來管理和組織主機。域名71填空題1、Internet服務提供商（ISP）是用戶接入In3、在點—點網絡中，分組從通信子網的源節點到達目的結點的路由是由

【1】

決定的。路由器

4、【1】是用戶接入Internet的入口點，一方面它為用戶提供Internet接入服務，另一方面也為用戶提供各類信息服務ISP723、在點—點網絡中，分組從通信子網的源節點到達目的結點的路由過關練習1、用于實現網絡設備名字到IP地址映射的網絡服務是

A)TELNETB)SMTPC)DNSD)FTPC2、下列哪一個協議是Internet使用的協議？（本題分值：1分）

A．OSI參考模型中規定的傳輸層協議

B．TCP/IP傳輸控制/網間協議

C．IEEE802.3系列協議

D．幀中繼傳輸協議

B3、通常可用傳輸速率描述通信線路的數據傳輸能力，傳輸速率指的是

A．每秒鐘可以傳輸的中文字符個數

B．每秒鐘可以傳輸的字符數

C．每秒鐘可以傳輸的比特數

D．每秒鐘可以傳輸的文件數C73過關練習1、用于實現網絡設備名字到IP地址映射的網絡服務是

填空題1、聯網的各個計算機共享一個公共通道，當一臺計算機發送信息時，所有其他計算機都能“收聽”到此信息，這種網路稱為【1】網絡。

廣播網絡2、在通信網中，為了防止當發送能力大于接收能力時造成數據丟失的想象，要進行【2】流量控制74填空題1、聯網的各個計算機共享一個公共通道，當一臺計算機發送1.4信息安全基礎（3分）重點751.4信息安全基礎（3分）重點75考點1信息安全信息安全：防止非法攻擊和病毒傳播信息安全包括四方面內容：(保證電子信息有效性）

信息保密（confidentiality)

完整性integrity

可用性availability

可控性controllability涉及到網絡安全、操作系統安全、數據庫安全、信息系統安全方面內容76考點1信息安全信息安全：防止非法攻擊和病毒傳播76信息安全采用如下技術：信息保密信息認證密鑰管理防火墻病毒防護77信息安全采用如下技術：77考點2信息保密信息保密原理加密體制由5部分組成：明文空間、密文空間、加密密鑰空間、解密密鑰空間、加密和解密算法集78考點2信息保密信息保密原理加密體制由5部分組成：明文空間、現有加密體制分為兩種，一種是單鑰加密體制，也稱為私鑰或對稱加密體制（DES體制）；另一種是雙鑰加密體制（公鑰或非對稱加密）（RSA體制，大數分解和素性檢測理論）密碼體系中，加密、解密算法可以公開，但密鑰要保密，密鑰管理是關鍵。單鑰加密體制分為兩類：流密碼（明文逐位加密）和分組密碼（明文分組，逐組加密）79現有加密體制分為兩種，一種是單鑰加密體制，也稱為私鑰或對稱加考點3密鑰管理加密體制中關鍵是密鑰，密鑰泄露影響系統安全密鑰管理包括密鑰的產生、存儲、裝入、分配、保護、丟失、銷毀及保密等內容密鑰的分配和存儲是最關鍵和困難的問題密鑰管理與密鑰分配協議和密鑰協定有關。一般通過數字證書表明公鑰持有的合法性。公鑰證書是由一個可信機構簽發的關于某人的公開密鑰證書80考點3密鑰管理加密體制中關鍵是密鑰，密鑰泄露影響系統安全8考點4信息認證信息認證：驗證信息發送者的真實性（防假冒）和信息的完整性（防篡改）認證是防止對系統進行主動攻擊（偽造、篡改）的重要技術主動攻擊：通過增、刪、重放、偽造等手段主動向系統注入假信息。被動攻擊：對密文進行分析和識別。有關認證的實用技術中，主要的有數字簽名技術、身份識別技術和信息的完整性校驗技術。81考點4信息認證信息認證：驗證信息發送者的真實性（防假冒）和數字簽名通過簽名算法實現（發送者的真實性）（常采用公鑰體制）身份識別：基于密碼識別技術的身份識別有兩種方式，即通行字方式（口令）和持證方式。生物識別：個人特征（指）紋、聲紋、手形、視網膜、血型、基因、筆跡、習慣性簽字。已有的識別協議大都為詢問-應答協議（基于私鑰或公鑰密碼技術）。消息認證：①驗證消息的源與宿。（數字簽名和身份識別完成）②驗證消息的內容是否保持完整性，即未被篡改（摘要）②消息的序號利時間性。（防止消息重放）82數字簽名通過簽名算法實現（發送者的真實性）（常采用公鑰體制）考點5計算機病毒計算機病毒特征：

傳染性

破環性

隱蔽性

潛伏性

可激發性83考點5計算機病毒計算機病毒特征：83惡意軟件特洛依木馬（下載的非法程序）登錄陷阱（網絡釣魚，虛假頁面）邏輯炸彈（在程序中設置的破環代碼）后門陷阱（在程序中設置的繞開登錄進入系統）緩沖區溢出：僵尸網絡：一對多進行控制84惡意軟件84防火墻技術起到防止外界入侵的目的常用防火墻技術：1、包過濾防火墻：靜態包過濾防火墻和動態包過濾防火墻。要求：事先知道可信的IP地址2、代理防火墻即應用網關防火墻。增加了傳輸時間。85防火墻技術起到防止外界入侵的目的85考點6網絡安全構成對網絡安全威脅的主要因案及相關技術①網絡攻擊、攻擊檢測與防范。②網絡安全漏洞與安全對策。③網絡中的信息安全保密。④網絡內部安全防范。⑤網絡防病毒。⑥網絡數據備份與恢復、災難恢復86考點6網絡安全構成對網絡安全威脅的主要因案及相關技術861、網絡服務攻擊分類：

服務攻擊和非服務攻擊服務攻擊：對服務器發起攻擊，喪失服務能力，比如對WWW服務器攻擊，主頁被篡改非服務攻擊：對通信設備攻擊，使設備癱瘓2、網絡中的信息攻擊（安全保密）

信息存儲安全和傳輸安全信息存儲安全：操作系統、防火墻等完成871、網絡服務攻擊分類：87信息攻擊（傳輸安全）：防止信息泄露和被攻擊88信息攻擊（傳輸安全）：防止信息泄露和被攻擊8889893、網絡防病毒網絡防病毒軟件基本功能：查毒、檢查、隔離、報警等。允許用戶設置3中掃描方式：

實時掃描、預置掃描、人工掃描903、網絡防病毒90網絡安全服務的主要內容①安全攻擊；是指所有有損于網絡信息安全的操作。②安全機制：是指用于檢測、預防或從安全攻擊中恢復的機制。②安全服務：是指提高數據處理過程中的信息傳輸安全性服務。基木的安全服務功能①保密性：是防止傳輸的數據被截獲與篡改。②認證：用于解決網絡中信息傳送的源結點用戶與目的結點用戶身份的真實性。③數據完整性：用于保證發送信息與接收數據的一致性，防止出現信息在傳輸過程中被插入的問題。④防抵賴：用于保證源結點用戶與目的結點用戶不能對已發送或已接收的信息予以否認。⑥訪問控制：控制與限定網絡用戶對主機、應用程序、數據與網絡服務的訪問類型。91網絡安全服務的主要內容91考點7操作系統安全操作系統安全方法操作系統的安全措施一般可以從隔離、分層和內控3個方面來進行考慮。隔離可分為：①物理隔離：使不同安全要求的進程使用不同物理實體。②時間隔離：使不同進程在不同時間運行。③邏輯隔離：限制程序存取。④密碼隔離：進程以其他進程不知的方式隱蔽數據和計算92考點7操作系統安全操作系統安全方法92操作系統安全措施包括訪問控制、存儲保護及文件保護與保密。訪問控制：認證、訪問權限、文件保護、審計存儲保護：防止地址越界、防止操作越權93操作系統安全措施93考點8數據庫安全通過數據庫管理系統實現安全措施的層次①物理層②人員層③操作系統層④網絡層⑤數據庫系統層94考點8數據庫安全通過數據庫管理系統實現94權限和授權操作數據read(select)權限insertupdatedelete修改數據庫模式權限index,resource(關系）、alter(修改）、drop(刪除)最大數據庫權限給數據庫管理員DBA95權限和授權95權限的授予與回收grant 權限表on關系表to用戶表revoke權限表on關系表from用戶表96權限的授予與回收96（5）一般操作系統的安全措施可從隔離、分層和內控三個方面考慮，隔離是操作系統安全保障的措施之一。限制程序的存取，使其不能存取允許范圍以外的實體，這是

A）物理隔離

B）時間隔離

C）邏輯隔離

D）密碼隔離

（6）下列哪一個不屬于惡意軟件？

A）邏輯炸彈

B）服務攻擊

C）后門陷阱

D）僵尸網絡97（5）一般操作系統的安全措施可從隔離、分層和內控三個方面考慮在下載的普通程序中隱含了一些非法功能的代碼，用于竊取用戶私密信息或執行其他惡意程序，這種惡意軟件的攻擊方式稱為

A)特洛伊木馬

B)后門陷阱

C)邏輯炸彈

D)僵尸網絡2009.9A98在下載的普通程序中隱含了一些非法功能的代碼，用于竊取用戶私密哪個不屬于應用層協議？A、用戶數據報UDPB、文件傳輸協議FTPC、域名服務DNSD、電子郵件協議SMTPA2009.03下列關于域名和IP地址的敘述中，哪一條是不正確的？A、在Internet中訪問一臺主機必須使用它的主機名B、03是一個C類IP地址C、IP地址采用的分層結構D、主機名一IP地址是一一對應的A2008.0499哪個不屬于應用層協議？99考題1、一個數字簽名算法至少應該滿足三個條件，下列哪個不屬于數字簽名算法應滿足的條件：A簽名者事后不能否認自己的簽名B接收者能夠驗證簽名，其他人不能偽造簽名C數字簽名必須是所簽文件的物理部分D當發生簽名真偽爭執時，有第三方能夠解決爭執C2007092、一個功能完備的網絡系統應該提供基本的安全服務功能，其中解決網絡中信息傳輸源節點用戶與目的節點用戶身份真實性問題的功能是A保密B認證C完整性服務D訪問控制B200709100考題1、一個數字簽名算法至少應該滿足三個條件，下列哪個不屬于3、密鑰管理包括密鑰的產生、存儲、裝入、分配、保護、銷毀以及保密等內容，其中最關鍵和最困難的問題是A）密鑰的分配和存儲B）密鑰的產生和裝入C）密鑰的保護和保密D）密鑰的銷毀

A2007.044、信息認證是信息安全的一個重要方面，下列哪一項不屬于實施信息認證的方法？

A）身份識別

B）密鑰管理

C）數字簽名

D）消息認證B2006.091013、密鑰管理包括密鑰的產生、存儲、裝入、分配、保護、銷毀以及5、下列關于信息認證的敘述中，哪一項不正確A驗證體制中存在一個完成仲裁、頒發證書等功能的可信機構B數字簽名者事后不能否認自己的簽名C消息認證要檢驗的內容包括消息的序號和時間性D對密碼系統的主動攻擊是通過分析和識別截獲的密文完成D2006.096、下列哪一項不是網絡防病毒軟件允許用戶設置的掃描方式？A實時掃描B警告掃描C預置掃描D人工掃描B2006.091025、下列關于信息認證的敘述中，哪一項不正確1027、下列條目中，哪些屬于計算機病毒的特征？

I．傳染性

II．可激發性

III．隱蔽性

IV．潛伏性

A．只有I和III

B．只有I、II和IV

C．只有I、III和IV

D．都是

D2006.048、限制程序的存取，使操作系統不能存取允許范圍以外的實體，這種操作系統隔離安全措施稱為

A．物理隔離

B．時間隔離

C．邏輯隔離

D．密碼隔離C2006.041037、下列條目中，哪些屬于計算機病毒的特征？

I．傳染性

I9、______屬于實施操作系統安全措施的具體方案。I．認證II．訪問權限III．文件保護IV．審計A）僅I、II和IIIB）僅I、III和IVC）僅II、III和IVD）全部D2005.041049、______屬于實施操作系統安全措施的具體方案。104填空1、在密碼學中，將信息源稱作【1】明文2007.092、網絡安全技術的研究主要涉及三方面問題：

【2】

、安全機制和安全服務。安全攻擊2006.043、網絡攻擊者設法修改一個網站的主頁，使得該網站的WWW服務不能正常工作，這種網絡攻擊稱為

【2】

。服務攻擊2006.04105填空1、在密碼學中，將信息源稱作【1】1054、對于多個進程共享公共區域訪問限制和訪問檢查，是為了防止【1】操作越權1064、對于多個進程共享公共區域訪問限制和訪問檢查，是為了防止【過關練習1、下列身份識別技術中，哪一個屬于生物信息識別技術？

A)指紋B)密碼C)口令D)通行字

2、下列哪一項是對網絡進行非服務攻擊的結果？

A)網絡“拒絕服務”B)網絡通信設備嚴重阻塞

C)網站的主頁被涂改D)網站的WWW服務不能正常工作3下列哪一種方法不用于實現訪問控制?

A)存取控制表B)存取控制矩陣

C)口令D)保護鍵

ABD107過關練習1、下列身份識別技術中，哪一個屬于生物信息識別技術？三級數據庫技術第2章數據結構與算法108三級數據庫技術第2章數據結構與算法108本部分占總分的15%主要內容：數據結構與算法基本概念線性表的定義、存儲和運算樹型結構的定義、存儲和運算查找排序109本部分占總分的15%1092.1基本概念1102.1基本概念110考點1數據結構基本概念1、數據采用計算機能識別、存儲和處理的符號總稱。是對現實世界事務的描述

數據元素數據的基本單位，數據集合的個體一個數據元素由一個或多個數據項組成

數據項是數據的最小單位111考點1數據結構基本概念1、數據1112、數據結構數據之間的關系數據結構包括三方面內容：

邏輯關系、在計算機中的存儲方式、在數據上定義的運算集合1122、數據結構112數據結構數據的邏輯結構數據的存儲結構數據的運算線性結構→線性表→棧和隊列非線性結構→樹形結構(二叉樹、樹的遍歷)順序結構鏈式結構索引結構散列結構插入刪除查找－順序查找、二分法查找排序113數據數據的邏輯結構數據的存儲結構數據的運算線性結構→線性表→數據的邏輯結構什么是數據的邏輯結構？數據的邏輯結構是指數據元素之間的邏輯關系，與數據的存儲無關，是獨立于計算機的。數據的邏輯結構可分成2類線性結構非線性結構春夏秋冬父親兒子女兒114數據的邏輯結構什么是數據的邏輯結構？春夏秋冬父親兒子女兒11數據的存儲結構什么是數據的存儲結構？數據的存儲結構又稱為物理結構，是指數據元素及其關系在計算機內存中的表示，即數據的邏輯結構在計算機存儲器中的實現。數據的存儲結構可分為哪4類？順序結構、鏈式結構、索引結構、散列結構數據的存儲結構與邏輯結構的關系同一邏輯結構可以采用不同的存儲結構115數據的存儲結構什么是數據的存儲結構？115數據的運算定義在邏輯結構上，實現在存儲結構上116數據的運算定義在邏輯結構上，實現在存儲結構上116考點2主要的數據存儲方式順序存儲方式和鏈式存儲方式是最主要的內種存儲方式順序存儲方式，主要用于線性的數據結構，它把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里，結點之間的關系由存儲單元的鄰接關系來體現。（邏輯上相鄰物理上也相鄰）117考點2主要的數據存儲方式順序存儲方式和鏈式存儲方式是最主要線性表（K1,K2,K3,K4,K5)邏輯相鄰物理相鄰示意圖順序存儲結構的主要特點如下：①結點中沒有鏈接信息域，只有自身的信息域，存儲密度大，空間利用串高。②數據結構中第i個結點的存儲地址Li可由下述公式計算求得。Li＝L1十(i—1)×m其中，L1為第一個節點的存儲地址，m為每個節點所占用的存儲單元個數。②插入、刪除運算會引起相應結點的大量移動。118線性表（K1,K2,K3,K4,K5)邏輯相鄰1182．鏈式存儲方式線性表（K1,K2,K3,K4,K5)邏輯相鄰物理相鄰示意圖1192．鏈式存儲方式119鏈式存儲方式特點：有表示鏈接信息的指針,存儲空間利用率低,存儲密度小，邏輯上相鄰的結點在物理上不必鄰接，可用于線性表、樹和圖等多種邏輯結構的存儲表示插入、刪除操作靈活方便120鏈式存儲方式特點：120算法分析與設計算法的五個特征輸入（0個或多個輸入）輸出（1個或多個輸出）有窮性（在有限時間內完成）確定性（執行結果確定的）有效性（程序是可以實現的）算法分析---時間代價和空間代價121算法分析與設計121考題1、下列哪些是數據結構研究內容I、數據的采集與清洗II、數據的邏輯組織III、數據的集成V、數據傳輸IV、數據的檢索

A、僅II和IIIB、II和VC、僅I、II、IVD、I、III和IVB2009.042、下列哪個術語與數據存儲結構無關？A、順序表B、雙鏈表C、線性表D、散列表C122考題1、下列哪些是數據結構研究內容1223、下列與算法有關的敘述中，哪個不正確？A、運算是數據結構的一個重要方面，運算的實現步驟用算法描述B、算法是精確定義的一系列規則，它指出怎樣從給定輸入信息經過有限步驟產生輸出C、算法設計采用由粗到細，由抽象到具體逐步求精的方法D、對于算法的分析，指的是分析算法運行所要占用的機器時間，即算法的時間代價D2008.094、下列關于鏈式存儲結構敘述中，哪個選項正確？I、邏輯相鄰物理上不必相鄰II、每個節點都包含恰好一個指針域III、用指針體現元素邏輯聯系IV、結點中的指針都不能為空V、可以通過計算直接確定某個結點的存儲地址A、僅I和IIB、僅I和IIIC、僅I、III和VD、僅II、IV和VB2008.041233、下列與算法有關的敘述中，哪個不正確？1235、下列關于數據結構基本概念的敘述中，哪一條是不正確的？A）數據是采用計算機能夠識別、存儲和處理的方式，對現實世界的事物進行的描述B）數據元素（或稱結點、記錄等）是數據的基本單位C）一個數據元素至少由兩個數據項組成D）數據項是有獨立含義的數據最小單位C2007.046、下列關于鏈式存儲結構的敘述中，哪些是正確的？I邏輯上相鄰的結點物理上不必鄰接II每個結點都包含恰好一個指針域III用指針來體現數據元素之間邏輯上的聯系IV可以通過計算機直接確定第i個結點的存儲地址V存儲密度小于順序存儲結構A）I、II和IIIB）I、II、III和IVC）II、IV和VD）I、III和VD2007.041245、下列關于數據結構基本概念的敘述中，哪一條是不正確的？127、下列關于數據運算的敘述中，哪條不正確？A、數據運算是數據結構的一個重要方面B、數據運算的具體實現在數據的邏輯結構上進行C、檢索是一種常用的運算D、插入是一種常用的運算B1257、下列關于數據運算的敘述中，哪條不正確？125填空題1、數據結構包括三方面的內容：數據的邏輯結構、數據的存儲結構、數據的

【3】

運算2006.092、散列存儲的基本思想是由節點的【1】決定節點的存儲位置關鍵碼值126填空題1、數據結構包括三方面的內容：數據的邏輯結構、數據的存2.2線性表（重點）順序表鏈表棧隊列串1272.2線性表（重點）順序表127不同的存儲結構的線性表叫法不同順序存儲的線性表：順序表鏈式存儲的線性表：鏈表散列方式存儲的線性表：散列表在線性表上運算不同叫法不同插入和刪除在線性表一端，棧插入和刪除在線性表兩端進行，隊列128不同的存儲結構的線性表叫法不同128考點1順序表和一維數組順序表元素位置計算機

元素n…元素i…元素2元素1起始位置LoLo+mLo+(i-1)*mLo+(n-1)*mLi=L0+i*mi從0開始1、所有元素所占的存儲空間是連續的2、各元素在存儲空間中是按邏輯順序存放的129考點1順序表和一維數組順序表元素位置計算機元素n…元素i…順序表的插入和刪除元素移動次數插入算法的效率(數據元素的移動次數)最好情況：最壞情況：平均情況：0nn/2刪除算法的時間復雜度(數據元素的移動次數)最好情況：最壞情況：平均情況：0n-1(n-1)/2130順序表的插入和刪除元素移動次數插入算法的效率(數據元素的移動考點2鏈表（這兩年沒有考這個類型題）鏈式存儲方式就是在每個結點中至少包括一個指針域（存放下個結點的地址），用指針來體現數據元素之間邏輯上的聯系。鏈表分為線性鏈表和非線性鏈表1536元素21400元素11346元素3∧元素41345數據域指針域hh空指針鏈表中指針指向后繼結點，最后的結點指針為空(^,nil)需要一個指針head指向第一個結點鏈表的重要特點：插入和刪除靈活，只需修改指針131考點2鏈表（這兩年沒有考這個類型題）鏈式存儲方式就是在每個鏈表的查找、插入和刪除操作指針數據結點132鏈表的查找、插入和刪除操作指針數據結點132hppp查找結束線性鏈表的查找操作查找C133hppp查找結束線性鏈表的查找操作查找C133h線性鏈表的插入操作ab∧dchPQ×1、M↑link=Q2、P↑link=M或者1、M↑link=P↑link2、P↑link=M134h線性鏈表的插入操作ab∧dchPQ×1、M↑link=Q或線性鏈表的刪除操作刪除Q指向結點hab∧dchPQ×P↑link=Q↑link或P↑link=P↑link↑link135線性鏈表的刪除操作hab∧dchPQ×P↑link=Q↑循環鏈表a1ana2…h雙向鏈表a1∧a2an∧…ha1a2∧ana3…h線性鏈表136循環鏈表a1ana2…h雙向鏈表a1∧a2an∧…ha1a2考點3棧棧是一種特殊的線性表，是限定在一端進行插入和刪除的線性表（后進先出，LIFO。棧頂和棧底入棧和出棧（只能在棧頂進行）aaa…a入棧出棧棧頂n-1n21棧底棧可以順序存儲，也可以鏈式存儲137考點3棧棧是一種特殊的線性表，是限定在一端進行插入和刪除的棧的操作①push(s，x)：往棧s中插入(或推入)一個位為x的元素。②pop(s，x)：從棧s中刪除(或彈出)一個位為x的元素。②top(s，x)：把棧s的棧頂兒素讀到變量x中，棧保持不變。④empty(s)：判斷棧s是否為空棧，是則返問值為真。⑥Makempty(s)：將棧s置為空棧138棧的操作138考點4隊列隊列是一種特殊的線性表，允許在一端進行插入操作，在另一端進行刪除操作，FIFO(LILO)。隊頭和隊尾入隊和出隊出隊←a1a2…an←入隊↑隊頭↑隊尾139考點4隊列隊列是一種特殊的線性表，允許在一端進行插入操作，隊列的存儲方式也有順序存儲方式和鏈式存儲方式兩種140隊列的存儲方式也有順序存儲方式和鏈式存儲方式兩種140考點5串串(字符串)，是由零個或多個字符組成的有限序列注意：空串和空格串是不同的141考點5串串(字符串)，是由零個或多個字符組成的有限序列1考題1、基于以下描述：有一個初始為空的棧和輸入序列A、B、C、D、E、F、G：現發過如下操作：push,push,top,pop,push,push,top,push,pop,pop,pop.（10）下列哪一個是正確的從棧中刪除元素的序列？A）BEB）BDC）BEDCD）BDECA進棧，B進棧，讀B，B出棧，C進棧，D進棧，讀D，E進棧，E出棧，D出棧，C出棧C（11）下列哪一個是上述操作序列完成后棧中的元素列表（從底到頂）A）AB）BDC）ABCED）ABCDEA（2007.04）142考題1、基于以下描述：有一個初始為空的棧和輸入序列A、B、C2、棧S最多容納4個元素，現有6個元素A、B、C、D、E、F順序入棧，下列哪個序列是可能的出棧序列A、EDCBAFB、BCEFADC、CBEDAFD、ADFEBCA答案：只有4個元素，出棧的不可能為EB答案：A在D之后D答案：B在C之后C（2006.09）1432、棧S最多容納4個元素，現有6個元素A、B、C、D、E、F3、在包含1000個元素的線性表中實現如下各運算，哪一個所需的執行時間最短？

A．線性表按順序方式存儲，查找關鍵碼值為666的結點

B．線性表按鏈接方式存儲，查找關鍵碼值為666的結點

C．線性表按順序方式存儲，查找線性表中第900個結點

D．線性表按鏈接方式存儲，查找線性表中第900個結點C順序存儲適合隨機訪問（2005.09）4、在包含1000個元素的線性表中實現如下各運算，哪一個所需的執行時間最長？

A．線性表按順序方式存儲，在線性表的第100個結點后面插入一個新結點

B．線性表按鏈接方式存儲，在線性表的第100個結點后面插入一個新結點

C．線性表按順序方式存儲，刪除線性表的第900個結點

D．線性表按鏈接方式存儲，刪除指針P所指向的結點A移動元素時間長（2007.09，2005.09）1443、在包含1000個元素的線性表中實現如下各運算，哪一個所需6、從單鏈表中刪除指針S所指結點的下一個結點T，其關鍵步驟為A、S↑link=TB、T↑link=SC、T↑link=S↑linkD、S↑link=T↑linkD1456、從單鏈表中刪除指針S所指結點的下一個結點T，其關鍵步驟為7、下列哪一個不是隊列的基本運算？

A．從隊尾插入一個新元素

B．從隊列中刪除第i個元素

C．判斷一個隊列是否為空

D．讀取隊頭元素的值B8、棧結構不適用于下列哪一種應用？

A．表達式求值

B．樹的層次次序周游算法的實現

C．二叉樹對稱序周游算法的實現

D．快速排序算法的實現B1467、下列哪一個不是隊列的基本運算？

A．從隊尾插入一個新元1471472.3多維數組、稀疏矩陣和廣義表1482.3多維數組、稀疏矩陣和廣義表148考點1多維數組順序存儲一行n個元素a11149考點1多維數組順序存儲一行n個元素a11149考點2稀疏矩陣存儲下三角矩陣行優先數組存儲還可用三元組存儲、十字鏈表3123451245150考點2稀疏矩陣存儲下三角矩陣還可用三元組存儲、十字鏈表3考點3廣義表廣義線性表，零個或多個單元素或子表組成表中含表151考點3廣義表廣義線性表，零個或多個單元素或子表組成151考題1、以下關于廣義表的敘述中，哪一條是正確的？

A．廣義表是0個或多個單元素或子表組成的有限序列

B．廣義表至少有一個元素是子表

C．廣義表不可以是自身的子表

D．廣義表不能為空表A2、如下是一個稀疏矩陣的三元組法存儲表示和基于此表示所得出的相關敘述I.該稀疏矩陣有5行II.該稀疏矩陣有4列III.該稀疏矩陣有6個非0元素這些敘述中______是正確的。A）僅IB）I和IIC）僅IIID）全部C152考題1、以下關于廣義表的敘述中，哪一條是正確的？

A．廣義表2.4樹形結構（重點）1532.4樹形結構（重點）153154154考點1樹的定義樹是一種重要的樹型結構ABCDEFGHIJKLM根結點父結點結點D的子結點葉子結點該樹的度為3第0層第1層第2層第3層結點B的兩棵子樹度為3度為2該樹的深度為3155考點1樹的定義樹是一種重要的樹型結構ABCDEFGHIJK考點2二叉樹二叉樹是另一種樹形結構空樹或由根和左右子樹組成，左右子樹也是一棵二叉樹abcdefg左支樹右支樹根結點156考點2二叉樹二叉樹是另一種樹形結構abcdefg左支樹右支二叉樹和樹的區別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區別是，二叉樹的結點的子樹要區分左子樹和右子樹，即使在結點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。157二叉樹和樹的區別：二叉樹不是樹的特殊情況，157123114589121367101415123114589126710滿二叉樹完全二叉樹思考：給出完全二叉樹有n個結點，問有多少個葉子結點？深度是多少呢？滿二叉樹：每一層結點數達到最大完全叉樹：除最后一層外，其余每一層結點數達到最大，最后一層結點或滿，或右邊連續缺少若干結點最后一個非葉子結點[n/2]158123114589121367101415123114589考點3樹和二叉樹的轉換連兄弟，斷父子順時針旋轉45二叉樹轉換為樹，斷右子女，連父親159考點3樹和二叉樹的轉換連兄弟，斷父子二叉樹轉換為樹，斷右子森林轉換為二叉樹ABCDEFABCDEFABCDEF160森林轉換為二叉樹ABCDEFABCDEFABCDEF160考點4二叉樹和樹的周游（遍歷）遍歷：按一定次序訪問所有結點，并且每個結點只被訪問一次二叉樹的周游（遍歷）按訪問根的次序：二叉樹的周游主要有三種方式①前序法(NLR)：訪問根，按前序周游左子樹，按前序周游右子樹②后序法(LRN)：按后序周游左子樹，按后序周游右子樹，訪問根③對稱（中序）法(LNR)：按對稱序周游左子樹，訪問根，按對稱序周游右子樹161考點4二叉樹和樹的周游（遍歷）遍歷：按一定次序訪問所有結點ADBCNLRANLRNLR>B>>D>>CNLR先序遍歷序列：ABDC前序遍歷:162ADBCNLRADBCLNRBLNRLNR>A>>D>>CLNR中序遍歷序列：BDAC中序遍歷:163ADBCLNRADBCLRNLRNLRN>A>>D>>CLRN后序遍歷序列：DBCA后序遍歷:B164ADBCLR周游樹和森林對樹和森林的周游分為按深度優先和按廣度優先兩種方式樹深度優先：先根次序（對應二叉樹的前序）和后根次序（對應二叉樹的中序序）周游森林的先序和后序號對應二叉樹的先序和中序樹廣度優先：按層次訪問先根后根廣度165周游樹和森林先根后根廣度165考點5二叉樹的存儲和線索二叉樹二叉樹的llink-rlink法存儲表示指向右子樹根指向左子樹根166考點5二叉樹的存儲和線索二叉樹二叉樹的llink-rlin線索二叉樹，n個結點，n+1個空指針（n個結點，2n個指針，n-1個指針指向結點）中序遍歷DBGEACHFI167線索二叉樹，n個結點，n+1個空指針（n個結點，2n個指針，完全二叉樹存儲完全二叉樹中除最下面一層外，各層都被結點充滿了，每一層結點個數是上一層結點個數的2倍。i2i2i+1168完全二叉樹存儲i2i2i+1168考點6哈夫曼樹（huffman)(霍夫曼樹）最優二叉樹樹的帶權路徑長度最小的樹樹的帶權路徑長度：各個葉子結點到根的路徑長度與結點權值乘積之和WPL=169考點6哈夫曼樹（huffman)(霍夫曼樹）最優二叉樹樹的Huffman算法求最優二叉樹1012162130結點權值如下：101224162130第一步（最小的兩棵樹構成新樹10122416213037第二步單結點森林170Huffman算法求最優二叉樹1012162130結點權值10122416213037第二步10122416213037第三步5410122416213037第四步5491求WPL17110122416213037第二步101224162130考題1、下列關于二叉樹周游的敘述中，哪一條是正確的？

A）若一個結點是二叉樹的對稱序最后一個結點，則它必是該二叉樹的前序最后一個結點

B）若一個結點是某二叉樹的前序最后一個結點，則它必是該二叉樹的對稱序最后一個結點

C）若一個樹葉是某二叉樹的對稱序最后一個結點，則它必是該二叉樹的前序最后一個結點

D）若一個樹葉是某二叉樹的前序最后一個結點，則它必是該二叉樹的對稱序最后一個結點

C2009.04（右子樹為空）AB對稱序BA前序AB172考題1、下列關于二叉樹周游的敘述中，哪一條是正確的？

2、按層次次序將一棵有n個結點的完全二叉樹的所有結點從1到n編號，當i<n/2時，編號為i的結點的左子女的編號為

A）2i-1

B）2i

C）2i+1

D）不確定B

2009.04

1732、按層次次序將一棵有n個結點的完全二叉樹的所有結點從1到n1）該二叉樹對應的樹林包括幾棵樹？2008。04A、1B、2C、3D、4C（根結點右子樹轉換為樹）2）如果用llink-rlink存儲該二叉樹，則各結點指針域共包含多少空指針A、0B、4C、8D、12CN+13）如果將該二叉樹存儲為對稱序線索二叉樹，則結點C的左線索指向哪個結點？A、結點AB、結點BC、結點ED、結點G對稱序：DBGEACFA1741）該二叉樹對應的樹林包括幾棵樹？2008。04174試題（12）—（14）基于如下所示的二叉樹。2007.04（12）該二叉樹對應的樹林包括幾棵樹？A）1B)2C）3D）4B去掉右子樹與父親連線（13）按后根次序周游該二叉樹對應的樹林，所得到的結點序列為A）DBAFEGCB）ABCDEFGC）DBFGECAD）ACBEGDFA后根訪問第一課樹的子樹，訪問第一棵樹的根，后根訪問其他樹（二叉樹的中序（14）按層次次序周游該二叉對應的樹林，所得到的結點序列為A）DBAFEGCB）ABCDEFGC）DBFGECAD）ACBEGDFD175試題（12）—（14）基于如下所示的二叉樹。2007.04填空1、一棵二叉樹結點的前序序列為A、B、D、E、G、C、F、H、I，對稱序序列為D、B、G、E、A、C、H、F、I，則該二叉樹結點的后序序列為

【4】A為根結點，對稱序列中D，B，G，E為左子樹，B為左子樹根

ABDEGCFHI176填空1、一棵二叉樹結點的前序序列為A、B、D、E、G、C、F2.5查找在數據結構中找出滿足條件的結點的過程1772.5查找在數據結構中找出滿足條件的結點的過程177考點1順序查找逐個依次查找，對邏輯次序無要求（不必排序），可以是順序存儲也可以是鏈式存儲優點：簡單缺點：速度慢，檢索長度與結點N成正比178考點1順序查找逐個依次查找，對邏輯次序無要求（不必排序），考點2二分查找線性表結點必須按關鍵碼值排序，以順序存儲方式存儲的（考概念）二分查找過程（查找612）179考點2二分查找線性表結點必須按關鍵碼值排序，以順序存儲方式例題1：對線性表進行二分法檢索，其前提條件是：線性表以【1】方式存儲，并且按關鍵碼值排好序。180例題1：對線性表進行二分法檢索，其前提條件是：線性表以【1考點3分塊查找線性表分塊每塊不必有序塊間有序查找過程1、在索引表中確定記錄所在塊2、在塊中查找記錄索引表181考點3分塊查找線性表分塊索引表181考點4散列表的存儲和查找（重點）散列表（哈希表）：利用散列法構建的線性表，是一種重要的存儲方式和檢索方式基本思想：1、由結點的關鍵碼k通過散列函數f(k)決定結點的存儲地址2、將結點存入該地址，查找的時候，通過該散列函數取得地址，讀取結點數據182考點4散列表的存儲和查找（重點）散列表（哈希表）：利用散列由于采用函數值作為地址，不同關鍵碼函數值可能相同，即K1<>K2,但f(k1)=f(k2)，這就產生了碰撞（沖突）碰撞處理：開放地址法（線性探測法）和拉鏈法開放地址法：當在d地址發生碰撞時，按如下序列進行探查d+1,d+2,m-1,0,1,..d-1183由于采用函數值作為地址，不同關鍵碼函數值可能相同，即K1<>例題1：設散列表的地址空間為0到12，散列函數為h（k）=kmod13,用線性探查法解決碰撞。現從空的散列表開始，依次插入關鍵碼值14,95,24,61，27,82,69,

則最后一個關鍵碼69的地址為【4】。求地址：h(14)=1地址數據h(95)=4h(24)=11h(61)=9h(27)=1產生沖突地址+1h(82)=4產生沖突地址+1h(69)=4產生沖突地址+1，+114279582696124184例題1：設散列表的地址空間為0到12，散列函數為h（k）=k負載因子（裝填因子）上題的負載因子7/13=185負載因子（裝填因子）上題的負載因子7/13=185考點5樹形結構與查找二叉排序樹（適合內存查找）特點：結點左子樹所有結點關鍵碼都小于該結點關鍵碼，右子樹所有結點都大于該結點關鍵碼中序周游（遍歷）為有序序列186考點5樹形結構與查找二叉排序樹（適合內存查找）中序周游（遍極端情況，檢索達n次187極端情況，檢索達187B樹和B+樹（適合于外存查找）B樹是一種平衡多路查找樹188B樹和B+樹（適合于外存查找）188至少有[M/2]-1個關鍵碼,最多M-1個關鍵碼NULL189至少有[M/2]-1個關鍵碼,最多M-1個關鍵碼NULL18B樹的插入結點和刪除結點仍然要滿足B樹特征190B樹的插入結點和刪除結點仍然要滿足B樹特征190以下兩題基于圖3-8所示的5階B樹結構1、向該B樹中插入關鍵碼72后，該B樹第2層結點數為（）A、6B、7C、8D、9C2、從該B樹中刪除關鍵碼15后，該B樹的第2層結點數為()A、6B、7C、8D、9B351018456082258111523263038414753647073788695191以下兩題基于圖3-8所示的5階B樹結構1、向該B樹中插入關鍵結點分支多于5個，需要分為兩個結點每個結點至少含2個關鍵碼（分裂）351018456082258111523263038414753647073788695647072737845607282

38414753607073788695中間關鍵碼至少為[5/2]-12,最多4個192結點分支多于5個，需要分為兩個結點35101845刪除15結點只剩一個關鍵碼，不滿足要求從右邊移一個元素（合并）3510184560822581115232630384147536470737886951115102325811182630中間關鍵碼至少為[5/2]-12,最多4個193刪除15結點只剩一個