高一信息技術(shù)（必修1）課時(shí)13-第三單元-3-2數(shù)據(jù)與結(jié)構(gòu)（第二課時(shí)）-課件

高一—教科版—信息技術(shù)—必修一第三單元3.2數(shù)據(jù)與結(jié)構(gòu)（第2課時(shí)）學(xué)習(xí)目標(biāo)1.了解樹(shù)的概念和特征2.了解圖的概念和特征3.掌握通過(guò)把圖轉(zhuǎn)化成樹(shù)（枚舉路徑）

來(lái)解決問(wèn)題的基本方法基礎(chǔ)知識(shí)回顧

數(shù)據(jù)結(jié)構(gòu)是存在特定關(guān)系的數(shù)據(jù)元素的集合。在解決有些問(wèn)題時(shí)，一些相關(guān)聯(lián)的數(shù)據(jù)將集中在一起，形成一個(gè)數(shù)據(jù)的集合，這種集合能夠單獨(dú)或作為一個(gè)整體被訪問(wèn)和處理。

線性數(shù)據(jù)結(jié)構(gòu)又稱為線性表。在線性數(shù)據(jù)結(jié)構(gòu)中，除首元素沒(méi)有前趨元素、尾元素沒(méi)有后繼元素外，其他元素都只有一個(gè)前趨元素和一個(gè)后繼元素，如圖3.2.2所示。線性表中數(shù)據(jù)元素之間是一對(duì)一的關(guān)系?；A(chǔ)知識(shí)回顧

典型的線性數(shù)據(jù)結(jié)構(gòu)——隊(duì)列典型的線性數(shù)據(jù)結(jié)構(gòu)——棧任務(wù)二探究快遞配送過(guò)程每個(gè)快遞員只負(fù)責(zé)固定的派送范圍。快遞員從快遞派送點(diǎn)領(lǐng)取到快件以后，分別送到各自負(fù)責(zé)的快遞領(lǐng)取點(diǎn)?？爝f派送點(diǎn)學(xué)校收發(fā)室A同學(xué)B同學(xué)某單位傳達(dá)室職工小王職工小李樹(shù)結(jié)構(gòu)

樹(shù)結(jié)構(gòu)是一種具有層次關(guān)系的非線性結(jié)構(gòu)。樹(shù)是由n

(n≥0)個(gè)節(jié)點(diǎn)組成的有限集合。若n=

0，則稱為空樹(shù)。

(1)僅有一個(gè)稱為根的節(jié)點(diǎn);

(2)

當(dāng)n>0時(shí)，其余節(jié)點(diǎn)可分為m

(

m≥0)個(gè)互不相交的有限集合，其中每個(gè)集合又是一棵樹(shù)，并稱為根的子樹(shù)。樹(shù)結(jié)構(gòu)的兩個(gè)條件

在圖3.2.3中，

A為唯一的根節(jié)點(diǎn)，B、C、D為A的子節(jié)點(diǎn)，同時(shí)A的子樹(shù)的根節(jié)點(diǎn)。同理，E、F、G是B的子樹(shù)的根節(jié)點(diǎn)，B是E、F、G的父節(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中，數(shù)據(jù)元素之間是一對(duì)多的關(guān)系。組織架構(gòu)樹(shù)快遞到達(dá)目的地城市后，物流圖的結(jié)構(gòu)呈樹(shù)狀活動(dòng)2了解城市間的物流網(wǎng)絡(luò)由于需要綜合考慮運(yùn)營(yíng)成本，商品在城市間運(yùn)輸?shù)穆肪€是需要計(jì)算和規(guī)劃的。請(qǐng)你查看圖3.2.5中的物流過(guò)程，嘗試用圓圈表示城市，用線段表示城市之間的送達(dá)關(guān)系，將圖3.2.6補(bǔ)充完整，了解商品配送的路線特點(diǎn)。圖3.2.5圖結(jié)構(gòu)

圖結(jié)構(gòu)是由一組節(jié)點(diǎn)和一組節(jié)點(diǎn)間的連線(稱為邊或弧)構(gòu)成的一種數(shù)據(jù)結(jié)構(gòu)。圖結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)都可以與其他節(jié)點(diǎn)有邊相連，圖結(jié)構(gòu)中數(shù)據(jù)元素之間是多對(duì)多的關(guān)系。

右圖是一個(gè)圖結(jié)構(gòu)，其中，節(jié)點(diǎn)A與兩條邊相連，連接節(jié)點(diǎn)B和E；節(jié)點(diǎn)E與節(jié)點(diǎn)A、D、F相連。網(wǎng)絡(luò)管理系統(tǒng)流程圖（有向圖）圖片來(lái)自互聯(lián)網(wǎng)南京大學(xué)理工學(xué)院地圖（帶權(quán)圖）圖片來(lái)自互聯(lián)網(wǎng)

四縱四橫是中華人民共和國(guó)鐵道部《中長(zhǎng)期鐵路網(wǎng)規(guī)劃（2008年調(diào)整）》，中國(guó)規(guī)劃建設(shè)“四縱四橫”客運(yùn)專線，客車速度目標(biāo)值達(dá)到每小時(shí)200公里以上（宜萬(wàn)鐵路時(shí)速160公里）。

四縱四橫已完美收官。

圖片來(lái)自新華網(wǎng)

2016年7月，國(guó)家發(fā)展改革委、交通運(yùn)輸部、中國(guó)鐵路總公司聯(lián)合發(fā)布了《中長(zhǎng)期鐵路網(wǎng)規(guī)劃》，勾畫了新時(shí)期“八縱八橫”高速鐵路網(wǎng)的宏大藍(lán)圖。

圖片來(lái)自互聯(lián)網(wǎng)活動(dòng)3規(guī)劃取快遞最快路線

某同學(xué)網(wǎng)購(gòu)的書已經(jīng)到達(dá)家附近的快遞門店，需要他自己去取。不巧的是，這次購(gòu)買的三本書是三個(gè)不同的物流公司派送的。我們可以將該同學(xué)家和快遞門店的位置抽象成頂點(diǎn)，兩個(gè)位置間的步行線路抽象成邊，邊上的值表示步行時(shí)間。家快遞門店A2min快遞門店B4min快遞門店C4min家10min共20min快遞門店C6min快遞門店B4min家5min共17min快遞門店B5min快遞門店A4min快遞門店C6min家10min共25min

利用樹(shù)結(jié)構(gòu)，我們能夠更清晰地實(shí)現(xiàn)不重復(fù)、不遺漏地列舉所有方案，更利于通過(guò)比較得到最優(yōu)解。小結(jié)1對(duì)1排隊(duì)1對(duì)多行政區(qū)域、書本目錄、磁盤文件存儲(chǔ)多對(duì)多地圖、電話網(wǎng)絡(luò)、互聯(lián)網(wǎng)謝謝觀看！3.2數(shù)據(jù)與結(jié)構(gòu)

答疑高一—教科版—信息技術(shù)—必修一第三單元1.樹(shù)中任意節(jié)點(diǎn)允許有零個(gè)或多個(gè)子節(jié)點(diǎn)，除根節(jié)點(diǎn)外，其余節(jié)點(diǎn)___

父節(jié)點(diǎn)。A.沒(méi)有B.有兩個(gè)C.有且只有一個(gè)D.或許有一個(gè)答案：C2.在樹(shù)中，若節(jié)點(diǎn)A有4個(gè)兄弟，而且B是A的父節(jié)點(diǎn)，則B的有（?

）個(gè)孩子。A．3?

B．4?C．5

D．6AB答案：C3.二叉樹(shù)是一種重要的樹(shù)結(jié)構(gòu)，他每個(gè)節(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，請(qǐng)問(wèn)只有三個(gè)節(jié)點(diǎn)的二叉樹(shù)，共有多少種形態(tài)？五種，具體如下圖：4.有一樹(shù)如右圖所示，回答下面的問(wèn)題

這棵樹(shù)的根節(jié)點(diǎn)是________

這棵樹(shù)的葉子節(jié)點(diǎn)是________

節(jié)點(diǎn)C的度是________

整棵樹(shù)的度是________

樹(shù)有______層

AFGHIJ2345.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是(

)。

A．棧B．