數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)知識(shí)點(diǎn)

第一章：概論知識(shí)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)等之間的區(qū)和聯(lián)系。數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)各有哪些基本類(lèi)型、數(shù)據(jù)的基本邏輯結(jié)構(gòu)有什么特點(diǎn)。我們所學(xué)的幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)中（順序表、鏈表、隊(duì)列、棧、串、樹(shù)、圖等），哪些是線性數(shù)據(jù)結(jié)構(gòu)，哪些是非線性數(shù)據(jù)結(jié)構(gòu)？算法復(fù)雜性的概念、內(nèi)容和算法復(fù)雜性的計(jì)算。簡(jiǎn)單算法復(fù)雜性的判斷：(1)sum=0;for(i=1;i<=n;i++)sum=sum+i;其中i=1,2,3,…,k,需頻度k<=n，所以復(fù)雜性為O(n)(2)i=1;while(i<=n)i=i+2;其中i=1,3,5,…,(2k-1),需2k-1<=n，則頻度k<=(n+1)/2，復(fù)雜性為O(n)(3)i=1;while(i<=n)i=i*3;其中i=1,3,32,…,3k,需3k<=n，則頻度k<=log3n，復(fù)雜性為O(log3n)(4)i=1;while(i*i<=n)i++;其中i=1,2,3,…,k，需k2<=n，則頻度k<=n1/2，復(fù)雜性為O(n1/2)習(xí)題：1、填空題（1）數(shù)據(jù)的邏輯結(jié)構(gòu)包括：、、、；（2）存儲(chǔ)結(jié)構(gòu)包括：、、、。（3）數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是（4）下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是：i=1；while(i<n)i=i*2;（5）計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為_(kāi)______。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;（6）下面程序段的時(shí)間復(fù)雜度為_(kāi)_______。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;2、選擇題（1）算法的計(jì)算量的大小稱(chēng)為計(jì)算的（）。A．效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度（2）算法的時(shí)間復(fù)雜度取決于（）A．問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B（3）計(jì)算機(jī)算法指的是（），它必須具備（）這三個(gè)特性。(1)A．計(jì)算方法B.排序方法C.解決問(wèn)題的步驟序列D.調(diào)度方法(2)A．可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性（4）從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類(lèi)。A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)（5）以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）？A．廣義表B.二叉樹(shù)C.稀疏矩陣D.串（6）在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（）for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1A．O(2n)B．O(n)C．O(n2)D．O(log2n)（7）程序段for(i=n;i>=1;i--)for(j=1;j<=n;j++)IFA[j]>A[j+1]THENA[j]與A[j+1]對(duì)換；其中n為正整數(shù)，則最后一行的語(yǔ)句頻度在最壞情況下是（）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)（8）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)A．樹(shù)B．字符串C．隊(duì)D．棧（9）連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（）。A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)3、問(wèn)答題（1）數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？（2）數(shù)據(jù)的邏輯結(jié)構(gòu)有哪些基本類(lèi)型？（3）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？第二章：線性表知識(shí)點(diǎn)：線性表的基本概念和兩種存儲(chǔ)方式：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)順序表的概念、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)，插入、刪除運(yùn)算及其時(shí)間復(fù)雜度；順序表的特點(diǎn)：隨機(jī)存儲(chǔ)單鏈表的存儲(chǔ)、插入、刪除運(yùn)算特點(diǎn)？是否可以隨機(jī)存取？訪問(wèn)、增加或者刪除結(jié)點(diǎn)時(shí)的時(shí)間復(fù)雜度？單鏈表中插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)的基本步驟？頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別，頭結(jié)點(diǎn)與首元結(jié)點(diǎn)的關(guān)系？在鏈表里面，引入頭結(jié)點(diǎn)有什么作用？有頭結(jié)點(diǎn)、無(wú)頭結(jié)點(diǎn)的單鏈表為空的條件分別是什么？有頭結(jié)點(diǎn)：L->next==NULL，無(wú)頭結(jié)點(diǎn)：L==NULL習(xí)題：1、選擇題（1）下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（）A．存儲(chǔ)密度大B．插入運(yùn)算方便C．刪除運(yùn)算方便D．可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示（2）下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。（3）線性表是具有n個(gè)（）的有限序列（n>0）。A3．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)E．信息項(xiàng)（4）鏈表不具有的特點(diǎn)是（）A．插入、刪除不需要移動(dòng)元素B．可隨機(jī)訪問(wèn)任一元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線性長(zhǎng)度成正比（5）下面的敘述不正確的是（）A．線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比B.線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)C.線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比D.線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)（6）若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)（7）對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)（8）線性表（a1,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（）A．O（i）B．O（1）C．O（n）D．O（i-1）2、填空（1）當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_______存儲(chǔ)結(jié)構(gòu)。（2）線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是________。（3）在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)__1______個(gè)元素。（4）在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_______。（5）鏈接存儲(chǔ)的特點(diǎn)是利用_______來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。（6）順序存儲(chǔ)結(jié)構(gòu)是通過(guò)_______表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)______表示元素之間的關(guān)系的。（7）對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共_____個(gè)，單鏈表為_(kāi)_____個(gè)。（8）在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：__（9）線性結(jié)構(gòu)包括______、______、_____和______。線性表的存儲(chǔ)結(jié)構(gòu)分成_____和______。3、應(yīng)用題（1）線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（2）說(shuō)明在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別；頭結(jié)點(diǎn)與首元結(jié)點(diǎn)的關(guān)系。（3）刪除順序表中所有的正數(shù)，要求移動(dòng)次數(shù)小。搜索順序表，對(duì)每一個(gè)正數(shù)，先不刪除，而是累計(jì)當(dāng)前正數(shù)個(gè)數(shù)s，于是，對(duì)每個(gè)非正數(shù)，將它一次性前移s位。算法復(fù)雜性為O（n）。voiddels(sqlist*L){ints,i;s=0; //正數(shù)計(jì)數(shù)器for(i=0;i<L->n;i++)if(L->data[i]>0s++; //累計(jì)當(dāng)前正數(shù)elseif(s>0)L->data[i-s]=l->data[i];//向前移動(dòng)s位L->n=L->n-s; //調(diào)整表長(zhǎng)}還可以刪除順序表中所有的負(fù)數(shù)、字符等，主要是刪除數(shù)據(jù)的條件不一樣（4）單鏈表算法運(yùn)用，如鏈表合并，將兩個(gè)有序表合并為一個(gè)有序表lklistpurge(lklistA,lklistB){pointerC,p,q,r;p=A->next;q=B->next;C=A;r=C; //取A頭結(jié)點(diǎn)作C頭結(jié)點(diǎn)while(p!=NULL&&q!=NULL){if(p->data<=q->data){r?>next=p;r=p;p=p->next;}else{r?>next=q;r=q;q=q->next;}}if(p!=NULL)r->next=p; //A表有剩余結(jié)點(diǎn)elser->next=q;deleteB; //釋放B頭結(jié)點(diǎn)returnC;}第三章棧、隊(duì)列和串知識(shí)點(diǎn)：棧的定義、棧頂、棧底、運(yùn)算特點(diǎn)（先進(jìn)后出），順序?qū)崿F(xiàn)和鏈接實(shí)現(xiàn)及其特點(diǎn)，棧的應(yīng)用隊(duì)列的概念，隊(duì)頭、隊(duì)尾、運(yùn)算特點(diǎn)（后進(jìn)后出），順序?qū)崿F(xiàn)、循環(huán)隊(duì)列、鏈隊(duì)列串的概念和串長(zhǎng)的計(jì)算習(xí)題選擇題（1）對(duì)于棧操作數(shù)據(jù)的原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序（2）棧在（）中應(yīng)用。A.遞歸調(diào)用B.子程序調(diào)用C.表達(dá)式求值D.A，Ｂ，Ｃ（3）一個(gè)遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分（4）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改（5）用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)()。A．僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都可能要修改（6）遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱(chēng)為（）的數(shù)據(jù)結(jié)構(gòu)。A．隊(duì)列B．多維數(shù)組C．棧D.線性表（7）棧和隊(duì)列都是（）A．順序存儲(chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)應(yīng)用題（1）名詞解釋?zhuān)簵?、?duì)列？（2）簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。第4章多維數(shù)組和廣義表知識(shí)點(diǎn)：1、多維數(shù)組的定義，對(duì)于一個(gè)多維數(shù)據(jù)，如何計(jì)算里面元素的個(gè)數(shù)？在存儲(chǔ)多維數(shù)組時(shí)，如果已知首元素的存儲(chǔ)地址，如何求數(shù)組里面任意元素的存儲(chǔ)地址？（注意，行優(yōu)先、列優(yōu)先、元素的長(zhǎng)度）2、廣義表的概念、表長(zhǎng)、深度、表頭、表尾；廣義表的取表頭和取表尾操作；注意，取表頭去的是原則取表尾得到的是表，會(huì)利用廣義表的取表頭和取表尾操作分離廣義表的原子。習(xí)題：1、選擇題（1）將一個(gè)A[1..100，1..100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665（即該元素下標(biāo)i=66，j=65），在B數(shù)組中的位置K為（）。供選擇的答案：A.198B.195C.197（2）設(shè)A是n*n的對(duì)稱(chēng)矩陣，將A的對(duì)角線及對(duì)角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對(duì)上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-1（3）設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標(biāo)為()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-1（4）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（）。A.55B.45C.36D.16（5）廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d（6）廣義表運(yùn)算式Tail(((a,b),(c,d)))的操作結(jié)果是（）。A.(c,d)B.c,dC.((c,d))D.d（7）廣義表（（a,b,c,d））的表頭是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）2、填空題（1）設(shè)廣義表L=((),()),則head(L)是(1)___；tail(L)是(2)__；L的長(zhǎng)度是(3)_；深度是(4)__。（2）已知廣義表A=(9,7,(8,10,(99)),12)，試用求表頭和表尾的操作Head()和Tail()將原子元素99從A中取出來(lái)。（3）廣義表的深度是__。（4）廣義表(a,(a,b),d,e,((i,j),k))的長(zhǎng)度是，深度是_。（5）已知廣義表LS=(a，(b，c，d)，e),運(yùn)用head和tail函數(shù)取出LS中原子b的運(yùn)算是_____。（6）廣義表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是:___。第五章樹(shù)形結(jié)構(gòu)知識(shí)點(diǎn)：樹(shù)的概念、根、度、兄弟、路徑、葉子、孩子、雙親、高度、深度、層數(shù)；根據(jù)一棵樹(shù)，能夠知道它的度、根節(jié)點(diǎn)、葉子結(jié)點(diǎn)、深度等；根據(jù)樹(shù)中的某個(gè)結(jié)點(diǎn)，可以找出它的孩子結(jié)點(diǎn)；二叉樹(shù)的概念、性質(zhì)和幾種特殊形態(tài)的二叉樹(shù)及其特點(diǎn)：斜樹(shù)、滿二叉樹(shù)、完全二叉樹(shù)二叉樹(shù)的存儲(chǔ)（順序存儲(chǔ)，適合完全二叉樹(shù)；鏈?zhǔn)酱鎯?chǔ)）二叉樹(shù)的遍歷及其應(yīng)用（先根、中根和后根遍歷）二叉樹(shù)的雙序列生成（先根和中根或者中根和后根生成二叉樹(shù)）樹(shù)和森林的概念、樹(shù)和森林與二叉樹(shù)的相互轉(zhuǎn)換方法、以及轉(zhuǎn)換的二叉樹(shù)的特點(diǎn)，樹(shù)和森林的遍歷哈弗曼編碼的概念和哈弗曼樹(shù)的構(gòu)造題目選擇題（1）已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE（2）設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．8（3）在下述結(jié)論中，正確的是（）①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0;②二叉樹(shù)的度為2；③二叉樹(shù)的左右子樹(shù)可任意交換;④深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。A．①②③B．②③④C．②④D．①④（4）設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（）A．m-nB．m-n-1C．n+1D．條件不足，無(wú)法確定（5）若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）A．9B．11C．15D．不確定（6）在一棵三元樹(shù)中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)A．4B．5C．6D．7（7）設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（）。A．M1B．M1+M2C．M3D．M2+M3（8）具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有（）個(gè)度為2的結(jié)點(diǎn)，A．8B．9C．10D．ll（9）一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A．250B．500C．254D．505E．以上答案都不對(duì)（10）設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為()A．不確定B．2nC．2n+1D．2n-1（11）有關(guān)二叉樹(shù)下列說(shuō)法正確的是（）A．二叉樹(shù)的度為2B．一棵二叉樹(shù)的度可以小于2C．二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2（12）二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為（）A．2IB．2I-1-1C．2I-1D．2I-1（13）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（）A．11B．10C．11至1025之間D．10至1024之間（14）一棵二叉樹(shù)高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少有()結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+1（15）在一棵高度為k的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（）A．2k-1B．2kC．2k-1D．?log2k?+1（16）一棵樹(shù)高為K的完全二叉樹(shù)至少有（）個(gè)結(jié)點(diǎn)A．2k–1B.2k-1–1C.2k-1D.2k（17）一棵二叉樹(shù)的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG（18）已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定（19）某二叉樹(shù)中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：（）A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對(duì)（20）二叉樹(shù)的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹(shù)根的右子樹(shù)的根是：（）A、EB、FC、GD、H填空題（1）二叉樹(shù)由_(1)__，__(2)_，_(3)__三個(gè)基本單元組成。（2）具有256個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)_____。（3）深度為k的完全二叉樹(shù)至少有___(1)___個(gè)結(jié)點(diǎn)，至多有___(2)____個(gè)結(jié)點(diǎn)。（4）深度為H的完全二叉樹(shù)至少有_(1)___個(gè)結(jié)點(diǎn)；至多有_(2)___個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是(3)。（5）假設(shè)根結(jié)點(diǎn)的層數(shù)為１，具有ｎ個(gè)結(jié)點(diǎn)的二叉樹(shù)的最大高度是____。（6）在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0=______（7）高度為K的完全二叉樹(shù)至少有_____個(gè)葉子結(jié)點(diǎn)。（8）高度為8的完全二叉樹(shù)至少有_____個(gè)葉子結(jié)點(diǎn)。（9）已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是______。（10）層完全二叉樹(shù)至少有_____個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的最大層數(shù)為_(kāi)_____。應(yīng)用題（1）樹(shù)所有結(jié)點(diǎn)的度數(shù)之和與結(jié)點(diǎn)數(shù)有何關(guān)系？與邊數(shù)有何關(guān)系？二叉樹(shù)（或者樹(shù)中），度為0的結(jié)點(diǎn)數(shù)與度不為0的結(jié)點(diǎn)樹(shù)有何關(guān)系？（2）已知一棵二叉樹(shù)的對(duì)稱(chēng)序和后序序列如下：中序：GLDHBEIACJFK后序：LGHDIEBJKFCA出這棵二叉樹(shù)，并寫(xiě)出該二叉樹(shù)的先序序列：寫(xiě)出這棵二叉樹(shù)的根節(jié)點(diǎn)、葉子節(jié)點(diǎn)、度為1的節(jié)點(diǎn)、度為2的節(jié)點(diǎn)(3)轉(zhuǎn)換為對(duì)應(yīng)的森林：（3）從概念上講，樹(shù)，森林和二叉樹(shù)是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)，森林轉(zhuǎn)化為二叉樹(shù)的基本目的是什么，并指出樹(shù)和二叉樹(shù)的主要區(qū)別。（4）二叉樹(shù)的遍歷算法及其應(yīng)用，如求葉子結(jié)點(diǎn)數(shù)、度為1的結(jié)點(diǎn)數(shù)、度為2的結(jié)點(diǎn)數(shù)，交換二叉樹(shù)的左右子樹(shù)、判斷兩棵二叉樹(shù)是否等價(jià)等。第6章圖知識(shí)點(diǎn)圖的概念：有向圖、無(wú)向圖、完全圖、連通圖、強(qiáng)連通圖、鄰接點(diǎn)、頂點(diǎn)的度、出度、入度、路徑圖的存儲(chǔ)：有向圖和無(wú)向圖的鄰接矩陣存儲(chǔ)和鄰接表存儲(chǔ)，及其特點(diǎn)圖的深度優(yōu)點(diǎn)遍歷和廣度優(yōu)先遍歷生成樹(shù)、最小生成樹(shù)，Prim和Kruskal算法有向無(wú)環(huán)圖的應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑（課件例題）習(xí)題1、選擇題（1）圖中有關(guān)路徑的定義是（）。A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B．由不同頂點(diǎn)所形成的序列C．由不同邊所形成的序列D．上述定義都不是（2）設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2（3）一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為（）。A．n-1B．nC．n+1D．nlogn；（4）要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條邊。A．n-lB．nC．n+lD．2n（5）n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）（6）一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（）個(gè)連通分量，最多有（）個(gè)連通分量。A．0B．1C．n-1D．n（7）在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（）倍。A．1/2B．2C．1D．4（8）下列哪一種圖的鄰接矩陣是對(duì)稱(chēng)矩陣？（）A．有向圖B．無(wú)向圖C．AOV網(wǎng)D．AOE網(wǎng)（9）下列說(shuō)法不正確的是（）。A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次C．圖的深度遍歷不適用于有向圖B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷D．圖的深度遍歷是一個(gè)遞歸過(guò)程（10）下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）：（）A．深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑（11）已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵ǎ?。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7（12）在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（）。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的路徑C．G中沒(méi)有弧<Vi,Vj>D．G中有一條從Vj到Vi的路徑（13）關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。A．從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長(zhǎng)回路D．最短回路（14）下面關(guān)于求關(guān)鍵路徑的說(shuō)法不正確的是（）。A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B．一個(gè)事件的最早開(kāi)始時(shí)間同以該事件為尾的弧的活動(dòng)最早開(kāi)始時(shí)間相同C．一個(gè)事件的最遲開(kāi)始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開(kāi)始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D．關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上（15）下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）。A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C．所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D．某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成2、填空題（1）判斷一個(gè)無(wú)向圖是一棵樹(shù)的條件是______。（2）一個(gè)連通圖的______是一個(gè)極小連通子圖。（3）具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)____。（4）若用n表示圖中頂點(diǎn)數(shù)目，則有______條邊的無(wú)向圖成為完全圖。（5）G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有___個(gè)頂點(diǎn)。（6）在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要___條弧。（7）在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)______。（8）在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的______；對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的_____。（9）在有向圖的鄰接矩陣表示中，計(jì)算第I個(gè)頂點(diǎn)入度的方法是______。（10）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接表的表示，則表頭向量大小為_(kāi)____，鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為_(kāi)____。（11）構(gòu)造連通網(wǎng)最小生成樹(shù)的兩個(gè)典型算法是_____。（12）求圖的最小生成樹(shù)有兩種算法，______算法適合于求稀疏圖的最小生成樹(shù)。(13)Prim（普里姆）算法適用于求_____的網(wǎng)的最小生成樹(shù)；kruskal（克魯斯卡爾）算法適用于求_____的網(wǎng)的最小生成樹(shù)。三、應(yīng)用題（1）1）．如果G1是一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖，那么G1最多有多少條邊？G1最少有多少條邊？2）．如果G2是一個(gè)具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖，那么G2最多有多少條邊？G2最少有多少條邊？EABEABGCDF536141325（2）考慮右圖：1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)：ABGFDEC2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)：EACFBDG3）根據(jù)普利姆(Prim)算法，求它的最小生成樹(shù)并計(jì)算最小生成樹(shù)的權(quán)值（3）已知一個(gè)無(wú)向圖如下圖所示，要求分別用Prim和Kruskal算法生成最小樹(shù)并計(jì)算最小生成樹(shù)的權(quán)值（假設(shè)以①為起點(diǎn)，試畫(huà)出構(gòu)造過(guò)程）。121265432010116618101459第七章排序知識(shí)點(diǎn)排序的基本概念。如穩(wěn)定性、內(nèi)排序、外排序，有序區(qū)增長(zhǎng)法，有序度增長(zhǎng)等。理解下面排序算法的原理、穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜度，最好情況、最壞情況：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序?qū)τ谏厦娼o的排序算法，給出一組序列，可以寫(xiě)出每一趟的排序結(jié)果。習(xí)題選擇題（1）某內(nèi)排序方法的穩(wěn)定性是指()。A．該排序算法不允許有相同的關(guān)鍵字記錄B．該排序算法允許有相同的關(guān)鍵字記錄C．平均時(shí)間為0（nlogn）的排序方法D．以上都不對(duì)（2）下面給出的四種排序法中()排序法是不穩(wěn)定性排序法。A.插入B.冒泡C.二路歸并D.堆（3）下列排序算法中，其中（）是穩(wěn)定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接選擇排序，歸并排序D.歸并排序，冒泡排序（4）若要求盡可能快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選（）。A．快速排序B．歸并排序C．冒泡排序（5）下面給出的四種排序方法中，排序過(guò)程中的比較次數(shù)與排序方法無(wú)關(guān)的是。()A．選擇排序法B.插入排序法C.快速排序法D.堆積排序法（6）在下列排序算法中,哪一個(gè)算法的時(shí)間復(fù)雜度與初始排序無(wú)關(guān)（）。A．直接插入排序B.氣泡排序C.快速排序D.直接選擇排序（7）下列排序算法中()不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序（8）下列排序算法中()排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A.選擇