【正文】 既希望較快的查找又便于線性表動態(tài)變化的查找方法是 ( ) A．順序查找 。若結點的存儲地址與其關鍵字之間存在某種映射關系，則稱這種存儲結構為( )A)順序存儲結構 B)鏈式存儲結構 C)索引存儲結構 D)散列存儲結構具有5層結點的平衡二叉樹至少有（ ）個結點。有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素查找概率相等的情況下，查找成功所需的平均比較次數(shù)為（ ）。一棵深度為k的平衡二叉樹，其每個非終端結點的平衡因子均為0，則該平衡二叉樹共有（ ）結點。如果采用二次探測再散列處理沖突，則關鍵字49的結點的地址是（ ）。A) 4； B) 5； C) 7； D) 10。A) O（n2）； B) O（n*log2 n）； C) O（n）； D) O（log2 n）。A) 以順序方式存儲； B) 以順序方式存儲，且結點按關鍵字值有序排列；C) 以鏈接方式存儲； D) 以鏈接方式存儲，且結點按關鍵字值有序排列。Int AlinkB(Graph G, VertexType A, VertexType B)1寫一個算法，求圖G的連通分支數(shù)。已知一個圖如下： 1）分別寫出從頂點1開始的DFS和BFS遍歷序列； 2）找出一棵生成樹； 3）求頂點4到各點的最短路徑；1A,B是圖G的兩個頂點。123465已知一個圖的頂點集V和邊集G分別為： V={0，1，2，3，4，5，6，7，8}E={0，1，0，2，1，3，1，4，2，4，2，5，3，6，3，7，4，7，4，8，5，7，6，7，7，8} 。找出所有關鍵路徑；求出活動V3的最早開始時間?！　　　∮肒ruskal算法求下圖的最小生成樹(寫出步驟)。21４、已知如下圖所示的無向圖，求：（1）鄰接矩陣；3（2）鄰接表；54對下圖所示的連通圖，請用Prim算法構造其最小生成樹。　(2) 請給出其鄰接矩陣、鄰接表及逆鄰接表。三、 問答題與算法題１、 在下圖所示的各無向圖中：　　　　　(１)哪些圖是連通圖?對非連通圖給出其連通分量。1一個含n個頂點的無向連通圖的每條邊的權重都是a(a0),則它的最小生成樹的權重等于（ ）。1G是一個非連通的無向圖，共有28條邊，則該圖至少有多少頂點。1如果含n個頂點n條邊的無向圖成一個環(huán)，則該圖有多少棵生成樹。1求n個頂點的有向圖某頂點到其他各頂點的最短路徑的Dijkstra算法時間復雜度是（ ）。1具有n個頂點和ｍ條邊的圖，采用鄰接表存儲結構。1具有e條邊的圖，求最小生成樹的Kuruscal算法時間復雜度是（ ）。具有n個頂點的圖，求最小生成樹的Prim算法時間復雜度是（ ）。圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷；圖的寬度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷判定一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用（ ）度優(yōu)先遍歷算法。對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小（ ）。具有4個頂點的無向完全圖有（ ）條邊。A．O（n） B. O（n+ e） C. O（n*n） D. O（n*n*n）二、 填空題在一個圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的（ ）倍。1設圖有n個頂點和e條邊，則采用鄰接表存儲時，求最小生成樹的 Prim 算法的時間復雜度為( )。 （1）A)12354； B)12345； C)13452； D)14352。ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是( )。從A點開始， DFS遍歷的輸出序列是（ ）。A)1354267； B)1347625； C)1534276； D)1247653。A．a(chǎn),b,e,c,d,f B．a(chǎn),c,f,e,b,d C．a(chǎn),e,b,c,f,d D．a(chǎn),e,d,f,c,b下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）： A．深度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D. 求關鍵路徑圖1給出一個無向圖。有N個頂點的有向圖用鄰接矩陣A表示時，頂點入Vi的度是（ ）。在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍。一個具有n個頂點的有向強連通圖最多有（ ）邊，最少有（ ）邊。第七章　圖一、 選擇題一個具有n個頂點的無向連通圖最多有（ ）邊，最少有（ ）邊。HFAJIGDCBKE1欲傳輸一段電文如下：CATEATDATACAECATAEA AE請你設計出這段電文中的每個字符的哈夫曼二進制編碼。1試畫出上題所示的二叉樹的先序線索二叉樹和后序線索二叉樹。1已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。1一棵有11個結點的二叉樹的靜態(tài)鏈表存儲結構如下表。Char Parent(Bitree T)已知非空二叉樹T，寫一個算法求兩度點的個數(shù)。 }}已知二叉樹T的數(shù)據(jù)域均為正數(shù)，寫一個算法求數(shù)據(jù)域的最大值。 BT rchild = = NULL ) c2 ++。 if ( BT lchild = = NULL amp。 c2 ){ if ( BT ! = NULL) { ABC ( BT lchild , c1,c2 )。 }寫出下列算法的功能．void ABC ( BiTree BT , int amp。 if(plchild) Push(S, plchild)。if(Visit(pdata)) return ERROR。Push(S,T)。 } return OK。 if(plchild) EnQueue(Q, plchild)。While(!QueueEmpty(Q)) {DeQueue(Q,p)。寫出下列算法的功能．Void LevelOrderTraverse (BiTree T, Status (*vist)(TelemType e)) {InitQueue(Q)。 ABC(BTrchild)。 ABC(BTlchild)。有一份電文中共使用 6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，則字符c的哈夫曼編碼是（ ），電文的編碼總長度為（ ）。1．一個無序序列可以通過構造一棵（ 　 　）樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。1有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是（　 ?。?，帶權路徑長度WPL為（　 ?。?。它共有（　 　）個葉子結點和（　 ?。﹤€非葉子結點，其中深度最大的那棵樹的深度是（　 ?。?，它共有（　 ?。﹤€葉子結點和（　 ?。﹤€非葉子結點。1一棵樹T中，包括一個度為1的結點，兩個度為2的結點，三個度為3的結點，四個度為4的結點和若干葉子結點，則T的葉結點數(shù)為（　 ?。?．設F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有（ ）結點，右子樹中有（ ）個結點。已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹有（　?。﹤€葉子結點。已知一棵樹T的邊集為{（I ，M），（I ，N），（E ，I），（B ，E），（B ，D），（C ，B），（G ，J），（G ，K），（A ，G），（A ，F(xiàn)），（H ，L），（A ，H），（C ，A）}。則該二叉樹的前序遍歷序列是：（　　　　?。摱鏄涞膶纳职ā　　。┛脴?。一棵哈夫曼樹有19個結點，則其葉子結點的個數(shù)是( )。含A、B、C三個結點的不同形態(tài)的樹有（　 ?。┛茫煌螒B(tài)的二叉樹有（　?。┛?。一棵二叉樹有67個結點，結點的度要么是0，要么是2。A．空或只有一個根結點 B．任一非葉結點無左子樹 C．高度等于其結點數(shù) D．任一非葉結點無右子樹1線索二叉樹是一種（ ）結構。對于前序遍歷和后序遍歷結果相同的二叉樹為（ ）的二叉樹。與森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是（ ）。 A B C D算術表達式a+b*（c+d/e）轉為后綴表達式后為（ ）A．a(chǎn)b+cde/* B．a(chǎn)bcde/+*+ C．a(chǎn)bcde/*++ D．a(chǎn)bcde*/++1設樹T的度為4，其中度為1，2，3和4的結點個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）個。在線索化二叉樹中，t所指結點沒有左子樹的充要條件是（ ）。A．CBEFDA B． FEDCBA C． CBEDFA D．不定７、已知二叉樹的中序遍歷序列是debac，后序遍歷序列是dabec，則前序遍歷序列是（ ）。A) 48； B) 49； C) 50； D) 51。一棵具有n個葉結點的哈夫曼樹，共有（ ）個結點。具有n個結點的滿二叉樹有（ ）個葉結點。高度為h的完全二叉樹至少有（ D ）個結點，至多有（ B）個結點。第六章　樹和二叉樹一、選擇題設高度為h的二叉樹只有度為0和2的結點，則此類二叉樹的結點數(shù)至少有（ B ）個，至多有（E ）個。設廣義表LS=(soldier , (teacher , student) , ( worker , farmer ) )，用取表頭函數(shù)GetHead ( ) 和取表尾函數(shù)GetTail ( )分離出原子student 。 ３、設二維數(shù)組A5╳6的每個元素占4個字節(jié)，已知Loc(a00)=1000，A共占多少個字節(jié)? A的終端結點A45的起始地位為何? 按行和按列優(yōu)先存儲時，A25的起始地址分別為何?已知一個稀疏矩陣如下圖所示： 0 4 0 0 0 0 0 0 0 0 3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 7 0 0 0 2 0 0 0 0 6 0 0 0 (1) 寫出它的三元組順序存儲表示；(2) 給出它的行邏輯鏈接的順序存儲表示；
畫出下列廣義表的圖形表示：(1) A=((a,b),(c,d))(2) B=(a,(b,(c,d)),(e))畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲結構。２、設有三對角矩陣 An╳n=，將其三條對角線上的元素逐行地存儲到向量B[0...3n3]中，使得B[k]=aij,求：　　(1)用i , j 表示k的下標變換公式。1設廣義表A((( ),(a,(b),c)))，則head(tail(head(tail(head(A))))=（ ）。1己知三對角矩陣A[1..9,1..9]