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

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