數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料課件

數(shù)據(jù)結(jié)構(gòu)考前輔導(dǎo)

2010-2011學(xué)年第一學(xué)期

輔導(dǎo)教師：馬之力數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(考試概況考試時(shí)間為90分鐘，滿分為100分，試題共分五個(gè)部分：

1、單項(xiàng)選擇題（10道，每道2分）2、判斷題（5道，每道2分）3、填空題（10空，每空2分）/名詞解釋4、簡答題（3道左右）5、綜合應(yīng)用題（3道左右，本、?？贫甲?，本、?？聘髯觯?shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(重點(diǎn)章節(jié)第2章線性表第3章棧和隊(duì)列第6章樹和二叉樹第7章圖第9章查找第10章內(nèi)部排序數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第1章緒論數(shù)據(jù)結(jié)構(gòu)定義:

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)元素是數(shù)據(jù)的基本單位,

數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位.數(shù)據(jù)結(jié)構(gòu)有邏輯結(jié)構(gòu)和物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）之分。通常所說的數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(數(shù)據(jù)結(jié)構(gòu)是具有一定關(guān)系的數(shù)據(jù)元素的集合，這種關(guān)系包括集合、線性、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的四類基本結(jié)構(gòu):(1)集合(2)線性結(jié)構(gòu)(3)樹形結(jié)構(gòu)

(4)圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的優(yōu)缺點(diǎn)。第1章緒論數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(算法的5個(gè)重要特性：有窮性、確定性、可行性、輸入、輸出要會(huì)計(jì)算時(shí)空復(fù)雜度。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第2章線性表1.線性結(jié)構(gòu)的特點(diǎn)。2.線性結(jié)構(gòu)既可以用順序結(jié)構(gòu)表示，又可以用鏈?zhǔn)浇Y(jié)構(gòu)表示。3.線性表:n個(gè)數(shù)據(jù)元素的有限序列.

線性表是有限序列,可以為空.4.單鏈表插入、刪除結(jié)點(diǎn)時(shí)的具體操作。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(舉例例：數(shù)據(jù)的邏輯結(jié)構(gòu)中非線性結(jié)構(gòu)有（）

A、線形結(jié)構(gòu)B、樹形結(jié)構(gòu)

C、順序結(jié)構(gòu)D、鏈?zhǔn)浇Y(jié)構(gòu)注意：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)是物理結(jié)構(gòu)，所以C、D排除；邏輯結(jié)構(gòu)中非線性結(jié)構(gòu)有集合、樹形、圖狀或網(wǎng)狀，所以選B。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(舉例例：判斷對錯(cuò)數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。（正確）數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（正確）

數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第3章棧和隊(duì)列

1.棧:限定僅在表尾進(jìn)行插入或刪除操作的線性表。2.棧:后進(jìn)先出.3.隊(duì)列:是一種先進(jìn)先出的線性表，它只允許在表的隊(duì)尾進(jìn)行插入，而在隊(duì)頭刪除元素。注:棧和隊(duì)列都是操作受限的線性表.要搞清楚棧和隊(duì)列的相同點(diǎn)和不同點(diǎn)。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(舉例例：鏈?zhǔn)疥?duì)列Q為空的判定條件是？

Q.front==Q.rear

例：棧和隊(duì)列都是操作不受任何限制的線性表。 （錯(cuò)誤）例：在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為_______。

答案：rear==front

判斷隊(duì)滿的條件為：(rear+l)％n==front數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第四章串1.串(字符串):由零個(gè)或多個(gè)字符組成的有限序列.2.空串:零個(gè)字符組成的串.

空格串:由一個(gè)或多個(gè)空格組成的串.3.串的長度:串中元素的個(gè)數(shù).例1:

設(shè)s=“IAMAWOMAN”,則字符串的長度為_____.(B)A、11B、12C、14D、15數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(4.串聯(lián)接Concat(&T,s1,s2)

假設(shè)s1,s2,T都是ssting型的串變量,且串T是由s1聯(lián)結(jié)s2得到的,即:T的值的前一段和s1的值相等,T的值的后一段和s2的值相等.例2:

設(shè)s1=“GOOD”,s2=“BYE!”則字符串s1和s2連接后的結(jié)果是____。

(D)A、BYEGOOD!B、GOODBYE!C、BYEDGOOD!D、GOODBYE!數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(例3兩個(gè)字符串相等的條件是_____.

答案：兩串的長度相等，并且對應(yīng)位置上的字符相同。例4判斷對錯(cuò)空串與空格串沒有區(qū)別。（錯(cuò)）數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第五章數(shù)組和廣義表1.廣義表一般記為:LS=(a1,a2,…,an)

當(dāng)廣義表LS非空時(shí),稱第一個(gè)元素a1為LS的表頭,其余元素組成的表(a2,a3,…,an)是LS的表尾.一個(gè)廣義表的表尾總是一個(gè)廣義表

數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(例1:（判斷）廣義表的表頭可以是廣義表，也可以是單個(gè)元素。(正確

)例2:廣義表（（ab）,ab）的表頭是______(A)A、（ab）B、abC、abD、((ab))例3判斷對錯(cuò)廣義表有兩個(gè)特殊的基本運(yùn)算：取表頭和取表尾。（正確）三維數(shù)組存儲(chǔ)地址的計(jì)算。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第6章樹和二叉樹1.二叉樹:每個(gè)結(jié)點(diǎn)至多只有二棵子樹,并且,二叉樹的子樹有左右之分,其次序不能任意顛倒.例1:三個(gè)結(jié)點(diǎn)的二叉樹可以有哪幾種形式？數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(2.樹的度是樹內(nèi)各節(jié)點(diǎn)的度的最大值。3.二叉樹有5種基本形態(tài)。4.在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>=1).5.深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)(i>=1).6.滿二叉樹:一棵深度為k且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹.7.完全二叉樹:深度為k,有n個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對應(yīng).數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(例3:對完全二叉樹敘述正確的是（

B）A、完全二叉樹就是滿二叉樹B、完全二叉樹同一層上左子樹未滿不會(huì)有右子樹C、完全二叉樹和滿二叉樹編號(hào)不對應(yīng)D、以上都不正確數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(6.遍歷二叉樹的操作定義先序遍歷二叉樹的操作定義為:

若二叉樹為空,則空操作;否則

(1)訪問根結(jié)點(diǎn);(2)先序遍歷左子樹;(3)先序遍歷右子樹.

中序遍歷二叉樹的操作定義為:

若二叉樹為空,則空操作;否則

(1)中序遍歷左子樹;(2)訪問根結(jié)點(diǎn);(3)中序遍歷右子樹.數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(

后序遍歷二叉樹的操作定義為:

若二叉樹為空,則空操作;否則

(1)后序遍歷左子樹;(2)后序遍歷右子樹.(3)訪問根結(jié)點(diǎn);數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(例5:已知一棵二叉樹中序和后序序列為分別為:和畫出這棵二叉樹。

數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(7.哈夫曼樹構(gòu)造方法:

1.根據(jù)給定的n個(gè)權(quán)值{w1,w2,…wn}構(gòu)成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)wi的根結(jié)點(diǎn)，左右子樹均空。2.在F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。3.在F中刪除這兩棵樹，并將新的二叉樹加入F中。4.重復(fù)前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹

數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(例7判斷對錯(cuò)滿二叉樹也是完全二叉樹。（正確）例8若采用孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的先根遍歷應(yīng)采用二叉樹的_____。()A、層次遍歷B、先序遍歷

C、中序遍歷D、后序遍歷數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第七章圖1.圖分為:有向圖和無向圖.2.頂點(diǎn)v的入度:以頂點(diǎn)v為頭的弧的數(shù)目.

頂點(diǎn)v的出度:以頂點(diǎn)v為尾的弧的數(shù)目.3.一個(gè)連通圖的生成樹:

是一個(gè)極小連通子圖,它含有圖中全部頂點(diǎn),但只有足以構(gòu)成一棵樹的n-1條邊.4.圖的表示法:鄰接表,鄰接多重表,十字鏈表5.數(shù)組表示法(鄰接矩陣):以二維數(shù)組表示有n個(gè)頂點(diǎn)的圖時(shí),需存放n個(gè)頂點(diǎn)信息和n^2個(gè)弧信息的存儲(chǔ)量.6.強(qiáng)連通圖：在有向圖G中，對于任意一個(gè)頂點(diǎn)如果存在它到任意其它頂點(diǎn)的路徑，則稱G是強(qiáng)連通圖數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(7.無向圖的鄰接矩陣是對稱矩陣。8.n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊.9.在一個(gè)有n個(gè)頂點(diǎn)的無向圖中，有n(n-1)/2條邊的圖稱為完全圖。10.一個(gè)強(qiáng)連通圖的連通分量不只有一個(gè)。11.圖的遍歷:從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn),且使每一個(gè)頂點(diǎn)僅被訪問一次.12.兩條遍歷圖的途徑:深度優(yōu)先搜索,

廣度優(yōu)先搜索.13.圖的廣度優(yōu)先遍歷算法類似于二叉樹的(層次遍歷).數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(

第9章查找

1.查找表：是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。2.折半查找算法思想：

將數(shù)列按有序化(遞增或遞減)排列，查找過程中采用跳躍式方式查找，即先以有序數(shù)列的中點(diǎn)位置為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半。

數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(折半查找的局限性：

(1)

查找表要有序；

(2)

需要順序存儲(chǔ)結(jié)構(gòu)例1:判斷對錯(cuò)折半查找適用于采用順序存儲(chǔ)結(jié)構(gòu)的有序表。（正確）折半查找適用于采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的無序表。（錯(cuò)誤）采用折半查找方法查找長度為n的線性表時(shí),每個(gè)元素的平均查找長度為O(logn)。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(3.哈希表不需要進(jìn)行比較便可以直接取得所查記錄.4.哈希表構(gòu)造方法:直接定址法,數(shù)字分析法,平方取中法,折疊法,除留余數(shù)法,隨機(jī)數(shù)法.5.處理沖突的方法:

什么是沖突?處理沖突的方法是什么?

若某個(gè)散列函數(shù)H對于不相等的關(guān)鍵字key1和key2得到相同的散列地址(即H(key1)=H(key2))則將該現(xiàn)象稱為沖突.

解決沖突的方法有:開放定址法和鏈地址法.數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(第10章排序深刻理解冒泡排序的基本思想并能夠解題。例1已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采用冒泡排序法進(jìn)行排序時(shí)每一趟的排序結(jié)果。數(shù)據(jù)結(jié)構(gòu)第四篇考前輔導(dǎo)導(dǎo)學(xué)資料(初態(tài)：