數(shù)據(jù)結(jié)構(gòu)習(xí)題1217

1、選擇題（ ）由某一數(shù)據(jù)對(duì)象和該對(duì)象中各個(gè)成員之間的關(guān)系組成。依據(jù)所有數(shù)據(jù)成員之間關(guān)系的不同，（ ）分為兩大類：（ ）和（ ）。在（ ）中的各個(gè)數(shù)據(jù)成員依次排列在一個(gè)線性序列中；（ ）的各個(gè)數(shù)據(jù)成員不再保持在一個(gè)線性序列中，每個(gè)數(shù)據(jù)成員可能與零個(gè)或多個(gè)其他數(shù)據(jù)成員發(fā)生聯(lián)系。根據(jù)視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的（ ）和（ ）。（ ）是面向問題的，（ ）是面向計(jì)算機(jī)的。緒論練習(xí)緒論練習(xí)A：數(shù)據(jù)結(jié)構(gòu)B：線性結(jié)構(gòu) C：非線性結(jié)構(gòu)D：邏輯結(jié)構(gòu)E：存儲(chǔ)結(jié)構(gòu)A AA AB BC CB BC CD DE ED DE E判斷題數(shù)據(jù)元素是數(shù)據(jù)的最小單位。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元素之間關(guān)系的集合。數(shù)據(jù)結(jié)構(gòu)是具有

2、結(jié)構(gòu)的數(shù)據(jù)對(duì)象。數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的。從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。FTFTFTT填空題算法是一個(gè)有窮的指令集，它為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。它應(yīng)當(dāng)具有輸入、輸出、（ ）、有窮性和可執(zhí)行性等特性。算法效率的度量分為（ ）和（ ）。（ ）主要通過在算法的某些部位插裝時(shí)間函數(shù)來(lái)測(cè)定算法完成某一規(guī)定功能所需要的時(shí)間。而（ ）不實(shí)際運(yùn)行算法，它是分析算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)度量算法的時(shí)間復(fù)雜度。A：確定性 B：事后測(cè)

3、量C：事前估計(jì)A AB BB BC CC C有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫出它們分別對(duì)應(yīng)的圖形表示。A=（K,R）其中K=a,b,c,d,R= C=（K,R）其中K=1,2,3,4,5,6,R=,B=（K,R）其中K=a,b,c,d,e,f,g,h,R=,選擇題一個(gè)數(shù)據(jù)元素ai與 的表示等價(jià)。A.*(a+i) B.a+i C.*a+i D.&a+i對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是 不同則不是重載函數(shù)。A.參數(shù)類型 B.參數(shù)個(gè)數(shù) C.函數(shù)類型 若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為 參數(shù)。A.指針 B.引用 C.值下面程序的時(shí)間復(fù)雜度為 。For(int i=0;im

4、;i+)for (int j=0;jn;j+)aij=I*j;A.O(m2) B. O(n2) C.O(m*n) D.O(m+n)ACBC執(zhí)行下面程序，執(zhí)行S語(yǔ)句的次數(shù)為 。For(int i=1;i=n;i+)for (int j=1;ji;j+)S;A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 下面算法的時(shí)間復(fù)雜度為 。int if f(unsigned int n) if (n=0|n=1) return 1;else return n*f(n-1) A. O(1) B. O(n2) C.O(n) D.O(n!)下面程序中s=s+p語(yǔ)句執(zhí)行的次數(shù)為 ，p*=j語(yǔ)

5、句執(zhí)行的次數(shù)為 ，該程序段T(n)為 。int i=0,s=0;while(+i=n)int p=1;for (int j=1;j=i;j+) p*=j;s=s+p;DCA. n2B. nC. n(n+1)D.n(n+1)/2BDE. O(n2)F. O(n)G. O(n!)H. O(1)E第二章 線性表線性表（Linear list）是最簡(jiǎn)單且最常用的一種數(shù)據(jù)）是最簡(jiǎn)單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。這種結(jié)構(gòu)具有下列特點(diǎn)：存在一個(gè)唯一的沒有前結(jié)構(gòu)。這種結(jié)構(gòu)具有下列特點(diǎn)：存在一個(gè)唯一的沒有前驅(qū)的（頭）數(shù)據(jù)元素；存在一個(gè)唯一的沒有后繼的（尾）驅(qū)的（頭）數(shù)據(jù)元素；存在一個(gè)唯一的沒有后繼的（尾）數(shù)據(jù)元素；此

6、外，每一個(gè)數(shù)據(jù)元素均有一個(gè)直接前驅(qū)和數(shù)據(jù)元素；此外，每一個(gè)數(shù)據(jù)元素均有一個(gè)直接前驅(qū)和一個(gè)直接后繼數(shù)據(jù)元素。通過本章的學(xué)習(xí)，大家應(yīng)能掌一個(gè)直接后繼數(shù)據(jù)元素。通過本章的學(xué)習(xí)，大家應(yīng)能掌握線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及線性表的基本運(yùn)握線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及線性表的基本運(yùn)算以及實(shí)現(xiàn)算法。算以及實(shí)現(xiàn)算法。【知識(shí)點(diǎn)知識(shí)點(diǎn)】線性表、順序表、鏈表線性表、順序表、鏈表2.1 線性表及邏輯結(jié)構(gòu)線性表及邏輯結(jié)構(gòu)2.2 線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)2.3 線性表的鏈?zhǔn)酱鎯?chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)2.4 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的應(yīng)用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的應(yīng)用2.5 小結(jié)小結(jié)2.6 練習(xí)練習(xí) 線性表：線性表：一個(gè)線性表是n0個(gè)數(shù)據(jù)

7、元素a0，a1，a2，an-1的有限序列。 線性表的順序存儲(chǔ)結(jié)構(gòu)：線性表的順序存儲(chǔ)結(jié)構(gòu)：在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，稱作線性表的順序存儲(chǔ)結(jié)構(gòu)。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元結(jié)點(diǎn)（可以是不連續(xù)的）存儲(chǔ)線性表的數(shù)據(jù)元素。表中每一個(gè)數(shù)據(jù)元素，都由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放直接前驅(qū)或直接后繼結(jié)點(diǎn)的地址（指針）的指針域組成。 單鏈表：?jiǎn)捂湵恚簡(jiǎn)捂湵恚↙inear Linked List）是指鏈表中的每一個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域指向直接后繼。本章小結(jié)本章小結(jié)循環(huán)鏈表：循環(huán)鏈表：循環(huán)鏈表(Circular Li

8、nked List)是將單鏈表的表中最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他的結(jié)點(diǎn)。雙向鏈表：雙向鏈表：雙向鏈表中，在每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指針域，一個(gè)指針（next）指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針（prior）指向它的前驅(qū)結(jié)點(diǎn)。除上述基本概念以外，學(xué)生還應(yīng)該了解：線性表的基本操作（初始化、插入、刪除、存?。?、順序存儲(chǔ)結(jié)構(gòu)的表示、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示、一元多項(xiàng)式Pn(x)，掌握順序存儲(chǔ)結(jié)構(gòu)（初始化、插入操作、刪除操作）、單鏈表（單鏈表的初始化、單鏈表的插入、單鏈表的刪除）。一、判斷題線性表的邏輯順序與物理順序總是一致的。線性

9、表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。線性表若采用鏈?zhǔn)酱鎯?chǔ)表示。時(shí)所有存儲(chǔ)單元的地址可連續(xù)可不連續(xù)。每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和搜索。線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。1.順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。 F FF FT TT T練習(xí)練習(xí)F FF F二、填空題線性表（ a1,a2,an）有兩種存儲(chǔ)結(jié)構(gòu)：（A）和（B）。（A）存儲(chǔ)密度較大，（B）存儲(chǔ)利用率較高，（A）可隨機(jī)存取，（B）不可隨機(jī)存取，（B）插入和刪除操作比較方便。在單鏈表中，刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是：（）帶頭結(jié)點(diǎn)的單循環(huán)鏈表Head的判空條件是（）。1.畫出下列數(shù)據(jù)

10、結(jié)構(gòu)的圖示：順序表 單鏈表 雙鏈表 循環(huán)鏈表A：順序存儲(chǔ)結(jié)構(gòu)B：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)pnext=pnextnextHeadnext=Head在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1=inext-next=L 2p-next!=null 順序 指針三、選擇題設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？A：s-link=p-link; p-link=s;B: q-link=s;s-link=p;C: p-link=s-link;s-link=p;D: p-link=s;s-link=q;答案：答案：B B

11、設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？A：s-link=p; p-link=s;B：s-link=p-link;p-link=s;C：s-link=p-link;p=s;D：p-link=s;s-link=p;答案：答案：B B設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。若想摘除結(jié)點(diǎn)*p的直接后繼，則應(yīng)執(zhí)行下列哪一個(gè)操作？A：p-link=p-link-link;B： p=p-link; p-link=p-link-link;C：p-link=p-link;D：p=p-link-link;答案：答案：A

12、A設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針，若想刪除鏈表第一個(gè)結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個(gè)操作？A：s=rear; rear=rear-link;free(s);B：rear=rear-link; free(rear);C： rear=rear-link-link; free(rear) ;D： s=rear-link-link; rear-link-link=s-link; free(s);答案：答案：D D設(shè)雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,lLink,rLink),且不帶頭結(jié)點(diǎn)。若想在指針p所指結(jié)點(diǎn)之后插入指針s所指結(jié)點(diǎn)，則

13、應(yīng)執(zhí)行下列哪一個(gè)操作？A：p-rLink=s; s-lLink=p; p-rLink-lLink=s; s-rLink=p-rLink;B： p-rLink=s;p-rLink-lLink=s; s-lLink=p; s-rLink =p-rLink;C：s-lLink=p; s-rLink=p-rLink; p-rLink=s; p-rLink-lLink=s;D： s-lLink=p;s-rLink=p-rLink; p-rLink-lLink=s;p-rLink=s;答案：答案：D D若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間

14、。 A順序表B雙鏈表C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D單循環(huán)鏈表 A A在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。A(p-llink)-rlink:=p-rlink;(p-rlink)-llink:= p-llink;Bp- llink:=(p-llink)-llink;(p-llink)- rlink:=p;C(p-rlink)-llink:=p;p-rlink:=(p-rlink)- rlinkDp-rlink:=(p-llink)-llink;p-llink:=(p- rlink)-rlink; A A第三章 棧和隊(duì)列從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊(duì)列也是線性表，不過是兩種特從數(shù)據(jù)結(jié)構(gòu)上看，

15、棧和隊(duì)列也是線性表，不過是兩種特殊的線性表。棧只允許在表的一端進(jìn)行插入或刪除操作，殊的線性表。棧只允許在表的一端進(jìn)行插入或刪除操作，而隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)而隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作。因而，棧和隊(duì)列也可以被稱作為操作受限行刪除操作。因而，棧和隊(duì)列也可以被稱作為操作受限的線性表。通過本章的學(xué)習(xí)，大家應(yīng)能掌握棧和隊(duì)列的的線性表。通過本章的學(xué)習(xí)，大家應(yīng)能掌握棧和隊(duì)列的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及棧和隊(duì)列的基本運(yùn)算以及實(shí)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及棧和隊(duì)列的基本運(yùn)算以及實(shí)現(xiàn)算法?，F(xiàn)算法?！局R(shí)點(diǎn)知識(shí)點(diǎn)】棧、隊(duì)列棧、隊(duì)列3.0 課前思考課前思考3.1 棧棧

16、3.2 棧的應(yīng)用棧的應(yīng)用3.3 隊(duì)列隊(duì)列 3.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用3.5 小結(jié)小結(jié) 2.6 練習(xí)練習(xí)本章主要介紹了如下一些基本概念：本章主要介紹了如下一些基本概念：棧：是一種只允許在一端進(jìn)行插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進(jìn)行插入和刪除的一端稱為棧頂（top），另一端稱為棧底(bottom)。棧頂元素總是最后入棧的，因而是最先出棧；棧底元素總是最先入棧的，因而也是最后出棧。因此，棧也被稱為“后進(jìn)先出”的線性表。棧的順序存儲(chǔ)結(jié)構(gòu)：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)母鱾€(gè)數(shù)據(jù)元素，稱為棧的順序存儲(chǔ)結(jié)構(gòu)。雙向棧：使兩個(gè)棧共享一維數(shù)組stackMAXNUM，利

17、用棧的“棧底位置不變，棧頂位置動(dòng)態(tài)變化”的特性，將兩個(gè)棧底分別設(shè)為-1和MAXNUM，而它們的棧頂都往中間方向延伸的棧稱為雙向棧。本章小結(jié)本章小結(jié)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元（可以是不連續(xù)的）存儲(chǔ)棧中的數(shù)據(jù)元素，這種結(jié)構(gòu)的棧簡(jiǎn)稱為鏈棧。在一個(gè)鏈棧中，棧底就是鏈表的最后一個(gè)結(jié)點(diǎn)，而棧頂總是鏈表的第一個(gè)結(jié)點(diǎn)。隊(duì)列：隊(duì)列（queue）是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它是一種操作受限的線性表。在表中只允許進(jìn)行插入的一端稱為隊(duì)尾（rear），只允許進(jìn)行刪除的一端稱為隊(duì)頭(front)。隊(duì)頭元素總是最先進(jìn)隊(duì)列的，也總是最先出隊(duì)列；隊(duì)尾元素總是最后進(jìn)隊(duì)列

18、，因而也是最后出隊(duì)列。因此，隊(duì)列也被稱為“先進(jìn)先出”表。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)：利用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的數(shù)據(jù)元素，稱為隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。重點(diǎn)是循環(huán)隊(duì)列。其中：約定初始化建空隊(duì)列時(shí)， front=rear=0，在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素，而尾指針指向隊(duì)尾元素的“下一個(gè)”位置。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元（可以是不連續(xù)的）存儲(chǔ)隊(duì)列中的數(shù)據(jù)元素，這種結(jié)構(gòu)的隊(duì)列稱為鏈隊(duì)列。在一個(gè)鏈隊(duì)列中需設(shè)定兩個(gè)指針(頭指針和尾指針)分別指向隊(duì)列的頭和尾。除上述基本概念以外，學(xué)生還應(yīng)該了解：棧的基本操作（初始化、棧的非空判斷、入棧、出棧、取棧元素、置?？詹僮?/p>

19、）、棧的順序存儲(chǔ)結(jié)構(gòu)的表示、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示、隊(duì)列的基本操作（初始化、隊(duì)列非空判斷、入隊(duì)列、出隊(duì)列、取隊(duì)頭元素、求隊(duì)列長(zhǎng)度）、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，掌握順序棧（入棧操作、出棧操作）、鏈棧（入棧操作、出棧操作）、順序隊(duì)列（入隊(duì)列操作、出隊(duì)列操作）、鏈隊(duì)列（入隊(duì)列操作、出隊(duì)列操作）等。一、判斷題兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，對(duì)頭使用也存在空間溢出問題。 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。棧與隊(duì)列是一種特殊操作的線性表。 若輸入序列為1,2,3,4,5,6,則通過一個(gè)棧可以輸出序列3,2,5,6,4,1 。若輸

20、入序列為1，2，3，4，5，6，則通過一個(gè)棧可以輸出序列1，5，4，6，2，3。隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。 1.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。T TT TT T練習(xí)練習(xí)T TF FF FT TT T二、填空題棧是（ ）的線性表，其運(yùn)算遵循（）的原則。（）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是（ ）

21、，而棧頂指針值是（） H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。 1.用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為（ ） 。 后進(jìn)先出23100C 操作受限 棧 SSSS （）又稱作先進(jìn)先出表。 區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是（ ）和（ ）。設(shè)循環(huán)隊(duì)列用數(shù)組A1.M表示，隊(duì)首、隊(duì)尾指針分別是FRONT和TAIL，判定隊(duì)滿的條件為 （） 。 表達(dá)式求值是（ ） 應(yīng)用的一個(gè)典型例子。循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear ，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是（ ）。 隊(duì)列 犧牲一個(gè)存儲(chǔ)單元 設(shè)標(biāo)

22、記 （TAIL+1）MOD M=FRONT 棧 （rear-front+m）% m三、選擇題對(duì)于棧操作數(shù)據(jù)的原則是（ ）。 A. 先進(jìn)先出B. 后進(jìn)先出C. 后進(jìn)后出D. 不分順序 B B一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1=i=n）個(gè)元素是（ ）。 A. 不確定 B. n-i+1 C. i D. n-i B B有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？( ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 C C在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否(),在作退棧

23、運(yùn)算時(shí)應(yīng)先判別棧是否()。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量為()。 為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 ()分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)()時(shí)，才產(chǎn)生上溢。 : A.空 B. 滿 C. 上溢 D.下溢 : A. n-1 B. n C. n+1 D.n/2 : A. 長(zhǎng)度 B. 深度 C. 棧頂 D.棧底 : A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)。 B. 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)。 C. 兩個(gè)棧的棧頂在棧空間的某一位置相遇。 D. 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底。 答案：答案：

24、 B B A A B B D DC C設(shè)一個(gè)棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 D D表達(dá)式3* 2(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（ ），其中為乘冪 。 A. 3,2,4,1,1；#*(+*- B. 3,2,8；#*- C. 3,2,4,2,2；#*(- D. 3,2,8；#*(- D D用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ ）。 A. 僅修改頭指針B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針

25、可能都要修改 D D假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。 A(rear-front+m)%mBrear-front+1C(front-rear+m)%mD(rear-front)%m A A循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ ）。A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1) mod (m+1) D D若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素

26、，再加入兩個(gè)元素后，rear和front的值分別為多少？( )A. 1和 5 B. 2和4C. 4和2 D. 5和1 B B棧的特點(diǎn)是（）,隊(duì)列的特點(diǎn)是（）,棧和隊(duì)列都是（）。若進(jìn)棧序列為1,2,3,4 則（）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（）是一個(gè)出隊(duì)列序列。棧和隊(duì)列的共同點(diǎn)是（）。: A. 先進(jìn)先出 B. 后進(jìn)先出 C. 進(jìn)優(yōu)于出 D. 出優(yōu)于進(jìn): A.順序存儲(chǔ)的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu) D.限制存取點(diǎn)的非線性結(jié)構(gòu): A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F

27、. 1,2,3,4 G. 1,3,2,4 A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素D. 沒有共同點(diǎn) 答案：答案： B B A A C C C CF F C C四、寫出下列程序段的輸出結(jié)果四、寫出下列程序段的輸出結(jié)果1、 （棧的元素類型（棧的元素類型SElemTypeSElemType為為CharChar）Void main()stack s;char x,y;Initstack(s);x=c;y=k;Push(s,x);Push(s,a);Push(s,y);Pop(s,x);Push(s,t);Push(s,x);Pop(s,x);Push(s,s);whi

28、le(!StackEmpty(s) Pop(s,y);Printf(y);Printf(x);輸出結(jié)果：輸出結(jié)果：stackstack2、 （隊(duì)列中的元素類型（隊(duì)列中的元素類型QElemTypeQElemType為為CharChar）Void main()Queue Q;InitQueue(Q);char x=e,y=c;EnQueue(Q,h); EnQueue(Q,r); EnQueue(Q,y);DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,a);while(!QueueEmpty(Q) DeQueue(Q,y); Printf(

29、y);Printf(x);輸出結(jié)果：輸出結(jié)果：charchar五、簡(jiǎn)述算法的功能五、簡(jiǎn)述算法的功能1 1、（棧的元素類型、（棧的元素類型SElemTypeSElemType為為intint）Status sf1(stack s,int e)stack t;int d;initstack(T);while(!stackEmpty(S)Pop(S,d);if (d!=e) Push(T,d);while(!StackEmpty(T) Pop(T,d);Push(S,d);利用棧利用棧T T輔助將棧輔助將棧S S中所有值為中所有值為e e的數(shù)據(jù)的數(shù)據(jù)元素刪除去。元素刪除去。2 2、（棧和隊(duì)列的元素類

30、型均為、（棧和隊(duì)列的元素類型均為intint）void sf2(Queue &Q)stack S;int d;initstack(S);while(! QueueEmpty(Q)DeQueue(Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d);EnQueue(Q,d); 利用棧利用棧S S作輔助，將隊(duì)列作輔助，將隊(duì)列Q Q中的數(shù)據(jù)元中的數(shù)據(jù)元素進(jìn)行逆置。素進(jìn)行逆置。第四章 串在計(jì)算機(jī)的各方面應(yīng)用中，非數(shù)值處理問題的應(yīng)用越來(lái)在計(jì)算機(jī)的各方面應(yīng)用中，非數(shù)值處理問題的應(yīng)用越來(lái)越多。在早期的程序設(shè)計(jì)語(yǔ)言中，串僅作為輸入和輸出越多。在早期的程序設(shè)計(jì)語(yǔ)言中

31、，串僅作為輸入和輸出的常量出現(xiàn)。隨著計(jì)算機(jī)應(yīng)用的擴(kuò)展，需要在程序中進(jìn)的常量出現(xiàn)。隨著計(jì)算機(jī)應(yīng)用的擴(kuò)展，需要在程序中進(jìn)行對(duì)行對(duì)串串的操作，如在事務(wù)處理系統(tǒng)中，用戶的姓名和的操作，如在事務(wù)處理系統(tǒng)中，用戶的姓名和地址及貨物的名稱、規(guī)格等也是字符串?dāng)?shù)據(jù)。地址及貨物的名稱、規(guī)格等也是字符串?dāng)?shù)據(jù)。字符串一般簡(jiǎn)稱為串，可以將它看作是一種特殊的線性字符串一般簡(jiǎn)稱為串，可以將它看作是一種特殊的線性表，這種線性表的數(shù)據(jù)元素的類型總是字符型的，字符表，這種線性表的數(shù)據(jù)元素的類型總是字符型的，字符串的數(shù)據(jù)對(duì)象約束為字符集。在一般線性表的基本操作串的數(shù)據(jù)對(duì)象約束為字符集。在一般線性表的基本操作中，大多以中，大多以“單

32、個(gè)元素單個(gè)元素”作為操作對(duì)象，而在串中，則作為操作對(duì)象，而在串中，則是以是以“串的整體串的整體”或一部分作為操作對(duì)象。因此，一般或一部分作為操作對(duì)象。因此，一般線性表和串的操作有很大的不同。本章主要討論串的基線性表和串的操作有很大的不同。本章主要討論串的基本概念、存儲(chǔ)結(jié)構(gòu)和一些基本的串處理操作。本概念、存儲(chǔ)結(jié)構(gòu)和一些基本的串處理操作?！局R(shí)點(diǎn)知識(shí)點(diǎn)】串的類型定義、串的存儲(chǔ)表示、串匹配串的類型定義、串的存儲(chǔ)表示、串匹配4.1 串的基本概念串的基本概念 4.2 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu) 4.3 串的基本運(yùn)算及其實(shí)現(xiàn)串的基本運(yùn)算及其實(shí)現(xiàn) 4.4 模式匹配模式匹配4.5 串的應(yīng)用串的應(yīng)用 4.6 小結(jié)

33、小結(jié) 4.7 練習(xí)練習(xí)本章主要介紹了如下一些基本概念：本章主要介紹了如下一些基本概念：串：串（或字符串）（String）是由零個(gè)或多個(gè)字符組成的有限序列。主串和子串：一個(gè)串的任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串，包含該子串的串稱為主串。串的靜態(tài)存儲(chǔ)結(jié)構(gòu)：類似于線性表的順序存儲(chǔ)結(jié)構(gòu)，用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列的存儲(chǔ)方式稱為串的順序存儲(chǔ)結(jié)構(gòu)。串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：類似于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，采用鏈表方式存儲(chǔ)串值字符序列的存儲(chǔ)方式稱為串的順序存儲(chǔ)結(jié)構(gòu)。堆存儲(chǔ)結(jié)構(gòu)：用一組空間足夠大的、地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但其存儲(chǔ)空間在程序執(zhí)行過程中能動(dòng)態(tài)分配的存儲(chǔ)方式稱為堆存儲(chǔ)結(jié)構(gòu)。

34、本章小結(jié)本章小結(jié)除上述基本概念以外，學(xué)生還應(yīng)該了解串的基本運(yùn)算（字符串拷貝（賦值、字符串的聯(lián)接、求字符串的長(zhǎng)度、子串的查詢、字符串的比較）、串的靜態(tài)存儲(chǔ)結(jié)構(gòu)的表示、串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示、串的堆存儲(chǔ)結(jié)構(gòu)的表示，能在各種存儲(chǔ)結(jié)構(gòu)方式中求字符串的長(zhǎng)度、能在各種存儲(chǔ)結(jié)構(gòu)方式中利用C語(yǔ)言提供的串函數(shù)進(jìn)行操作。一、判斷題如果兩個(gè)串含有相同的字符，則說明它們相等。如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。設(shè)有兩個(gè)串P和Q，其中Q是P的子串，把Q在P中首次出現(xiàn)的位置作為子串Q在P中的位置的算法稱為匹配。單引號(hào)和雙引號(hào)都可做為串的定界符。單引號(hào)是串的一部分。1.設(shè)s= ，t= ，則s

35、=tF FF FT T練習(xí)練習(xí)F FF FF F二、選擇題串是（ ）。 A.少于一個(gè)字母的序列 B.任意個(gè)字母的序列 C.不少于一個(gè)字母的序列 D.有限個(gè)字母的序列D D串的長(zhǎng)度是（ ）。 A.串中不同字母的個(gè)數(shù)B.串中不同字符的個(gè)數(shù) C.串中所含字符的個(gè)數(shù)，且大于0D.串中所含字符的個(gè)數(shù) D D設(shè)有兩中串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算( ）。A. 連接 B.模式匹配C.求子串D. 求串長(zhǎng)B B串的聯(lián)結(jié)運(yùn)算不滿足（ ）。 A.分配律B.交換律C.結(jié)合律B B設(shè)字符串s1=ABCDEFG,s2=PQRST,而T，sub1，sub2為空串，則運(yùn)算S=Concation(T,SubStrin

36、g(sub1,s1,2,SubLength(s2),SubString(sub2,s1,SubLength(s2),2)后的串T的值為（ ）。 A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEFE.BCQR D D三、填空題1.設(shè)s=I am a student,t=good,q=worker。則：S t r L e n g t h ( s ) = （ ） ，S u b S t r i n g ( s , 8 , 7 ) = （） ，BFIndex(s,a)= （ ）, BFIndex(s,t)=（ ）, Concation (SubString (s,6,2),Concati

37、on(t, SubString(s,7,8)=（ ）,Replace(s,student,q)=（ ）studenta good studentI am a worker14 3 0 2.已知下列字符串：a=this,f=a sample, c=good,d=ne,b=,g=is。則：s=Concation(a,Concation(SubString(f,2,7), Concation(b,SubString(a,3,2)= （ ） t=Replace(f,SubString(f,3,6),c)=（ ） u=Concation(SubString(c,3,1),d)= （ ） v=Concat

38、ion(s,Concation(b,Concation(t,Concation(b,u)=（ ） StrLength(s)=（ ），BFIndex(v,g)=（）, BFIndex(u,g)=（）。a good143s=this sample is one This sample is a good one0四、寫出下列程序段的輸出結(jié)果寫出下列程序段的輸出結(jié)果Void demonstrate()StrAssign(s,this is a book);Replace(s,SubString(s,3,7),ese are);StrAssign(t,Concation(s,s);StrAssign(

39、u,xyxyxyxyxyxy);StrAssign(v,SubString(u,6,3);StrAssign(w,w);printf(t=,t,v=,v,u=,Replace(u,v,w);/demonstrate輸出結(jié)果：輸出結(jié)果：t=these are books,v=yxy,u=xwxwxw第五章第五章 數(shù)組和廣義表數(shù)組和廣義表本章主要介紹數(shù)組的概念及在計(jì)算機(jī)中的存放，特殊矩本章主要介紹數(shù)組的概念及在計(jì)算機(jī)中的存放，特殊矩陣的壓縮存儲(chǔ)及相應(yīng)運(yùn)算，廣義表的概念和存儲(chǔ)結(jié)構(gòu)及陣的壓縮存儲(chǔ)及相應(yīng)運(yùn)算，廣義表的概念和存儲(chǔ)結(jié)構(gòu)及其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過本章學(xué)習(xí)，要求掌握如下內(nèi)容其相關(guān)運(yùn)算的實(shí)現(xiàn)。通過本

40、章學(xué)習(xí)，要求掌握如下內(nèi)容:1數(shù)組的定義及在計(jì)算機(jī)中的存儲(chǔ)表示；數(shù)組的定義及在計(jì)算機(jī)中的存儲(chǔ)表示；2對(duì)稱矩陣、三角矩陣、對(duì)角矩陣等特殊矩陣在計(jì)算機(jī)對(duì)稱矩陣、三角矩陣、對(duì)角矩陣等特殊矩陣在計(jì)算機(jī)中的壓縮存儲(chǔ)表示及地址計(jì)算公式；中的壓縮存儲(chǔ)表示及地址計(jì)算公式；3稀疏矩陣的三元組表示；稀疏矩陣的三元組表示；4廣義表存儲(chǔ)結(jié)構(gòu)表示。廣義表存儲(chǔ)結(jié)構(gòu)表示?！局R(shí)點(diǎn)知識(shí)點(diǎn)】數(shù)組的類型定義、數(shù)組的存儲(chǔ)表示、特殊矩?cái)?shù)組的類型定義、數(shù)組的存儲(chǔ)表示、特殊矩陣的壓縮存儲(chǔ)表示方法、稀疏矩陣的壓縮存儲(chǔ)表示方法陣的壓縮存儲(chǔ)表示方法、稀疏矩陣的壓縮存儲(chǔ)表示方法5.1 數(shù)組的基本概念數(shù)組的基本概念 5.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組的存儲(chǔ)

41、結(jié)構(gòu) 5.3 特殊矩陣及其壓縮存儲(chǔ)特殊矩陣及其壓縮存儲(chǔ) 5.4 稀疏矩陣稀疏矩陣5.5 廣義表廣義表 5.6 小結(jié)小結(jié) 5.7 練習(xí)練習(xí)1多維數(shù)組在計(jì)算機(jī)中有兩種存放形式多維數(shù)組在計(jì)算機(jī)中有兩種存放形式:行優(yōu)先和列優(yōu)先。行優(yōu)先和列優(yōu)先。2行優(yōu)先規(guī)則是左邊下標(biāo)變化最慢，右邊下標(biāo)變化最快，行優(yōu)先規(guī)則是左邊下標(biāo)變化最慢，右邊下標(biāo)變化最快，右邊下標(biāo)變化一遍，與之相鄰的左邊下標(biāo)才變化一次。右邊下標(biāo)變化一遍，與之相鄰的左邊下標(biāo)才變化一次。3列優(yōu)先規(guī)則是右邊下標(biāo)變化最慢，左邊下標(biāo)變化最快，列優(yōu)先規(guī)則是右邊下標(biāo)變化最慢，左邊下標(biāo)變化最快，左邊下標(biāo)變化一遍，與之相鄰的右邊下標(biāo)才變化一次。左邊下標(biāo)變化一遍，與之相

42、鄰的右邊下標(biāo)才變化一次。4對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱。為節(jié)省存儲(chǔ)單元，可以進(jìn)對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱。為節(jié)省存儲(chǔ)單元，可以進(jìn)行壓縮存儲(chǔ)，對(duì)角線以上的元素和對(duì)角線以下的元素可以行壓縮存儲(chǔ)，對(duì)角線以上的元素和對(duì)角線以下的元素可以共用存儲(chǔ)單元，故共用存儲(chǔ)單元，故n n的對(duì)稱矩陣只需的對(duì)稱矩陣只需 個(gè)存儲(chǔ)單元即可。個(gè)存儲(chǔ)單元即可。5三角矩陣有上三角矩陣和下三角矩陣之分，為節(jié)省內(nèi)存三角矩陣有上三角矩陣和下三角矩陣之分，為節(jié)省內(nèi)存單元，可以采用壓縮存儲(chǔ)，單元，可以采用壓縮存儲(chǔ)，n n的三角矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的三角矩陣進(jìn)行壓縮存儲(chǔ)時(shí)，只需，只需+1個(gè)存儲(chǔ)單元即可。個(gè)存儲(chǔ)單元即可。6稀疏矩陣的非零元排列無(wú)任何規(guī)

43、律，為節(jié)省內(nèi)存單元，稀疏矩陣的非零元排列無(wú)任何規(guī)律，為節(jié)省內(nèi)存單元，進(jìn)行壓縮存儲(chǔ)時(shí)，可以采用三元組表示方法，即存儲(chǔ)非零進(jìn)行壓縮存儲(chǔ)時(shí)，可以采用三元組表示方法，即存儲(chǔ)非零元素的行號(hào)、列號(hào)和值。若干個(gè)非零元有若干個(gè)三元組，元素的行號(hào)、列號(hào)和值。若干個(gè)非零元有若干個(gè)三元組，若干個(gè)三元組稱為三元組表。若干個(gè)三元組稱為三元組表。7廣義表為線性表的推廣，里面的元素可以為原子，也可廣義表為線性表的推廣，里面的元素可以為原子，也可以為子表，故廣義表的存儲(chǔ)采用動(dòng)態(tài)鏈表較方便。以為子表，故廣義表的存儲(chǔ)采用動(dòng)態(tài)鏈表較方便。本章小結(jié)本章小結(jié)一、判斷題數(shù)組是同類型值的集合。數(shù)組是一組相繼的內(nèi)存單元。數(shù)組是一種復(fù)雜的數(shù)據(jù)

44、結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，既不是線性的，也不是樹型的。插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。數(shù)組的存儲(chǔ)方式分為順序和鏈?zhǔn)絻煞N。使用三元組表表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。廣義表是由零或多個(gè)單元素或子表所組成的有序列，所以廣義表可能為空表。1.線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是單元素，則廣義表便成為線性表。T TT TT T練習(xí)練習(xí)F FF FF FT TT T二、選擇題一個(gè)n*n的對(duì)稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為（ ）。 A.n*nB.n*n/2C.n(n+1)/2D.(n+1)*(n+1)/2E.(n-

45、1)*n/2F.n(n-1)C C在二維數(shù)組A79中，假定每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元， A00的存儲(chǔ)位置（基地址）為100，則A56的存儲(chǔ)位置為（ ）。 A.232B.151C.204D.304D D設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a85的地址為（ ）。 A.13 B.33 C.18 D.40B二維數(shù)組a的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)i的范圍從0-8，列下標(biāo)j的范圍是從1-10。存放a至少需要( ）個(gè)字節(jié)。 A.90 B.180 C.240D.270E.540A的第8列和第5行共占（ ）字節(jié)。

46、A.108B.114 C.54D.60E.150若a按行存放，元素a8,5的起始地址與當(dāng)a按列存放的元素( ）的起始地址一致。A.a8,5 B. a3,10C.a5,8D. a0,9E EA AB B已知廣義表LS=（a,(b,c,c),e）,運(yùn)用HEAD和T A I L 函 數(shù) 取 出 L S 中 的 單 元 素 b 的 運(yùn) 算 是（ ）。 A.HEAD(HEAD(LS) B.TAIL(HEAD(LS)C.HEAD(HEAD(TAIL(LS) D.HEAD(TAIL(LS)C C已知廣義表A=(a,b,c),(d,e,f),從A中取出單元素e的運(yùn)算是（ ）。 A.TAIL(HEAD(A)B.

47、HEAD(TAIL(A) C.HEAD(TAIL(TAIL(HEAD(A)D.HEAD(TAIL(HEAD(TAIL(A)E.HEAD(TAIL(TAIL(A)D D設(shè)廣義表LS=（a,b,LS）, 其長(zhǎng)度是（ ），其深度為（ ）。 A. B.3C.2 D.5B B下列廣義表為線性表的是（ ）。 A.E(a,(b,c) B.E(a,E)C.E(a,b)D.E(a,L()A AC C第六章第六章 樹和二叉樹樹和二叉樹本章主要介紹樹和二叉樹的概念，以及它們的存儲(chǔ)結(jié)構(gòu)本章主要介紹樹和二叉樹的概念，以及它們的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法，二叉樹的各種遍歷，樹和森林與二叉樹和相應(yīng)的算法，二叉樹的各種遍歷，樹和森

48、林與二叉樹之間的轉(zhuǎn)換等。通過本章學(xué)習(xí)，要求掌握如下內(nèi)容之間的轉(zhuǎn)換等。通過本章學(xué)習(xí)，要求掌握如下內(nèi)容:1.領(lǐng)會(huì)樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差領(lǐng)會(huì)樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別。別。2.熟記二叉樹的主要特性，并掌握它們的證明方法。熟記二叉樹的主要特性，并掌握它們的證明方法。3.熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。法實(shí)現(xiàn)二叉樹的其它操作。4.理解二叉樹的線索化過程以及在中序線索化樹上找給定理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。結(jié)點(diǎn)的前驅(qū)和后繼的方法。5.

49、熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。6.學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。7.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。法?！局R(shí)點(diǎn)知識(shí)點(diǎn)】樹的類型定義、二叉樹的類型定義、二叉樹樹的類型定義、二叉樹的類型定義、二叉樹的存儲(chǔ)表示、二叉樹的遍歷以及其它操作的實(shí)現(xiàn)、線索的存儲(chǔ)表示、二叉樹的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹、樹和森林的存儲(chǔ)表示、樹和森林的遍歷以及其二叉樹、樹和森林的存儲(chǔ)表示、樹和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹和赫夫曼編碼它操作的實(shí)現(xiàn)

50、、最優(yōu)樹和赫夫曼編碼第六章第六章 樹和二叉樹樹和二叉樹6.0 課前思考課前思考6.1 樹的基本概念樹的基本概念6.2 二叉樹二叉樹6.3 線索二叉樹線索二叉樹6.4 樹、森林和二叉樹的關(guān)系樹、森林和二叉樹的關(guān)系6.5 哈夫曼樹哈夫曼樹6.6 小結(jié)小結(jié)6.7 練習(xí)練習(xí)1在這一章討論了樹和二叉樹兩種數(shù)據(jù)類型的在這一章討論了樹和二叉樹兩種數(shù)據(jù)類型的定義以及它們的實(shí)現(xiàn)方法。樹是以分支關(guān)系定義定義以及它們的實(shí)現(xiàn)方法。樹是以分支關(guān)系定義的層次結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著的層次結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一一對(duì)多對(duì)多的關(guān)系，因此它為計(jì)算機(jī)應(yīng)用中出現(xiàn)的具的關(guān)系，因此它為計(jì)算機(jī)應(yīng)用中出現(xiàn)的具有層次關(guān)系或

51、分支關(guān)系的數(shù)據(jù)，提供了一種自然有層次關(guān)系或分支關(guān)系的數(shù)據(jù)，提供了一種自然的表示方法。如用樹描述人類社會(huì)的族譜和各種的表示方法。如用樹描述人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)。在計(jì)算機(jī)學(xué)科和應(yīng)用領(lǐng)域中樹也社會(huì)組織機(jī)構(gòu)。在計(jì)算機(jī)學(xué)科和應(yīng)用領(lǐng)域中樹也得到廣泛應(yīng)用，例如在編譯程序中，用樹來(lái)表示得到廣泛應(yīng)用，例如在編譯程序中，用樹來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)等。源程序的語(yǔ)法結(jié)構(gòu)等。2二叉樹是和樹不同的另一種樹型結(jié)構(gòu)，它有二叉樹是和樹不同的另一種樹型結(jié)構(gòu)，它有明確的左子樹和右子樹，因此當(dāng)用二叉樹來(lái)描述明確的左子樹和右子樹，因此當(dāng)用二叉樹來(lái)描述層次關(guān)系時(shí)，其層次關(guān)系時(shí)，其左孩子左孩子表示表示下屬關(guān)系下屬關(guān)系，而，而右

52、孩子右孩子表示的是表示的是同一層次的關(guān)系同一層次的關(guān)系。本章小結(jié)本章小結(jié)3樹和二叉樹的遍歷算法是實(shí)現(xiàn)各種操作的基礎(chǔ)。對(duì)非樹和二叉樹的遍歷算法是實(shí)現(xiàn)各種操作的基礎(chǔ)。對(duì)非線性結(jié)構(gòu)的遍歷需要選擇合適的搜索路徑，以確保在這條線性結(jié)構(gòu)的遍歷需要選擇合適的搜索路徑，以確保在這條路徑上可以訪問到結(jié)構(gòu)中的所有數(shù)據(jù)元素，并使每一個(gè)數(shù)路徑上可以訪問到結(jié)構(gòu)中的所有數(shù)據(jù)元素，并使每一個(gè)數(shù)據(jù)元素只被訪問一次。由于樹和二叉樹是層次分明的結(jié)構(gòu)，據(jù)元素只被訪問一次。由于樹和二叉樹是層次分明的結(jié)構(gòu)，因此按層次進(jìn)行遍歷是自然的事，它必能實(shí)現(xiàn)既訪問到所因此按層次進(jìn)行遍歷是自然的事，它必能實(shí)現(xiàn)既訪問到所有元素，又不會(huì)重復(fù)訪問。此外，

53、對(duì)樹和二叉樹還可進(jìn)行有元素，又不會(huì)重復(fù)訪問。此外，對(duì)樹和二叉樹還可進(jìn)行先左后右的遍歷。先左后右的遍歷。 4遍歷的實(shí)質(zhì)是按某種規(guī)則將二叉樹中的數(shù)據(jù)元素排列遍歷的實(shí)質(zhì)是按某種規(guī)則將二叉樹中的數(shù)據(jù)元素排列成一個(gè)線性序列，二叉樹的線索鏈表便可看成是二叉樹的成一個(gè)線性序列，二叉樹的線索鏈表便可看成是二叉樹的一種一種線性線性存儲(chǔ)結(jié)構(gòu)，在線索鏈表上可對(duì)二叉樹進(jìn)行存儲(chǔ)結(jié)構(gòu)，在線索鏈表上可對(duì)二叉樹進(jìn)行線線性化性化的遍歷，即不需要的遍歷，即不需要遞歸遞歸，而是從，而是從第一個(gè)元素第一個(gè)元素起起，逐個(gè)訪問，逐個(gè)訪問后繼元素后繼元素直至直至后繼后繼為為空空止。因此線索止。因此線索鏈表是通過遍歷生成的，即在遍歷過程中保

54、存結(jié)點(diǎn)之間的鏈表是通過遍歷生成的，即在遍歷過程中保存結(jié)點(diǎn)之間的前驅(qū)前驅(qū)和和后繼后繼的關(guān)系，并為方便起見，在線索鏈表中添的關(guān)系，并為方便起見，在線索鏈表中添加一個(gè)加一個(gè)頭結(jié)點(diǎn)頭結(jié)點(diǎn)，并由此構(gòu)成一個(gè)，并由此構(gòu)成一個(gè)雙向循環(huán)鏈表雙向循環(huán)鏈表。在實(shí)。在實(shí)際應(yīng)用時(shí)也可簡(jiǎn)化為際應(yīng)用時(shí)也可簡(jiǎn)化為單向循環(huán)鏈表單向循環(huán)鏈表（即只保存后繼或前（即只保存后繼或前驅(qū)關(guān)系）。驅(qū)關(guān)系）。5在這一章作為應(yīng)用，介紹了最優(yōu)樹和最優(yōu)前在這一章作為應(yīng)用，介紹了最優(yōu)樹和最優(yōu)前綴編碼的構(gòu)造方法，最優(yōu)樹是一種綴編碼的構(gòu)造方法，最優(yōu)樹是一種帶權(quán)路徑長(zhǎng)帶權(quán)路徑長(zhǎng)度最短度最短的樹，最優(yōu)前綴編碼是最優(yōu)二叉樹的一的樹，最優(yōu)前綴編碼是最優(yōu)二叉樹的一

55、種應(yīng)用。種應(yīng)用。 一、一、選擇選擇二、二、判斷判斷三、三、填空填空四、四、應(yīng)用題應(yīng)用題一、選擇題一、選擇題n已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( )A-A+B*C/DE B. -A+B*CD/EC-+*ABC/DE D. -+A*BC/DEn算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ ）Aab+cde/* Babcde/+*+Cabcde/*+Dabcde*/+1.設(shè)有一表示算術(shù)表達(dá)式的二叉樹，它所表示的算術(shù)表達(dá)式是（ ）A. A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G) C.(A*B+C)/(

56、D*E+（F-G）)D. A*B+C/D*E+F-G EFDGAB/+*-C*DBC練習(xí)練習(xí)n在下述結(jié)論中，正確的是（ ）只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;二叉樹的度為2；二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。 A B C Dn若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定n有關(guān)二叉樹下列說法正確的是（ ）A二叉樹的度為2B一棵二叉樹的度可以小于2 C二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 DBBn具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（ ）個(gè)度為2的結(jié)點(diǎn)。 A8 B9

57、C10 Dll n一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ） A 250 B 500 C254 D505 E以上答案都不對(duì) BE由二叉樹結(jié)點(diǎn)的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因?yàn)閚=1001,所以1002=2n0+n1,在完全二叉樹樹中，n1只能取0或1,在本題中只能取0，故n=501，因此選E。 n二叉樹的第i層上最多含有結(jié)點(diǎn)數(shù)為（ ） A2i B 2i-1-1 C 2i-1 D2i -1 n一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ） A11 B10 C11至1025之間D10至1024之間n一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有( )結(jié)點(diǎn)A2h B2h-1 C2h+1 Dh+1 n對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為（ ） Anlog2n Blog2n Clog2n|+1 D不確定n一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹