2018年9月全國計算機等級考試《二級Web程序設(shè)計》復(fù)習(xí)全書核心講義+歷年真題詳解

1、2018年9月全國計算機等級考試二級Web程序設(shè)計復(fù)習(xí)全書【核心講義+歷年 真題詳解】THROUGH TRR/N 1最新資料，WORD格式，可編輯修改! TOC o 1-5 h z 第一部分備考指南3第1章考試概述3第2章復(fù)習(xí)技巧14第二部分 核心講義1.7.【公共基礎(chǔ)知識】 1.7.第1章 數(shù)據(jù)結(jié)構(gòu)與算法 1.7.第2章 程序設(shè)計基礎(chǔ) 36.第3章 軟件工程基礎(chǔ) 44第4章 數(shù)據(jù)庫設(shè)計基礎(chǔ) 73.【W(wǎng)eb程序設(shè)計】 95.第1章 Web技術(shù)基礎(chǔ)95.第2章 HTTP協(xié)議基礎(chǔ) 1.16.第3章 HTML語言基礎(chǔ) 1.35.第 4 章 CSS基礎(chǔ).1.6.0.第5章 JavaScript語言基礎(chǔ)

2、1.79第6章動態(tài)網(wǎng)頁技術(shù)概述21.2.第三部分歷年真題及詳解 2.39.全國計算機等級考試二級 Web程序設(shè)計真題精選（一）239全國計算機等級考試二級 Web程序設(shè)計真題精選（二）2.46第四部分 模擬試題及詳解 2.53.全國計算機等級考試二級 Web程序設(shè)計模擬試題及詳解（一） 2.53全國計算機等級考試二級 Web程序設(shè)計模擬試題及詳解（二） 2.60第一部分備考指南 第1章考試概述一、考試簡介全國計算機等級考試(National Computer Rank Examination ,簡稱 NCRE),是經(jīng)原國家教育委員會(現(xiàn)教育部)批準，由教育部考試中心主辦，面 向社會，用于考查應(yīng)

3、試人員計算機應(yīng)用知識與技能的全國性計算機水平考試體系。計算機技術(shù)的應(yīng)用在我國各個領(lǐng)域發(fā)展迅速，為了適應(yīng)知識經(jīng)濟和信息社會 發(fā)展的需要，操作和應(yīng)用計算機已成為人們必須掌握的一種基本技能。許多單位、 部門已把掌握一定的計算機知識和應(yīng)用技能作為人員聘用、職務(wù)晉升、職稱評定、 上崗資格的重要依據(jù)之一。鑒于社會的客觀需求，經(jīng)原國家教委批準，原國家教 委考試中心于1994年面向社會推出了 NCRE,其目的在于以考促學(xué)，向社會推廣 和普及計算機知識，也為用人部門錄用和考核工作人員提供一個統(tǒng)一、客觀、公 正的標準。、考試科目級別科目名稱科目代碼考試時間考核課程代碼一級計算機基礎(chǔ)及WPS Office應(yīng)用149

4、0分鐘114計算機基礎(chǔ)及MS Office應(yīng)用1590分鐘115計算機基礎(chǔ)及Photoshop應(yīng)用1690分鐘116二級C語百程序設(shè)計24120分鐘201 、 224VB語百程序設(shè)計26120分鐘201 、 226VFP數(shù)據(jù)庫程序設(shè)計27120分鐘201 、 227Java語百程序設(shè)計28120分鐘201 、 228Access數(shù)據(jù)庫程序設(shè)計29120分鐘201 、 229C+語百程序設(shè)計61120分鐘201、261MySQL數(shù)據(jù)庫程序設(shè)計63120分鐘201 、 263Web程序設(shè)計64120分鐘201 、 264MS Office高級應(yīng)用65120分鐘201 、 265三級網(wǎng)絡(luò)技術(shù)3512

5、0分鐘335數(shù)據(jù)庫技術(shù)36120分鐘336軟件測試技術(shù)37120分鐘337信息安全技術(shù)38120分鐘338嵌入式系統(tǒng)開發(fā)技術(shù)39120分鐘339四級網(wǎng)絡(luò)工程師4190分鐘401 、 403數(shù)據(jù)庫工程師4290分鐘404、405軟件測試工程師4390分鐘401 、 405信息安全工程師4490分鐘401 、 403嵌入式系統(tǒng)開發(fā)工程師4590分鐘401 、 402說明:同次考試考生可報考多個級別或科目，但不允許重復(fù)報考同一個科目，具體 要求請想所在省級承辦機構(gòu)進行咨詢。報考多個科目時需咨詢考點，避免考場安排時沖突。如：考生同時報考了二 級C、三級網(wǎng)絡(luò)技術(shù)、四級網(wǎng)絡(luò)工程師三個科目，結(jié)果通過了三級網(wǎng)

6、絡(luò)技術(shù)、四 級網(wǎng)絡(luò)工程師考試，但沒有通過二級 C考試，將不頒發(fā)任何證書，三級網(wǎng)絡(luò)技術(shù)、 四級網(wǎng)絡(luò)工程師兩個科目成績，自考試結(jié)束之日起可保留半年（按月計算）。下 一次考試考生報考二級C并通過，將一次獲得三個級別的證書；若沒有通過二級 C,將不能獲得任何證書。同時，三級網(wǎng)絡(luò)技術(shù)、四級網(wǎng)絡(luò)工程師兩個科目成績自 動失效。三、報考條件.考生不受年齡、職業(yè)、學(xué)歷等背景的限制，任何人均可根據(jù)自己學(xué)習(xí)和使 用計算機的實際情況，選考不同等級的考試?？忌淮沃荒軋罂家粋€科目的考試。 考生一次考試只能在一個考點報名?？忌梢圆粎⒓涌记芭嘤?xùn)，直接報名參加考 試。.每次考試報名的具體時間由各?。ㄗ灾螀^(qū)、直轄市）級承辦機

7、構(gòu)規(guī)定?？?生按照有關(guān)規(guī)定到就近考點報名。上次考試的筆試和上機考試僅其中一項成績合 格的，下次考試報名時應(yīng)出具上次考試成績單，成績合格項可以免考，只參加未 通過項的考試。.特殊人員報考條件：現(xiàn)役軍人可使用軍官證報考 NCRE考試，在其軍官證號碼前后各加入識別碼， 此辦法也適用于沒有身份證的未成年人，識別碼的編碼有統(tǒng)一格式，前 6位后4 位。國務(wù)院和中央軍事委員會聯(lián)合下發(fā)的 510號令，已經(jīng)公布現(xiàn)役軍人和人民 武裝警察居民身份證中領(lǐng)發(fā)放辦法，該辦法自 2008年1月1日起實施，現(xiàn)役 軍人可以通過團以上單位集中向地方公安機關(guān)申請居民身份證。無身份證的學(xué)生可攜帶戶口本參加報名，身份證丟失者憑公安機關(guān)

8、開具的身 份證明，外籍人員憑護照參加報名。四、報考方式分為考點現(xiàn)場報名與網(wǎng)上報名?？忌诳键c現(xiàn)場報名時，需出示身份證以及繳納相關(guān)的考試費?？忌欢ㄒ?親自到場，不能由任何單位、個人代勞?？忌匆筮M行信息采集，并逐一核實 報名表上的個人信息：姓名、身份證號、照片、報考科目、報考類別（是否補考） 等，發(fā)現(xiàn)信息不一致要立刻更改。報名完成后請妥善保管“考生報名登記表”防 止阻礙準考證的領(lǐng)取?？忌扇【W(wǎng)上報名方式，需先在所在省份的網(wǎng)上報名系統(tǒng)注冊并填報相關(guān)基 本信息、上傳正面免冠電子近照，然后網(wǎng)上繳費或至指定地點繳費并確認身份信 息，完成報名。一般情況下，每次考試每個考生只能在一個考點完成報名。考生報

9、名時繳納的考試費的具體金額由各省級承辦機構(gòu)根據(jù)考試需要和當?shù)?物價水平確定，并報當?shù)匚飪r部門核準?？键c不得擅自加收費用。注：報名時依據(jù)的身份證明包括：居民身份證、軍人的證件、護照、戶口本五、報考時間考試安排第一場第二場第三場報名時間12月開始5月開始11月10日以后注：各地的報名時間由考生報考所在地的當?shù)乜荚嚈C構(gòu)決定六、考試時間NCRE以往每年開考兩次，從2014年開始每年開考次數(shù)由兩次增為三次。2016年NCRE安排三次考試，考試時間分別為 3月21日24日、9月19日22日、12月12日13日，其中3月和9月考試開考全部級別全部科目，12月只開考一級和二級，由各省級承辦機構(gòu)根據(jù)實際情況確定

10、是否開考12月的考試。七、各級別考試介紹一級科目一級 WPS Office一級 MS Office一級 Photoshop考試環(huán) 境NCRE 一級上機考試環(huán)境為Windows 7簡體中文版考試軟 件WPS Office 2012 辦公軟件MS Office 2010Photoshop CS5（典型方式安裝）題型及 分值比 例.單項選擇題，20題，20 分. Windows操作系統(tǒng)的使 用，10分. WPS文字的操作，25分. WPS表格的操作，20分. WPS演示軟件的操作，15分.瀏覽器（IE）的簡單使用 和電子郵件收發(fā)，10分1 .單項選擇題，20題,20 分Windows操作系統(tǒng)的使 用

11、，10分Word操作，25分Excel 操作,20 分PowerPoint 操作，15 分.瀏覽器（IE）的簡單使用 和電子郵件收發(fā)，10分.單項選擇題，55題， 55分（含計算機基礎(chǔ) 知識部分20分）. Photoshop 操作題，45分考核內(nèi) 容.考核內(nèi)谷包括計算機基礎(chǔ)知識和操作技能兩部分。.各科目對基礎(chǔ)知識的要求相同，以考查應(yīng)知應(yīng)會為主，題型為選擇題，分數(shù)占全 卷的20% （20分）。.辦公軟件類考試，操作技能部分包括漢子錄入、 Windows系統(tǒng)使用、文子排版、 電子表格、演示文稿、IE的簡單應(yīng)用及電子郵件收發(fā)。. Photoshop 考試，要求了解數(shù)字圖像的基本知識，熟悉 Photo

12、shop 的界面與 基本操作方法，掌握并熟練運用繪圖工具進行圖像的繪制、編輯、修飾，會使用圖 層蒙版、樣式以及文字工具。形式完全采取上機考試形式，各科上機考試時間均為 90分鐘，滿分100分。獲證條 件總分不低于60分。備注參加NCRE ”計算機基礎(chǔ)及Photoshop 應(yīng)用”科目考生，可以在 NCRE報名時自 愿申請免試取得“ Adobe Photoshop 產(chǎn)品工程師認證”證書，即：通過 NCRE “計 算機基礎(chǔ)及Photoshop應(yīng)用”科目考試實現(xiàn)一次考試，可以同時取得全國計算機等 級證書與 Adobe Photoshop廣品工程師認證證書，即 考雙證。二級語言程序設(shè)計類數(shù)據(jù)庫程序設(shè)計類

13、辦公軟件高級應(yīng) 用科目C語百C+ +JavaVBWebVFPAccessMySQL辦公軟件高級應(yīng) 用考試 環(huán)境NCRE二級上機考試環(huán)境為 Windows 7 簡體中文版考試軟件VisualC+ 6.0Vis ual C+ +6.0Net- Bea ns 中國 教育 考試 版 200 7VB6 .0 簡體 中義 專業(yè) 版NetBe ans中 國教育 考試 版，IE6.0 及以上VFP 6.0 簡體 中義 專業(yè) 版MSAccess2010MySQL (Comm unity 5.5.16 )MS Office2010題型 及分 值比 例.單項選 擇題，40 題，40分（含公共基礎(chǔ)知識 部分10分）.

14、程序程1 .單項選擇題，40題，40分（含公共基礎(chǔ)知識部分10 分）.基本操作題，18分.簡單應(yīng)用題，24分.綜合應(yīng)用/操作題，18分.單項選擇題，20分（含公共基 礎(chǔ)知識部分10 分）.文字處理題（Word ） , 30分空題，3小 空，18分 3.程序改 錯題，2個 錯誤，24 分4.程序設(shè) 計題，18 分.電子去格題(Excel) , 30分.演示文稿題(PowerPoint),20 分考核 內(nèi)容二級定位為程序員，考核內(nèi)容包括公共基礎(chǔ)知識和程序設(shè)計。所有科目對基礎(chǔ)知識作今 要求，使用今的公共基礎(chǔ)知識考試大綱和教程。二級公共基礎(chǔ)知識在各科考試選擇題中 體現(xiàn)。程序設(shè)計部分，主要考查考生對程序

15、設(shè)計諦言使用和編程調(diào)試等基本能力，在選擇 題和操作題中1口以體現(xiàn)。形式完全采取上機考試形式。各科上機考試時間均為 120分鐘，滿分100分。獲證條件總分不低于60分三級科目網(wǎng)絡(luò)技 術(shù)數(shù)據(jù)庫技 術(shù)軟件測試技術(shù)信息安全技 術(shù)嵌入式系統(tǒng)開發(fā)技 術(shù)考試環(huán)境 與軟件. NCRE三級上機考試環(huán)境為 Windows 7 簡體中文版.數(shù)據(jù)庫技術(shù)考核C諦言程序設(shè)計，使用 Visual C+ 6.0題型及分 值比例.單選題，40題,40分.綜合題，40分.應(yīng)用題，20分考核內(nèi)容.網(wǎng)絡(luò)技術(shù)。網(wǎng)絡(luò)規(guī)劃與設(shè)計、局域網(wǎng)組網(wǎng)技術(shù)、計算機網(wǎng)絡(luò)信息服務(wù) 系統(tǒng)的建立及計算機網(wǎng)絡(luò)安全與管理。.數(shù)據(jù)庫技術(shù)。數(shù)據(jù)庫應(yīng)用系統(tǒng)分析及規(guī)劃、

16、數(shù)據(jù)庫設(shè)計及實現(xiàn)、數(shù)據(jù) 庫存儲技術(shù)、并發(fā)控制技術(shù)、數(shù)據(jù)庫管理與維護、數(shù)據(jù)庫技術(shù)的發(fā)展及 新技術(shù)。.軟件測試技術(shù)。軟件測試的基本概念、軟件測試技術(shù)、軟件測試過程和管理方法。.信息安全技術(shù)。信息安全保障概論、信息安全基礎(chǔ)技術(shù)與原理、系統(tǒng) 安全、網(wǎng)絡(luò)安全、應(yīng)用安全、信息安全管理、信息安全標準與法規(guī)。.嵌入式系統(tǒng)開發(fā)技術(shù)。嵌入式系統(tǒng)的概念與基礎(chǔ)知識、嵌入式處理器、 嵌入式系統(tǒng)硬件組成、嵌入式系統(tǒng)軟件、嵌入式系統(tǒng)的開發(fā)等相關(guān)知識 和技能。形式完全采取上機考試形式。各科上機考試時間均為120分鐘，滿分100分。獲證條件.總分不彳氐于60分，并已經(jīng)（或同時）獲得二級相關(guān)證書。.三級數(shù)據(jù)庫技術(shù)證書要求已經(jīng)（或

17、同時）獲得二級數(shù)據(jù)庫程序設(shè)計類 證書；網(wǎng)絡(luò)技術(shù)、軟件測試技術(shù)、信息安全技術(shù)、嵌入式系統(tǒng)開發(fā)技術(shù) 等四個證書要求已經(jīng)（或同時）獲得二級語言程序設(shè)計類證書。.考生早期獲得的證書（如 Pascal、FoxBase等），不嚴格區(qū)分諦言程 序設(shè)計和數(shù)據(jù)庫程序設(shè)計，可以直接報考并獲得證書。備注當口 NCRE ”計算機基礎(chǔ)及Photoshop 應(yīng)用”科目考生，可以在 NCRE 報名時自愿申請免試取得“ Adobe Photoshop 產(chǎn)品工程師認證”證書， 即：通過NCRE ”計算機基礎(chǔ)及Photoshop應(yīng)用”科目考試實現(xiàn)一次考 試，可以同時取得全國計算機等級證書與 “Adobe Photoshop 產(chǎn)品

18、工程 師認證”證書，即“一考雙證”。四級科目網(wǎng)絡(luò)工程 師數(shù)據(jù)庫工程 師軟件測試工程 師信息安全工 程師嵌入式系統(tǒng) 開發(fā)工程師考試環(huán)境NCRE四級上機考試環(huán)境為 Windows 7 簡體中文版。題型及分 值比例.單選題，60題,60分.多選題，20題,40分考核內(nèi)容.網(wǎng)絡(luò)工程師?？己擞嬎銠C網(wǎng)絡(luò)、操作系統(tǒng)原理兩門課程。測試內(nèi)容包 括網(wǎng)絡(luò)系統(tǒng)規(guī)劃與設(shè)計的基礎(chǔ)知識及中小型網(wǎng)絡(luò)的系統(tǒng)組建、設(shè)備配置 調(diào)試、網(wǎng)絡(luò)系統(tǒng)現(xiàn)場維護與管理的基本技能。.數(shù)據(jù)庫工程師。考核數(shù)據(jù)庫原理、軟件工程兩門課程。測試內(nèi)容包括 數(shù)據(jù)庫系統(tǒng)的基本理論以及數(shù)據(jù)庫設(shè)計、維護、管理與應(yīng)用開發(fā)的基本能力。.軟件測試工程師。考核操作系統(tǒng)原理、

19、軟件工程兩門課程。測試內(nèi)容 包括軟件測試的基本理論、軟件測試的規(guī)范及標準，以及制定測試計劃、 設(shè)計測試用例、選擇測試工具、執(zhí)行測試并分析評估結(jié)果等軟件測試的 基本技能。.信息安全工程師?？己擞嬎銠C網(wǎng)絡(luò)、操作系統(tǒng)原理兩門課程。測試內(nèi) 容包括網(wǎng)絡(luò)攻擊與保護的基本理論與技術(shù)，以及操作系統(tǒng)、路由設(shè)備的 安全防范技能。.嵌入式系統(tǒng)開發(fā)工程師?？己瞬僮飨到y(tǒng)原理、計算機組成與接口兩門 課程。測試內(nèi)容包括嵌入式系統(tǒng)基本理論、邏輯電路基礎(chǔ)以及嵌入式系 統(tǒng)中的信息表示與運算、評價方法等基本技能。形式.無紙化考試，考試總時間為 90分鐘，單課程考試沒有時間要求。.四級考試科目由五門專業(yè)基礎(chǔ)課程中指定的兩門課程組成，

20、總分100分，兩門課程各占50分。.專業(yè)基礎(chǔ)課程為計算機專業(yè)核心課程，包括：操作系統(tǒng)原理、計算機 組成與接口、計算機網(wǎng)絡(luò)、數(shù)據(jù)庫原理、軟件工程。獲證條件兩門課程分別達到30分及以上，并已經(jīng)（或同時）獲得三級相關(guān)證書。 2013年3月及以前狀得的三級各科目證書，不區(qū)分科目，可以作為四級 任一科目的獲證條件。備注當口 NCRE ”計算機基礎(chǔ)及Photoshop 應(yīng)用”科目考生，可以在 NCRE 報名時自愿申請免試取得“ Adobe Photoshop 產(chǎn)品工程師認證”證書， 即：通過NCRE ”計算機基礎(chǔ)及Photoshop應(yīng)用”科目考試實現(xiàn)一次考 試，可以同時取得全國計算機等級證書與 “Adob

21、e Photoshop 產(chǎn)品工程 師認證”證書，即“一考雙證”。2015年NCRE繼續(xù)實施2013年版考試大綱，教材參見全國計算機等級考試 教材目錄（2015年版）。八、考試要求.理解Web工作原理，了解 Web技術(shù)基礎(chǔ)。.理解超文本傳輸協(xié)議HTTP的基本概念和模型，掌握 HTTP的消息格式、 常用消息頭、請求消息和常用請求方法、響應(yīng)消息和常用響應(yīng)狀態(tài)。.熟練掌握超文本標記語言 HTML文檔的結(jié)構(gòu)、常用文檔元素的含義和基 本使用方法。.理解樣式表語言CSS的基本概念和作用，掌握 CSS的基本語法和使用方 法。.掌握腳本語言JavaScript的基本概念和語法，掌握 JavaScript對常用

22、HTML文檔元素的操作方法；了解文檔對象模型 DOM的基本概念和作用。. 了解主要動態(tài)網(wǎng)頁技術(shù)的基本概念。九、考試內(nèi)容（一）Web技術(shù)基礎(chǔ).Internet與 Web技術(shù)的基本概念Web技術(shù)的主要組成Web瀏覽器與服務(wù)器的基本概念和工作原理Web應(yīng)用開發(fā)構(gòu)架和開發(fā)技術(shù)（二）HTTP協(xié)議基礎(chǔ). HTTP的基本概念與交互模型HTTP消息格式HTTP請求消息和常用請求方法HTTP響應(yīng)消息和常用響應(yīng)狀態(tài)HTTP常用消息頭（三）HTML基礎(chǔ). HTML文檔的基本結(jié)構(gòu)和語法HTML常用元素及其基本屬性HTML表單與常用控件（四）CSS基礎(chǔ). CSS的基本概念和作用CSS的基本語法和基本使用方法CSS的層次

23、及其作用優(yōu)先級（五）JavaScript程序設(shè)計基礎(chǔ). JavaScript的基本概念和作用. JavaScript的基本語法. JavaScript常用內(nèi)置對象.瀏覽器對象模型BOM的基本概念和作用.文檔對象模型DOM的基本概念和作用(六)動態(tài)網(wǎng)頁技術(shù)概述Java Servlet和JSP基本概念和原理ASP.NET基本概念和原理PHP基本概念和原理. AJAX基本概念和原理十、成績及證書NCRE實行百分制計分，但以等第通知考生成績。等第共分優(yōu)秀、及格、 不及格三等。90100分為優(yōu)秀、6089分為及格、059分為不及格。一般在 考后30個工作日內(nèi)由教育部考試中心將成績處理結(jié)果下發(fā)給各省級承辦

24、機構(gòu)。考后50個工作日，考生可登錄教育部考試中心綜合查詢網(wǎng)( ) 進行成績查詢。部分省市如江蘇、黑龍江等也可通過省市考試院或者人事考試中 心進行查詢。NCRE成績在及格以上者，由教育部考試中心頒發(fā)合格證書?？己?45個 工作日教育部考試中心將證書發(fā)給各省級承辦機構(gòu)，然后由各省級承辦機構(gòu)逐級 轉(zhuǎn)發(fā)給考生?？忌C書若丟失，可登錄教育部考試中心綜合查詢網(wǎng)補辦合格證明 書。補辦合格證明書收費21元，其中制證、郵寄費用20元，銀行收取手續(xù)費1 元。NCRE合格證書式樣按國際通行證書式樣設(shè)計，用中、英兩種文字書寫， 證書編號全國統(tǒng)一，證書上印有持有人身份證號碼。該證書全國通用，是持有人 計算機應(yīng)用能力的證

25、明，也可供用人部門錄用和考核工作人員時參考。一級證書表明持有人具有計算機的基礎(chǔ)知識和初步應(yīng)用能力，掌握 Office辦 公自動化軟件的使用及因特網(wǎng)應(yīng)用， 或掌握基本圖形圖像工具軟件(Photoshop ) 的基本技能，可以從事政府機關(guān)、企事業(yè)單位文秘和辦公信息化工作。二級證書表明持有人具有計算機基礎(chǔ)知識和基本應(yīng)用能力，能夠使用計算機 高級語言編寫程序，可以從事計算機程序的編制、初級計算機教學(xué)培訓(xùn)以及企業(yè) 中與信息化有關(guān)的業(yè)務(wù)和營銷服務(wù)工作。三級證書表明持有人初步掌握與信息技術(shù)有關(guān)崗位的基本技能，能夠參與軟 硬件系統(tǒng)的開發(fā)、運維、管理和服務(wù)工作。四級證書表明持有人掌握從事信息技術(shù)工作的專業(yè)技能，

26、并有系統(tǒng)的計算機 理論知識和綜合應(yīng)用能力。第2章復(fù)習(xí)技巧一、備考指導(dǎo).勇往直前進入下午考試，也許有疲勞或不好的感覺，自信心就會下降；當看到題干很 長，操作較復(fù)雜的題時，就有想回避或焦慮、急燥的情緒。這是典型的“兩軍未 戰(zhàn)，兵先屈”的敗興思緒。要知道兩對手相遇勇者勝，勇者相遇智者勝。拋開所 有不必要的想法，相信自己的實力，做到心無旁鷲，勇往直前。.審清題干題干包含了整個題目的條件和要求，若題干比較復(fù)雜，就要注意將題干“分 段”來閱讀，前后注意銜接，必要時在草稿紙上記載下關(guān)鍵點。有時候題干很長, 看似很復(fù)雜，讓很多人望而卻步。其實，這種題更好解，因題干長了則提示信息 也就多了。主要是考你有沒有勇氣

27、和耐心。.解讀試題首先，要翻閱一下全部試卷，注意試題的時間及分數(shù)的分配情況，做到心中 有數(shù)。其次，要弄清楚題意，明確題目要求。因為考試要求可能與自己習(xí)慣的答題 要求有所不同，所以一定要按題意和要求去回答。最后，要特別注意題目中比較隱蔽的條件。一般而言，條件隱蔽的問題難度 較大，考生必須看清有關(guān)的線索，找出隱蔽條件，問題才能迎刃而解。.相信自己當題做得非常順利時，心里不要太得意，因為越是看似容易的題目越是錯的 多，當然也不要逆向思維，覺得這題這么簡單是不是做錯了，要相信自己，說到 底還是要審清題目的意思；二、題型分析.選擇題選擇題為單選題，是客觀性試題，試題覆蓋面廣，一般情況下考生不可能做 到對

28、每個題目都有把握答對。這時，就需要考生學(xué)會放棄，即不確定的題目不要 在上面花費太多的時間，應(yīng)該在此題上做上標記，立即轉(zhuǎn)移注意力，作答其他題 目。最后有空余的時間再回過頭來仔細考慮此題。但要注意，對于那些實在不清 楚的題目，就不要浪費時間了，放棄繼續(xù)思考，不要因小失大。絕大多數(shù)選擇題的設(shè)問是正確觀點，稱為正面試題；如果設(shè)問是錯誤觀點， 稱為反面試題?？忌谧鞔疬x擇題時可以使用一些答題方法，以提高答題準確率。(1)正選法(順選法)：如果對題支中的 4個選項，一看就能肯定其中的1 個是正確的，就可以直接得出答案。注意，必須要有百分之百的把握才行。(2)逆選法(排謬法)：逆選法是將錯誤答案排除的方法。

29、對題支中的4個選項，一看就知道其中的1個(或2個、3個)是錯誤的，可以使用逆選法，即 排除錯誤選項。(3)比較法(蒙猜法)：這種辦法是沒有辦法的辦法，在有一定知識基礎(chǔ)上 的蒙猜也是一種方法。.操作題上機考試重點考察考生的基本操作能力，要求考生具有綜合運用基礎(chǔ)知識進 行實際操作的能力。上機操作題綜合性強、難度較大。上機考試的評分是以機評 為主，人工復(fù)查為輔的。機評當然不存在公正性的問題，但卻存在呆板的問題， 有時還可能因為出題者考慮不周出現(xiàn)錯評的情況。考生做題時不充分考慮到這些 情況，就有可能吃虧。掌握好上機考試的應(yīng)試技巧，可以使考生的實際水平在考試時得到充分發(fā)揮， 從而取得較為理想的成績。歷次

30、考試均有考生因為忽略了這一點，加之較為緊張 的考場氣氛影響了水平的發(fā)揮，致使考試成績大大低于實際水平。因此每個考生 在考試前，都應(yīng)有充分的準備?？偨Y(jié)以下幾點供考生在復(fù)習(xí)和考試時借鑒：(1)對于上機考試的復(fù)習(xí)，切不可“死記硬背”根據(jù)以往考試經(jīng)驗，有部分考生能夠通過筆試，而上機考試卻不能通過，主 要原因是這部分考生已經(jīng)習(xí)慣于傳統(tǒng)考試的“死記硬背”，而對于真正的知識應(yīng) 用，卻顯得束手無策。為了克服這個弊病，考生一定要在熟記基本知識點的基礎(chǔ) 上，加強上機訓(xùn)練，從歷年試題中尋找解題技巧，理清解題思路，將各類典型試 題反復(fù)練習(xí)。(2)在考前，一定要重視等級考試模擬軟件的使用在考試之前，應(yīng)使用等級考試模擬軟

31、件進行實際的上機操作練習(xí)，尤其要做 一些具有針對性的上機模擬題，以便熟悉考試題型，體驗真實的上機環(huán)境，減輕 考試時的緊張程度。(3)學(xué)會并習(xí)慣使用幫助系統(tǒng)大部分軟件都有較全面的幫助系統(tǒng)，熟練掌握幫助系統(tǒng)，可以使考生減少記 憶量，解決解題中的疑難問題。(4)熟悉考試場地及環(huán)境尤其是要熟悉考場的硬件情況和所使用的相關(guān)軟件的情況?？键c在正式考試 前，會給考生提供一次模擬上機的機會。模擬考試時，考生重點不應(yīng)放在把題做 出來，而是放在熟悉考試環(huán)境，相應(yīng)軟件的使用方法，考試系統(tǒng)的使用等方面。(5)做上機題時要不急不燥，認真審題先分析，后操作。明白了問題是什么以后，先把問題在腦海里過一遍，考慮 好如何操作后

32、，再依思路從容做答。而不要手忙腳亂、毛毛躁躁、急于作答。對 于十分了解或熟悉的問題，切忌粗心大意、得意忘形、而應(yīng)認真分析，必須將題 目給出的全部內(nèi)容逐字看清楚后針對具體問題進行操作。常言道“熟能生巧”、“打鐵還得本身硬”，再好的方法與技巧若沒有基礎(chǔ), 是發(fā)揮不了作用的；如若有了一定的功底，再差的招式也會產(chǎn)生很大的威力，就 像金庸小說中楊過的那柄鈍劍。但是如果只看不練，不會有提高。建議大家多做 模擬試題和歷年試題，鍛煉解題的能力與節(jié)奏。第二部分核心講義【公共基礎(chǔ)知識】第1章數(shù)據(jù)結(jié)構(gòu)與算法一、算法.算法的基本概念(1)算法的定義算法是指解題方案的準確而完整的描述，即算法是對特定問題求解步驟的一 種

33、描述。它是一組嚴謹定義運算順序的規(guī)則，且每個規(guī)則都是明確有效的，此順 序?qū)⒃谟邢薜拇螖?shù)下終止。需要注意的是：算法不等于程序，也不等于計算方法.(2)算法的基本特征可行性a.算法中的每一步驟都必須能夠?qū)崿F(xiàn)；b.算法執(zhí)行的結(jié)果要能夠達到預(yù)期的目的。確定性確定性是指算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的 解釋，也不允許有多義性。有窮性有窮性是指算法必須能在有限的時間內(nèi)做完，即必須能在執(zhí)行有限個步驟之 后終止，且必須有合理的執(zhí)行時間。擁有足夠的情報算法是否有效，取決于為算法所提供的情報是否足夠。一般而言，當算法有 足夠的情報時，此算法有效，而當提供的情報不夠時，算法可能無效。.算法設(shè)

34、計基本方法(1)列舉法基本思想根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦?需要的，哪些是不需要的。常用于解決“是否存在”或“有多少種可能”等類型 的問題。主要特點 算法比較簡單，但列舉情況較多時，算法工作量很大。注意事項例舉算法時，通過對實際問題進行詳細分析，將與問題有關(guān)的知識條理化、 完備化、系統(tǒng)化，并從中找出規(guī)律，或?qū)λ锌赡艿那闆r進行分類，從而引出一 些有用的信息，減少列舉量。(2)歸納法基本思想通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。主要特點a .比列舉法更能反映問題的本質(zhì)，可解決列舉量為無限的問題；b.可操作性低，不易歸納出一個具體數(shù)學(xué)模型；c.

35、歸納得出的結(jié)論只是一種猜測，須對這種猜測加以必要的證明。(3)遞推基本思想從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。主要特點a.初始條件或問題本身已給定，或通過對問題的分析化簡得到；b.遞推本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果；c .數(shù)值型遞推算法計算過程中必須注意數(shù)值計算的穩(wěn)定性問題。(4)遞歸基本思想將復(fù)雜問題逐層分解，歸結(jié)為一些簡單的問題，將簡單問題解決掉，再沿著 原來分解的逆過程逐步進行綜合。主要特點a.遞歸的基礎(chǔ)是歸納，對問題逐層分解的過程實際上并沒有對問題進行求解;b .在可計算性理論和算法設(shè)計中占有重要地位；c.遞歸算法比遞推算法清晰易讀，結(jié)構(gòu)簡練；d.

36、設(shè)計遞歸算法比遞推算法容易，但是其執(zhí)行效率較低。分類a.直接遞歸。一個算法P顯式地調(diào)用自己。b.間接遞歸。算法P調(diào)用另一個算法Q,而算法Q又調(diào)用算法P。遞歸與遞推的區(qū)別遞歸與遞推的區(qū)別主要在于二者實現(xiàn)方法的不同，表現(xiàn)為：a.遞歸是從算法本身到達遞歸的邊界的；b.遞推是從初始條件出發(fā)，逐次推出所需求的結(jié)果。(5)減半遞推技術(shù)減半遞推技術(shù)是工程上常用的分治法，其中，“減半”指將問題的規(guī)模減半， 而問題的性質(zhì)不變；“遞推”指重復(fù)“減半”的過程。(6)回溯法回溯法是指通過對問題的分析，找出一個解決問題的線索，然后沿著這個線 索逐步試探，若試探成功，則問題得到解決，若試探失敗，則逐步回退換別的路 線再進

37、行試探。.算法復(fù)雜度(1)時間復(fù)雜度定義算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運 算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f (n)其中，n是問題的規(guī)模。在同一問題規(guī)模下，若算法的基本運算次數(shù)取決于某一特定輸入，可用以 下兩種方法來分析算法的工作量：a.平均性態(tài)平均性態(tài)分析是指用各種特定輸入下的基本運算次數(shù)的加權(quán)平均值來度量算 法的工作量。算法的平均性態(tài)定義為：A(n) = p(x) t(x)x 二Dn其中，x是所有可能輸入中的某個特定輸入，p (x)是x出現(xiàn)的概率，即輸 入為x的概率，t (x)是算法在輸入為x時所執(zhí)行

38、的基本運算次數(shù)，Dn表示當規(guī) 模為n時，算法執(zhí)行時所有可能輸入的集合。b.最壞情況復(fù)雜性最壞情況分析是指規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)。其定義 為：W(n) = max 1t(x)(2)空間復(fù)雜度定義算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間。存儲空間組成一個算法的存儲空間包括以下幾種：a.算法程序占用的空間；b.輸入的初始數(shù)據(jù)占用的存儲空間；c.算法執(zhí)行過程中所需要的額外空間。額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附 加存儲空間，若額外空間相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。二、數(shù)據(jù)結(jié)構(gòu)的基本概念.概述(1)數(shù)據(jù)處理概述定義數(shù)據(jù)處

39、理是指對數(shù)據(jù)集合中的各元素以各種方式進行運算，包括插入、刪除、 查找、更改等運算，也包括對數(shù)據(jù)元素進行分析。關(guān)鍵問題大量數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)省計 算機的存儲空間，這是進行數(shù)據(jù)結(jié)構(gòu)處理的關(guān)鍵問題。(2)數(shù)據(jù)結(jié)構(gòu)研究概述研究問題a.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；b.在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲 結(jié)構(gòu)；c.對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。研究目的數(shù)據(jù)結(jié)構(gòu)研究和討論上述3個問題的主要目的在于提高數(shù)據(jù)處理效率， 包括: a.提高數(shù)據(jù)處理的速度；b .盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空 問。.數(shù)據(jù)結(jié)

40、構(gòu)的概念(1)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，即它是反映數(shù)據(jù)元素之間關(guān)系 的數(shù)據(jù)元素集合的表示。簡言之，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，這 里的“結(jié)構(gòu)”指數(shù)據(jù)元素之間的前后件關(guān)系。一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面內(nèi) 容：表述數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的前后件關(guān)系。(2)數(shù)據(jù)的邏輯結(jié)構(gòu)定義數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。要素：a.數(shù)據(jù)元素的集合，通常記為 D;b. D上的關(guān)系，通常記為R,它反映了 D中各數(shù)據(jù)元素之間的前后件關(guān)系。表小一個數(shù)據(jù)結(jié)構(gòu)B可表示為：B= (D, R)為反映D中個數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。(3)數(shù)據(jù)

41、的存儲結(jié)構(gòu)定義數(shù)據(jù)的存儲結(jié)構(gòu)，也稱數(shù)據(jù)的物理結(jié)構(gòu)，是指數(shù)據(jù)邏輯結(jié)構(gòu)在計算機存儲空 間中的存放形式。在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，而且要 存放各數(shù)據(jù)元素之間的前后件信息。常用的存儲結(jié)構(gòu)：a.順序；b.鏈接；c.索引。采用不同的存儲結(jié)構(gòu)，數(shù)據(jù)處理的效率是不同的。3.數(shù)據(jù)結(jié)構(gòu)的圖形表示(1)在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，數(shù)據(jù)集合D中每個元素用中間標有元素值的 方框表示，稱為數(shù)據(jù)結(jié)點(簡稱結(jié)點)；對關(guān)系 R中的每一個二元組，用一條有 向線段從前件結(jié)點指向后件結(jié)點。(2)在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點，沒有后件的結(jié)點稱為終端 結(jié)點(也稱葉子結(jié)點)，其余結(jié)點都稱為內(nèi)部結(jié)點。(3)數(shù)據(jù)結(jié)

42、構(gòu)中的元素結(jié)點可能是在動態(tài)變化的，這種變化體現(xiàn)在結(jié)點數(shù)量 的增減以及各結(jié)點之間的前后件關(guān)系的動態(tài)變化上。4.線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，可將數(shù)據(jù)結(jié)構(gòu)分 為：(1)線性結(jié)構(gòu)(線性表)一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件時，稱其為線性結(jié)構(gòu)：有且只有一個根結(jié)點；每個結(jié)點最多只有一個前件，也最多只有一個后件。線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點還應(yīng)是線性結(jié)構(gòu)，如果不滿足這個條件 就不能稱之為線性結(jié)構(gòu)。(2)非線性結(jié)構(gòu)如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。注：線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。一個空的數(shù)據(jù)結(jié)構(gòu)屬于 線性結(jié)構(gòu)還是非線性結(jié)構(gòu)，需要根據(jù)

43、對該數(shù)據(jù)結(jié)構(gòu)的運算是否按照線性結(jié)構(gòu)的規(guī) 則來處理進行判斷。三、線性表及其順序存儲結(jié)構(gòu).線性表的基本概念(1)線性表是一種最常見最簡單的數(shù)據(jù)結(jié)構(gòu)，由一組數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元 素在線性表中的位置值只取決于它們自己的序號，即數(shù)據(jù)元素之間的相對位置是 線性的。(2)非空線性表的結(jié)構(gòu)特征：有且只有一個根結(jié)點a1，它無前件；有且只有一個終端結(jié)點an,它無后件；除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。線性表中結(jié)點的個數(shù)n稱為線性表的長度。當n = 0時，稱為空表。.線性表的順序存儲結(jié)構(gòu)(1)概述順序存儲是一種最簡單的在計算機中存放線性表的方法，也稱順序分配。(2)特點：線性表

44、中所有元素所占的存儲空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。(3)運算在線性表的順序存儲結(jié)構(gòu)下，可對線性表進行以下運算：插入：在線性表的指定位置處加入一個新的元素；刪除：在線性表中刪除指定的元素；查找：在線性表中查找某個(或某些)特定的元素；排序：對線性表中的元素進行整序；分解：按要求將一個線性表分解成多個線性表；合并：按要求將多個線性表合并成一個線性表；復(fù)制：復(fù)制一個線性表；逆轉(zhuǎn)：逆轉(zhuǎn)一個線性表等。.順序表的插入運算假設(shè)線性表的存儲空間為 V (1 : m),線性表

45、的長度為n ( n & m),插入的 位置為i (表示在第i個位置插入元素)，則順序表插入新元素過程如下：(1)首先處理以下三種異常情況：當存儲空間已滿(即n = m)時為“上溢”錯誤，不能進行插入，算法結(jié)束；當in時，認為在最后一個元素之后(即第 n + 1個元素之前)插入；當i1時，認為在第1個元素之前插入。(2)從最后一個元素開始，直到第i個元素，其中每一個元素均往后移動一 個位置。(3)最后將新元素插入到第i個位置，并且將線性表的長度增加 1。.順序表的刪除運算假設(shè)線性表的存儲空間為 V (1 : m),線性表的長度為n ( n & m),刪除的 位置為i (表示刪除第i個元素)，則順

46、序表刪除元素的過程如下：(1)首先處理以下兩種異常情況：當線性表為空(即n = 0)時為“上溢”錯誤，不能進行插入，算法結(jié)束；當in時，認為在最后一個元素之后(即第 n + 1個元素之前)插 入。(2)然后從第i + 1個元素開始，直到最后一個元素，其中每一個元素均依 次往前移動一個位置。(3)最后將線性表的長度減小1。四、棧和隊列.棧及其基本運算(1)棧的定義棧是限定在一端進行插入與刪除的線性表。(2)棧的特點：允許插入和刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。棧 頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插 入也是最后被刪除的。棧遵循“先進后出”或“后

47、進先出”的原則，具有記憶功能。通常用指針top來指示棧頂位置，用指針bottom 指向棧底，棧頂指針top 動態(tài)反映了棧中元素的變化情況。(3)棧的順序存儲及其運算在棧的順序存儲空間S (1:m)中，top =0表示?？?；top =m表示棧滿。棧的三種運算：入棧運算人棧運算是指在棧頂位置插入一個新元素。操作過程如下：a.首先判斷棧頂指針是否已經(jīng)指向存儲空間的最后一個位置。如果是，則說 明?？臻g已滿，不可能再進行入棧操作(這種情況稱為?！吧弦纭卞e誤)，算法結(jié)束。b .然后將棧頂指針進一(即top加1)。c.最后將新元素x插入棧頂指針指向的位置。退棧運算退棧運算是指取出棧頂元素并賦給一個指定的變量

48、。操作過程如下：a.首先判斷棧頂指針是否為0o如果是，則說明?？?，不可能進行退棧操作 （這種情況稱為棧“下溢”錯誤），算法結(jié)束。b.然后將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量。c.最后將棧頂指針退一（即top減1）。讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。操作過程如下：a.首先判斷棧頂指針是否為0o如果是，則說明?？?，讀不到棧頂元素，算 法結(jié)束。b .然后將棧頂元素賦給指定的變量 y。這個運算不刪除棧頂元素，只是將它的值賦給一個變量，棧頂指針不會變。.隊列及其基本運算（1）什么是隊列隊列（Queue ）是指允許在一端進行插入、而在另一端進行刪除的線性表。（2）隊列的特

49、點允許插入的一端稱為隊尾，用隊尾指針指向隊尾元素；允許刪除的一端稱 為隊頭，用排頭指針指向排頭元素的前一個位置。最先插入的元素最先被刪除，最后插入的元素最后被刪除，遵循“先進先 出”或“后進后出”原則。隊尾指針rear和排頭指針front共同反映隊列中元素變動情況。入隊運算指只涉及隊尾指針rear變化，退隊運算只涉及排頭指針front變 化。（3）循環(huán)隊列及其運算循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的 環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊尾元素，用排頭指針front指向排頭元素的前一個位置，從排頭指針front指向的后一個位置 到隊尾指針

50、rear指向的位置均是隊列中元素。隊列空的條件是s=0;隊列滿的條 件是 s = 1 且 front = rear。隊列的兩種運算假設(shè)循環(huán)隊列的初始狀態(tài)為空，即：s=0,且front =rear=m。入隊運算入隊運算是指在循環(huán)隊列的隊尾加入一個新元素。操作過程如下：a.首先判斷循環(huán)隊列是否滿。當循環(huán)隊列非空（S=1）且隊尾指針等于排頭 指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為“上溢”。此時算法結(jié)束。b .然后將隊尾指針進一（即rear = rear + 1）,并當rear = m + 1時置rear =1。c.最后將新元素x插入隊尾指針指向的位置，并且置循環(huán)隊列非空標志。退隊運

51、算退隊運算是指在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。操作 過程如下：a.首先判斷循環(huán)隊列是否為空。當循環(huán)隊列為空（s= 0）時，不能進行退隊 運算。這種情況稱為“下溢”。此時算法結(jié)束。b .然后將排頭指針進一（即front = front + 1）,并當front = m + 1時置front =1。c.再將排頭指針指向的元素賦給指定的變量。d.最后判斷退隊后循環(huán)隊列是否為空。當 front = rear時置循環(huán)隊列空標志 （即 S= 0） o五、線性鏈表.線性鏈表的基本概念（1）線性表的順序存儲結(jié)構(gòu)存在的缺陷：在插入或刪除元素時，為保證操作后的線性表仍然是順序存儲，需要大量 移動

52、數(shù)據(jù)元素，效率很低。在順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充，易產(chǎn)生上溢現(xiàn)象。線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。（2）鏈式存儲結(jié)點組成：數(shù)據(jù)域：用于存放數(shù)據(jù)元素值；指針域：用于存放指針。指針用于指向該結(jié)點的前一個或后一個結(jié)點，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以 不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù) 元素之間的邏輯關(guān)系是由指針域來確定的。鏈式存儲方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。在用鏈式 結(jié)構(gòu)表示較復(fù)雜的非線性結(jié)構(gòu)時，其指針域的個數(shù)要多一些。(3)線性鏈表定義：線性鏈表是線性表的鏈式存儲結(jié)構(gòu)。特點a.各數(shù)據(jù)結(jié)點的存儲序號是不連續(xù)的，各結(jié)

53、點在存儲空間中的位置關(guān)系與邏 輯關(guān)系也不一致；b .各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點的指針域來指示的；c.每一個結(jié)點只有一個指針域，由這個指針只能找到后件結(jié)點，不能找到前 件結(jié)點，只能順指針向鏈尾進行掃描。為了彌補線性單鏈表的缺陷，在某些應(yīng)用中為線性鏈表每個結(jié)點設(shè)置兩個指 針，左指針用以指向其前件結(jié)點，右指針指向其后件結(jié)點。(4)帶鏈的棧帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結(jié)點。與順序棧一樣，帶鏈棧的基本操作有以下幾個：棧的初始化：建立一個空棧的順序存儲空間；入棧運算：在棧頂位置插入一個新元素；退棧運算：取出棧頂元素并賦給一個指定的變量；讀棧頂元素：將棧頂元素賦給一個指定的變

54、量。(5)帶鏈的隊列與順序隊列一樣，帶鏈隊列的基本操作有以下幾個：隊列的初始化：建立一個空隊列的順序存儲空間；入隊運算：在循環(huán)隊列的隊尾加入一個新元素；退隊運算：在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。.線性鏈表的基本運算(1)常見的線性表的運算線性鏈表的運算主要有以下幾個：在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素；在線性鏈表中刪除包含指定元素的結(jié)點；將兩個線性鏈表按要求合并成一個線性鏈表；將一個線性鏈表按要求進行分解；逆轉(zhuǎn)線性鏈表；復(fù)制線性鏈表；線性鏈表的排序；線性鏈表的查找。(2)在線性鏈表中查找指定元素非空線性鏈表中尋找包含指定元素值 x的前一個結(jié)點p的基本方法：從頭指

55、針指向的結(jié)點開始往后沿指針進行掃描，直到后面已沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為x為止。因此，由這種方法找到的結(jié)點 p有兩種可能：當線性 鏈表中存在包含元素x的結(jié)點時，則找到的p為第一次遇到的包含元素x的前一 個結(jié)點序號；當線性鏈表中不存在包含元素 x的結(jié)點時，則找到的p為線性鏈表 中的最后一個結(jié)點號。(3)線性鏈表的插入定義：線性鏈表的插入是指在鏈式儲存結(jié)構(gòu)下的線性表中插入一個新元素。 插入過程：在線性鏈表中包含元素x的結(jié)點之前插入一個新元素boa.從可利用棧取得一個結(jié)點，設(shè)該結(jié)點號為 p,并置結(jié)點p的數(shù)據(jù)域為插入 的元素值b。 b.在線性鏈表中尋找包含元素x的前一個結(jié)點，設(shè)該結(jié)點的存儲序 號為

56、q。c.最后將結(jié)點p插入到結(jié)點q之后。為了實現(xiàn)這一步，只要改變以下兩個結(jié) 點的指針域內(nèi)容：第一，使結(jié)點P指向包含元素x的結(jié)點；第二，使結(jié)點q的指針域內(nèi)容改為指向結(jié)點p。插入特點：a.不會發(fā)生上溢現(xiàn)象；b.可方便實現(xiàn)存儲空間動態(tài)分配；c.不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只改變結(jié)點指針，提高插入效率。(4)線性鏈表的刪除定義：線性鏈表的刪除是指在鏈式儲存結(jié)構(gòu)下的線性表中刪除包含指定元 素的結(jié)點。刪除過程：在線性鏈表中刪除包含元素x的結(jié)點。a.在線性鏈表中尋找包含元素x的前一個結(jié)點，設(shè)該結(jié)點序號為 q；b.將結(jié)點q后的結(jié)點p從線性鏈表中刪除，即讓結(jié)點q的指針指向包含元 素x的結(jié)點p的指針指向的結(jié)點；c.將包

57、含元素x的結(jié)點p送回可利用棧。在線性鏈表中刪除一個元素后，不需要移動表的數(shù)據(jù)元素，只需改變被刪除元 素所在結(jié)點的前一個結(jié)點的指針域即可。.循環(huán)鏈表(1)與線性鏈表相比，循環(huán)鏈表具有的特點：在循環(huán)鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置， 指針域指向線性表的第一個元素的結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點。循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán) 鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。(2)與線性單鏈表相比，循環(huán)鏈表具有兩方面優(yōu)點：在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問 到表中其他所有的結(jié)點。而線性單鏈表做不到這一點。由于在循環(huán)

58、鏈表中設(shè)置了一個表頭結(jié)點，因此，在任何情況下循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。循環(huán)鏈表的插入與刪除運算要比一般單鏈表簡單，不用考慮在空鏈表和在第 一個結(jié)點前插入以及空鏈表的刪除等特殊情況，從而實現(xiàn)了空表與非空表運算的 統(tǒng)一。六、樹與二叉樹.樹的基本概念(1)樹是一種簡單的非線性結(jié)構(gòu)，在這種結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系 具有明顯的層次特性。在樹的圖形表示中，上端結(jié)點是前件，下端結(jié)點是后件。(2)在樹結(jié)構(gòu)中，每個結(jié)點只有一個前件(父結(jié)點)，沒有前件的結(jié)點只有 一個，稱為樹的根結(jié)點。每個結(jié)點都可以有多個后件(子結(jié)點)，沒有后件的結(jié) 點稱為葉子結(jié)點。(3) 一個結(jié)點擁有的后

59、件個數(shù)稱為該結(jié)點的度。某結(jié)點的度為n,表示該結(jié)點有n個分支，每個分支指向一個后件，除根結(jié)點外，每個結(jié)點都有一個唯一的 分支指向它。樹中的結(jié)點數(shù)為樹中所有結(jié)點的度之和再加1。(4)根結(jié)點在第1層，同一層上所有結(jié)點的所有子結(jié)點都在下一層，樹的最 大層次稱為樹的深度(5)在樹中，葉子結(jié)點沒有子樹。(6)用樹來表示算術(shù)表達式的原則：表達式中的每一個運算符在樹中對應(yīng)一個結(jié)點，稱為運算符結(jié)點；運算符的每一個運算對象在樹中為該運算符結(jié)點的子樹(在樹中的順序為 從左到右)；運算對象中的單變量均為葉子結(jié)點。在樹中，葉子結(jié)點沒有子樹。.二叉樹及其基本性質(zhì)(1)二叉樹定義二叉樹是一種很有用的非線性結(jié)構(gòu)，與樹結(jié)構(gòu)很相

60、似，樹結(jié)構(gòu)的所有術(shù)語都 可以用到叉樹這種數(shù)據(jù)結(jié)構(gòu)上。(2)二叉樹的兩個特點非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。(3)二叉樹的基本性質(zhì)在二叉樹的第k層上，最多有2k-1 ( k 1)個結(jié)點。深度為m的二叉樹最多有2m-1個結(jié)點。在任意一棵二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為 2的結(jié)點 多一個。具有n個結(jié)點的二叉樹，其深度至少為log 2n + 1,其中l(wèi)og 2n表示取 log 2n的整數(shù)部分。(4)滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。滿二叉樹除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹a.除最