【正文】 ,所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。 （A）1/2（B）1（C）2（D）4（ ）條邊。 （A）n （B）n(n1)（C）n(n1）/2（D）2n（ ）條邊。 （A）6（B）12（C）16（D）20（ ）條邊才能確保是一個連通圖。 （A）5（B）6（C）7（D）8,要連通全部頂點至少需要（ ）條邊。 （A）n （B）n+1（C）n1（D）n/2,若采用鄰接矩陣表示,則該矩陣的大?。?） （A）n （B）(n1) 2（C）n1 （D）n2,若采用鄰接表表示,則表頭向量的大小為（ ），所有鄰接表中的結(jié)點總數(shù)是（ ）。 ①（A）n （B）n+1（C）n1（D）n+e②（A）e/2（B）e（C）2e （D）n+e（ ）。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 （ ）。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 ,還可以利用（ ）.（A）求關(guān)鍵路徑的方法（B）求最短路徑的Dijkstm方法 （C）寬度優(yōu)先遍歷算法（D）深度優(yōu)先遍歷算法 ，在算法執(zhí)行的某刻，已選取的頂點集合U＝{1，2，5}，邊的集合TE＝{（1，2），（2，5）}，要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從（ ）組中選取。 (A){（1，4），（3，4），（3，5），（2，5）}(B){（5，4），（5，3），（5，6）}　　　 (C){（1，2），（2，3），（3，5）}　　　 (D){（3，4），（3，5），（4，5），（1，4）} 三、填空題 。 ，若存在一條從頂點i到頂點j的弧，則在頂點的拓撲序列中，頂點i與頂點j的先后次序是_________________。 ，若表結(jié)點的個數(shù)是m，則圖中邊的條數(shù)是________________條。 4. 如果從一個頂點出發(fā)又回到該頂點，則此路徑叫做_______。 ，則該圖一定是____________。 ，則圖的廣度優(yōu)先搜索類似于二叉樹的________遍歷。 7. 一個連通圖的生成樹是該圖的________連通子圖。若這個連通圖有n個頂點, 則它的生成樹有________條邊。 四、算法設(shè)計： ： (1)往圖中插入一個頂點 (2)往圖中插入一條邊 (3)刪去圖中某頂點 (4)刪去圖中某條邊 ，試以下圖中的v0為源點執(zhí)行該算法，請回答下述問題：(1)對圖中頂點vn+1，它需入隊多少次？它被重復(fù)訪問多少次?(2)若要避免重復(fù)訪問同一個頂點的錯誤，應(yīng)如何修改此算法?void BFS(ALGraph *G,int k){//以下省略局部變量的說明，visited各分量初值為假 InitQueue(amp。Q)。//置空隊列 EnQueue(amp。Q,k)。//k入隊 while(!QueueEmpty(amp。Q)){i=DeQueue(amp。Q)。//vi出隊 visited[i]=TRUE。//置訪問標記 printf(%c,Gadjlist[i].vertex。//訪問vifor(p=Gadjlist[i].firstedge。p。p=pnext)//依次搜索vi的鄰接點vj(不妨設(shè)padjvex=j)if(!visited[padjvex])//若vj沒有訪問過 EnQueue(amp。Q,padjvex)。//vj入隊 }//endofwhile}//BFS ，分別寫出基于DFS和BFS遍歷的算法來判別頂點vi和vj(ij)之間是否有路徑。 (或生成森林)的算法，要求打印出所有的樹邊。 。 ，試以鄰接矩陣和鄰接表為存儲結(jié)構(gòu)，分別寫出算法： (1)求頂點vi到頂點vj(ij)的最短路徑 (2)求源點vi到其余各頂點的最短路徑 要求輸出路徑上的所有頂點(提示：利用BFS遍歷的思想)，寫一個基于DFS遍歷策略的算法，求圖中通過某頂點vk的簡單回路(若存在)。 (若存在)，分析算法的時間復(fù)雜度。參考答案：一、判斷題√二、選擇題 1. C 3. C 4. A 5. A B A、C A D 1D 1B 三、填空題n1 i在前，j在后 m/2 回路 強連通圖 按層 極大；n1第八章 查找 一、判斷題 ，這個順序表可以是按各鍵值排好序的，也可以是沒有按鍵值排好序的。（ ） 。（ ） （key）=key%p(p=m)這種方法是直接定址法。（ ） ，就越不容易發(fā)生沖突。( )：隨機性好、均勻性好和盡量避免沖突。( )二、填空題 ，二分查找法的平均查找長度為________，分塊查找法(以順序查找確定塊)的平均查找長度為__________，分塊查找法(以二分查找確定塊〉的平均查找長度為_________，哈希表查找法采用鏈接法處理沖突時的平均查找長度為_________。 ,平均查找長度與結(jié)點個數(shù)n無關(guān)的查法方法是_________,且是__________。 ,首先查找__________,然后再查找相應(yīng)的___________。 ,采用分塊查找法,每塊的最佳長度是____________。 (key)=key%p中,p應(yīng)取_______________。[1..20]上進行二分查找,則比較一次查找成功的結(jié)點數(shù)為_________,則比較二次查找成功的結(jié)點數(shù)為__________,則比較三次查找成功的結(jié)點數(shù)為_________,則比較四次查找成功的結(jié)點數(shù)為________,則比較五次查找成功的結(jié)點數(shù)為_________,平均查找長度為_________。 ,若進行順序查找,則時間復(fù)雜度為__________，若采用二分法查找,則時間復(fù)雜度為_________。 (12,18,20,25,29,32,40,62,83,90,95,98),當(dāng)二分查找值為29和90的元素時,分別需要________次和____________次比較才能查找成功；若采用順序查找時,分別需要___________次和_________次比較才能查找成功。 三、選擇題 （ ）的線性表。 （A）散列存儲（B）順序存儲或鏈接存儲（C）壓縮存儲（D）索引存儲 ,要求線性表必須（ ）。 （A）以順序方式存儲（B）以鏈接方式存儲 （C）以順序方式存儲,且結(jié)點按關(guān)鍵字有序排序 （D）以鏈接方式存儲,且結(jié)點按關(guān)鍵字有序排序 ,每個元素的平均查找長度為（ ） （A）n （B）n/2（C）(n+1)/2（D）(n1)/2,每個元素的平均查找長度為（ ） （A）O(n2)（B）O(log2n)（C）O(n)（D）O(log2n)（ ）。 （A）相同? （B）不相同? （C）無法比較 {1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值為82的結(jié)點時,（ ）次比較后查找成功。 （A）1（B）2（C）4（D）8=14,哈希函數(shù)H(key)=key%11。表中已有4個結(jié)點:addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空，如用二次探測再散列處理沖突,關(guān)鍵字為49的結(jié)點的地址是（ ）。 （A）8（B）3（C）5（D）9,按二分查找法對該表進行查找,在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（? ） （A）35/12（B）37/12（C）39/12（D）43/12,若線性表中共有625個元素,查找每個元素的概率相同,假設(shè)采用順序查找來確定結(jié)點所在的塊時,每塊應(yīng)分（ ）個結(jié)點最佳。 （A）10（B）25（C）6（D）625,又能適應(yīng)動態(tài)變化的要求,可以采用（ ）查找方法。 （A）分塊（B）順序（C）二分（D）散列 四、問答題 (38,25,74,63,52,48),假定采用H(k)=k%7計算散列地址進行散列存儲,試分別求出利用線性探測的開放定址法處理沖突和利用鏈接法處理沖突,在該散列表上進行查找的平均查找長度。 (87,25,310,8,27,132,68,95,187,123,70,63,47),散列函數(shù)為h(k)=k%13,采用鏈接法處理沖突。設(shè)計出這種鏈表結(jié)構(gòu),并求該表平均查找長度。 (32,75,63,48，94,25,36,18,70),散列地址空間為[0...10],若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突,試給出它們對應(yīng)的散列表,并求出在等概率情況下的平均查找長度。 。 (A）散列表 （1）查找和存取速度快,但插入和刪除速度慢。 (B)順序有序表 (2）查找、插入和刪除速度快,但不能進行順序存取。 (C)順序表 (3）插入、刪除和順序存取速度快,但查找速度慢。 (D)鏈接表 (4)查找、插入和刪除速度慢,但順序存取和隨機存取第i個元素速度快。 五、應(yīng)用題 設(shè)閉散列表容量為7，給定表（30，36，47，52，34），散列函數(shù)H（K）＝k mod 6，采用線性探測解決沖突，要求： （1）構(gòu)造此散列表(散列地址為0~6)： （2）求查找34需要進行比較的次數(shù)。 六、算法設(shè)計 哈希表的刪除 參考答案：一、判斷題 √二、填空題 (n+1)/2；((n+1)*log2(n+1))/n1；(s2+2s+n)/2s；log2(n/s+1)+s/2；1+α 哈希表查找 順序；有序的 索引；塊 15 小于表長的最大素數(shù) ①1 ②2 ③4 ④8 ⑤5 ⑥ ①O(n) ② O(log2n) 10 三、選擇題 1. B 3. C 4. D 5. B 8. B 六、算法設(shè)計 哈希表的刪除 hashtable del_hashtable (hashtable amp。hash, keytype K){t=h(k)。if ( hash[t]= = null) return (infeasible)。else if (hash[t]= =K) hash[t]=hash[t]next。else { found=0。q=hash[t]。p=hash[t]next。while ((!found)amp。amp。(p null))if ( pkey= =K){found=1。qnext=pnext。}else{q=p。 p=pnext。}if(!found) return (infeasible)。}return(hash)。} 第九章 排序 一、選擇題 ，關(guān)鍵字比較的次數(shù)與記錄得初始排列次序無關(guān)的是（ ） （A）希爾排序 （B）起泡排序 （C）插入排序 （D）選擇排序 ,希望用最快的速度挑選出其中前10個最大的元素,最好（ ）排序法。 （A）起泡排序（B）快速排序（C）堆排序（D）基數(shù)排序 ,效率最高的排序方法是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 (46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（ ）。 （A）79,46,56,38,40,80 （B）84,79,56,38,40,46（C）84,79,56,46,40,38 （D）84,56,79,40,46,38(46,79,56,38,40,84),則利用快速排序的方法,以第一個記錄為基準得到的一次劃分結(jié)果為（ ）。 （A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,79(25,48,16,35,79,82,23,40,36,72),其中含有5個長度為2的有序表,按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為（ ）。 （A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,82,從未排序序列中依次取出元素與己排序序列(初始時為空)中的元素進行比較,將其放入己排序序列的正確位置上的方法,稱為（ ） （A）希爾排序（B）起泡排序（C）插入排序（D）選擇排序 ,從未排序序列中挑選元素并將其依次放入己排序序列(初始為空)的一端的方法,稱為（ ） （A）希爾排序（B）歸并排序（C）插入排序（D）選擇排序 (25,84,21,47,15,27,68,35,20)進行排序時,元素序列的變化情況如下: (1)25,84,21,47,15,27,68,35,20 ??(2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 ??(4)15,20,21,25,27,35,47,68,845則所采用的排序方法是（ ）。 （A）選擇排序（B）希爾排序（C）歸并排序（D）快速排序 ,平均查找長度最小的是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 ,要求內(nèi)存量最大的是（ ）。 （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 。( )（A）要排序的數(shù)據(jù)量太大??? （B）要排序的數(shù)據(jù)中含有多個相同值 （C）要排序的數(shù)據(jù)已基本有序（D）要排序的數(shù)據(jù)個數(shù)為奇數(shù) ,希望盡快挑選出其中前10個最大值元素,在不改變已有算法結(jié)構(gòu)的前提下,以下幾種內(nèi)排序算法中(?? ?)最合適。 (A)選擇排序法(B)快速排序法(C)堆排序法(D)冒泡排序法。 ，不穩(wěn)定的方法是（ ） (A)直接插入排序 (B)冒泡排序 (C)歸并排序　(D)直接選擇排序