計(jì)算思維復(fù)習(xí)大綱課件

期末復(fù)習(xí)－及考試相關(guān)關(guān)于考試考試時(shí)間：1月4號(hào)8:00-9:50考試形式：閉卷筆試考試題型：50個(gè)單選題（每個(gè)1分） 10個(gè)填空題（每空1分）

10個(gè)判斷題（每個(gè)1分）

6個(gè)綜合題（每個(gè)5分）考試范圍：第1、2、3、4、5章全部內(nèi)容注意:開考后40分鐘后方可交卷,答題紙上印有"座號(hào)"字樣,請(qǐng)按本班學(xué)號(hào)排序號(hào)填寫第一章計(jì)算、計(jì)算工具的歷史沿革：

在電腦史前史里，帕斯卡被公認(rèn)為制造出機(jī)械計(jì)算機(jī)的第一人。P7

巴貝奇耗費(fèi)了整整１０年時(shí)間，于１８２２年完成了第一臺(tái)差分機(jī)。P9

楚澤的繼電器計(jì)算機(jī)是世界上第一臺(tái)二進(jìn)制電子運(yùn)算機(jī)器。P11

美國賓夕法尼亞大學(xué)和有關(guān)單位在１９４６年制成了第一臺(tái)電子計(jì)算機(jī)——電子數(shù)字積分儀與計(jì)算機(jī)”ＥＮＩＡＣ。P11-12計(jì)算與學(xué)科滲透：P13

隨著當(dāng)代科學(xué)技術(shù)的發(fā)展，不同學(xué)科之間的相互滲透、交叉和綜合已成為當(dāng)今科技發(fā)展的一個(gè)重要趨勢(shì)。計(jì)算機(jī)科學(xué)并不是一門獨(dú)立的學(xué)科，它在學(xué)科融合、滲透中獨(dú)占鰲頭。當(dāng)前熱點(diǎn)計(jì)算：云計(jì)算：云計(jì)算是一種按使用量付費(fèi)的模式，這種模式提供可用的、便捷的、按需的網(wǎng)絡(luò)訪問，進(jìn)入可配置的計(jì)算資源共享池(資源包括網(wǎng)絡(luò)、服務(wù)器、存儲(chǔ)、應(yīng)用軟件、服務(wù))，這些資源能夠被快速提供，只需投入很少的管理工作或與服務(wù)供應(yīng)商進(jìn)行很少的交互。

P24

特點(diǎn)：虛擬化技術(shù)、靈活定制、動(dòng)態(tài)可擴(kuò)展性、高可靠性和安全性、高性價(jià)比。物聯(lián)網(wǎng)：廣義的物聯(lián)網(wǎng)定義認(rèn)為物聯(lián)網(wǎng)是在互聯(lián)網(wǎng)的基礎(chǔ)上，借助各種信息傳感設(shè)備，通過各種接入網(wǎng)絡(luò)實(shí)現(xiàn)物體與互聯(lián)網(wǎng)連接，形成人與物、物與物互聯(lián)的巨大智能網(wǎng)絡(luò)。

廣泛應(yīng)用于航天、交通、農(nóng)業(yè)、物流等領(lǐng)域。P27

大數(shù)據(jù)：指需要新處理模式才能具有更強(qiáng)的決策力、洞察發(fā)現(xiàn)力和流成優(yōu)化能力的海量、高增長率和多樣化的信息資產(chǎn)。P30

特點(diǎn)：數(shù)據(jù)體量巨大、數(shù)據(jù)種類繁多、流動(dòng)速度快、價(jià)值密度低。P31

可穿戴計(jì)算：智慧城市：思維與計(jì)算思維：常見的思維模式分為３種：P38①以觀察和歸納自然(包括人類社會(huì)活動(dòng))規(guī)律為特征的實(shí)證思維；②以推理和演繹為特征的邏輯思維；③以抽象化和自動(dòng)化為特征的計(jì)算思維；第二章計(jì)算機(jī)概述：P45-46

1、世界上第一臺(tái)電子計(jì)算機(jī)，1946年2月在美國賓夕法尼亞大學(xué)誕生,取名為ＥＮＩＡＣ。2、電子計(jì)算機(jī)的發(fā)展按構(gòu)成計(jì)算機(jī)的電子器件來劃分，至今已經(jīng)歷了４代：第一代電子管計(jì)算機(jī)，主要用于科學(xué)計(jì)算；第二代晶體管計(jì)算機(jī)，提出操作系統(tǒng)概念，出現(xiàn)FORTRAN等高級(jí)語言；第三代集成電路計(jì)算機(jī)；第四代大規(guī)模和超大規(guī)模集成電路計(jì)算機(jī)時(shí)代，微型計(jì)算機(jī)開始出現(xiàn)。圖靈與圖靈機(jī)：P55圖靈機(jī)是英國數(shù)學(xué)家阿蘭圖靈于１９３６年提出的一種抽象計(jì)算模型。計(jì)算機(jī)的基本組成及工作原理：

馮諾依曼原理：

P57現(xiàn)代計(jì)算機(jī)是一個(gè)自動(dòng)化的信息處理裝置，而它之所以能實(shí)現(xiàn)自動(dòng)化信息處理，是因?yàn)椴捎昧恕按鎯?chǔ)程序”工作原理。這一原理是１９４６年由馮諾依曼提出并論證的，這一原理確立了現(xiàn)代計(jì)算機(jī)的基本組成和工作方式：①計(jì)算機(jī)硬件由５個(gè)基本部分組成:運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備和輸出設(shè)備；②計(jì)算機(jī)內(nèi)部采用二進(jìn)制來表示程序和數(shù)據(jù)；③采用“存儲(chǔ)程序”的方式，將程序和數(shù)據(jù)放入同一個(gè)存儲(chǔ)器中，計(jì)算機(jī)能夠自動(dòng)高速地從存儲(chǔ)器中取出指令加以執(zhí)行。五大部件在控制器的控制下協(xié)調(diào)統(tǒng)一地工作。首先，把表示計(jì)算步驟的程序和計(jì)算中需要的原始數(shù)據(jù)在控制器輸入命令的控制下，通過輸入設(shè)備送入計(jì)算機(jī)的存儲(chǔ)器進(jìn)行存儲(chǔ)；

其次當(dāng)計(jì)算開始時(shí)，在取指令作用下把程序指令逐條送入控制器，控制器對(duì)指令進(jìn)行譯碼，并根據(jù)指令的操作要求向存儲(chǔ)器和運(yùn)算器發(fā)出存儲(chǔ)、取數(shù)命令和運(yùn)算命令，經(jīng)過運(yùn)算器計(jì)算并把結(jié)果存放在存儲(chǔ)器內(nèi)，

最后在控制器的取數(shù)和輸出命令作用下，通過輸出設(shè)備輸出計(jì)算結(jié)果。

1、通常將運(yùn)算器和控制器統(tǒng)稱為中央處理器(ＣＰＵ)，它是整個(gè)計(jì)算機(jī)的核心部件，是計(jì)算機(jī)的“大腦”，它控制了計(jì)算機(jī)的運(yùn)算、處理、輸入和輸出等工作。）2、存儲(chǔ)容量的大小以字節(jié)為單位來度量，經(jīng)常使用ＫＢ(千字節(jié))、ＭＢ(兆字節(jié))、ＧＢ(千兆字節(jié))和ＴＢ(兆兆字節(jié))來表示。它們之間的關(guān)系是:１ＫＢ＝１０２４Ｂ；１ＭＢ＝１０２４ＫＢ；１ＧＢ＝１０２４ＭＢ；１ＴＢ＝１０２４ＧＢ。3、存儲(chǔ)器分為內(nèi)存儲(chǔ)器(主存儲(chǔ)器)和外存儲(chǔ)器(輔助存儲(chǔ)器)兩大類。P59

內(nèi)存在計(jì)算機(jī)主機(jī)內(nèi)，它直接與運(yùn)算器、控制器交換信息，容量雖小，但存取速度快，一般只存放那些正在運(yùn)行的程序和待處理的數(shù)據(jù)。

內(nèi)存分為RAM(可隨機(jī)讀寫，斷電后數(shù)據(jù)消失)和ROM（它只能讀出信息，不能寫入信息，斷電后仍能保存數(shù)據(jù))

外存儲(chǔ)器是指除計(jì)算機(jī)內(nèi)存及ＣＰＵ緩存（高速緩存讀取速度相對(duì)更快）以外的存儲(chǔ)器，外存中的程序和數(shù)據(jù)必須先送入內(nèi)存才能被計(jì)算機(jī)執(zhí)行，外存存取速度慢，但容量很大，此類存儲(chǔ)器一般斷電后仍然能保存數(shù)據(jù)。常見的外存儲(chǔ)器有硬盤、軟盤、光盤、Ｕ盤等。

4、常用的輸入設(shè)備有鍵盤、鼠標(biāo)、光筆、掃描儀、數(shù)字化儀、條形碼閱讀器等；常用的輸出設(shè)備有顯示器、打印機(jī)、繪圖儀等。

5、沒有安裝軟件的計(jì)算機(jī)稱為“裸機(jī)”。

6、計(jì)算機(jī)軟件可分為系統(tǒng)軟件和應(yīng)用軟件兩大類。P61

系統(tǒng)軟件包括操作系統(tǒng)、數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng)、程序設(shè)計(jì)語言及其解釋編譯程序、網(wǎng)絡(luò)管理軟件等；

應(yīng)用軟件包括文字處理、圖形圖像處理、音頻視頻處理、殺毒類等。7、操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中必不可少的軟件，是用戶和計(jì)算機(jī)之間的接口，任何一個(gè)用戶要使用計(jì)算機(jī)都必須首先安裝操作系統(tǒng)。操作系統(tǒng)是一個(gè)管理電腦硬件與軟件資源的程序，同時(shí)也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石。目前常見的操作系統(tǒng)有ＤＯＳ、ＯＳ/２、ＵＮＩＸ、Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ系列、Ｎｅｔｗａｒｅ等8、主板(又稱主機(jī)板ＭａｉｎＢｏａｒｄ或系統(tǒng)板ＳｙｓｔｅｍＢｏａｒｄ等)是微機(jī)內(nèi)最大的一塊集成電路板。計(jì)算機(jī)問題求解：P68精確問題也可稱為界定清晰的問題，是指初始狀態(tài)、目標(biāo)狀態(tài)以及由初始狀態(tài)如何達(dá)到目標(biāo)狀態(tài)的一系列過程都很清楚的問題。例如：已知Ａ>Ｂ，Ｂ<Ｃ，問Ａ與Ｃ哪個(gè)大？這是一個(gè)目的非常明確的問題。模糊問題也稱界定含糊的問題，是指那些對(duì)問題的初始狀態(tài)或目標(biāo)狀態(tài)沒有清楚的說明，或者對(duì)二者都沒有明確說明的問題，這些問題具有很大的不確定性。例如“如何寫一篇論文”這個(gè)問題的初始狀態(tài)和目標(biāo)狀態(tài)都是不清楚的。計(jì)算機(jī)求解問題過程首先是分析問題并建立數(shù)學(xué)模型

二進(jìn)制：進(jìn)制之間的轉(zhuǎn)換：

十－二進(jìn)制轉(zhuǎn)換：整數(shù)部分，除2取余法；小數(shù)部分，乘2取整法。二－八進(jìn)制轉(zhuǎn)換：整數(shù)部分，三位一組，從右往左；小數(shù)部分，三位一組，從左往右數(shù)值信息的表示與運(yùn)算：在計(jì)算機(jī)中數(shù)值型的數(shù)據(jù)有兩種表示方法，一種叫做定點(diǎn)數(shù)，另一種叫做浮點(diǎn)數(shù)。原碼、反碼、補(bǔ)碼

第三章非數(shù)值型數(shù)據(jù)：1、非數(shù)值信息包括文字、圖形、圖像、聲音等，在計(jì)算機(jī)中采用編碼的方式來表示。2、目前計(jì)算機(jī)中采用的字符編碼主要是ASCII碼，它是ＡmericanStandardCodeforInformationInterchange（美國標(biāo)準(zhǔn)信息交換代碼)的縮寫，已被國際標(biāo)準(zhǔn)化組織(ISO)采納，作為國際通用的信息交換標(biāo)準(zhǔn)代碼。ASCII碼有７位ASCII碼和８位ASCII碼兩種編碼方式。

７位ASCII

碼稱為標(biāo)準(zhǔn)ASCII碼，用一個(gè)字節(jié)(８位)表示一個(gè)字符，并規(guī)定其最高位為０，可表示128個(gè)不同字符。

８位ASCII

碼稱為擴(kuò)展ASCII碼，用８位二進(jìn)制進(jìn)行編碼，最高位恒為１。擴(kuò)展部分的范圍為128-255，代表128個(gè)擴(kuò)展字符。８位ASCII

碼總共可以代表256個(gè)字符。

會(huì)使用標(biāo)準(zhǔn)ASCII碼字符表P98

漢字編碼：P99

漢字處理過程：在計(jì)算機(jī)中輸入漢字時(shí)，操作者在鍵盤上輸入“輸入碼”，通過“輸入碼”找到漢字的國標(biāo)區(qū)位碼(也稱為交換碼)，再計(jì)算出漢字的機(jī)內(nèi)碼后存儲(chǔ)，而當(dāng)顯示或打印漢字時(shí)，則首先從指定地址取出漢字內(nèi)碼，根據(jù)內(nèi)碼從字模庫中取出漢字的字形碼，并以漢字字形碼輸出到屏幕或打印機(jī)上。

1、輸入碼是用鍵盤上的字母符號(hào)編碼組合來表示每一個(gè)漢字的編碼，它使人們通過鍵入字母符號(hào)代替鍵入漢字，也稱為漢字外部碼(簡稱外碼)。

2、漢字交換碼是指具有漢字處理功能的不同計(jì)算機(jī)系統(tǒng)之間在交換漢字信息時(shí)所使用的代碼標(biāo)準(zhǔn)，也稱國標(biāo)碼。為了能區(qū)分漢字與ASCII碼，在計(jì)算機(jī)內(nèi)部表示漢字時(shí)把交換碼(國標(biāo)碼)兩個(gè)字節(jié)的最高位改為１，稱為機(jī)內(nèi)碼。在漢字信息系統(tǒng)內(nèi)部對(duì)漢字信息的采集、傳輸、存儲(chǔ)、加工運(yùn)算的各個(gè)過程都要用到機(jī)內(nèi)碼，機(jī)內(nèi)碼是計(jì)算機(jī)內(nèi)部真正用來存儲(chǔ)和處理漢字信息的代碼。

3、字形碼記錄漢字的外形，用來將漢字顯示到屏幕上或打印到紙上，是漢字的輸出形式。記錄漢字字形通常有點(diǎn)陣法和矢量法兩種方法，其中點(diǎn)陣規(guī)模越大，字形越清晰美觀，在字模庫中所占用的空間也越大?！按蟆雹蹤C(jī)內(nèi)碼：漢字在計(jì)算機(jī)內(nèi)部采用漢字內(nèi)碼存儲(chǔ)，每個(gè)漢字占兩字節(jié)且最高位均為1的0，1型編碼。計(jì)算機(jī)內(nèi)部由外到內(nèi)由內(nèi)到外b7

b6b5b4b3b2b1b0

b7

b6b5b4b3b2b1b0

0011010001110011國標(biāo)碼1011010011110011(機(jī))內(nèi)碼“大”漢字字形碼是一種字模點(diǎn)陣碼。也有不同的處理漢字點(diǎn)陣信息的編碼，如向量編碼等oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11ooooo1oo1111111111111111oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo111oooooooooooo11oo1oooooooooo11oooo1oooooooo11ooooo11ooooooo1ooooooo11ooooo1ooooooooo111o

11ooooooooooo1oo計(jì)算機(jī)內(nèi)部由外到內(nèi)由內(nèi)到外大④字形碼是用0和1編碼有、無亮點(diǎn)像素，形成一種點(diǎn)陣形式的漢字字形編碼，通過顯示器或打印機(jī)輸出漢字。0和1與字母符號(hào)---編碼(6)漢字如何進(jìn)行處理?為什么會(huì)有那么多種漢字編碼?簡易１６Ｘ１６，普及２４Ｘ２４，提高３２Ｘ３２，精密４８Ｘ４８，點(diǎn)陣規(guī)模越大，字形越清晰美觀，在字模庫中所戰(zhàn)勝的空間也越大。多媒體信息的表示和處理：1、圖像是由掃描儀、照相機(jī)等輸入設(shè)備捕捉實(shí)際的畫面產(chǎn)生的數(shù)字化文件，由像素點(diǎn)陣構(gòu)成。圖像中的每個(gè)像素點(diǎn)用二進(jìn)制位表示，位數(shù)越高，所表示的圖像越接近自然影像，所以圖像又稱為位圖。

常用的圖像文件格式有:BMP、GIF、JPEG、TIFF、PNG、WMF、PSD、PDF等

2、圖形是由一組存儲(chǔ)在計(jì)算機(jī)中的指令組成的，這些指令描述點(diǎn)、線、面等大小形狀及其位置、維數(shù)，計(jì)算機(jī)通過讀取這些指令并將其轉(zhuǎn)換為屏幕上所顯示的形狀和顏色的方式來顯示的圖像，又稱為矢量圖，如office中的剪貼畫?？偟膩碚f，由于矢量圖像存儲(chǔ)的是指令，所以要比位圖圖像文件小得多。

3、音頻文件：常用的聲音文件格式有：WAV、MP3、MIDI等。

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。邏輯結(jié)構(gòu)是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系。包括以下四種：集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)物理結(jié)構(gòu)是指數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)形式。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)、數(shù)據(jù)之間的關(guān)系第四章四種邏輯結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素看做是一個(gè)結(jié)點(diǎn)，用圓圈表示。元素之間的關(guān)系用連線表示。281954736集合：數(shù)據(jù)元素除了同屬于一個(gè)集合外，它們之間沒有什么關(guān)系。各元素是平等的。123456789線性結(jié)構(gòu)：數(shù)據(jù)元素之間是一對(duì)一關(guān)系。數(shù)據(jù)元素之間存在線性關(guān)系，也稱先后關(guān)系，每個(gè)元素都有一個(gè)唯一的前導(dǎo)元素和一個(gè)唯一的后繼元素，第一個(gè)元素沒有前導(dǎo)，最后一個(gè)元素沒有后繼。四種邏輯結(jié)構(gòu)：樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系。1234567圖結(jié)構(gòu)：數(shù)據(jù)元素之間是任意（孤立點(diǎn)、一對(duì)一，一對(duì)多，多對(duì)多）關(guān)系。281954736數(shù)據(jù)元素之間呈現(xiàn)層次關(guān)系，在樹形結(jié)構(gòu)中，每一個(gè)元素通常稱為一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）有一個(gè)父結(jié)點(diǎn)，一個(gè)結(jié)點(diǎn)可以有多個(gè)子結(jié)點(diǎn)在圖狀結(jié)構(gòu)中每個(gè)元素稱為一個(gè)結(jié)點(diǎn)，圖狀結(jié)構(gòu)又稱網(wǎng)狀結(jié)構(gòu)。圖結(jié)構(gòu)可表達(dá)元素之間的任意關(guān)系。物理結(jié)構(gòu)：也稱為存儲(chǔ)結(jié)構(gòu)，即如何把數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中（主要指內(nèi)存，外存通常用文件來描述）。物理結(jié)構(gòu)應(yīng)正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。兩種存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)：邏輯上相鄰的元素存儲(chǔ)在連續(xù)的存儲(chǔ)單元里。用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)集合中的元素。

借助于數(shù)據(jù)在存儲(chǔ)器中的相對(duì)位置表示數(shù)據(jù)之間的關(guān)系。鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素可存放在任意存儲(chǔ)單元里，數(shù)據(jù)元素之間的關(guān)系用箭頭（指針）表示。用一個(gè)指針表示結(jié)點(diǎn)（數(shù)據(jù)元素）之間的邏輯關(guān)系。每個(gè)結(jié)點(diǎn)之間沒有對(duì)應(yīng)的物理關(guān)系

線性結(jié)構(gòu)（棧、隊(duì)列、線性表）線性結(jié)構(gòu)是一種描述元素先后關(guān)系的數(shù)據(jù)結(jié)構(gòu)，也稱為線性表。線性表的順序存儲(chǔ)結(jié)構(gòu)可以用數(shù)組來表示。

a、元素存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元；b、元素的物理順序和邏輯順序一致；c、線性表中的數(shù)據(jù)元素可以隨機(jī)存取。

d、不便于進(jìn)行插入和刪除操作。

線性表的鏈?zhǔn)酱鎯?chǔ)：a、元素存儲(chǔ)在一組地址不連續(xù)的存儲(chǔ)單元；b、元素的物理順序和邏輯順序不一致；c、線性表中的數(shù)據(jù)元素不可以隨機(jī)存取。

d、便于進(jìn)行插入和刪除操作。數(shù)據(jù)域指針域CBAbottomtop棧(Stack)是一種后進(jìn)先出操作受限的線性表，它的插入和刪除操作只能在表的一端(表尾)進(jìn)行。插入：入棧，把新元素放入棧頂top上移刪除：出棧，把棧頂?shù)脑貏h除top下移頭指針尾指針隊(duì)列（Queue）是一種先進(jìn)先出（FirstInLastOut，F(xiàn)ILO）的線性表。只能在表的一端進(jìn)行插入操作（頭指針改變），在另一端進(jìn)行刪除操作（尾指針改變）?！纠恳阎€性表

(A，B，C，D，E，F(xiàn)，G)存儲(chǔ)地址如下表所示，頭指針是1438，填寫指針域中的指針并畫出單鏈表結(jié)構(gòu)圖。存儲(chǔ)地址數(shù)據(jù)域指針域1306F1320D1423C1438A1465G1489B1503EBLAMFECGIDHKJNO結(jié)點(diǎn)樹根葉子結(jié)點(diǎn)孩子雙親兄弟度深度樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系。樹形結(jié)構(gòu)a、數(shù)據(jù)元素之間呈現(xiàn)層次關(guān)系，b、在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)除外，

每個(gè)結(jié)點(diǎn)有一個(gè)雙親結(jié)點(diǎn)。c、一個(gè)結(jié)點(diǎn)可以有多個(gè)子結(jié)點(diǎn)，

數(shù)據(jù)之間的關(guān)系是一對(duì)多的。d、

葉子結(jié)點(diǎn)沒有子結(jié)點(diǎn)。e、度是指節(jié)點(diǎn)的孩子的個(gè)數(shù)。f、深度是組成樹的結(jié)點(diǎn)的最大層數(shù)。2二叉樹二叉樹（BinaryTree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，或者是空集，或者是由一個(gè)根和分別稱為左子樹、右子樹的兩個(gè)不相交的二叉樹構(gòu)成。二叉樹的兩棵子樹有左右之分。樹中結(jié)點(diǎn)的度是任意的，二叉樹中每個(gè)結(jié)點(diǎn)的度不能大于2。BGAHEDCFI二叉樹的應(yīng)用：二叉查找樹（二叉判定樹）二叉排序樹（中序遍歷）霍夫曼編碼（帶權(quán)的二叉樹）圖圖(Graph)是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成。通常表示為：G(V,E)，其中：G表示一個(gè)圖；V是圖G中頂點(diǎn)的集合；E是圖G中邊的集合。圖的基本概念：頂點(diǎn)(Vertex)邊：無向邊、有向邊無向圖、有向圖權(quán)：與邊相關(guān)的數(shù)，如頂點(diǎn)之間的距離、花費(fèi)等ABCD246254abcd貪心算法貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。TSP問題，在下圖中，現(xiàn)要從濟(jì)南出發(fā)，依次旅行完每一個(gè)城市，且每個(gè)城市只去一次，最后回到濟(jì)南，用貪心算法，應(yīng)按何種順序旅游？最短路程是多少？圖的應(yīng)用數(shù)據(jù)管理技術(shù)(1)人工管理階段約20世紀(jì)50年代中期之前數(shù)據(jù)管理（DataManagement）:對(duì)數(shù)據(jù)進(jìn)行高效地組織、編目、分類、定位、排序、存儲(chǔ)、檢索和維護(hù)等。(2)文件系統(tǒng)階段在20世紀(jì)50年代后期到60年代中期(3)數(shù)據(jù)庫系統(tǒng)階段

20世紀(jì)60年代后期以來數(shù)據(jù)庫數(shù)據(jù)庫(DB):DataBase數(shù)據(jù)庫管理員(DBA):DataBaseAdministrator數(shù)據(jù)庫管理系統(tǒng)(DBMS):DataBbaseManagementSystem數(shù)據(jù)庫應(yīng)用(DBAP):DataBaseApplication數(shù)據(jù)庫管理系統(tǒng)（DBMS)的基本功能

a、數(shù)據(jù)庫定義：定義數(shù)據(jù)庫中數(shù)據(jù)表的名稱、標(biāo)題等。

b、數(shù)據(jù)庫操作:向數(shù)據(jù)庫的Table中增加/刪除/更新數(shù)據(jù)及對(duì)數(shù)據(jù)進(jìn)行查詢、檢索、統(tǒng)計(jì)等。c、數(shù)據(jù)庫管理控制:控制數(shù)據(jù)庫中數(shù)據(jù)的使用---哪些用戶可以使用,哪些不可以。常見的數(shù)據(jù)庫管理系統(tǒng)有:AccessSQLServerOracleMySQLFoxProSybase……數(shù)據(jù)模型數(shù)據(jù)庫常見的數(shù)據(jù)模型:層次模型：以樹的形式組織數(shù)據(jù)網(wǎng)狀模型：以圖/網(wǎng)的形式組織數(shù)據(jù)關(guān)系模型：以二維表格的形式組織數(shù)據(jù)面向?qū)ο竽Ｐ停翰捎妹嫦驅(qū)ο蟮姆椒▉碓O(shè)計(jì)數(shù)據(jù)庫其中關(guān)系模型是目前最常見的數(shù)據(jù)模型。數(shù)據(jù)模型是描述數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)的模式，是對(duì)客觀事物及其聯(lián)系的抽象化描述。集合運(yùn)算RABCa12c32d32TABCb22c32d32(1)并R∪TABCa12b22c32d32(2)交R∩TABCc32d32集合運(yùn)算RABCa12c32d32TABCb22c32d32(3)差R-TABCa12T-RABCb22集合運(yùn)算RABCa12c32d32TABCb22c32d32(4)廣義笛卡爾積a12a12a12b22c32d32R×TR.AR.BR.CT.AT.BT.Cc32c32c32b22c32d32d32d32d32b22c32d32選擇(Selection)SnoSname95001李勇SsexSageSdept男20計(jì)算機(jī)95002劉琛女19計(jì)算機(jī)95003王敏女18信息95004章立男19機(jī)械Student查詢計(jì)算機(jī)系全體學(xué)生：查詢計(jì)算機(jī)系女同學(xué)：投影(Projection)SnoSname95001李勇SsexSageSdept男20計(jì)算機(jī)95002劉琛女19計(jì)算機(jī)95003王敏女18信息95004章立男19機(jī)械StudentSname李勇Sdept計(jì)算機(jī)劉琛計(jì)算機(jī)王敏信息章立機(jī)械b.查詢學(xué)生所在系：Sdept計(jì)算機(jī)信息機(jī)械查詢學(xué)生姓名和所在系：投影之后不僅取消了原關(guān)系中的某些列，而且還可能取消某些元組（避免重復(fù)行）計(jì)算機(jī)問題求解過程利用計(jì)算機(jī)求解問題是問題求解手段的改變，計(jì)算機(jī)求解問題的過程與人的計(jì)算過程不同。計(jì)算機(jī)問題求解過程包括數(shù)學(xué)建模、算法設(shè)計(jì)、程序設(shè)計(jì)，最后運(yùn)行程序才能得到問題的解。數(shù)學(xué)建模算法設(shè)計(jì)程序設(shè)計(jì)問題的解問題分析運(yùn)行程序問題數(shù)學(xué)建模：將問題抽象為一個(gè)數(shù)學(xué)問題，并給出求解該數(shù)學(xué)問題的數(shù)學(xué)模型。問題求解的第一步就是要數(shù)學(xué)建模百錢百雞問題、哥尼斯堡七橋問題、漢諾塔問題、TSP問題、阿基米德分牛問題等通過問題分析抽象或引入數(shù)學(xué)變量從而將一個(gè)具體問題的求解推廣為一類問題的求解。首要的和關(guān)鍵的一步就是建立研究對(duì)象的數(shù)學(xué)模型，然后才能借助計(jì)算機(jī)求解。第五章算法設(shè)計(jì)算法設(shè)計(jì)包括算法策略設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和控制結(jié)構(gòu)設(shè)計(jì)。(1)算法策略設(shè)計(jì)算法是解決問題的方法和步驟，算法設(shè)計(jì)即設(shè)計(jì)解決問題的算法策略。TSP問題的算法策略設(shè)計(jì)：

遍歷算法：出現(xiàn)的問題是：

組合爆炸！對(duì)于n個(gè)城市路徑組合數(shù)目：(n-1)!

貪心算法：則可以在局部最優(yōu)的基礎(chǔ)上找出可行路徑，但不一定是全局最優(yōu)解。(2)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)是指與問題或算法相關(guān)的數(shù)據(jù)之間的邏輯關(guān)系及存儲(chǔ)關(guān)系的設(shè)計(jì)，即如何來組織數(shù)據(jù)，才能更高效的解決問題。TSP問題：城市映射為編號(hào):A--1,B--2,C--3,D--4城市間距離關(guān)系:矩陣或二維數(shù)組D，用D[i][j]或D[i,j]來城市間的距離

訪問路徑/解:

一維數(shù)組S，用S[j]來按順序存放到過的城市(3)控制結(jié)構(gòu)設(shè)計(jì)算法的控制結(jié)構(gòu)設(shè)計(jì)即設(shè)計(jì)算法的計(jì)算步驟或計(jì)算規(guī)則，即如何構(gòu)造和表達(dá)處理的規(guī)則，以便能夠按規(guī)則逐步計(jì)算出結(jié)果。控制結(jié)構(gòu)分為三種：①順序結(jié)構(gòu)：即按書寫的順序從上到下、從左到右執(zhí)行。假設(shè)a=5，b=10，如要交換a、b的值，則需按順序執(zhí)行語句：

temp=a;a=b;b=temp;②分支（選擇）結(jié)構(gòu)：根據(jù)條件，成立時(shí)執(zhí)行某些操作，不成立則執(zhí)行另一些操作，或者從多個(gè)分支中選擇一個(gè)來執(zhí)行。③循環(huán)結(jié)構(gòu)：根據(jù)條件，成立則重復(fù)執(zhí)行某些操作，不成立時(shí)則不再循環(huán)。sum=0;for(i=1;i<=n;i++)sum=sum+i;printf("%d",sum);程序設(shè)計(jì)程序設(shè)計(jì)是根據(jù)選定的算法策略和數(shù)據(jù)結(jié)構(gòu)、控制結(jié)構(gòu)設(shè)計(jì)結(jié)果，給出解決特定問題程序的過程。程序設(shè)計(jì)往往以某種計(jì)算機(jī)程序設(shè)計(jì)語言為工具，如C語言、C++語言、Java語言等，寫出這種語言下的程序。從發(fā)展歷程來看，程序設(shè)計(jì)語言一般分為機(jī)器語言、匯編語言和高級(jí)語言。

高級(jí)語言程序的通用性和可移植性大為提高。但高級(jí)語言所編制的程序不能直接被計(jì)算機(jī)識(shí)別，必須經(jīng)過翻譯才能被執(zhí)行，按照翻譯方式的不同，可將它們分為解釋和編譯兩類程序設(shè)計(jì)過程應(yīng)當(dāng)包括分析、設(shè)計(jì)、編碼、測(cè)試、排錯(cuò)等不同階段。最后，運(yùn)行程序，即可得到問題的解。

算法算法（Algorithm）是指解決問題的方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令的計(jì)算序列。算法具有的５個(gè)重要特征：有窮性、確定性、0個(gè)或多個(gè)輸入、一個(gè)或多個(gè)輸出、可行性。

算法描述：自然語言、流程圖、N-S流程圖、偽代碼，掌握任意一種。算法的評(píng)價(jià)和分析算法設(shè)計(jì)首先要保證算法正確性。只有在算法正確的前提下，討論算法的優(yōu)劣才有意義。首先：要對(duì)算法進(jìn)行正確性分析，這個(gè)算法是正確的嗎？算法的輸出是問題的解嗎？其次：算法的復(fù)雜性分析。最常見的是時(shí)間復(fù)雜度分析和空間復(fù)雜度分析。求的值，即表達(dá)式1+2+3+…+n的值。n為正整數(shù)，由鍵盤輸入。算法描述自然語言描述的算法如下：Step1：從鍵盤輸入正整數(shù)nStep2：設(shè)表達(dá)式的值用s表示，且s初始化為0，即s←0Step3：設(shè)變量i的初值為1，即i←1Step4：把i累加到s中，即s←s+iStep5：i的值增1，即i←i+1Step6：如果i<=n，則轉(zhuǎn)Step4；否則轉(zhuǎn)Step7Step7：輸出s的值Step8：結(jié)束開始輸入ns=0i=1i<=n?s=s+1i=i+1輸出s結(jié)束NY開始輸入nsum=0i=1i<=n?sum=sum+ii=i+1輸出sum結(jié)束偽代碼描述：begininputns=0i=1whilei<=ndobegins←s+ii←i+1endoutputsendN-S流程圖描述流程圖描述分析下列程序段的時(shí)間復(fù)雜度。temp=a;a=b;b=temp;上面3個(gè)語句均為賦值語句，都是元操作，執(zhí)行頻度均為1，因此該段代碼的執(zhí)行時(shí)間是與問題規(guī)模n無關(guān)的常數(shù)，即算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。同理，如果算法中僅僅是執(zhí)行了若干條基本操作語句，即使有成千上萬條語句，執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)，也不會(huì)隨著問題規(guī)模n的增加而有所增加，因此這類算法的時(shí)間復(fù)雜度都是O(1)，稱為常量階。分析下列程序段的時(shí)間復(fù)雜度。s=0;i=1;for(i=1;i<=n;i++)s=s+i;分析該算法，各行執(zhí)行的次數(shù)分別為1、1、n、n，因此時(shí)間復(fù)雜度為：T(n)=2n+2=O(n)，稱為線性階。

經(jīng)典問題的算法求解窮舉法：銀行密碼：n位0～9之間的任何數(shù)字，密碼有10n種可能。

0-1背包問題：如果有n件物品，所有可能解的情況則有：

要用一個(gè)n位二進(jìn)制計(jì)數(shù)器，來表示n件物品放入背包的情況。

TSP旅行商問題：實(shí)際上就是路徑的遍歷，出現(xiàn)的問題是：

組合爆炸！對(duì)于n個(gè)城市路徑組合數(shù)目：(n-1)!貪心算法：0-1背包問題，為了使包內(nèi)物品的總價(jià)值最大，先計(jì)算出所有物品的單位價(jià)值，然后從單位價(jià)值由高到低的順序依次選擇物品放入背包，在不超過背包限重的情況下盡可能放更多的物品

TSP旅行商問題：依據(jù)貪心算法思想，每次在選擇下一個(gè)城市

的時(shí)候，只考慮當(dāng)前情況，保證迄今為止所經(jīng)過的總路程最短。

經(jīng)典問題的算法求解遞推法：菲波那切數(shù)列

走樓梯：有一段樓梯有N級(jí)臺(tái)階，規(guī)定每一步只能跨一級(jí)或兩級(jí)，要登上第N級(jí)臺(tái)階有幾種不同的走法,臺(tái)階走法：f(1)=1f(2)=2f(N)=f(N-1)+f(N-2)

兔子繁殖：1-12月份：幼兔：f(1)=0f(2)=1f(n)=f(n-1)+f(n-2)1-12月份：成兔：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)

1-12月份：總兔：f(1)=1f(2)=2f(n)=f(n-1)+f(n-2)

遞歸法：菲波那切數(shù)列、自然數(shù)的定義自然數(shù)n的階乘定義：

漢諾塔的求解：對(duì)于n個(gè)金片，移動(dòng)的次數(shù)是2n-1查找所謂查找，也稱為搜索，是指從若干個(gè)對(duì)象中，找出想要的對(duì)象。順序查找：就是在查找范圍內(nèi)，將給定值按順序逐個(gè)與查找對(duì)象進(jìn)行比較，相等即為查找成功，如果全部比較完還沒有相等的則查找失敗。

查找成功的平均長度為：ASL=折半查找：（二分查找）線性表中的記錄是按照關(guān)鍵字有序的（升序或降序）排列。查找成功的平均長度為：ASL=

算法：首先選取表的中間元素，設(shè)序號(hào)為mid=(1+n)/2，元素Rmid將數(shù)據(jù)表分成大致相等的兩部分{R1,R2,…,Rmid-1}和{Rmid+1,Rmid+2,…,Rn}。先對(duì)Rmid和key作比較，假設(shè)序列升序有序，則比較結(jié)果有三種情況：首先，將表中間位置元素值與查找數(shù)據(jù)比較：key=Rmid：查找成功，返回元素序號(hào)mid。key<Rmid：折半查找前一子表{R1,R2,…,Rmid-1}。key>Rmid：折半查找后一子表{Rmid+1,Rmid+2,…,Rn}。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。折半查找算法演示：數(shù)據(jù)表（查找key=8）K1K2K3K4K5K6K7K8K9K10368121622304558633681216223045586336812162230455863結(jié)論：比較3次終于找到。問題：有哪些數(shù)需要比較1次、2次、3次或4次才能找到？16645382258123063排序：排序是對(duì)一組對(duì)象按照某種規(guī)則進(jìn)行有序排列，通常是把一組對(duì)象整理成按關(guān)鍵字遞增(或遞減)的排列，關(guān)鍵字是指對(duì)象的一個(gè)用于排序的特性。選擇排序：首先在所有數(shù)據(jù)（保存于數(shù)組中）中找出最小值，放在第一個(gè)數(shù)組元素中；接著在不包含第一個(gè)數(shù)組元素的余下的數(shù)組元素中再找出最小值的元素，放置在第二個(gè)數(shù)組元素中；如此下去，一直到最后一個(gè)元素。冒泡