計算機基礎《三級數(shù)據(jù)庫技術》考試培訓-筆試部分課件

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

為基礎，由

五大部分組成

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

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

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

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

A)雷達

B)彩色電視機

C)數(shù)字音視頻設備

D)數(shù)字圖像處理設備

B2009.914考題下列哪一個不是指令系統(tǒng)中包含的指令類型

A存儲控制類指令B數(shù)據(jù)傳送類指令

C算術邏輯類指令D判定控制類指令A15（1）馮·諾依曼奠定了現(xiàn)代計算機工作原理的基礎。下列敘述中，哪個（些）是正確的？

I．程序必須裝入內(nèi)存才能執(zhí)行

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

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

A）僅I

B）僅I和II

C）僅II和III

D）都正確

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

A）立即尋址

B）直接尋址

C）寄存器尋址

D）寄存器間接尋址

161下列哪一項指標在實時控制系統(tǒng)時不需要滿足？A、可靠性B、實時性C、交互性D、抗干擾性答案C2用計算機進行導彈飛行軌道的計算，屬于下列哪一個計算機應用領域？A．人工智能B．過程控制C．輔助設計D．科學和工程計算

D173通常一臺計算機系統(tǒng)的存儲介質(zhì)包括Cache、內(nèi)存、磁帶和硬盤，其中訪問速度最慢的是

A．Cache

B．磁帶

C．硬盤

D．內(nèi)存

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

A．中央處理器直接對存儲器中的數(shù)據(jù)進行處理

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

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

D．程序和數(shù)據(jù)均存放在存儲器中

D185計算機硬件系統(tǒng)中，完成解釋指令、執(zhí)行指令的部件是______。

A）運算器B）控制器C）存儲器D）輸入輸出設備B6下列哪一種設備不是輸入設備？A鍵盤B光筆C數(shù)/模轉換器D聲音識別器C19填空題1將文本、音頻、視頻、動畫、圖形和圖像等各種媒體綜合起來的技術稱為【1】技術多媒體2計算機是由運算器、

【1】

、存儲器、輸入設備和輸出設備這5個主要功能部件組成的，它們被稱為計算機的五大硬件控制器201.2計算機軟件21考點1計算機語言機器語言依賴于硬件0，1二進制代碼，運行速度快不易被人識別（最初級語言）匯編語言

助記符表示指令的語言，易于理解和記憶，計算機不能識別，經(jīng)過匯編程序翻譯成機器語言執(zhí)行（仍然依賴機器，低級語言）2223高級語言人工設計語言，接近人的理解，對算法描述特點：獨立硬件、可移植和通用性好Basic:普及性會話語言Fortran:科學及工程計算Pascal:教學語言C語言：系統(tǒng)開發(fā)C++：面向?qū)ο笳Z言Cobol:商業(yè)事務處理和金融Prolog:人工智能語言

24高級語言程序機器語言編譯編譯程序運行結果運行編譯過程25考點2系統(tǒng)軟件操作系統(tǒng)，系統(tǒng)軟件的核心語言處理程序（解釋程序和編譯程序）數(shù)據(jù)庫管理系統(tǒng)服務性程序（調(diào)試程序、糾錯程序、診斷程序）26考點3應用軟件27計算機系統(tǒng)技術指標運算速度MIPS(MillionInstructionsPerSecond)主頻GHZ字長：一次處理的二進制位數(shù)存儲容量GMKB（1024）數(shù)據(jù)傳輸率1Kb1Mb1Gb的關系（1000）28計算機中的信息表示進制轉換

10-2進制轉換：除2取余

2-8進制：從右到左每三位一組，轉換為8進制數(shù)

2-16進制：從右到左每四位一組，轉換為16進制數(shù)小數(shù)部分從左到右每三位或四位一組29（10）10-()2(10.1)2->()10或8進制到10進制（10001001.10）2->（）830原碼、反碼和補碼正整數(shù)，原碼、反碼和補碼一樣，都是正數(shù)本身。負整數(shù)，原碼的符號位為1，數(shù)值部分取絕對值反碼的符號位為1，其他位是原碼取反補碼的符號位為1，其他位原碼取反，加1.如：29-2931服務程序是一類輔助性程序，它提供各種軟件運行時所需的服務，下列哪一個屬于服務程序？A)語言處理程序B）調(diào)試程序C）操作系統(tǒng)D）數(shù)據(jù)庫管理系統(tǒng)32八進制數(shù)1507轉換成十進制數(shù)是多少2009.1033考題1、完成輔助診斷疾病的軟件屬于下列哪一類計算機軟件？

A）系統(tǒng)軟件

B、科學計算軟件

C）人工智能軟件

D、數(shù)據(jù)和信息處理軟件C2、下列有關高級語言的敘述中，哪一個是不正確的？A）高級語言又稱為算法語言B）高級語言獨立于計算機硬件C）高級語言程序可以直接在計算機上執(zhí)行D）用高級語言編寫的程序其通用性和移植性好C343、計算機軟件分為系統(tǒng)軟件和應用軟件兩大類，其中處于系統(tǒng)軟件核心地位的是

A)操作系統(tǒng)

B）編譯程序

C）數(shù)據(jù)庫管理系統(tǒng)

D）網(wǎng)絡通信軟件

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

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

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

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

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

A．操作系統(tǒng)

B．編譯程序

C．數(shù)據(jù)庫管理系統(tǒng)

D．網(wǎng)絡通信軟件A6、匯編語言是一種符號語言，通常用指令功能的英文詞縮寫代替操作碼。助記符MOV表示的指令是______。

A）加法B）中斷C）空操作D）傳送D367、下列關于系統(tǒng)軟件的敘述中，哪個不正確？A)操作系統(tǒng)管理系統(tǒng)的軟硬件資源B)解釋程序?qū)⒃闯绦蜣D換為目標程序，邊解釋邊執(zhí)行C）Informix是一種數(shù)據(jù)庫管理系統(tǒng)D）故障診斷程序是一類服務程序B37填空題1、語言處理程序應屬于【1】軟件系統(tǒng)38過關練習1、下列哪一項不屬于系統(tǒng)軟件？

A)調(diào)試程序B)計算機輔助設計程序

C)編譯程序D)數(shù)據(jù)庫管理系統(tǒng)

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

A．系統(tǒng)軟件是在應用軟件基礎上開發(fā)的

B．系統(tǒng)軟件應提供友好的人機界面

C．系統(tǒng)軟件與硬件密切相關

D．系統(tǒng)軟件與具體應用領域無關

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

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

BAA391.3計算機網(wǎng)絡基礎（4分）重點40考點1計算機網(wǎng)絡概述計算機網(wǎng)絡是通信技術與計算機技術緊密結合的產(chǎn)物．計算機網(wǎng)絡的發(fā)展歷史

(1)具有通信功能的單機系統(tǒng)階段

(2)具有通信功能的多機系統(tǒng)階段

(3)計算機網(wǎng)絡階段計算機網(wǎng)絡特征

1、資源共享：硬件共享、軟件共享、數(shù)據(jù)共享

2、自治計算機

3、共同網(wǎng)絡協(xié)議：語法（結構和格式）、語義（意義）、時序（事件的執(zhí)行順序）41考點2計算機網(wǎng)絡分類分類方法（1）根據(jù)傳輸技術分類：廣播式網(wǎng)絡與點-點網(wǎng)絡(2)根抓網(wǎng)絡的覆蓋范圍與規(guī)模分類：局域網(wǎng)（LAN）、城域問（MAN)及廣域網(wǎng)(WAN）局域網(wǎng)：（以太網(wǎng)、令牌總線和令牌環(huán)）決定局域網(wǎng)特性主要技術要素為網(wǎng)絡拓撲、傳輸介質(zhì)與介質(zhì)訪問控制方法（共享式和交換式局域網(wǎng)）局域網(wǎng)常用的傳輸介質(zhì)有：同軸電纜、雙絞線、光纖與無線通信信道。42城域網(wǎng)：早期城域網(wǎng)主要采用光纖分布式數(shù)據(jù)接口FDDI

具有雙環(huán)結構，容錯能力具有動態(tài)分配帶寬能力共同特點：傳輸介質(zhì)采用光纖，交換接點采用基于IP交換的高速路由交換機或ATM交換機，在體系結構上采用核心交換層，業(yè)務匯聚層與接入層三層模式。城域網(wǎng)MAN介于廣域網(wǎng)與局域網(wǎng)之間的一種高速網(wǎng)絡。廣域網(wǎng)（分組交換技術）（X.25,幀中繼、ISDN,ATM)

大容量與突發(fā)性通信要求綜合業(yè)務服務要求

開放設備接口與規(guī)范化的協(xié)議完善的通信服務和網(wǎng)絡管理43X．25：建立在速率低、誤碼率高的電纜介質(zhì)上，X.25協(xié)議包括差錯控制、流量控制和擁塞控制等，由通信子網(wǎng)完成。FR（幀中繼）：建立在速率高、誤碼率低的光纖上，對X.25協(xié)議進行簡化，差錯控制由用戶終端完成。B-ISDN（寬帶綜合業(yè)務數(shù)字網(wǎng)）、N-ISDN（窄帶綜合業(yè)務數(shù)字網(wǎng)）ATM（異步傳輸模式，一種數(shù)據(jù)傳輸與分組交換技術，能滿足多媒體應用的高速率與低延遲的要求，具有線路交換實時性好和分組交換靈活性好的雙重優(yōu)點。44考點3Internet基礎1、Internet的形成和發(fā)展（1）TCP/IP協(xié)議與ARPnet結合，使ARPnet成為Internet的主干網(wǎng)（2）NSFnet是第一個使用TCP/IP的廣域網(wǎng)（3）Internet實現(xiàn)了TCP/IP參考模型與協(xié)議的結合，TCP/IP協(xié)議不受主機、操作系統(tǒng)的限制452、Internet結構與組成

Internet是通過網(wǎng)絡互聯(lián)設備-路由器連接起來的大型廣域網(wǎng)（通信線路、路由器、主機、信息資源）46路由器：為數(shù)據(jù)包選擇路徑。4748

3、TCP/IP協(xié)議、域名與IP地址（重點）TCP/IP協(xié)議組的四個層次應用層傳輸層網(wǎng)絡層物理層TCPUDPIP49應用層協(xié)議：網(wǎng)絡終端協(xié)議TELNET,實現(xiàn)遠程登錄文件傳送協(xié)議FTP

域名服務協(xié)議DNS，實現(xiàn)域名到IP地址映射路由信息協(xié)議RIP，交換路由信息電子郵件協(xié)議SMTP

HTTP協(xié)議，WWW服務50域名與IP地址域名和IP地址是Internet上的兩種地址表示形式IP地址由網(wǎng)絡地址和機器地址組成IP地址長度為32位，X.X.X.X表示，X為8為，表示0-255,(點分十進制地址）51A類：7位24位B類：14位16位C類：21位8位網(wǎng)絡地址機器地址010110---52域名

IP地址數(shù)字，難記憶，出現(xiàn)字符型主機名即域名格式主機名.組名.網(wǎng)點名

域名與IP地址一一對應53考點4Internet提供的主要服務WWW服務：超文本和超媒體是WWW信息組織形式（鏈接）使用的協(xié)議HTTP（Hypertexttransferprotocol)54HTML(超文本標記語言)和HTTP（超文本傳輸協(xié)議）是WWW工作的基礎55URL:統(tǒng)一資源定位器（uniformResourceLocator),定位頁面56電子郵件服務（E-Mail)

由郵件服務器、電子郵箱組成，并規(guī)定電子郵件書寫規(guī)則工作原理發(fā)送方郵件服務器發(fā)送方接收方郵件服務器接收方SMTP簡單郵件傳輸協(xié)議POP3、IMAP郵局協(xié)議交互式郵件存取協(xié)議FTP郵箱57電子郵件內(nèi)容協(xié)議MIME(MultipurposeInternetMailExtensions)，可以傳送圖像、聲音等多媒體信息58考點5Internet基本接入方式局域網(wǎng)接入數(shù)據(jù)通信網(wǎng)（X.25,DDN,ADSL,ISDN）

ISP（InternetServiceProvider，ISP）Internet服務提供商，為用戶提供接入和提供信息服務59電話網(wǎng)接入60ADSL(AsymmetricalDigitalSubscriberLoop)非對稱數(shù)字用戶環(huán)路。用戶通過電信接入Internet，普遍采用ADSL方式?；陔娫捑€，上、下行傳輸速率不同，上行（從用戶到網(wǎng)絡）為低速，可達1Mbps；下行（從網(wǎng)絡到用戶）為高速，可達8Mbps。傳輸距離有限制：3-5km61下列關于ADSL技術的敘述中，哪些是正確的？

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

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

Ⅲ.ADSL寬帶接入方式可用于網(wǎng)絡互聯(lián)業(yè)務

A)僅Ⅰ和Ⅱ

B)僅Ⅱ和Ⅲ

C)僅Ⅰ和Ⅲ

D)全部

C2009.962（3）用于實現(xiàn)Internet中文件傳輸功能所采用的應用層協(xié)議是

A）FTP

B）DNS

C）SMTP

D）HTTP

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

A）FTP

B）DNS

C）SMTP

D）HTTP

63數(shù)據(jù)包要求從源主機出發(fā)，最終到目的主機。下列哪一個設備可為數(shù)據(jù)包選擇輸出路徑，將它從一個網(wǎng)絡傳送到另一個網(wǎng)絡？

A)通信線路

B)路由器

C)WWW服務器

D)調(diào)制解調(diào)器

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

Ⅰ.簡單郵件傳輸協(xié)議SMTP

Ⅱ.郵局協(xié)議POP3

Ⅲ.交互式郵件存取協(xié)議IMAP

A)僅Ⅰ

B)僅Ⅱ

C)僅Ⅱ和Ⅲ

C)僅Ⅰ和Ⅲ

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

A．鏈路層

B．網(wǎng)絡層

C．傳輸層

D．應用層C675、下列關于異步傳輸模式ATM技術的敘述中，哪一條是不正確的？

A．ATM技術可以滿足用戶對數(shù)據(jù)傳輸?shù)姆召|(zhì)量的要求

B．ATM是B-ISDN選擇的數(shù)據(jù)傳輸技術

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

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

(2005.09)A．SMTP

B．POP3

C．IMAP

D．MIMEA687、______不是網(wǎng)絡協(xié)議的要素。(2005.04)A）語法B）語義C）時態(tài)D）時序C8、若想在本地機上顯示Internet上的各種信息，要安裝運行一個軟件，該軟件是______。(2005.04)A）搜索引擎B）WWW瀏覽器C）電子郵件服務D）遠程登錄服務B6910、IP地址由網(wǎng)絡地址和主機地址組成，C類網(wǎng)絡的主機地址長度為

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

70填空題1、Internet服務提供商（ISP）是用戶接入Intemet的入口點，一般用戶計算機接入Internet有兩種方式：一種是通過電話網(wǎng)，另一種是通過【2】

局域網(wǎng)2、針對采用TCP/IP協(xié)議聯(lián)網(wǎng)的主機數(shù)量增多情況，可以用【1】來管理和組織主機。域名713、在點—點網(wǎng)絡中，分組從通信子網(wǎng)的源節(jié)點到達目的結點的路由是由

【1】

決定的。路由器

4、【1】是用戶接入Internet的入口點，一方面它為用戶提供Internet接入服務，另一方面也為用戶提供各類信息服務ISP72過關練習1、用于實現(xiàn)網(wǎng)絡設備名字到IP地址映射的網(wǎng)絡服務是

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

A．OSI參考模型中規(guī)定的傳輸層協(xié)議

B．TCP/IP傳輸控制/網(wǎng)間協(xié)議

C．IEEE802.3系列協(xié)議

D．幀中繼傳輸協(xié)議

B3、通?？捎脗鬏斔俾拭枋鐾ㄐ啪€路的數(shù)據(jù)傳輸能力，傳輸速率指的是

A．每秒鐘可以傳輸?shù)闹形淖址麄€數(shù)

B．每秒鐘可以傳輸?shù)淖址麛?shù)

C．每秒鐘可以傳輸?shù)谋忍財?shù)

D．每秒鐘可以傳輸?shù)奈募?shù)C73填空題1、聯(lián)網(wǎng)的各個計算機共享一個公共通道，當一臺計算機發(fā)送信息時，所有其他計算機都能“收聽”到此信息，這種網(wǎng)路稱為【1】網(wǎng)絡。

廣播網(wǎng)絡2、在通信網(wǎng)中，為了防止當發(fā)送能力大于接收能力時造成數(shù)據(jù)丟失的想象，要進行【2】流量控制741.4信息安全基礎（3分）重點75考點1信息安全信息安全：防止非法攻擊和病毒傳播信息安全包括四方面內(nèi)容：(保證電子信息有效性）

信息保密（confidentiality)

完整性

integrity

可用性

availability

可控性

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

傳染性

破環(huán)性

隱蔽性

潛伏性

可激發(fā)性83惡意軟件特洛依木馬（下載的非法程序）登錄陷阱（網(wǎng)絡釣魚，虛假頁面）邏輯炸彈（在程序中設置的破環(huán)代碼）后門陷阱（在程序中設置的繞開登錄進入系統(tǒng)）緩沖區(qū)溢出：僵尸網(wǎng)絡：一對多進行控制84防火墻技術起到防止外界入侵的目的常用防火墻技術：

1、包過濾防火墻：靜態(tài)包過濾防火墻和動態(tài)包過濾防火墻。要求：事先知道可信的IP地址

2、代理防火墻即應用網(wǎng)關防火墻。增加了傳輸時間。85考點6網(wǎng)絡安全構成對網(wǎng)絡安全威脅的主要因案及相關技術①網(wǎng)絡攻擊、攻擊檢測與防范。②網(wǎng)絡安全漏洞與安全對策。③網(wǎng)絡中的信息安全保密。④網(wǎng)絡內(nèi)部安全防范。⑤網(wǎng)絡防病毒。⑥網(wǎng)絡數(shù)據(jù)備份與恢復、災難恢復861、網(wǎng)絡服務攻擊分類：

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

信息存儲安全和傳輸安全信息存儲安全：操作系統(tǒng)、防火墻等完成87信息攻擊（傳輸安全）：防止信息泄露和被攻擊88893、網(wǎng)絡防病毒網(wǎng)絡防病毒軟件基本功能：查毒、檢查、隔離、報警等。允許用戶設置3中掃描方式：

實時掃描、預置掃描、人工掃描90網(wǎng)絡安全服務的主要內(nèi)容①安全攻擊；是指所有有損于網(wǎng)絡信息安全的操作。②安全機制：是指用于檢測、預防或從安全攻擊中恢復的機制。②安全服務：是指提高數(shù)據(jù)處理過程中的信息傳輸安全性服務?；镜陌踩展δ堍俦Ｃ苄裕菏欠乐箓鬏?shù)臄?shù)據(jù)被截獲與篡改。②認證：用于解決網(wǎng)絡中信息傳送的源結點用戶與目的結點用戶身份的真實性。③數(shù)據(jù)完整性：用于保證發(fā)送信息與接收數(shù)據(jù)的一致性，防止出現(xiàn)信息在傳輸過程中被插入的問題。④防抵賴：用于保證源結點用戶與目的結點用戶不能對已發(fā)送或已接收的信息予以否認。⑥訪問控制：控制與限定網(wǎng)絡用戶對主機、應用程序、數(shù)據(jù)與網(wǎng)絡服務的訪問類型。91考點7操作系統(tǒng)安全操作系統(tǒng)安全方法操作系統(tǒng)的安全措施一般可以從隔離、分層和內(nèi)控3個方面來進行考慮。隔離可分為：①物理隔離：使不同安全要求的進程使用不同物理實體。②時間隔離：使不同進程在不同時間運行。③邏輯隔離：限制程序存取。④密碼隔離：進程以其他進程不知的方式隱蔽數(shù)據(jù)和計算92操作系統(tǒng)安全措施包括訪問控制、存儲保護及文件保護與保密。訪問控制：認證、訪問權限、文件保護、審計存儲保護：防止地址越界、防止操作越權93考點8數(shù)據(jù)庫安全通過數(shù)據(jù)庫管理系統(tǒng)實現(xiàn)安全措施的層次①物理層②人員層③操作系統(tǒng)層④網(wǎng)絡層⑤數(shù)據(jù)庫系統(tǒng)層94權限和授權操作數(shù)據(jù)

read(select)權限

insertupdatedelete修改數(shù)據(jù)庫模式權限index,resource(關系）、alter(修改）、drop(刪除)最大數(shù)據(jù)庫權限給數(shù)據(jù)庫管理員DBA95權限的授予與回收

grant 權限表on關系表to用戶表

revoke權限表on關系表from用戶表96（5）一般操作系統(tǒng)的安全措施可從隔離、分層和內(nèi)控三個方面考慮，隔離是操作系統(tǒng)安全保障的措施之一。限制程序的存取，使其不能存取允許范圍以外的實體，這是

A）物理隔離

B）時間隔離

C）邏輯隔離

D）密碼隔離

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

A）邏輯炸彈

B）服務攻擊

C）后門陷阱

D）僵尸網(wǎng)絡97在下載的普通程序中隱含了一些非法功能的代碼，用于竊取用戶私密信息或執(zhí)行其他惡意程序，這種惡意軟件的攻擊方式稱為

A)特洛伊木馬

B)后門陷阱

C)邏輯炸彈

D)僵尸網(wǎng)絡2009.9A98哪個不屬于應用層協(xié)議？

A、用戶數(shù)據(jù)報UDPB、文件傳輸協(xié)議FTPC、域名服務DNSD、電子郵件協(xié)議SMTPA2009.03下列關于域名和IP地址的敘述中，哪一條是不正確的？A、在Internet中訪問一臺主機必須使用它的主機名B、03是一個C類IP地址C、IP地址采用的分層結構D、主機名一IP地址是一一對應的A2008.0499考題1、一個數(shù)字簽名算法至少應該滿足三個條件，下列哪個不屬于數(shù)字簽名算法應滿足的條件：

A簽名者事后不能否認自己的簽名

B接收者能夠驗證簽名，其他人不能偽造簽名

C數(shù)字簽名必須是所簽文件的物理部分

D當發(fā)生簽名真?zhèn)螤巿?zhí)時，有第三方能夠解決爭執(zhí)C2007092、一個功能完備的網(wǎng)絡系統(tǒng)應該提供基本的安全服務功能，其中解決網(wǎng)絡中信息傳輸源節(jié)點用戶與目的節(jié)點用戶身份真實性問題的功能是A保密B認證C完整性服務D訪問控制B2007091003、密鑰管理包括密鑰的產(chǎn)生、存儲、裝入、分配、保護、銷毀以及保密等內(nèi)容，其中最關鍵和最困難的問題是A）密鑰的分配和存儲B）密鑰的產(chǎn)生和裝入C）密鑰的保護和保密D）密鑰的銷毀

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

A）身份識別

B）密鑰管理

C）數(shù)字簽名

D）消息認證B2006.091015、下列關于信息認證的敘述中，哪一項不正確A驗證體制中存在一個完成仲裁、頒發(fā)證書等功能的可信機構B數(shù)字簽名者事后不能否認自己的簽名C消息認證要檢驗的內(nèi)容包括消息的序號和時間性D對密碼系統(tǒng)的主動攻擊是通過分析和識別截獲的密文完成D2006.096、下列哪一項不是網(wǎng)絡防病毒軟件允許用戶設置的掃描方式？A實時掃描B警告掃描C預置掃描D人工掃描B2006.091027、下列條目中，哪些屬于計算機病毒的特征？

I．傳染性

II．可激發(fā)性

III．隱蔽性

IV．潛伏性

A．只有I和III

B．只有I、II和IV

C．只有I、III和IV

D．都是

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

A．物理隔離

B．時間隔離

C．邏輯隔離

D．密碼隔離C2006.041039、______屬于實施操作系統(tǒng)安全措施的具體方案。

I．認證II．訪問權限III．文件保護IV．審計

A）僅I、II和IIIB）僅I、III和IVC）僅II、III和IVD）全部D2005.04104填空1、在密碼學中，將信息源稱作【1】明文2007.092、網(wǎng)絡安全技術的研究主要涉及三方面問題：

【2】

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

【2】

。服務攻擊2006.041054、對于多個進程共享公共區(qū)域訪問限制和訪問檢查，是為了防止【1】操作越權106過關練習1、下列身份識別技術中，哪一個屬于生物信息識別技術？

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

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

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

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

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

C)口令D)保護鍵

ABD107三級數(shù)據(jù)庫技術第2章數(shù)據(jù)結構與算法108本部分占總分的15%主要內(nèi)容：數(shù)據(jù)結構與算法基本概念線性表的定義、存儲和運算樹型結構的定義、存儲和運算查找排序1092.1基本概念110考點1數(shù)據(jù)結構基本概念1、數(shù)據(jù)采用計算機能識別、存儲和處理的符號總稱。是對現(xiàn)實世界事務的描述

數(shù)據(jù)元素數(shù)據(jù)的基本單位，數(shù)據(jù)集合的個體

一個數(shù)據(jù)元素由一個或多個數(shù)據(jù)項組成

數(shù)據(jù)項是數(shù)據(jù)的最小單位1112、數(shù)據(jù)結構數(shù)據(jù)之間的關系數(shù)據(jù)結構包括三方面內(nèi)容：

邏輯關系、在計算機中的存儲方式、在數(shù)據(jù)上定義的運算集合112數(shù)據(jù)結構數(shù)據(jù)的邏輯結構數(shù)據(jù)的存儲結構數(shù)據(jù)的運算線性結構→線性表→棧和隊列非線性結構→樹形結構(二叉樹、樹的遍歷)順序結構鏈式結構索引結構散列結構插入刪除查找－順序查找、二分法查找排序113數(shù)據(jù)的邏輯結構什么是數(shù)據(jù)的邏輯結構？數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯關系，與數(shù)據(jù)的存儲無關，是獨立于計算機的。數(shù)據(jù)的邏輯結構可分成2類線性結構非線性結構春夏秋冬父親兒子女兒114數(shù)據(jù)的存儲結構什么是數(shù)據(jù)的存儲結構？數(shù)據(jù)的存儲結構又稱為物理結構，是指數(shù)據(jù)元素及其關系在計算機內(nèi)存中的表示，即數(shù)據(jù)的邏輯結構在計算機存儲器中的實現(xiàn)。數(shù)據(jù)的存儲結構可分為哪4類？順序結構、鏈式結構、索引結構、散列結構數(shù)據(jù)的存儲結構與邏輯結構的關系同一邏輯結構可以采用不同的存儲結構115數(shù)據(jù)的運算定義在邏輯結構上，實現(xiàn)在存儲結構上116考點2主要的數(shù)據(jù)存儲方式順序存儲方式和鏈式存儲方式是最主要的內(nèi)種存儲方式順序存儲方式，主要用于線性的數(shù)據(jù)結構，它把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，結點之間的關系由存儲單元的鄰接關系來體現(xiàn)。（邏輯上相鄰物理上也相鄰）117線性表（K1,K2,K3,K4,K5)邏輯相鄰物理相鄰示意圖順序存儲結構的主要特點如下：①結點中沒有鏈接信息域，只有自身的信息域，存儲密度大，空間利用串高。②數(shù)據(jù)結構中第i個結點的存儲地址Li可由下述公式計算求得。

Li＝L1十(i—1)×m其中，L1為第一個節(jié)點的存儲地址，m為每個節(jié)點所占用的存儲單元個數(shù)。②插入、刪除運算會引起相應結點的大量移動。1182．鏈式存儲方式線性表（K1,K2,K3,K4,K5)邏輯相鄰物理相鄰示意圖119鏈式存儲方式特點：有表示鏈接信息的指針,存儲空間利用率低,存儲密度小，邏輯上相鄰的結點在物理上不必鄰接，可用于線性表、樹和圖等多種邏輯結構的存儲表示插入、刪除操作靈活方便120算法分析與設計算法的五個特征輸入（0個或多個輸入）

輸出（1個或多個輸出）有窮性（在有限時間內(nèi)完成）確定性（執(zhí)行結果確定的）有效性（程序是可以實現(xiàn)的）算法分析---時間代價和空間代價121考題1、下列哪些是數(shù)據(jù)結構研究內(nèi)容I、數(shù)據(jù)的采集與清洗II、數(shù)據(jù)的邏輯組織III、數(shù)據(jù)的集成V、數(shù)據(jù)傳輸IV、數(shù)據(jù)的檢索

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

A、數(shù)據(jù)運算是數(shù)據(jù)結構的一個重要方面

B、數(shù)據(jù)運算的具體實現(xiàn)在數(shù)據(jù)的邏輯結構上進行

C、檢索是一種常用的運算

D、插入是一種常用的運算B125填空題1、數(shù)據(jù)結構包括三方面的內(nèi)容：數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構、數(shù)據(jù)的

【3】

運算2006.092、散列存儲的基本思想是由節(jié)點的【1】決定節(jié)點的存儲位置關鍵碼值1262.2線性表（重點）順序表鏈表棧隊列串127不同的存儲結構的線性表叫法不同順序存儲的線性表：順序表鏈式存儲的線性表：鏈表散列方式存儲的線性表：散列表在線性表上運算不同叫法不同插入和刪除在線性表一端，棧插入和刪除在線性表兩端進行，隊列128考點1順序表和一維數(shù)組順序表元素位置計算機

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

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

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

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

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

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

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

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

D．線性表按鏈接方式存儲，刪除指針P所指向的結點A移動元素時間長（2007.09，2005.09）1446、從單鏈表中刪除指針S所指結點的下一個結點T，其關鍵步驟為A、S↑link=T

B、T↑link=S

C、T↑link=S↑linkD、S↑link=T↑linkD1457、下列哪一個不是隊列的基本運算？

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

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

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

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

A．表達式求值

B．樹的層次次序周游算法的實現(xiàn)

C．二叉樹對稱序周游算法的實現(xiàn)

D．快速排序算法的實現(xiàn)B1461472.3多維數(shù)組、稀疏矩陣和廣義表148考點1多維數(shù)組順序存儲aij一行n個元素a11149考點2稀疏矩陣存儲下三角矩陣行優(yōu)先數(shù)組存儲還可用三元組存儲、十字鏈表3000700-100-1-200000000000203123451245150考點3廣義表廣義線性表，零個或多個單元素或子表組成表中含表151考題1、以下關于廣義表的敘述中，哪一條是正確的？

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

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

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

D．廣義表不能為空表A2、如下是一個稀疏矩陣的三元組法存儲表示和基于此表示所得出的相關敘述I.該稀疏矩陣有5行II.該稀疏矩陣有4列III.該稀疏矩陣有6個非0元素這些敘述中______是正確的。

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

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

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

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

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

C2009.04（右子樹為空）AB對稱序BA前序AB1722、按層次次序?qū)⒁豢糜衝個結點的完全二叉樹的所有結點從1到n編號，當i<n/2時，編號為i的結點的左子女的編號為

A）2i-1

B）2i

C）2i+1

D）不確定B

2009.04

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

ABDEGCFHI1762.5查找在數(shù)據(jù)結構中找出滿足條件的結點的過程177考點1順序查找逐個依次查找，對邏輯次序無要求（不必排序），可以是順序存儲也可以是鏈式存儲優(yōu)點：簡單缺點：速度慢，檢索長度與結點N成正比178考點2二分查找線性表結點必須按關鍵碼值排序，以順序存儲方式存儲的（考概念）二分查找過程（查找612）179例題1：對線性表進行二分法檢索，其前提條件是：線性表以【1】方式存儲，并且按關鍵碼值排好序。180考點3分塊查找線性表分塊每塊不必有序塊間有序查找過程1、在索引表中確定記錄所在塊2、在塊中查找記錄索引表181考點4散列表的存儲和查找（重點）散列表（哈希表）：利用散列法構建的線性表，是一種重要的存儲方式和檢索方式基本思想：

1、由結點的關鍵碼k通過散列函數(shù)f(k)決定結點的存儲地址

2、將結點存入該地址，查找的時候，通過該散列函數(shù)取得地址，讀取結點數(shù)據(jù)182由于采用函數(shù)值作為地址，不同關鍵碼函數(shù)值可能相同，即K1<>K2,但f(k1)=f(k2)，這就產(chǎn)生了碰撞（沖突）碰撞處理：開放地址法（線性探測法）和拉鏈法開放地址法：當在d地址發(fā)生碰撞時，按如下序列進行探查d+1,d+2,m-1,0,1,..d-1183例題1：設散列表的地址空間為0到12，散列函數(shù)為h（k）=kmod13,用線性探查法解決碰撞。現(xiàn)從空的散列表開始，依次插入關鍵碼值14,95,24,61，27,82,69,

則最后一個關鍵碼69的地址為【4】。01234567891011求地址：h(14)=1地址數(shù)據(jù)h(95)=4h(24)=11h(61)=9h(27)=1產(chǎn)生沖突地址+1h(82)=4產(chǎn)生沖突地址+1h(69)=4產(chǎn)生沖突地址+1，+114279582696124184負載因子（裝填因子）上題的負載因子7/13=185考點5樹形結構與查找二叉排序樹（適合內(nèi)存查找）特點：結點左子樹所有結點關鍵碼都小于該結點關鍵碼，右子樹所有結點都大于該結點關鍵碼中序周游（遍歷）為有序序列186極端情況，檢索達

n次187B樹和B+樹（適合于外存查找）B樹是一種平衡多路查找樹188至少有[M/2]-1個關鍵碼,最多M-1個關鍵碼NULL189B樹的插入結點和刪除結點仍然要滿足B樹特征190以下兩題基于圖3-8所示的5階B樹結構1、向該B樹中插入關鍵碼72后，該B樹第2層結點數(shù)為（）A、6B、7C、8D、9C2、從該B樹中刪除關鍵碼15后，該B樹的第2層結點數(shù)為()A、6B、7C、8D、9B351018456082258111523263038414753647073788695191結點分支多于5個，需要分為兩個結點每個結點至少含2個關鍵碼（分裂）351018456082258111523263038414753647073788695647072737845607282

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