數(shù)據(jù)結(jié)構(gòu)全真模擬測驗(yàn)題

1、全真模擬試卷(1)一、單項(xiàng)選擇題1、線性表是具有n個(gè)的有限序列(n0)。表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)TOCo1-5hz2、棧和隊(duì)列都是。順序存儲(chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)3、若對n階對稱矩陣A以行序列為主序方式將其上三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aj(inext=s;s-prev=p;p-prev=s;s-next=p-next;Bp-next-prev=s;p-next=s;s-prev=p;s-next=p-nextCs-prev=p;s-next=p-next

2、;p-next=s;p-next-prev=sDs-prev=p;s-next=p-next;p-next-prev=s;p-next=s2、一個(gè)棧的入棧序列為A,B,C,D,E,則棧的不可能的出棧序列是。二叉樹在線索化后，仍不能有效解決問題是。先序線索二叉樹中求先序后繼中序線索二叉樹中求中序后繼C中序線索二叉樹中求中序前驅(qū)D后序線索二叉樹中求后序后繼若一個(gè)具有N個(gè)頂點(diǎn)，K條邊得無向圖時(shí)一個(gè)森林(NK),則該森林中必有課樹。以下存儲(chǔ)結(jié)構(gòu)中，不是樹的存儲(chǔ)結(jié)構(gòu)的是。雙親存儲(chǔ)結(jié)構(gòu)B.順序存儲(chǔ)結(jié)構(gòu)C.孩子鏈存儲(chǔ)結(jié)構(gòu)D.孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)若G是一個(gè)具有36條邊得非連通無向圖(不含自回路和多重邊)，則圖G

3、至少有個(gè)頂點(diǎn)。當(dāng)圖采用鄰接矩陣存儲(chǔ)時(shí)，深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為,廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度為，其中n為圖的頂點(diǎn)數(shù)，e是圖的邊樹。O(n2),O(n2)B.O(n2),O(n+e)C.O(n+e),O(n2)D.O(n+e),O(n+e)若采用鏈地址法構(gòu)圖散列表，散列函數(shù)為H(key)=keyMOD17，則需17個(gè)鏈表。這些鏈的鏈?zhǔn)字羔槝?gòu)成一個(gè)指針數(shù)組，數(shù)組的下標(biāo)范圍為。A.017B.117C.016D.116若用冒泡排序方法對序列10,14,26,29,41,52,從大到小排序，需進(jìn)行次比較。10在含有n個(gè)關(guān)鍵字的小根堆(堆頂元素最小)中，關(guān)鍵字最大的記錄有可能存儲(chǔ)在位置上。A.匚n/

4、2B.匚n/2-1C.1D.匚n/2+2二、綜合應(yīng)用題已知如圖所示的AOE網(wǎng)，求：每項(xiàng)活動(dòng)的最早發(fā)生時(shí)間(ve)和最遲開始時(shí)間(vl)完成此工程最少需要多少單位時(shí)間？關(guān)鍵活動(dòng)與關(guān)鍵路徑。已知下列各種初始狀態(tài)(長度為n)元素，試問當(dāng)利用直接插入法進(jìn)行排序時(shí)，至少需要進(jìn)行多少次比較(要求排序后的文件按關(guān)鍵字從小到大順序排列)？關(guān)鍵字自小到大有序(key1key2key2.keyn)。奇數(shù)關(guān)鍵字順序有序，偶數(shù)關(guān)鍵字順序有序(key1key3.,key2key4)前半部分元素按關(guān)鍵字順序有序，后半部分元素按關(guān)鍵字順序逆序(key1key2keym+2keyn,m為中間位置)。全真模擬試卷（4）一、單項(xiàng)

5、選擇題TOCo1-5hz對于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的但鏈表，判定該表為空表的條件是。A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL一個(gè)棧的入棧元素序列是，若允許出棧操作可在任意可能的時(shí)刻進(jìn)行，則下面的序列中，不可能出現(xiàn)的出棧序列是。用s表示入棧操作，x表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序相應(yīng)的s和x的操作串為。若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是A.二叉排序樹B.哈夫曼樹C.堆D.AVL樹由元素序列（）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（

6、即離插入TOCo1-5hz結(jié)點(diǎn)最近且平衡因子的絕對值為2的結(jié)點(diǎn)）為。根據(jù)使用頻率，為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能時(shí)。如圖所示，從頂點(diǎn)A出發(fā)，如按照廣度優(yōu)先搜索法進(jìn)行遍歷，可能得到的一種頂點(diǎn)序列為。對AOE網(wǎng)的關(guān)鍵路徑，下面的說法是正確的。提高關(guān)鍵路徑的一個(gè)關(guān)鍵活動(dòng)的速度，必然使整個(gè)工程縮短工期完成工程的最短時(shí)間是從始點(diǎn)到終點(diǎn)的最答案路徑的長度。一個(gè)AOE網(wǎng)的關(guān)鍵路徑只有一個(gè)，但關(guān)鍵活動(dòng)可有多個(gè)。任何一項(xiàng)活動(dòng)持續(xù)時(shí)間的改變都可能會(huì)影響關(guān)鍵路徑的改變。關(guān)于雜奏查找不正確的有。采用鏈地址法解決沖突是，查找任一個(gè)元素的時(shí)間是相同的。采用鏈地址法解決沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個(gè)元素的時(shí)間

7、是相同的。用鏈地址法解決沖突沖突易引起聚集現(xiàn)象。再哈希法不易產(chǎn)生聚集在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序的方法是。直接插入排序起泡排序直接選擇排序快速排序二、綜合應(yīng)用題利用兩個(gè)棧S1和S2來模擬一個(gè)隊(duì)列。若不存在棧溢出問題，則請寫出用棧的操作來實(shí)現(xiàn)隊(duì)列的插入和刪除的算法。42以下圖為例，按dijkstra算法計(jì)算得到從頂點(diǎn)A到其他各個(gè)頂點(diǎn)的最短路徑和最長路徑長度。一、單項(xiàng)選擇題以下關(guān)于先性表的描述，正確的是。線性表中并不是所有元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼線性表的順序存儲(chǔ)結(jié)構(gòu)插入和撒謊年初是效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)好。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的元素隨機(jī)訪問效率太低，因

8、此它不如順序存儲(chǔ)結(jié)構(gòu)好順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入，刪除運(yùn)算效率高。用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算是。僅修改頭指針僅修改尾指針頭尾指針都有修改頭尾指針可能都要修改一棵深度為4的完全二叉排序樹，最少有個(gè)結(jié)點(diǎn)。在常用的描述二叉排序樹的存儲(chǔ)結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)左子樹一定為空右子樹一定為空左右子樹均為空左右子樹均不為空正確的是。0元素?cái)?shù)就是該圖的邊數(shù)0元素就是該圖所有頂點(diǎn)的度之和i行的非0元素之和是第i行的非0元素之和是第個(gè)。以下關(guān)于鄰接矩陣的描述，無向圖的鄰接矩陣中非無向圖的鄰接矩陣中非i個(gè)頂點(diǎn)的入度i個(gè)頂點(diǎn)的出度i個(gè)頂點(diǎn)的入度i個(gè)頂點(diǎn)的出度有向圖的鄰接矩陣中第有向圖的鄰接矩陣

9、中第有向圖的所有拓?fù)渑判蛐蛄杏?，若查找元素58，則它將依次與表中元素折半查找有序表(比較大小，查找結(jié)果是失敗。下列關(guān)于m階B-樹的說法錯(cuò)誤的是根結(jié)點(diǎn)至多有m棵子樹所有葉子都在同一層次上非葉結(jié)點(diǎn)至少有m/2(m為偶數(shù))或m/2+1(m為奇數(shù))棵子樹根結(jié)點(diǎn)中的數(shù)據(jù)是有序的若不考慮基數(shù)排序，則在排序過程中，主要的兩種基本操作是A.比較和交換B.比較和移動(dòng)C.選擇和交換D.選擇和移動(dòng)歸并排序中，歸并的趟數(shù)是_。A.O(n)B.O(log2n)CO(nlog2n)DO(n2)二、綜合應(yīng)用題41請利用棧的基本操作寫出復(fù)制一顆二叉樹的非遞歸算法。要求以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)。設(shè)棧已定義：initst

10、ack(S)，push(S,e)，stackempty(S),Gettop(S,e),Pop(S,e)分別為棧初始化，入棧，判斷?？眨@得棧頂元素，出棧等操作。函數(shù)原型如下：voidbitree-Copy(BitreeT,Bitree&U)42設(shè)有關(guān)鍵字序列為：50.71.80.60.55.40.25.99，用數(shù)組存儲(chǔ)。請以堆排序方式把數(shù)據(jù)排序成遞增序列，并給出建堆和每趟堆調(diào)整后的數(shù)據(jù)序列。一、單項(xiàng)選擇題設(shè)n個(gè)元素的線性表順序存儲(chǔ)，若刪除其第i個(gè)元素和在第i，第i+1個(gè)元素之間插入一個(gè)新元素，則分別需要移動(dòng)個(gè)元素。A.n-i,n-i+1B.n-i+1,n-iC.n-i,n-iD.n-i+1,n

11、-i+1若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V【m】，top【i】代表第i個(gè)棧(i=1,2)棧頂，棧TOCo1-5hz空時(shí)棧1的底在v0,top1=0,棧2的底在Vm-1,top2=m-1,則棧滿的條件是。Atop1=top2B.top1+1=top2C.top1+top2=mD.top1-1=top2設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對出現(xiàn)的算法，采用數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧已知某完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)數(shù)據(jù)信息的存放順序依次為A.B.C.D.E.F.G.H,該完全二叉樹的后序遍歷序列為。由帶權(quán)的5個(gè)葉子結(jié)點(diǎn)生成的哈夫曼樹的帶

12、權(quán)路徑長度為。無向圖G有16條邊，有3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)都小于3，則G中至少有個(gè)頂點(diǎn)。采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于樹的。中根遍歷先跟遍歷后跟遍歷按層次遍歷對大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下，對于查找失敗，它們的平均查找長度是，對于查找成功，它們的平均查找長度是相同的。相同的不同的無法確定的以上都不對(不要)9.下面關(guān)于B-樹和B+樹的敘述中，不正確的是。B-樹和B+樹都是平衡的多叉樹B-樹和B+樹都可用于文件的索引結(jié)構(gòu)B-樹和B+樹都能有效地支持順序檢索B-樹和B+樹都能有效地支持隨機(jī)檢索10第i趟處理是將Ai+1,An中關(guān)鍵

13、字最小者與Ai(i=1,2,.,n-1)進(jìn)行交換的排序算法為_。快速排序選擇排序冒泡排序插入排序二、綜合應(yīng)用題已知q是一個(gè)非空順序隊(duì)列，s是一個(gè)順序棧，請?jiān)O(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)將隊(duì)列q中所有元素逆置。已知無向圖G=(V,E)的鄰接表，給出求圖G的聯(lián)通分量個(gè)數(shù)的算法。一、單項(xiàng)選擇題以下關(guān)于線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)刪除結(jié)點(diǎn)運(yùn)算的描述，正確的是。帶頭結(jié)點(diǎn)的線性刪除結(jié)點(diǎn)時(shí)，不需要更改頭指針帶頭結(jié)點(diǎn)的線性鏈表刪除第一個(gè)結(jié)點(diǎn)時(shí)，需要更改頭指針不帶頭結(jié)點(diǎn)的線性鏈表刪除第一個(gè)結(jié)點(diǎn)時(shí)，需要更改頭指針不帶頭結(jié)點(diǎn)的線性鏈表刪除第一個(gè)結(jié)點(diǎn)時(shí)，不需要更改頭指針若循環(huán)隊(duì)列以數(shù)組Q0m-1作為其存儲(chǔ)結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中

14、的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按rear=(rear+1)Modm進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是。A.rear-lengthB.(rear-length+m)ModmC.(1+rear+m-length)ModmD.m-length如以順序方式存儲(chǔ)二叉樹，每個(gè)結(jié)點(diǎn)占用一個(gè)存儲(chǔ)單元，則深度為m的單左支二叉樹共浪費(fèi)_個(gè)存儲(chǔ)單元。m-1A2m-1-mB2m-1-m-1C2m-m-1D2m-m+1在度為m的哈夫曼樹中，其中結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為。A|n/m|-1B.|(n-1)/(m-1)|C.|n/(m-1)|-1D.|(n+1)/(m+

15、1)|下面關(guān)于圖的存儲(chǔ)的敘述中,正確的是。用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)在有向圖G的擴(kuò)撲中，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是。A.G中有弧B.G中有一條從Vi到Vj的路徑C.G中沒有弧D.G中有一條從Vj到Vi的路徑當(dāng)n足夠大時(shí),在按值有序的順序表中進(jìn)行折半查找,在查找概率相等的情況下,其查找成功的平均查找長度是。A.(n+1)/2B

16、.n/2C.log2(n+1)-1D.log2(n+1)二叉查找樹的查找效率與二叉樹的樹形有關(guān),在是其查找效率最低。A.結(jié)點(diǎn)太多B.完全二叉樹C.呈單支樹D.結(jié)點(diǎn)太復(fù)雜對一組數(shù)據(jù)()排序,數(shù)據(jù)的排列次序在排序的過程中的變化為8447251521(2)1547258421(3)1521258447(4)1521254784,則采用的排序是。A.選擇B.冒泡C.快速D.插入數(shù)據(jù)序列(8,9,10,4,5,6,20,1,2,)只能是下列排序算法中的的兩趟排序后的結(jié)果。A.選擇排序B.冒泡排序C.插入排序D.堆排序二、綜合應(yīng)用題某通信系統(tǒng)只可能有A.B.C.D.E.F.這6種字符,其出現(xiàn)的概率分別為0

17、.1,0.4,0.04,0.16,0.19,0.11,試畫出相應(yīng)的哈夫曼樹,并設(shè)計(jì)哈夫曼編碼。設(shè)有五個(gè)數(shù)據(jù)do,for,if,repeat,while,它們排在一個(gè)有序表中,其查找概率分別為p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01。而查找它們之間不存在數(shù)據(jù)的概率分別為q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01,如下圖所示。試畫出對該有序表采用順序查找是的判定樹和采用折半查找時(shí)的判定樹分別計(jì)算順序查找時(shí)的查找成功和不成功的平均查找長度，以及折半查找是的查找成功和不成功的憑據(jù)查找長度。判定是順序查找好？還是折半查找好

18、？一、單項(xiàng)選擇題某線性表中最常用的操作時(shí)在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表循環(huán)隊(duì)列存儲(chǔ)在數(shù)字Am中，則入隊(duì)時(shí)的操作為。A.rear=rear+1B.rear=(rear+1)%(rear-1)C.rear=(rear+1)%mD.rear=(rear+1)&(m+1)以下方法不能將線性表中元素逆序。將此線性表表中元素依次全部入棧，在全部出棧，再全部通過一個(gè)隊(duì)列將此線性表中元素依次全部通過一個(gè)隊(duì)列、再全部入棧、再全部出棧將此線性表中元素依次全部入棧、再全部出棧、再全部入棧、再全部

19、出棧將此線性表中元素依次全部通過一個(gè)隊(duì)列、再全部入棧、再全部出棧、再通過一個(gè)隊(duì)列TOCo1-5hz一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為。A.11B.10C.111025D.101024設(shè)森林F中有三棵樹，第一，第二，第三，棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為N1,N2和N3。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是。A.N1B.N1+M2C.N3D.N2+N3在n個(gè)頂點(diǎn)的無向連通圖的生成樹中，包含頂點(diǎn)數(shù)，頂點(diǎn)中的最小度數(shù)是。A.n,0B.n,1C.n-1,0D.無法確定下列說法不正確的是。圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次遍歷的基本算法有兩種：深度遍歷和廣度遍歷圖的深度遍歷不適用于有向

20、圖圖的深度遍歷是一個(gè)遞歸過程(不要)8.在二叉平衡序樹上成功地找到一個(gè)結(jié)點(diǎn)(設(shè)結(jié)點(diǎn)個(gè)數(shù)為n),在平均情況的最壞情況下的TOCo1-5hz時(shí)間復(fù)雜性分別是。2A.O(log2n),O(n)B.O(n),O(n)C.O(log2n),O(n2)D.O(log2n),O(log2n)9、排序方法有許多種,插入排序法從未排序的序列中依次取出元素,與已排序列(初始時(shí)為空)中的元素的作比較,將其放入已排序序列的正確位置上；選擇排序法從未排序的序列中挑選元素,并將其依次放入已排序序列(初始時(shí)為空)的一端；交換排序方法是對序列中的元素進(jìn)行一系列比較,當(dāng)被比較的兩元素逆序時(shí),進(jìn)行交換,起泡排序和快速排序是基于這

21、類方法的兩種排序方法；法是基于選擇排序的一種排序方法,是完全二叉樹結(jié)構(gòu)的一個(gè)重要應(yīng)用。A.歸并排序B.Shell排序C.堆排序D.基數(shù)排序10、設(shè)表中元素的初始狀態(tài)是按鍵值遞增的,分別用堆排序、快速排序、起泡排序和歸并排序方法對其進(jìn)行排序(按遞增順序),最省時(shí)間和最費(fèi)時(shí)間的排序方法是。A.堆排序，起泡排序B.快速排序，歸并排序C.起泡排序，快速排序D.起泡排序，歸并排序二、綜合應(yīng)用題41、使用普里姆(Prim)算法生成下圖的一個(gè)最小生成樹,并寫明每一步的狀態(tài)。42、有一種簡單的排序算法，叫做計(jì)數(shù)排序(countsorting)。這種排序算法對一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序,并將排序結(jié)果存

22、放到另一個(gè)新的表中。必須注意的是,表中所有待排序的關(guān)鍵碼互不相同,計(jì)數(shù)排序算法針對表中的每個(gè)記錄,掃描待排序的表一趟,統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小？假使針對某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c,那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c。(1)給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義。(2)使用C語言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法。(3)對于有n個(gè)記錄的表,關(guān)鍵碼比較次數(shù)是多少？(4)與簡單選擇排序相比較,這種方法是否更好？為什么？全真模擬試卷(9)一、單項(xiàng)選擇題1、設(shè)雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(prior,data,next),其中prior和next均為指針域，已知指針px指向該鏈表中的結(jié)點(diǎn)x

23、,設(shè)定結(jié)點(diǎn)x有前去和后繼，若刪除結(jié)點(diǎn)x,并釋放所占的空間，則需要執(zhí)行以下語句。px-prior-next=px-next;px-next-prior=px-prior;free(px)px-prior-next=px-prior;px-next-_prior=px_-next;free(px)px-prior-prior=px-next;px-next-next=px-prior;free(px)px-next-prior=px-next;px-prior-next=px-prior;free(px)2、一個(gè)循環(huán)隊(duì)列Q最多可存儲(chǔ)m個(gè)元素，已知其頭尾指針分別是front和rear，則判定該循環(huán)對

24、列為滿的條件是。=mB)Q.rear!=Q.forntC)Q.front=(Q.rear+1)%mD)Q.front=Q.rear%m+13、用一維數(shù)組B以列優(yōu)先存放帶狀矩陣A中的非零元素Ai,j(Kin,i-2wjwi+2),B中的第8個(gè)元素是A中的元素。第1行第3列B)第3行第1列C)第2行第1列D)第1行第2列4、有n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，從根結(jié)點(diǎn)開始對其層次順序進(jìn)行編號(hào)(設(shè)根結(jié)點(diǎn)編號(hào)為1),下列說法錯(cuò)誤的是。A)當(dāng)1wiwn/2時(shí)，結(jié)點(diǎn)i的左子女是結(jié)點(diǎn)2i,否則結(jié)點(diǎn)i沒有左子女當(dāng)1wiw(n-1)/2時(shí)，結(jié)點(diǎn)i的右子女是結(jié)點(diǎn)2i+1,否則結(jié)點(diǎn)i沒有右子女1wiwn時(shí)，結(jié)

25、點(diǎn)i的父母是結(jié)點(diǎn)i/2當(dāng)i為偶數(shù)且1iai+1,則將二者交換，以后重復(fù)上述過程，直至整個(gè)數(shù)組有序。試編寫實(shí)現(xiàn)該算法的函數(shù)。全真模擬試卷(10)一、單項(xiàng)選擇題1、對于一個(gè)頭指針為是。head的帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，可以作為判定該線性表為空表的條件A)head=NULLC)head-next=headB)head-next=NULLD)head!=NULL2、假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素，其頭尾指針分別是front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為。A)(rear-ront+m)%mB)rear-front+1C)(front-ear+m)%mD)(rear-front)%mTOCo1-5

26、hz3、設(shè)在某樹中，結(jié)點(diǎn)M、N是結(jié)點(diǎn)P上的第i、i+1個(gè)孩子，則在此樹的二叉樹表示中，結(jié)點(diǎn)M與N的關(guān)系是。A)M、N具有同一雙親B)M是N的左孩子C)N是M的左孩子D)N是M的右孩子4、以下的敘述中，正確的是。強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有弧任意圖頂點(diǎn)的入度等于出度有向完全圖一定是強(qiáng)連通有向圖有向圖的邊集的子集和頂點(diǎn)集的子集可構(gòu)成原有向圖的子圖TOCo1-5hz5、如下圖所示，已知某個(gè)深度優(yōu)先搜索序列為A*F*，則可能的序列為。CDaBDFECgABCFDEACEFBDACEFDB(ADCFEBADBFECA)0、C2和C6B)和C4C)3、C5D)、C4、C56、適用于折半查找的表

27、的存儲(chǔ)方式及元素排列要求為。A)鏈接方式存儲(chǔ)，元素?zé)o序B)鏈接方式存儲(chǔ)，元素有序C)順序方式存儲(chǔ)，元素?zé)o序D)順序方式存儲(chǔ)，元素有序(不要)7、一個(gè)m階B樹中，每個(gè)結(jié)點(diǎn)最少有個(gè)兒子結(jié)點(diǎn)。A)mB)m/2C)2D)m/2&判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用A)求關(guān)鍵路徑的方法B)求最短路徑的DIJKSTRA方法C)深度優(yōu)先遍歷算法D)廣度優(yōu)先遍歷算法9、在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是A)直接插入排序B)堆排序C)快速排序D)起泡排序10、就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是.A.堆排序快速排序歸并排

28、序C.堆排序歸并排序快速排序B.堆排序歸并排序快速排序堆排序快速排序歸并排序二、綜合應(yīng)用題41、將如下圖所示的森林轉(zhuǎn)換為一顆二叉樹，并寫出森林的兩種遍歷序列42、指定Hash函數(shù)H(k)=3xkmod11及線性探測地址法處理沖突，試在010的散列空間中對關(guān)鍵字序列(22,41,53,46,30,13,01,67)構(gòu)造Hash表，并求在等查找概率下查找成功的平均查找長度。例2、一個(gè)棧的輸入序列為1,2,3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？解：可以通過窮舉所有可能性來求解：1入1出，2入2出，3入3出，即123；1入1出，2、3入，3、2出，即132；1、2入，2出，3入3出

29、，即231；1、2入，2、1出，3入3出，即213；1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。例3、一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？解：43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；12345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。問：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；簡化了程序設(shè)計(jì)的問題。設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,則可得到出棧的元素序列是：A）a,b，c，dB）c,d,a,bC）b,c,d,aD）a,c

30、,d,bA）、D）可以，B）、C）不行。問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件的模擬（模擬事件發(fā)生的先后順序,例如CPU芯片中的指令譯碼隊(duì)列）操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；簡化程序設(shè)計(jì)。（1）假溢出順序隊(duì)列因多次入隊(duì)和出隊(duì)操作后出現(xiàn)的有存儲(chǔ)空間但不能進(jìn)行入隊(duì)操作的溢出。（2）如何解決順序隊(duì)列的假溢出問題？可采取四種方法：1）采用循環(huán)隊(duì)列；2）按最大可能的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大元素個(gè)數(shù)；3）修改出隊(duì)算法,使每次出隊(duì)列后都把隊(duì)列中剩余數(shù)據(jù)元素向隊(duì)頭方向移動(dòng)一個(gè)位置；4）修改入隊(duì)算法，增加判斷條件，當(dāng)假溢出時(shí)，把隊(duì)列中的數(shù)據(jù)元素向?qū)︻^移動(dòng),然后方完成入隊(duì)操作。順序

31、循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷問題新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear;隊(duì)滿時(shí)也會(huì)有front=rear;判決條件將出現(xiàn)二義性！解決方案有三：使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長）；判隊(duì)滿：count0&rear=front判隊(duì)空：count=0加設(shè)標(biāo)志位，出隊(duì)時(shí)置0，入隊(duì)時(shí)置1，則可識(shí)別當(dāng)前front=rear屬于何種情況判隊(duì)滿：tag=1&rear=front判隊(duì)空：tag=0&rear=front少用一個(gè)存儲(chǔ)單元判隊(duì)滿：front=（rear+1）%MaxQueueSize判隊(duì)空：rear=front問：空串和空白串有無區(qū)別？答：有區(qū)別?？沾∟ullString）是指長

32、度為零的串；而空白串（BlankString），是指包含一個(gè)或多個(gè)空白字符（空格鍵）的字符串.堆分配存儲(chǔ)特點(diǎn)：仍用一組連續(xù)的存儲(chǔ)單元來存放串，但存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得。模式匹配（定位）設(shè)有主串S和子串T（將S稱為目標(biāo)串，將T稱為模式串），在主串S中，從位置start開始查找，如若在主串S中找到一個(gè)與子串T相等的子串，則返回T的第一個(gè)字符在主串中的位置，否則返回-1。2、算法目的確定主串中所含子串第一次出現(xiàn)的位置（定位）3、算法種類BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法1、二叉樹的帶權(quán)路徑長度：從二叉樹根結(jié)點(diǎn)到所有葉子結(jié)點(diǎn)的路徑長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積（WP

33、L）WPL=?wklk2、例：設(shè)有4個(gè)字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2,4,怎樣編碼才能使它們組成的報(bào)文在網(wǎng)絡(luò)中傳得最快？法1：等長編碼（如二進(jìn)制編碼）令d=00,i=01,a=10,n=11，則：WPL1=2bitX（7+5+2+4）=36法2：不等長編碼（如Huffman編碼）令d=0;i=10,a=110,n=111，則：WPL2=1bitX72bitX5+3bitX（2+4）=353、對權(quán)值進(jìn)行合并、刪除與替換4、若集合X上的關(guān)系R是自反的、對稱的和傳遞的，則稱關(guān)系R是集合X上的等價(jià)關(guān)系。5、樹轉(zhuǎn)二叉樹舉例：方法：加線抹線旋轉(zhuǎn)6、討論2：二叉樹怎樣還原為樹？要點(diǎn)：逆操作，

34、把所有右孩子變?yōu)樾值埽?shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作的學(xué)科。計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門學(xué)科，針對非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作的學(xué)科。程序設(shè)計(jì)=好算法+好結(jié)構(gòu)數(shù)據(jù)類型：指一個(gè)類型和定義在這個(gè)類型上的操作集合。例：C語言（基本類型：整型、浮點(diǎn)型、字符型等構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉等）抽象數(shù)據(jù)元素：抽象定義的、沒有實(shí)際含義的數(shù)據(jù)元素。抽象數(shù)據(jù)類型：用戶自己定義的數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

35、?；虬凑找欢ㄟ壿嬯P(guān)系組織，并按一定存儲(chǔ)方法存儲(chǔ)的數(shù)據(jù)的集合，且需要定義一系列運(yùn)算。邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算合稱為三要素。表示為：Data_Structure=（D,R）其中，D元素有限集，R關(guān)系有限集抽象數(shù)據(jù)類型：用戶自己定義的數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。或按照一定邏輯關(guān)系組織，并按一定存儲(chǔ)方法存儲(chǔ)的數(shù)據(jù)的集合，且需要定義一系列運(yùn)算。形式定義表示為：Data_Structure=（D,R）其中，D元素有限集，R關(guān)系有限集數(shù)據(jù)結(jié)構(gòu)的三要素：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算。數(shù)據(jù)邏輯結(jié)構(gòu)（本質(zhì)）定義：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無

36、關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的物理結(jié)構(gòu)定義：物理結(jié)構(gòu)亦稱存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。抽象數(shù)據(jù)類型（AbstractDataType）：是一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）。算法概念：算法是一個(gè)有限的指令集，遵循指令流可以完成特定的功能。算法基本特征：有窮性：算法經(jīng)有限步后結(jié)束。確定性：下一步必須是明確的?？尚行裕好恳皇强梢詧?zhí)行的。評(píng)價(jià)指標(biāo)正確性可讀性健壯性高效率與低存儲(chǔ)量需求（見課本P20）1.0若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終

37、端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。t可表示為：（al,a2，,an）特點(diǎn)只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；特點(diǎn)除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是的。線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是（1）順序存儲(chǔ)結(jié)構(gòu):它是使用一片地址連續(xù)的有限內(nèi)存單元空間存儲(chǔ)數(shù)據(jù)元素的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：（任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理位置上也必然相鄰）邏輯上相鄰的元素，物理上也相鄰。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):它是把數(shù)據(jù)元素和指針定義成一個(gè)存儲(chǔ)體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法

38、。特點(diǎn)：（任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針鏈接實(shí)現(xiàn)的）邏輯上相鄰元素,物理上不一定相鄰。棧“上溢”在棧滿時(shí)還進(jìn)行入棧運(yùn)算，必定會(huì)產(chǎn)生空間的溢出,?！跋乱纭碑?dāng)棧空時(shí)仍進(jìn)行出棧運(yùn)算，必定會(huì)產(chǎn)生空間的溢出。例1：堆棧是什么？它與一般線性表有什么不同？堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。運(yùn)算規(guī)則：隨機(jī)存取運(yùn)算規(guī)則：后進(jìn)先出（LIFO）樹的度一般線性表邏輯結(jié)構(gòu)：1:1存儲(chǔ)結(jié)構(gòu)：順序表、鏈表邏輯結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧堆棧樹的深度（或高度）所有結(jié)點(diǎn)度中的最大值（Max各結(jié)點(diǎn)的度）

39、指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次）性質(zhì)3:對于任何一棵非空的二叉樹，若度為2的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n21（即n0=n2+1）證明：二叉樹中全部結(jié)點(diǎn)數(shù)n=n0+n1+n2（葉子數(shù)+1度結(jié)點(diǎn)數(shù)+2度結(jié)點(diǎn)數(shù)）又二叉樹中全部結(jié)點(diǎn)數(shù)n=B+1（總分支數(shù)+根結(jié)點(diǎn)）（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即一個(gè)分支）而總分支數(shù)B=n1+2n2（1度結(jié)點(diǎn)必有1個(gè)直接后繼，2度結(jié)點(diǎn)必有2個(gè)）三式聯(lián)立可得：nO+n1+n2=n1+2n2+1,即n0=n2+1性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k必為？log2（n+1）?-1（假定k為O時(shí)表示此二叉樹僅有根結(jié)點(diǎn)）證明：根據(jù)性質(zhì)2，深度

40、為k的二叉樹最多只有2k+1-1個(gè)結(jié)點(diǎn)，且完全二叉樹的定義是與同深度的滿二叉樹前面編號(hào)相同，即它的總結(jié)點(diǎn)數(shù)n位于k層和k-1層滿二叉樹容量之間，即2（k-1）+1-1nw2k+1-1，移項(xiàng)，有2kn+12k+1對不等式求對數(shù)，有klog2（n+1）wk+1因?yàn)閗是整數(shù)，所以k=?log2（n+1）?-1一棵完全二叉樹有1OOO個(gè)結(jié)點(diǎn)，則它必有個(gè)葉子結(jié)點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)結(jié)點(diǎn)只有非空左子樹，有個(gè)結(jié)點(diǎn)只有非空右子樹。正確答案：全部葉子數(shù)=?1000/2?=500個(gè)。度為2的結(jié)點(diǎn)=葉子總數(shù)一1=499個(gè)。因?yàn)樽詈笠粋€(gè)結(jié)點(diǎn)編號(hào)是偶數(shù)，所以必為左子樹。有1個(gè)結(jié)點(diǎn)只有非空左子樹，有0個(gè)結(jié)點(diǎn)只有非空右

41、子樹。例3：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。已知中序遍歷：BDCEAFHG已知后序遍歷：DECBHGFA線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn):可以隨機(jī)存取表中任一元素，方便快捷；缺點(diǎn)：在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素;需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)。解決問題的思路：改用另一種線性存儲(chǔ)方式：1.11(1)單鏈表:構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針。其結(jié)構(gòu)特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。1.12討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的

42、一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進(jìn)行操作時(shí)，可以對空表、非空表的情況以及對首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。1.13對比帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程和不帶帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程，可以得知：若設(shè)計(jì)的單鏈表帶頭結(jié)點(diǎn)，則無論是在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入還是在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入都不會(huì)改變頭指針的數(shù)值。若設(shè)計(jì)的單鏈表不帶頭結(jié)點(diǎn)，則在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入與在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入其算法的處理方法不同。在單鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)類似。因此，單鏈表一般構(gòu)造成帶頭結(jié)點(diǎn)的單鏈表。1.14討論1：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別和優(yōu)缺點(diǎn)？順序存儲(chǔ)時(shí)，邏輯上相

43、鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高；缺點(diǎn)是插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。完全圖：圖G任意兩個(gè)頂點(diǎn)都有一條邊相連接；若n個(gè)頂點(diǎn)的無向圖有n(n-1)/2條邊,稱為無向完全

44、圖若n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,稱為有向完全圖2.9、回路：若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。生成樹：是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n-1條邊。4、結(jié)點(diǎn)的度：結(jié)點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,結(jié)點(diǎn)的度等于該結(jié)點(diǎn)的入度與出度之和。其中結(jié)點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v);結(jié)點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)。5、連通圖：在無向圖中，若從頂點(diǎn)v1到頂點(diǎn)v2有路徑，則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通

45、分量。6、強(qiáng)連通圖：在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑，則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。7、分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點(diǎn)i的度=第i行例)中1的個(gè)數(shù)；特別：完全圖的鄰接矩陣中，對角元素為0，其余全1。8、分析1：有向圖的鄰接矩陣可能是不對稱的。分析2：頂點(diǎn)vi的出度=第i行元素之和，OD(vi)=?Aij頂點(diǎn)vi的入度=第i列元素之和。ID(vi)=?Aji頂點(diǎn)的度=第i行元素之和+第i列元素之和,即：TD(vi)=OD(vi)+ID(vi)9、鄰接矩陣：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)

46、之間是否有邊(弧)、找頂點(diǎn)的鄰接點(diǎn)等等。n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。10、鄰接表：分析1:對于n個(gè)頂點(diǎn)e條邊的無向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。11、討論：鄰接表與鄰接矩陣有什么異同之處？聯(lián)系：鄰接表中每個(gè)鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的(行列號(hào)與頂點(diǎn)編號(hào)一致)，但鄰接表不唯一(鏈接次序與頂點(diǎn)編號(hào)無關(guān))。鄰接矩陣