全國計算機等級考試《二級java語言程序設計》復習全書核心講義歷年真題詳解

全國計算機等級考試《二級Java語言程序設計》復習全書【核心講義＋歷年真題詳解】最新資料，WORD格式，可編輯修改！目錄第一部分備考指南1章考試概述一、考試簡介（NationalComputerRankExamination，簡稱NCRE），是經(jīng)原國家教育委員會（現(xiàn)教育部）批準，由教育部考試中心主辦，面向社會，用于考查應試人員計算機應用知識與技能的全國性計算機水平考試體系。計算機技術的應用在我國各個領域發(fā)展迅速，為了適應知識經(jīng)濟和信息社會發(fā)展的需要，操作和應用計算機已成為人們必須掌握的一種基本技能。許多單位、部門已把掌握一定的計算機知識和應用技能作為人員聘用、職務晉升、職稱評定、上崗資格的重要依據(jù)之一。鑒于社會的客觀需求，經(jīng)原國家教委批1994年面向社會推出了NCRE向社會推廣和普及計算機知識，也為用人部門錄用和考核工作人員提供一個統(tǒng)一、客觀、公正的標準。二、考試科目級別科目名稱科目代碼考試時間考核課程代碼WPSOffice1490114一級MSOffice1590115計算機基礎及Photoshop應用1690116C24120201、224VB26120201、226VFP27120201、227Java28120201、228二級Access29120201、229C++語言程序設計61120201、261MySQL63120201、263Web64120201、264MSOffice65120201、265網(wǎng)絡技術35120335數(shù)據(jù)庫技術36120336三級軟件測試技術37120337信息安全技術38120338嵌入式系統(tǒng)開發(fā)技術39120339網(wǎng)絡工程師4190401、403數(shù)據(jù)庫工程師4290404、405四級軟件測試工程師4390401、405信息安全工程師4490401、403嵌入式系統(tǒng)開發(fā)工程師4590401、402說明:同次考試考生可報考多個級別或科目，但不允許重復報考同一個科目，具體要求請向所在省級承辦機構進行咨詢。報考多個科目時需咨詢考點，避免考場安排時沖突。如：考生同時報考了二級C、三級網(wǎng)絡技術、四級網(wǎng)絡工程師三個科目，結果通過了三級網(wǎng)絡技術、四級網(wǎng)絡工程師考試，但沒有通過二級C考試，將不頒發(fā)任何證書，三級網(wǎng)絡技術、四級網(wǎng)絡工程師兩個科目成績，自考試結束之日起可保留半年（按月計算）。下一次考試考生報考二級C并通過，將一次獲得三個級別的證書；若沒有通過二級C，將不能獲得任何證書。同時，三級網(wǎng)絡技術、四級網(wǎng)絡工程師兩個科目成績自動失效。三、報考條件1．考生不受年齡、職業(yè)、學歷等背景的限制，任何人均可根據(jù)自己學習和使用計算機的實際情況，選考不同等級的考試?？忌淮沃荒軋罂家粋€科目的考試?？忌淮慰荚囍荒茉谝粋€考點報名?？忌梢圆粎⒓涌记芭嘤?，直接報名參加考試。每次考試報名的具體時間由各?。ㄗ灾螀^(qū)、直轄市）級承辦機構規(guī)定?？忌凑沼嘘P規(guī)定到就近考點報名。上次考試的筆試和上機考試僅其中一項成績合格的，下次考試報名時應出具上次考試成績單，成績合格項可以免考，只參加未通過項的考試。特殊人員報考條件：現(xiàn)役軍人可使用軍官證報考NCRE此辦法也適用于沒有身份證的未成年人，識別碼的編碼有統(tǒng)一格式，前6位后4位。國務院和中央軍事委員會聯(lián)合下發(fā)的510號令，已經(jīng)公布《現(xiàn)役軍人和人民武裝警察居民身份證申領發(fā)放辦法》，該辦法自2008年1月1日起實施，現(xiàn)役軍人可以通過團以上單位集中向地方公安機關申請居民身份證。無身份證的學生可攜帶戶口本參加報名，身份證丟失者憑公安機關開具的身份證明，外籍人員憑護照參加報名。四、報考方式分為考點現(xiàn)場報名與網(wǎng)上報名?？忌诳键c現(xiàn)場報名時，需出示身份證以及繳納相關的考試費。考生一定要親自到場，不能由任何單位、個人代勞。考生按要求進行信息采集，并逐一核實報名表上的個人信息：姓名、身份證號、照片、報考科目、報考類別（是否補考）等，發(fā)現(xiàn)信息不一致要立刻更改。報名完成后請妥善保管“考生報名登記表”防止阻礙準考證的領取。考生采取網(wǎng)上報名方式，需先在所在省份的網(wǎng)上報名系統(tǒng)注冊并填報相關基本信息、上傳正面免冠電子近照，然后網(wǎng)上繳費或至指定地點繳費并確認身份信息，完成報名。一般情況下，每次考試每個考生只能在一個考點完成報名?？忌鷪竺麜r繳納的考試費的具體金額由各省級承辦機構根據(jù)考試需要和當?shù)匚飪r水平確定，并報當?shù)匚飪r部門核準?？键c不得擅自加收費用。注：報名時依據(jù)的身份證明包括：居民身份證、軍人的證件、護照、戶口本等。五、報考時間考試安排考試安排第一場第二場第三場報名時間12報名時間1251110六、考試時間NCRE以往每年開考兩次，從2014年開始每年開考次數(shù)由兩次增為三次。2016年NCRE321～24919～221212～13391212月的考試。七、各級別考試介紹科目境

一級一級WPSOffice 一級MSOffice 一級PhotoshopNCRE一級上機考試環(huán)境為Windows7簡體中文版件例

WPSOffice2012件單項選擇題，20題，20Windows操作系統(tǒng)的使用，10WPS文字的操作，25分WPS表格的操作，20分WPS演示軟件的操作，15用和電子郵件收發(fā)，10分

MSOffice2010 PhotoshopCS5（典型方式安裝）單項選擇題，20題，20Windows用，10分 1．單項選擇題，55題，3．Word操作，25分 55（含計算機基礎知4．Excel操作，20分 識部分20分）5．PowerPoint操作，152．Photoshop操作題，分 45分瀏覽器（IE）的簡單分容形式件備注

考核內容包括計算機基礎知識和操作技能兩部分。各科目對基礎知識的要求相同，以考查應知應會為主，題型為選擇題，分數(shù)占全卷的20%（20分）。3．辦公軟件類考試，操作技能部分包括漢字錄入、Windows系統(tǒng)使用、文字排版、電子表格、演示文稿、IE的簡單應用及電子郵件收發(fā)。3．Photoshop考試，要求了解數(shù)字圖像的基本知識，熟悉Photoshop的界面與基本操作方版、樣式以及文字工具。完全采取上機考試形式，各科上機考試時間均為90分鐘，滿分100分。60參加NCRE“計算機基礎及Photoshop應用”科目考生，可以在NCRE報名時自愿申請免試取得“AdobePhotoshop產品工程師認證”證書，即：通過NCRE“計算機基礎及Photoshop應用”科目考試實現(xiàn)一次考試，可以同時取得全國計算機等級證書與“AdobePhotoshop產品工程師認證”證書，即“一考雙證”?？颇?C語言

語言程序設計類C++ Java VB

二級數(shù)據(jù)庫程序設計類VFP Access MySQL

用用考試 NCRE二級上機考試環(huán)境為Windows7簡體中文版環(huán)境Net-VisualVisualC++VisualC++Beans版2007簡NetBeans教育考試版，及以上簡MSAccess2MSOffice2010題，401．單項選擇題，例40（含公共基礎知識10）題，318程序改錯題，2錯誤，24分程序設計題，18分單項選擇題，40題，40分（10分）基本操作題，18分簡單應用題，24分綜合應用/操作題，18分20（含公共基礎知識部分10分）2．文字處理題（Word），30分3．電子表格題（Excel），304．演示文稿題（PowerPoint），20二級定位為程序員，考核內容包括公共基礎知識和程序設計。所有科目對基礎知識作統(tǒng)一要考核內容程序設計部分，主要考查考生對程序設計語言使用和編程調試等基本能力，在選擇題和操作題中加以體現(xiàn)。形式完全采取上機考試形式。各科上機考試時間均為120100三級網(wǎng)絡技數(shù)據(jù)庫技軟件測試技信息安全嵌入式系統(tǒng)開發(fā)三級網(wǎng)絡技數(shù)據(jù)庫技軟件測試技信息安全嵌入式系統(tǒng)開發(fā)術術術技術技術科目考試環(huán) 1．NCRE三級上機考試環(huán)境為Windows7簡體中文版件例容形式件備注

2．C語言程序設計，使用VisualC++1．單選題，40，40綜合題，40分應用題，20分1．網(wǎng)絡技術。網(wǎng)絡規(guī)劃與設計、局域網(wǎng)組網(wǎng)技術、計算機網(wǎng)絡信息服務系統(tǒng)的建立及計算機網(wǎng)絡安全與管理。2．數(shù)據(jù)庫技術。數(shù)據(jù)庫應用系統(tǒng)分析及規(guī)劃、數(shù)據(jù)庫設計及實現(xiàn)、數(shù)據(jù)庫存儲技術、并發(fā)控制技術、數(shù)據(jù)庫管理與維護、數(shù)據(jù)庫技術的發(fā)展及新技術。3．軟件測試技術。軟件測試的基本概念、軟件測試技術、軟件測試過程和管理方法。4．信息安全技術。信息安全保障概論、信息安全基礎技術與原理、系統(tǒng)安全、網(wǎng)絡安全、應用安全、信息安全管理、信息安全標準與法規(guī)。5．嵌入式系統(tǒng)開發(fā)技術。嵌入式系統(tǒng)的概念與基礎知識、嵌入式處理器、嵌入式系統(tǒng)硬件組成、嵌入式系統(tǒng)軟件、嵌入式系統(tǒng)的開發(fā)等相關知識和技能。120分鐘，滿分100分?？偡植坏陀?0分，并已經(jīng)（或同時）獲得二級相關證書。三級數(shù)據(jù)庫技術證書要求已經(jīng)（或同時獲得二級數(shù)據(jù)庫程序統(tǒng)開發(fā)技術等四個證書要求已經(jīng)（或同時）獲得二級語言程序設計類證書?？忌缙讷@得的證書（如Pascal、FoxBase等），不嚴格區(qū)分語言程序設計和數(shù)據(jù)庫程序設計，可以直接報考并獲得證書。無科目境例容

四級網(wǎng)絡工 數(shù)據(jù)庫工程 軟件測試工 信息安全工 程師 師 程師 程師 NCREWindows71．單選題，60題，60分2．多選題，20題，40分1．網(wǎng)絡工程師?？己擞嬎銠C網(wǎng)絡、操作系統(tǒng)原理兩門課程。測試內容包括網(wǎng)絡系統(tǒng)規(guī)劃與設計的基礎知識及中小型網(wǎng)絡的系統(tǒng)組建、設備配置調試、網(wǎng)絡系統(tǒng)現(xiàn)場維護與管理的基本技能。2．數(shù)據(jù)庫工程師?？己藬?shù)據(jù)庫原理、軟件工程兩門課程。測試內容包括數(shù)據(jù)庫系統(tǒng)的基本理論以及數(shù)據(jù)庫設計、維護、管理與應用開發(fā)的基本能力。3．軟件測試工程師?？己瞬僮飨到y(tǒng)原理、軟件工程兩門課程。測試內容包括軟件測試的基本理論、軟件測試的規(guī)范及標準，以及制定測試計劃、設計測試用例、選擇測試工具、執(zhí)行測試并分析評估結果等軟件測試的基本技能。4．信息安全工程師?？己擞嬎銠C網(wǎng)絡、操作系統(tǒng)原理兩門課程。測試內容包括網(wǎng)絡攻擊與保護的基本理論與技術，以及操作系統(tǒng)、路由設備的安全防范技能。5．嵌入式系統(tǒng)開發(fā)工程師?？己瞬僮飨到y(tǒng)原理、計算機組成與接口兩門課程。測試內容包括嵌入式系統(tǒng)基本理論、邏輯電路基礎以及嵌入式系統(tǒng)中的信息表示與運算、評價方法等基本技能。90分鐘，單課程考試沒有時間要求。分形式10050專業(yè)基礎課程為計算機專業(yè)核心課程，包括：操作系統(tǒng)原理、計算機組成與接口、計算機網(wǎng)絡、數(shù)據(jù)庫原理、軟件工程。兩門課程分別達到30分及以上并已（或同時獲得三級相關證獲證條 書。件 2013年3月及以前獲得的三級各科目證書，不區(qū)分科目，可以作為四級任一科目的獲證條件。備注 無·2015年NCRE繼續(xù)實施2013年版考試大綱，教材參見全國計算機等級考試教材目錄（2015）。八、考試要求掌握Java語言的特點、實現(xiàn)機制和體系結構。掌握Java語言中面向對象的特性。掌握Java語言提供的數(shù)據(jù)類型和結構。掌握Java語言編程的基本技術。會編寫Java用戶界面程序。會編寫Java簡單應用程序。7．會編寫Java小應用程序（Applet）。8Java九、考試內容（一）Java（二）Java體系結構1．JavaJavaJava（三）Java語言中面向對象的特性1．面向對象編程的基本概念和特征。類的基本組成和使用。對象的生成、使用和刪除。包與接口。Java（四）Java語言的基本數(shù)據(jù)類型和運算1．變量和常量?；緮?shù)據(jù)類型及轉換。Java運算符和表達式運算。字符串和數(shù)組。（五）Java語言的基本語句1．條件語句。循環(huán)語句。注釋語句。異常處理語句。表達式語句。（六）Java編程基本技術線程的概念和使用。程序的同步與共享。Java異常處理和斷言概念。Java語言的集合（Collections）框架和泛型概念。（七）編寫用戶界面程序基礎AWTSwingSwing（八）編寫小應用程序（Applet）基礎1．AppletAPI2．AppletAWTSwingApplet十、成績及證書NCRE實行百分制計分，但以等第通知考生成績。等第共分優(yōu)秀、及格、不及格三等。90～100分為優(yōu)秀、60～89分為及格、0～59分為不及格。一般在考后30個工作日內由教育部考試中心將成績處理結果下發(fā)給各省級承辦機構。考后50個工作日，考生可登錄教育部考試中心綜合查詢網(wǎng)（）進行成績查詢。部分省市如江蘇、黑龍江等也可通過省市考試院或者人事考試中心進行查詢。NCRE成績在及格以上者，由教育部考試中心頒發(fā)合格證書?？己?5個工作日教育部考試中心將證書發(fā)給各省級承辦機構，然后由各省級承辦機構逐級轉發(fā)給考生?？忌C書若丟失，可登錄教育部考試中心綜合查詢網(wǎng)補辦合格證明書。補辦合格證明書收費21元，其中制證、郵寄費用20元，銀行收取手1NCRE合格證書式樣按國際通行證書式樣設計，用中、英兩種文字書寫，證書編號全國統(tǒng)一，證書上印有持有人身份證號碼。該證書全國通用，是持有人計算機應用能力的證明，也可供用人部門錄用和考核工作人員時參考。一級證書表明持有人具有計算機的基礎知識和初步應用能力，掌握Office辦公自動化軟件的使用及因特網(wǎng)應用，或掌握基本圖形圖像工具軟件（Photoshop）的基本技能，可以從事政府機關、企事業(yè)單位文秘和辦公信息化工作。二級證書表明持有人具有計算機基礎知識和基本應用能力，能夠使用計算機高級語言編寫程序，可以從事計算機程序的編制、初級計算機教學培訓以及企業(yè)中與信息化有關的業(yè)務和營銷服務工作。三級證書表明持有人初步掌握與信息技術有關崗位的基本技能，能夠參與軟硬件系統(tǒng)的開發(fā)、運維、管理和服務工作。四級證書表明持有人掌握從事信息技術工作的專業(yè)技能，并有系統(tǒng)的計算機理論知識和綜合應用能力。2章復習技巧1．勇往直前進入下午考試，也許有疲勞或不好的感覺，自信心就會下降；當看到題干很長，操作較復雜的題時，就有想回避或焦慮、急燥的情緒。這是典型的“兩軍未戰(zhàn)，兵先屈”的敗興思緒。要知道兩對手相遇勇者勝，勇者相遇智者勝。拋開所有不必要的想法，相信自己的實力，做到心無旁鶩，勇往直前。審清題干段”來閱讀，前后注意銜接，必要時在草稿紙上記載下關鍵點。有時候題干很長，看似很復雜，讓很多人望而卻步。其實，這種題更好解，因題干長了則提示信息也就多了。主要是考你有沒有勇氣和耐心。解讀試題首先，要翻閱一下全部試卷，注意試題的時間及分數(shù)的分配情況，做到心中有數(shù)。其次，要弄清楚題意，明確題目要求。因為考試要求可能與自己習慣的答題要求有所不同，所以一定要按題意和要求去回答。最后，要特別注意題目中比較隱蔽的條件。一般而言，條件隱蔽的問題難度較大，考生必須看清有關的線索，找出隱蔽條件，問題才能迎刃而解。相信自己當題做得非常順利時，心里不要太得意，因為越是看似容易的題目越是錯的多，當然也不要逆向思維，覺得這題這么簡單是不是做錯了，要相信自己，說到底還是要審清題目的意思；1．選擇題選擇題為單選題，是客觀性試題，試題覆蓋面廣，一般情況下考生不可能做到對每個題目都有把握答對。這時，就需要考生學會放棄，即不確定的題目不要在上面花費太多的時間，應該在此題上做上標記，立即轉移注意力，作答其他題目。最后有空余的時間再回過頭來仔細考慮此題。但要注意，對于那些實在不清楚的題目，就不要浪費時間了，放棄繼續(xù)思考，不要因小失大。絕大多數(shù)選擇題的設問是正確觀點，稱為正面試題；如果設問是錯誤觀點，稱為反面試題?？忌谧鞔疬x擇題時可以使用一些答題方法，以提高答題準確率。正選法（順選法）：如果對題支中的4個選項，一看就能肯定其中的1個是正確的，就可以直接得出答案。注意，必須要有百分之百的把握才行。逆選法（排謬法）：逆選法是將錯誤答案排除的方法。對題支中的4個選項，一看就知道其中的1個（或2個、3個）是錯誤的，可以使用逆選法，即排除錯誤選項。比較法（蒙猜法）：這種辦法是沒有辦法的辦法，在有一定知識基礎上的蒙猜也是一種方法。2．操作題上機考試重點考察考生的基本操作能力，要求考生具有綜合運用基礎知識進行實際操作的能力。上機操作題綜合性強、難度較大。上機考試的評分是以機評為主，人工復查為輔的。機評當然不存在公正性的問題，但卻存在呆板的問題，有時還可能因為出題者考慮不周出現(xiàn)錯評的情況?？忌鲱}時不充分考慮到這些情況，就有可能吃虧。掌握好上機考試的應試技巧，可以使考生的實際水平在考試時得到充分發(fā)揮，從而取得較為理想的成績。歷次考試均有考生因為忽略了這一點，加之較為緊張的考場氣氛影響了水平的發(fā)揮，致使考試成績大大低于實際水平。因此每個考生在考試前，都應有充分的準備。總結以下幾點供考生在復習和考試時借鑒：對于上機考試的復習，切不可“死記硬背”根據(jù)以往考試經(jīng)驗，有部分考生能夠通過筆試，而上機考試卻不能通過，主要原因是這部分考生已經(jīng)習慣于傳統(tǒng)考試的“死記硬背”，而對于真正的知識應用，卻顯得束手無策。為了克服這個弊病，考生一定要在熟記基本知識點的基礎上，加強上機訓練，從歷年試題中尋找解題技巧，理清解題思路，將各類典型試題反復練習。在考前，一定要重視等級考試模擬軟件的使用在考試之前，應使用等級考試模擬軟件進行實際的上機操作練習，尤其要做一些具有針對性的上機模擬題，以便熟悉考試題型，體驗真實的上機環(huán)境，減輕考試時的緊張程度。學會并習慣使用幫助系統(tǒng)大部分軟件都有較全面的幫助系統(tǒng)，熟練掌握幫助系統(tǒng)，可以使考生減少記憶量，解決解題中的疑難問題。熟悉考試場地及環(huán)境尤其是要熟悉考場的硬件情況和所使用的相關軟件的情況?？键c在正式考試前，會給考生提供一次模擬上機的機會。模擬考試時，考生重點不應放在把題做出來，而是放在熟悉考試環(huán)境，相應軟件的使用方法，考試系統(tǒng)的使用等方面。做上機題時要不急不燥，認真審題先分析，后操作。明白了問題是什么以后，先把問題在腦海里過一遍，考慮好如何操作后，再依思路從容做答。而不要手忙腳亂、毛毛躁躁、急于作答。對于十分了解或熟悉的問題，切忌粗心大意、得意忘形、而應認真分析，必須將題目給出的全部內容逐字看清楚后針對具體問題進行操作。常言道“熟能生巧”、“打鐵還得本身硬”，再好的方法與技巧若沒有基礎，是發(fā)揮不了作用的；如若有了一定的功底，再差的招式也會產生很大的威力，就像金庸小說中楊過的那柄鈍劍。但是如果只看不練，不會有提高。建議大家多做模擬試題和歷年試題，鍛煉解題的能力與節(jié)奏。第二部分核心講義【公共基礎知識】1章數(shù)據(jù)結構與算法一、算法算法的定義算法是指解題方案的準確而完整的描述，即算法是對特定問題求解步驟的一種描述。它是一組嚴謹定義運算順序的規(guī)則，且每個規(guī)則都是明確有效的，此順序將在有限的次數(shù)下終止。需要注意的是：算法不等于程序，也不等于計算方法。算法的基本特征①可行性a．算法中的每一步驟都必須能夠實現(xiàn)；b．算法執(zhí)行的結果要能夠達到預期的目的。②確定性確定性是指算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋，也不允許有多義性。③有窮性有窮性是指算法必須能在有限的時間內做完，即必須能在執(zhí)行有限個步驟之后終止，且必須有合理的執(zhí)行時間。④擁有足夠的情報算法是否有效，取決于為算法所提供的情報是否足夠。一般而言，當算法有足夠的情報時，此算法有效，而當提供的情報不夠時，算法可能無效。算法設計基本方法列舉法①基本思想根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。常用于解決“是否存在”或“有多少種可能”等類型的問題。②主要特點算法比較簡單，但列舉情況較多時，算法工作量很大。③注意事項例舉算法時，通過對實際問題進行詳細分析，將與問題有關的知識條理化、完備化、系統(tǒng)化，并從中找出規(guī)律，或對所有可能的情況進行分類，從而引出一些有用的信息，減少列舉量。歸納法①基本思想通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。②主要特點a．比列舉法更能反映問題的本質，可解決列舉量為無限的問題；b．可操作性低，不易歸納出一個具體數(shù)學模型；c．歸納得出的結論只是一種猜測，須對這種猜測加以必要的證明。遞推①基本思想從已知的初始條件出發(fā)，逐次推出所要求的各中間結果和最后結果。②主要特點a．初始條件或問題本身已給定，或通過對問題的分析化簡得到；b．遞推本質上屬于歸納法，遞推關系式往往是歸納的結果；c．數(shù)值型遞推算法計算過程中必須注意數(shù)值計算的穩(wěn)定性問題。遞歸①基本思想將復雜問題逐層分解，歸結為一些簡單的問題，將簡單問題解決掉，再沿著原來分解的逆過程逐步進行綜合。②主要特點a．遞歸的基礎是歸納，對問題逐層分解的過程實際上并沒有對問題進行求解；b．在可計算性理論和算法設計中占有重要地位；c．遞歸算法比遞推算法清晰易讀，結構簡練；d．設計遞歸算法比遞推算法容易，但是其執(zhí)行效率較低。③分類直接遞歸。一個算法P顯式地調用自己。間接遞歸。算法PQQP。④遞歸與遞推的區(qū)別遞歸與遞推的區(qū)別主要在于二者實現(xiàn)方法的不同，表現(xiàn)為：a．遞歸是從算法本身到達遞歸的邊界的；b．遞推是從初始條件出發(fā)，逐次推出所需求的結果。減半遞推技術減半遞推技術是工程上常用的分治法，其中，“減半”指將問題的規(guī)模減半，而問題的性質不變；“遞推”指重復“減半”的過程?；厮莘ɑ厮莘ㄊ侵竿ㄟ^對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，若試探成功，則問題得到解決，若試探失敗，則逐步回退換別的路線再進行試探。算法復雜度時間復雜度①定義算法的時間復雜度是指執(zhí)行算法所需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量＝f（n）其中，n是問題的規(guī)模。②在同一問題規(guī)模下，若算法的基本運算次數(shù)取決于某一特定輸入，可用以下兩種方法來分析算法的工作量：平均性態(tài)平均性態(tài)分析是指用各種特定輸入下的基本運算次數(shù)的加權平均值來度量算法的工作量。算法的平均性態(tài)定義為：其中，x是所有可能輸入中的某個特定輸入，p（x）是x出現(xiàn)的概率，即輸入為x的概率，t（x）是算法在輸入為x時所執(zhí)行的基本運算次數(shù)，Dn

表示當規(guī)模為n最壞情況復雜性最壞情況分析是指規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)。其定義為：空間復雜度①定義算法的空間復雜度一般是指執(zhí)行這個算法所需要的內存空間。②存儲空間組成一個算法的存儲空間包括以下幾種：a．算法程序占用的空間；b．輸入的初始數(shù)據(jù)占用的存儲空間；c．算法執(zhí)行過程中所需要的額外空間。額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結構所需要的附加存儲空間，若額外空間相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。1．概述數(shù)據(jù)處理概述①定義數(shù)據(jù)處理是指對數(shù)據(jù)集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，也包括對數(shù)據(jù)元素進行分析。②關鍵問題大量數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)省計算機的存儲空間，這是進行數(shù)據(jù)結構處理的關鍵問題。數(shù)據(jù)結構研究概述①研究問題a．數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的邏輯結構；b．在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構；對各種數(shù)據(jù)結構進行的運算。②研究目的數(shù)據(jù)結構研究和討論上述3個問題的主要目的在于提高數(shù)據(jù)處理效率，包括：a．提高數(shù)據(jù)處理的速度；b．盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。2．數(shù)據(jù)結構的概念數(shù)據(jù)結構的定義數(shù)據(jù)結構是指相互有關聯(lián)的數(shù)據(jù)元素的集合，即它是反映數(shù)據(jù)元素之間關系的數(shù)據(jù)元素集合的表示。簡言之，數(shù)據(jù)結構是指帶有結構的數(shù)據(jù)元素的集合，這里的“結構”指數(shù)據(jù)元素之間的前后件關系。一個數(shù)據(jù)結構應包含以下兩方面內容：①表述數(shù)據(jù)元素的信息；②表示各數(shù)據(jù)元素之間的前后件關系。數(shù)據(jù)的邏輯結構①定義數(shù)據(jù)的邏輯結構是指反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結構。②要素：a．數(shù)據(jù)元素的集合，通常記為D；b．DR，它反映了D③表示一個數(shù)據(jù)結構B可表示為：B＝（D，R）為反映D中個數(shù)據(jù)元素之間的前后件關系，一般用二元組來表示。數(shù)據(jù)的存儲結構①定義數(shù)據(jù)的存儲結構，也稱數(shù)據(jù)的物理結構，是指數(shù)據(jù)邏輯結構在計算機存儲空間中的存放形式。在數(shù)據(jù)的存儲結構中，不僅要存放各數(shù)據(jù)元素的信息，而且要存放各數(shù)據(jù)元素之間的前后件信息。②常用的存儲結構：a．順序；b．鏈接；c．索引。采用不同的存儲結構，數(shù)據(jù)處理的效率是不同的。3．數(shù)據(jù)結構的圖形表示在數(shù)據(jù)結構的圖形表示中，數(shù)據(jù)集合D中每個元素用中間標有元素值的方框表示，稱為數(shù)據(jù)結點（簡稱結點）；對關系R中的每一個二元組，用一條有向線段從前件結點指向后件結點。在數(shù)據(jù)結構中，沒有前件的結點稱為根結點，沒有后件的結點稱為終端結點（也稱葉子結點），其余結點都稱為內部結點。數(shù)據(jù)結構中的元素結點可能是在動態(tài)變化的，這種變化體現(xiàn)在結點數(shù)量的增減以及各結點之間的前后件關系的動態(tài)變化上。4．線性結構與非線性結構根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間的前后件關系的復雜程度，可將數(shù)據(jù)結構分為：線性結構（線性表）一個非空的數(shù)據(jù)結構滿足下列兩個條件時，稱其為線性結構：①有且只有一個根結點；②每個結點最多只有一個前件，也最多只有一個后件。線性結構中插入或刪除任何一個結點還應是線性結構，如果不滿足這個條件就不能稱之為線性結構。非線性結構如果一個數(shù)據(jù)結構不是線性結構，則稱之為非線性結構。注：線性結構與非線性結構都可以是空的數(shù)據(jù)結構。一個空的數(shù)據(jù)結構屬于線性結構還是非線性結構，需要根據(jù)對該數(shù)據(jù)結構的運算是否按照線性結構的規(guī)則來處理進行判斷。三、線性表及其順序存儲結構1．線性表的基本概念線性表是一種最常見最簡單的數(shù)據(jù)結構，由一組數(shù)據(jù)元素構成。數(shù)據(jù)元素在線性表中的位置值只取決于它們自己的序號，即數(shù)據(jù)元素之間的相對位置是線性的。非空線性表的結構特征：a1，

它無前件；an③除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。線性表中結點的個數(shù)n稱為線性表的長度。當n＝0時，稱為空表。2．線性表的順序存儲結構概述順序存儲是一種最簡單的在計算機中存放線性表的方法，也稱順序分配。特點：①線性表中所有元素所占的存儲空間是連續(xù)的；②線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。運算在線性表的順序存儲結構下，可對線性表進行以下運算：①插入：在線性表的指定位置處加入一個新的元素；②刪除：在線性表中刪除指定的元素；③查找：在線性表中查找某個（或某些）特定的元素；④排序：對線性表中的元素進行整序；⑤分解：按要求將一個線性表分解成多個線性表；⑥合并：按要求將多個線性表合并成一個線性表；⑦復制：復制一個線性表；⑧逆轉：逆轉一個線性表等。3．順序表的插入運算假設線性表的存儲空間為V（1：m），線性表的長度為n（n≤m），插入的位置為i（i），則順序表插入新元素過程如下：首先處理以下三種異常情況：①當存儲空間已滿（即n＝m）時為“上溢”錯誤，不能進行插入，算法結束；②當i>n（即第n＋1）插入；③當i<11從最后一個元素開始，直到第i個元素，其中每一個元素均往后移動一個位置。最后將新元素插入到第i個位置，并且將線性表的長度增加1。4．順序表的刪除運算假設線性表的存儲空間為V（1：m），線性表的長度為n（n≤m），刪除的位置為i（i），則順序表刪除元素的過程如下：首先處理以下兩種異常情況：①當線性表為空（即n＝0）時為“上溢”錯誤，不能進行插入，算法結束；②當i<1i>n（n＋1）插入。然后從第i＋1個元素開始，直到最后一個元素，其中每一個元素均依次往前移動一個位置。最后將線性表的長度減小1。四、棧和隊列1．棧及其基本運算棧的定義棧是限定在一端進行插入與刪除的線性表。棧的特點：①允許插入和刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。棧頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入也是最后被刪除的。②棧遵循“先進后出”或“后進先出”的原則，具有記憶功能。③通常用指針topbottomtop動態(tài)反映了棧中元素的變化情況。棧的順序存儲及其運算在棧的順序存儲空間S（1:m）中，top＝0表示棧空；top＝m表示棧滿。棧的三種運算：①入棧運算人棧運算是指在棧頂位置插入一個新元素。操作過程如下：a．首先判斷棧頂指針是否已經(jīng)指向存儲空間的最后一個位置。如果是，則說明棧空間已滿，不可能再進行入棧操作（這種情況稱為棧“上溢”錯誤），算法結束。b．然后將棧頂指針進一（即top加1）。c．最后將新元素x插入棧頂指針指向的位置。②退棧運算退棧運算是指取出棧頂元素并賦給一個指定的變量。操作過程如下：首先判斷棧頂指針是否為0。如果是，則說明?？?，不可能進行退棧操作（這種情況稱為?！跋乱纭卞e誤），算法結束。然后將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量。c．最后將棧頂指針退一（top1）。③讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。操作過程如下：a．首先判斷棧頂指針是否為0。如果是，則說明?？?，讀不到棧頂元素，算法結束。b．然后將棧頂元素賦給指定的變量y。這個運算不刪除棧頂元素，只是將它的值賦給一個變量，棧頂指針不會變。2．隊列及其基本運算什么是隊列隊列（Queue）是指允許在一端進行插入、而在另一端進行刪除的線性表。隊列的特點①允許插入的一端稱為隊尾，用隊尾指針指向隊尾元素；允許刪除的一端稱為隊頭，用排頭指針指向排頭元素的前一個位置。②最先插入的元素最先被刪除，最后插入的元素最后被刪除，遵循“先進先出”或“后進后出”原則。rearfront④入隊運算指只涉及隊尾指針rear變化，退隊運算只涉及排頭指針front變化。循環(huán)隊列及其運算循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上rear指向隊尾元素，用排頭指針front指向排頭元素的前一個位置，從排頭指針front指向的后一個位置到隊尾指針rear指向的位置均是隊列中元素。隊列空的條件是s＝0；隊列滿s＝1front＝rear。隊列的兩種運算假設循環(huán)隊列的初始狀態(tài)為空，即：s＝0，且front＝rear＝m。①入隊運算入隊運算是指在循環(huán)隊列的隊尾加入一個新元素。操作過程如下：a．首先判斷循環(huán)隊列是否滿。當循環(huán)隊列非空（S＝1）且隊尾指針等于排頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為“上溢”。此時算法結束。b．然后將隊尾指針進一（rear＝rear＋1）rear＝m＋1rear＝1。c．最后將新元素x插入隊尾指針指向的位置，并且置循環(huán)隊列非空標志。②退隊運算退隊運算是指在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。操作過程如下：首先判斷循環(huán)隊列是否為空。當循環(huán)隊列為空（s＝0）時，不能進行退隊運算。這種情況稱為“下溢”。此時算法結束。然后將排頭指針進一（即front＝front＋1），并當front＝m＋1時置front＝1。再將排頭指針指向的元素賦給指定的變量。d．最后判斷退隊后循環(huán)隊列是否為空。當front＝rear時置循環(huán)隊列空標志（即s＝0）。1．線性鏈表的基本概念線性表的順序存儲結構存在的缺陷：①在插入或刪除元素時，為保證操作后的線性表仍然是順序存儲，需要大量移動數(shù)據(jù)元素，效率很低。②在順序存儲結構下，線性表的存儲空間不便于擴充，易產生上溢現(xiàn)象。③線性表的順序存儲結構不便于對存儲空間的動態(tài)分配。鏈式存儲結點組成：①數(shù)據(jù)域：用于存放數(shù)據(jù)元素值；②指針域：用于存放指針。指針用于指向該結點的前一個或后一個結點，存儲數(shù)據(jù)結構的存儲空間可以不連續(xù)，各數(shù)據(jù)結點的存儲順序與數(shù)據(jù)元素之間的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏輯關系是由指針域來確定的。鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。在用鏈式結構表示較復雜的非線性結構時，其指針域的個數(shù)要多一些。線性鏈表①定義：線性鏈表是線性表的鏈式存儲結構。②特點a．各數(shù)據(jù)結點的存儲序號是不連續(xù)的，各結點在存儲空間中的位置關系與邏輯關系也不一致；b．各數(shù)據(jù)元素之間的前后件關系是由各結點的指針域來指示的；c．每一個結點只有一個指針域，由這個指針只能找到后件結點，不能找到前件結點，只能順指針向鏈尾進行掃描。為了彌補線性單鏈表的缺陷，在某些應用中為線性鏈表每個結點設置兩個指針，左指針用以指向其前件結點，右指針指向其后件結點。帶鏈的棧帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點。與順序棧一樣，帶鏈棧的基本操作有以下幾個：①棧的初始化：建立一個空棧的順序存儲空間；②入棧運算：在棧頂位置插入一個新元素；③退棧運算：取出棧頂元素并賦給一個指定的變量；④讀棧頂元素：將棧頂元素賦給一個指定的變量。帶鏈的隊列與順序隊列一樣，帶鏈隊列的基本操作有以下幾個：①隊列的初始化：建立一個空隊列的順序存儲空間；②入隊運算：在循環(huán)隊列的隊尾加入一個新元素；③退隊運算：在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。2．線性鏈表的基本運算常見的線性表的運算線性鏈表的運算主要有以下幾個：①在線性鏈表中包含指定元素的結點之前插入一個新元素；②在線性鏈表中刪除包含指定元素的結點；③將兩個線性鏈表按要求合并成一個線性鏈表；④將一個線性鏈表按要求進行分解；⑤逆轉線性鏈表；⑥復制線性鏈表；⑦線性鏈表的排序；⑧線性鏈表的查找。在線性鏈表中查找指定元素非空線性鏈表中尋找包含指定元素值x的前一個結點p的基本方法：從頭指針指向的結點開始往后沿指針進行掃描，直到后面已沒有結點或下一個結點的數(shù)據(jù)域為x為止。因此，由這種方法找到的結點p有兩種可能：當線性鏈表中存在包含元素x的結點時，則找到的p為第一次遇到的包含元素x的前一個結點序號；當線性鏈表中不存在包含元素x的結點時，則找到的p為線性鏈表中的最后一個結點號。線性鏈表的插入①定義：線性鏈表的插入是指在鏈式儲存結構下的線性表中插入一個新元素。②插入過程：在線性鏈表中包含元素x的結點之前插入一個新元素b。a．從可利用棧取得一個結點，設該結點號為p，并置結點p的數(shù)據(jù)域為插b。b．在線性鏈表中尋找包含元素xq。c．最后將結點p插入到結點q之后。為了實現(xiàn)這一步，只要改變以下兩個結點的指針域內容：Px第二，使結點q的指針域內容改為指向結點p。③插入特點：a．不會發(fā)生上溢現(xiàn)象；b．可方便實現(xiàn)存儲空間動態(tài)分配；c．不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只改變結點指針，提高插入效率。線性鏈表的刪除①定義：線性鏈表的刪除是指在鏈式儲存結構下的線性表中刪除包含指定元素的結點。②刪除過程：在線性鏈表中刪除包含元素x的結點。a．在線性鏈表中尋找包含元素x的前一個結點，設該結點序號為q；b．將結點q后的結點p從線性鏈表中刪除，即讓結點q的指針指向包含元xpcxp在線性鏈表中刪除一個元素后，不需要移動表的數(shù)據(jù)元素，只需改變被刪除元素所在結點的前一個結點的指針域即可。3．循環(huán)鏈表與線性鏈表相比，循環(huán)鏈表具有的特點：①在循環(huán)鏈表中增加了一個表頭結點，其數(shù)據(jù)域為任意或者根據(jù)需要來設置，指針域指向線性表的第一個元素的結點。循環(huán)鏈表的頭指針指向表頭結點。②循環(huán)鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環(huán)鏈表中，所有結點的指針構成了一個環(huán)狀鏈。與線性單鏈表相比，循環(huán)鏈表具有兩方面優(yōu)點：①在循環(huán)鏈表中，只要指出表中任何一個結點的位置，就可以從它出發(fā)訪問到表中其他所有的結點。而線性單鏈表做不到這一點。②由于在循環(huán)鏈表中設置了一個表頭結點，因此，在任何情況下循環(huán)鏈表中至少有一個結點存在，從而使空表與非空表的運算統(tǒng)一。循環(huán)鏈表的插入與刪除運算要比一般單鏈表簡單，不用考慮在空鏈表和在第一個結點前插入以及空鏈表的刪除等特殊情況，從而實現(xiàn)了空表與非空表運算的統(tǒng)一。六、樹與二叉樹樹是一種簡單的非線性結構，在這種結構中，所有數(shù)據(jù)元素之間的關系具有明顯的層次特性。在樹的圖形表示中，上端結點是前件，下端結點是后件。在樹結構中，每個結點只有一個前件（父結點），沒有前件的結點只有一個，稱為樹的根結點。每個結點都可以有多個后件（子結點），沒有后件的結點稱為葉子結點。一個結點擁有的后件個數(shù)稱為該結點的度。某結點的度為n，表示該結點有n個分支，每個分支指向一個后件，除根結點外，每個結點都有一個唯一1。根結點在第1層，同一層上所有結點的所有子結點都在下一層，樹的最大層次稱為樹的深度在樹中，葉子結點沒有子樹。用樹來表示算術表達式的原則：①表達式中的每一個運算符在樹中對應一個結點，稱為運算符結點；②運算符的每一個運算對象在樹中為該運算符結點的子樹（在樹中的順序為從左到右）；③運算對象中的單變量均為葉子結點。在樹中，葉子結點沒有子樹。二叉樹及其基本性質二叉樹定義二叉樹是一種很有用的非線性結構，與樹結構很相似，樹結構的所有術語都可以用到叉樹這種數(shù)據(jù)結構上。二叉樹的兩個特點①非空二叉樹只有一個根結點；②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。二叉樹的基本性質①在二叉樹的第k層上，最多有2k-1（k≥1）個結點。②深度為m的二叉樹最多有2m-1個結點。③在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。④具有n個結點的二叉樹，其深度至少為[logn]＋1，其中[[log2

n]表示取2logn2滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。①滿二叉樹除最后一層外，每一層上的所有結點都有兩個子結點。②完全二叉樹a．除最后一層外，每一層上的結點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結點。b．更確切地說，如果從根結點起，對二叉樹的結點自上而下、自左至右用自然數(shù)進行連續(xù)編號，則深度為m、且有n個結點的二叉樹，當且僅當其每一個m1n二叉樹。對于完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現(xiàn)；對于任P，則其左分支下的子孫結Pp＋1。c．滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹具有以下兩個性質：具有n個結點的完全二叉樹的深度為[logn]＋1。2設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結點進行編號，則對于編號為k（k＝1，2，…，n）的結點有以下結論：第一，若k＝1，則該結點為根結點，它沒有父結點；若k>1，則該結點的INT（k/2）。第二，若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。第三，若2k＋1≤n，則編號為k的結點的右子結點編號為2k＋1；否則該結點無右子結點。根據(jù)完全二叉樹的這個性質，如果按從上到下、從左到右順序存儲完全二叉樹的各結點，則很容易確定每一個結點的父結點、左子結點和右子結點的位置。二叉樹的存儲結構在計算機中，二叉樹采用鏈式存儲結構。用于存儲二叉樹中各元素的存儲結點由兩部分組成：①數(shù)據(jù)域②指針域a．左指針：用于指向該結點的左子結點的存儲地址；b．右指針：指向該結點的右指結點的存儲地址。4．二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。在遍歷二叉樹結點中遵循先左后右的原則。二叉樹的遍歷可分為三種：前序遍歷（DLR）在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。該過程是一個遞歸的過程。中序遍歷（LDR）在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。因此，中序遍歷二叉樹的過程也是一個遞歸的過程。后序遍歷（LRD）在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。因此，后序遍歷二叉樹的過程也是一個遞歸的過程。如果知道了某二叉樹的前序序列和中序序列，則可以唯一地恢復該二叉樹，如果知道了某二叉樹的后序序列和中序序列，則也可以唯一地恢復該二叉樹。但如果只知道某二叉樹的前序序列和后序序列，是不能唯一恢復該二叉樹的。七、查找技術基本方法從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。以下兩種情況只能采用順序查找：①線性表為無序表（即表中元素的排列是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。②即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。順序查找的缺陷：效率太低2．二分法查找（對分查找）適用范圍只適用于順序存儲的有序表，在此所說的有序表是指線性表中元素按值非遞減排列。具體方法設有序線性表的長度為n，被查元素為x，則：①將x與線性表的中間項進行比較：若中間項的值等于x，則說明查到，查找結束；②若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找③若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找④這個過程一直進行到查找成功或子表長度為說明線性表中沒有這個元素）為止。八、排序技術冒泡排序法①定義：冒泡排序法是一種最簡單的交換類排序方法，通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。②基本過程：a．從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。b．從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個逆序。c．對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時的線性表已經(jīng)變?yōu)橛行?。③在上述排序過程中，對線性表的每一次來回掃描后，都將其中的最大者沉到了表的底部，最小者像氣泡一樣冒到表的前頭。冒泡排序由此而得名，且冒泡排序又稱下沉排序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前n/2n（n-1）/2。快速排序法①基本思想從線性表中選取一個元素T，將線性表后面小于T的元素移到前面，前面大于T的元素移到后面，這樣就以T為分割線將線性表分割成前后兩個子表。再將得到的子表按照這個過程繼續(xù)下去，直到所有子表為空為止。②快速排序在最壞情況下需要進行n（n-1）/2次比較，但實際的排序效率要比冒泡排序高得多。插入類排序法簡單插入排序法①定義:所謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。②插入過程：將第j個元素放到一個變量T中，然后從有序子表的最后一個元素（即線性j-1）開始，往前逐個與TT后移動一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，此時就將T（即原線性表中的第j）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖③這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n（n-1）/2希爾排序法①基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序。②子序列的分割方法：將相隔某個增量h的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當h減到1時，進行一次插入排序，排序就完成。增量序列一般取h＝n/k（k＝1，2，…，[logn]），其中n為待排序序列的長度。t 2③如果選取上述增量序列，則在最壞情況下，希爾排序所需要的比較次數(shù)0（）。選擇類排序法簡單選擇排序法①基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置）；然后對剩下的子表采用同樣的方法，直到子表空為止。對于長度為n的序列，選擇排序需要掃描n-1遍，每一遍掃描均從剩下的子表中選出最小的元素，然后將該最小的元素與子表中的第一個元素進行交換。②簡單選擇排序法在最壞情況下需要比較n（n-1）/2堆排序法①堆的定義具有n（h，h，…，h

），當且僅當滿足1 2 n（i＝1，2，…，n/2）時稱之為堆。②堆排序的方法：b．將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最大項應該在序列的最后）；c．反復做上一步，直到剩下的子序列為空為止。③在最壞情況下，堆排序需要比較的次數(shù)為0（nlog

n）。22章程序設計基礎一、程序設計方法與風格1．程序設計發(fā)展階段就程序設計方法和技術的發(fā)展而言，主要經(jīng)過了結構化程序設計和面向對象的程序設計階段。程序設計方格程序設計風格會影響軟件的質量和可維護性，良好的程序設計風格可以使結構清晰合理，程序代碼便于維護，程序設計風格總體強調簡明清晰，易讀易懂，程序必須是可理解的，總體遵循“清晰第一，效率第二”的原則。良好的程序設計風格應考慮的因素源程序文檔化①符號名的命名符號名的命名應具有一定的實際含義，以便于對程序功能的理解。②程序注釋位于每個程序的開頭部分，給出程序的整體說明，主要描述內容可以包括：程序標題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設計者、復審者、復審日期、修改日期等。b．功能性注釋嵌在源程序體之中，主要描述其后的語句或程序做什么。③視覺組織在程序中利用空格、空行、縮進等技巧可以使層次清晰，便于閱讀。數(shù)據(jù)說明的方法為使程序中的數(shù)據(jù)說明更易于理解和維護，應注意以下幾點：①數(shù)據(jù)說明的次序規(guī)范化數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的屬性容易查找，也有利于測試、排錯和維護。②說明語句中變量安排有序化當一個說明語句說明多個變量時，變量按照字母順序排序為好。③使用注釋來說明復雜數(shù)據(jù)的結構。語句的結構程序應該簡單易懂，語句構造應該簡單直接，不為提高效率而把語句復雜化。①在一行內只寫一條語句；②程序編寫應優(yōu)先考慮清晰性；③除非對效率有特殊要求，程序編寫要做到清晰第一，效率第二；④首先要保證程序正確，然后才要求提高速度；⑤避免使用臨時變量而使程序的可讀性下降；⑥避免不必要的轉移；⑦盡可能使用庫函數(shù)；⑧避免采用復雜的條件語句；⑨盡量減少使用“否定”條件的條件語句；⑩數(shù)據(jù)結構要有利于程序的簡化；要模塊化，使模塊功能盡可能單一化；利用信息隱蔽，確保每一個模塊的獨立性；從數(shù)據(jù)出發(fā)去構造程序；不要修補不好的程序，要重新編寫；輸入和輸出輸入輸出的方式和格式應當盡量方便用戶使用，在設計和編程時應遵循以下原則：①對所有的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性；②檢查輸入項的各種重要組合的合理性；③輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單；④輸入數(shù)據(jù)時，應允許使用自由格式；⑤應允許缺省值；⑥輸入一批數(shù)據(jù)時，最好使用輸入結束標志；⑦在以交互式輸入／輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結束時，應在屏幕上給出狀態(tài)信息；⑧當程序設計語言對輸入格式有嚴格要求時，應保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設計輸出報表格式。二、結構化程序設計結構化程序設計方法的主要原則可以概括為自頂向下，逐步求精，模塊化，goto自頂向下先考慮總體后考慮細節(jié)，先考慮全局目標，后考慮局部目標。先從最上層總目標開始設計，逐步使問題具體化。逐步求精對復雜問題，應設計一些子目標作過渡，逐步細化。模塊化把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。goto①濫用GOTO②完全避免使用GOTO語句也并非是個明智的方法，有些地方使用GOTO語句，會使程序流程更清楚、效率更高；③爭論的焦點不應該放在是否取消GOTO語句，而應該放在用什么樣的程序結構上。其中最關鍵的是，肯定以提高程序清晰性為目標的結構化方法。2．結構化程序的基本結構與特點基本結構①順序結構順序結構是一種簡單的程序設計，它是最基本、最常用的結構，按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序。②選擇結構（分支結構）選擇結構包括簡單懸著多分枝選擇，可根據(jù)設定條件，判斷應該選擇哪一個分支來執(zhí)行相應的語句序列。③循環(huán)結構根據(jù)給定的條件，判斷是否重復執(zhí)行某一個相同的或類似的程序段，利用循環(huán)可以大大簡化大量的程序行。當型循環(huán)結構：先判斷后執(zhí)行循環(huán)體；b．直到型循環(huán)結構：先執(zhí)行循環(huán)體后判斷。結構化程序設計方法的優(yōu)點①程序易于理解、使用和維護，便于控制、降低程序的復雜性，可理解性好；②提高了編程工作的效率，降低了軟件開發(fā)成本。3．結構化程序設計原則和方法的應用在結構化程序設計中應把握以下要素：使用程序設計語言中的順序、選擇、循環(huán)等有限的控制結構表示程序的控制邏輯；選用的控制結構只準許有一個入口和一個出口；程序語句組成容易識別的塊，每塊只有一個入口和一個出口；復雜結構應該用嵌套的基本控制結構進行組合嵌套來實現(xiàn)；語言中所沒有的控制結構，應該采用前后一致的方法來模擬；嚴格控制GOTO語句的使用。其意思是指：①用一個非結構化的程序設計語言去實現(xiàn)一個結構化的構造；GOTO③在某種可以改善而不是損害程序可讀性的情況下。三、面向對象的程序設計關于面向對象方法面向對象的本質從客觀世界固有的事物出發(fā)來構造系統(tǒng)，提倡用人類在現(xiàn)實生活中常用的思維方法來認識、理解和描述客觀事物，強調最終建立的系統(tǒng)能夠映射問題域，即系統(tǒng)中的對象以及對象之間的關系能夠如實地反映問題域中固有事物及其關系。面向對象的主要優(yōu)點①與人類習慣的思維方法一致面向對象的設計和技術以對象為核心，與客觀實體有直接的對應關系，對象之間傳遞信息互相聯(lián)系，以模擬現(xiàn)實世界中不同事物彼此之間的聯(lián)系。強調模擬現(xiàn)實世界中的概念而不是強調算法，鼓勵開發(fā)者在軟件開發(fā)的絕大部分過程中都應用領域的概念去思考。②穩(wěn)定性好面向對象的軟件系統(tǒng)結構是根據(jù)問題領域的模型建立起來，而不是基于對系統(tǒng)應完成功能的分解，當對系統(tǒng)的功能需求變化時不會引起軟件結構的整體變化，僅需要做一些局部性的修改。③可重用性好a．面向對象方法中使用的對象和數(shù)據(jù)是作為平等地位出現(xiàn)的。對象有很強的自含性，且對象固有的封裝性使得對象的內部實現(xiàn)與外界隔離，具有較強的獨立性。重復使用一個對象的兩種方法：第一，創(chuàng)建該類的實例，直接使用它；第二，從它派生出一個滿足當前需要的新類。④易于開發(fā)大型軟件產品用面向對象范型開發(fā)軟件時，可以把一個大型產品看作是一系列本質上相互獨立的小產品來處理，這就不僅降低了開發(fā)的技術難度，而且也使得對開發(fā)工作的管理變得容易。⑤可維護性好軟件的可維護性是長期困擾人們的一個嚴重問題，是軟件危機的突出表現(xiàn)。面向對象設計軟件可維護性好的主要表現(xiàn)①用面向對象的方法開發(fā)的軟件穩(wěn)定性比較好功能或性能的要求發(fā)生變化時，不會引起軟件整體變化，只需要對局部做修改，容易實現(xiàn)。②用面向對象的方法開發(fā)的軟件比較容易修改對象具有理想的模塊機制，獨立性好，修改一個類很少會牽扯到其它類，特有的繼承機制使得對開發(fā)的軟件的修改和擴充比較容易實現(xiàn)。③用面向對象的方法開發(fā)的軟件比較容易理解面向對象的技術符合人們習慣的思維方式，用這種方法所建立的軟件系統(tǒng)的結構與問題空間的結構基本一致。因此，面向對象的軟件系統(tǒng)比較容易理解。對面向對象軟件系統(tǒng)進行修改和擴充，通常是通過在原有類的基礎上派生出一些新類來實現(xiàn)。④易于測試和調試面向對象設計的軟件在維護后的測試和調試工作主要是圍繞新派生出來的類進行。類是獨立性很強的模塊，因此軟件的測試和調試就很容易實現(xiàn)。面向對象方法的基本概念對象①概念對象用來表示客觀世界中的任何實體，在應用領域中，有意義的、與所要解決的問題有關系的任何事物都可以作為對象。②面對對象的程序設計方法中的對象該對象是系統(tǒng)中用來描述客觀事物的一個實體，是構成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。a．屬性屬性即對象包含的信息，在設計對象時確定，一般只能通過執(zhí)行對象的操作來改變。b．操作描述了對象執(zhí)行的功能，通過消息傳遞還可以為其他對象使用，操作的過程對外是封閉的，用戶只能看到操作實施的結果，所有的操作過程都封裝在對象中。a．標識唯一性對象是可區(qū)分的，且這種區(qū)分是通過對象的內在本質，而不是通過描述來區(qū)分。b．分類性可以將具有相同屬性和操作的對象抽象成類。c．多態(tài)性同一個操作可以是不同對象的行為。d．封裝性從外面只能看到對象的外部特征，只知道數(shù)值的取值范圍和可以對數(shù)據(jù)施加的操作，無法知道數(shù)據(jù)的具體結構及實現(xiàn)操作的算法。對象的處理能力對外不可見，從外面不能直接使用對象的處理能力，無法修改其內部狀態(tài)，其內部狀態(tài)只能由其自身改變。e．模塊獨立性好對象是面向對象的軟件的基本模塊，它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為中心的，操作圍繞對其數(shù)據(jù)所需做的處理來設置，沒有無關的操作。從模塊的獨立性考慮，對象內部各種元素彼此結合得很緊密，內聚性強。類和實例①類是具有相同屬性，共同方法的對象的集合，它描述了屬于該對象類型的所有對象的性質，一個對象是其對應類的一個實例。②使用“對象”這個術語時，可以指一個具體的對象，也可以泛指一般的對象。當使用“實例”這個術語時，必然是指一個具體的對象。③類是關于對象性質的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。消息①消息是一個實例與另一個實例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。②消息中只包含傳遞者的要求，告訴接收者應該做哪些處理，但不指示接收者應該怎樣完成這些處理。接收者獨立決定采用什么樣的方式完成所需的處理。③一個對象能夠接收不同形式，不同內容的多個消息；相同形式的消息可以送往不同的對象，不同對象對于形式相同的消息可以有不同的解釋，作出不同反應。④一個消息由下述三部分組成：a．接收消息的對象的名稱；b．消息標識符（也稱為消息名）；c．零個或多個參數(shù)。繼承①定義：繼承是使用已有的類定義作為基礎建立新類的定義技術，已有的類可當做基類來引用，新類當做派生類來引用。②面對對象軟件技術的許多功能和優(yōu)點來源于將類組成一個層次結構的系統(tǒng)：一個類的上層可以有父類下層可以有子類，這種系統(tǒng)的重要性質是繼承性；一個類直接繼承父類的特性，子類自動地共享基類中定義的數(shù)據(jù)和方法。a．單繼承一個類只允許有一個父類，類等級為樹狀結構。b．多繼承一個類允許有多個父類，可以組合多個父類的性質構成所需要的性質。功能更強，使用更方便；注意避免二義性。④繼承性的優(yōu)點：a．相似的對象可以共享程序代碼和數(shù)據(jù)結構，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件修改維護。b．用戶在開發(fā)新的應用系統(tǒng)時不必完全從零開始，可以繼承原有的相似系統(tǒng)的功能或者從類庫中選取需要的類，再派生出新的類以實現(xiàn)所需要的功能。多態(tài)性①多態(tài)性是指對象根據(jù)所接收的消息而做出動作，同樣的消息被不同的對象接收時可導致完全不同的行動的一種現(xiàn)象。②在面向對象的軟件技術中，多態(tài)性是指子類對象可以像父類對象那樣使用，同樣的消息既可以發(fā)送給父類對象也可以發(fā)送給子類對象。③多態(tài)性機制增加了面向對象軟件系統(tǒng)的靈活性，進一步減少了信息冗余，顯著地提高了軟件的可重用性和可擴充性。3章軟件工程基礎一、軟件工程基本概念軟件定義與軟件特點軟件的定義計算機軟件（Software）是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關文檔的完整集合。軟件的組成①機器可以執(zhí)行的程序和數(shù)據(jù)；②機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關的文檔。軟件的特點①軟件是一種邏輯實體，而不是物理實體，具有抽象性?？捎涗浽诩埳匣虼鎯橘|上，無法看到其本身形態(tài)，必須通過觀察、分析、思考、判斷才能了解其功能和特性。②軟件的生產與硬件不同，它沒有明顯的制作過程。開發(fā)成功可以大量復制，所以對軟件的質量控制主要集中在開發(fā)方面。③軟件在運行、使用期間不存在磨損、老化問題。軟件雖然在生存周期后期不會因為磨損而老化，但為適應硬件等變化，必要時要做出修改。修改可能會引入錯誤，導致軟件失效率升高，軟件退化。④軟件的開發(fā)、運行對計算機系統(tǒng)有很大依賴性，導致軟件出現(xiàn)移植問題。⑤軟件復雜性高，成本昂貴。軟件開發(fā)涉及各行業(yè)的專業(yè)知識，需要投入大量、高強度的腦力勞動，成本高，風險大。⑥軟件開發(fā)涉及諸多的社會因素。許多軟件的開發(fā)和運行涉及軟件用戶的機構設置，體制問題以及管理方式等，甚至涉及人們的觀念和心理，軟件知識產權及法律等問題。軟件的分類軟件按照應用功能劃分，可分為：①應用軟件應用軟件是為解決特定領域的應用而開發(fā)的軟件。常用的應用軟件：事務處理軟件，工程與科學計算軟件，實時處理軟件等。②系統(tǒng)軟件系統(tǒng)軟件是計算機管理自身資源，提高計算機使用效率并服務于其他程序的軟件。常用的系統(tǒng)軟件：操作系統(tǒng)，編譯程序，匯編程序，網(wǎng)絡軟件，數(shù)據(jù)庫管理系統(tǒng)等③支撐軟件支撐軟件是介于系統(tǒng)軟件和應用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件，包括輔助和支持開發(fā)和維護應用軟件的工具軟件。常用的支撐軟件：需求分析工具軟件，設計工具軟件，編碼工具軟件，測試工具軟件等。軟件危機與軟件工程軟件危機①定義軟件危機泛指計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。②主要表現(xiàn)a．軟件需求的增長得不到滿足，用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生；b．軟件開發(fā)成本和進度無法控制，開發(fā)成本超出預算，開發(fā)周期大大超過規(guī)定日期的情況經(jīng)常發(fā)生；c．軟件質量難以保證；d．軟件不可維護或維護程度非常低；e．軟件的成本不斷提高；f．軟件開發(fā)生產率的提高趕不上硬件的發(fā)展和應用需求的增長。③產生原因a．對軟件需求速度大大超過了技術進步帶來的軟件生產率的提高；b．軟件工程所面臨的任務和其他工程之間的差異以及軟件和其他工業(yè)產品的不同。軟件工程①定義IEEE給出一個綜合的定義是：將系統(tǒng)化的、規(guī)范的、可度量的方法應用于軟件的開發(fā)、運行和維護的過程，即將工程化應用于軟件中。②三要素a．方法：完成軟件工程項目的技術手段。b．工具：支持軟件的開發(fā)、管理、文檔生成。c．過程：支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。③核心把軟件產品當作工程產品來處理，把需求計劃、可行性研究、工程審核、質量監(jiān)督等工程化的概念引入到軟件生產當中，以期達到工程項目的三個基本要素：進度、經(jīng)費和質量的目標。同時，也注重研究不同于其他工業(yè)產品生產的一些獨特特性，并針對軟件的特點提出了許多有別于一般工業(yè)工程技術的一些技術方法。代表性的有結構化的方法、面向對象方法和軟件開發(fā)模型及軟件開發(fā)過程等。軟件過程與軟件生命周期軟件過程①定義ISO9000動。②內涵a．為獲得軟件產品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動。通常包括四方面活動：第一，P（Plan）——軟件規(guī)格說明。規(guī)定軟件的功能及其運行時的限制；第二，D（Do）——軟件開發(fā)或軟件設計與實現(xiàn)。生產滿足規(guī)格說明的軟件；第三，C（Cheek）——軟件確認。確認軟件能夠滿足客戶提出的要求；第四，A（Action）——軟件演進。為滿足客戶的變更要求，軟件必須在使用的過程中演進。b．使用適當?shù)馁Y源，為開發(fā)軟件進行的一組開發(fā)活動，在過程結束時將輸入（用戶要求）轉化為輸出（軟件產品）。軟件生命周期①定義軟件生命周期是指軟件產品從提出、實現(xiàn)、使用維護到停止使用退役的過程。②階段軟件定義階段包括可行性研究初步項目計劃和需求分析階段。主要任務：確定軟件開發(fā)工作必須完成的目標，確定工程可行性b．軟件開發(fā)軟件開發(fā)階段包括總體設計、詳細設計、編碼與測試階段。主要任務：具體完成設計和實現(xiàn)定義階段所定義的軟件，總體設計和詳細設計又稱為系統(tǒng)設計，編碼和測試又稱為系統(tǒng)實現(xiàn)。c．軟件運行維護軟件運行維護階段包括使用、維護和退役階段。主要任務：使軟件在運行中持久地滿足用戶的需要，及時改正軟件在使用中發(fā)生的錯誤，修改軟件以適應不同的使用環(huán)境。③各階段的基本任務確定待開發(fā)軟件系統(tǒng)的開發(fā)目標和總的要求，給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開發(fā)任務的實施計劃。需求分析對待開發(fā)軟件提出的需求進行分析并給出詳細定義。編寫軟件規(guī)格說明書及初步的用戶手冊，提交評審。軟件設計系統(tǒng)設計人員和程序設計人員應該在反復理解軟件需求的基礎上，給出軟件的結構、模塊的劃分、功能的分配以及處理流程。在系統(tǒng)比較復雜的情況下，設計階段可分解成概要設計階段和詳細設計階段。編寫概要設計說明書、詳細設計說明書和測試計劃初稿，提交評審。編碼編碼是把軟件設計轉換成計算機可以接受的程序代碼。即完成源程序的編碼，編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試計劃。軟件測試在設計測試用例的基礎上，檢驗軟件的各個組成部分。編寫測試分析報告。f．運行和維護將已交付的軟件投入運行，并在運行使用中不斷地維護，根據(jù)新提出的需求進行必要而且可能的擴充和刪改。軟件工程的目標與原則軟件工程的目標①定義軟件工程的目標是，在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產品。②基本目標：a．付出較低的開發(fā)成本；b．達到要求的軟件功能；c．取得較好的軟件性能；d．開發(fā)的軟件易于移植；e．需要較低的維護費用；f．能按時完成開發(fā)，及時交付使用。③軟件工程的理論和技術性研究的內容：a．軟件開發(fā)技術第一，軟