數(shù)據(jù)結構--圖練習含答案.doc

數(shù)據(jù)結構-圖練習含答案一單項選擇題在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_c_倍。A）1/2 B) 1 C) 2 D) 4在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_b_倍。A) 1/2 B) 1 C) 2 D) 4一個有n個頂點的無向圖最多有_c_條邊。A) n B) n(n-1) C) n(n-1)/2 D) 2n具有4個頂點的無向完全圖有_a_條邊。A) 6 B) 12 C) 16 D) 20具有6個頂點的無向圖至少應有_a_條邊才能確保是一個連通圖。A) 5 B) 6 C) 7 D) 8在一個具有n個頂點的無向圖中，要連通全部頂點至少需要_c_條邊。A) n B) n+1 C) n-1 D) n/2對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_d_。A) n B) (n-1)2 C) n-1 D) n2對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表示，則表頭向量的大小為_a_，所有鄰接表中的結點總數(shù)是_c_。 A) n B) n+1 C) n-1 D) n+e A) e/2 B) e C) 2e D) n+e已知一個圖如下所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為_d_；按寬度搜索法進行遍歷，則可能得到的一種頂點序列為_b_ _。 A) a,b,c,d,e,f B) a,c,f,e,b,dC) a,e,b,c,f,d D) a,e,d,f,c,b A) a,b,c,d,e,f B) a,b,c,e,f,dC) a,e,b,c,f,d D) a,c,f,d,e,b已知一有向圖的鄰接表存儲結構如圖所示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是_c_。A) v1,v2,v3,v5,v4 B) v1,v2,v3,v4,v5 C) v1,v3,v4,v5,v2 D) v1,v4,v3,v5,v2根據(jù)有向圖的寬度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是_b_。A) v1,v2,v3,v4,v5 B) v1,v3,v2,v4,v5 C) v1,v2,v3,v5,v4 D) v1,v4,v3,v5,v2采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_a_。A) 先序遍歷 B）中序遍歷 C） 后序遍歷 D） 按層遍歷采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的d_。A) 先序遍歷 B）中序遍歷 C） 后序遍歷 D） 按層遍歷判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用_d_。A） 求關鍵路徑的方法 B） 求最短路徑的Dijkstra方法C） 寬度優(yōu)先遍歷算法 D） 深度優(yōu)先遍歷算法二填空題（將正確的答案填在相應的空中）N個頂點的連通圖至少_N-1_條邊。在無權圖G的鄰接矩陣A中，若（vi,vj）或屬于圖G的邊集合，則對應元素Aij等于_1_，否則等于_0_。在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji等于_1_。已知圖G的鄰接表如圖1所示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_，其從頂點v1出發(fā)的寬度優(yōu)先搜索序列為_v1v2v5v4v3v6_。已知一個圖的鄰接矩陣表示，計算第I個結點的入度的方法是_。已知一個圖的鄰接矩陣表示，刪除所有從第I個結點出發(fā)的邊的方法是_。查找一單項選擇題順序查找法適合于存儲結構為_b_的線性表。A） 散列存儲 B） 順序存儲或鏈接存儲C） 壓縮存儲 D） 索引存儲對線性表進行二分查找時，要求線性表必須_b_。A） 以順序方式存儲 B） 以順序方式存儲，且結點關鍵字有序排序C） 以鏈接方式存儲 D） 以鏈接方式存儲，且結點關鍵字有序排序采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為_c_。A） n B) n/2 C) (n+1)/2 D) (n-1)/2采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為_c_。A) O(n2) B) O(nlog2n) C) O(n) D) O(log2n)二分查找和二叉排序樹的時間性能_b_。A) 相同 B） 不相同有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當二分查找值82為的結點時，_c_次比較后查找成功。A） 1 B） 2 C） 4 D） 8設哈希表長m=14，哈希函數(shù)H(key)=key % 11。表中已有4個結點：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址為空。如用二次探測再散列處理沖突，關鍵字為49的結點的地址是_d_。A） 8 B） 3 C） 5 D） 98有一個長度為12的有序表，按二分查找法對該表進行查找，在表內各元素等概率情況下查找成功所需的平均比較次數(shù)為_b_。A） 35/12 B） 37/12 C） 39/12 D） 43/12分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊時，每塊應分_b_個結點最佳。A） 10 B） 25 C） 6 D） 625如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，可以采用_d_查找方法。A） 分塊 B） 順序 C） 二分 D） 散列二填空題順序查找法的平均查找長度為_；二分查找法的平均查找長度為_；分塊查找法（以順序查找確定塊）的平均查找長度為_；分塊查找法（以二分查找確定塊）的平均查找長度為_；哈希表查找法采用鏈接法處理沖突時的平均查找長度為_。在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是_。二分查找的存儲結構僅限于_，且是_。在分塊查找方法中，首先查找_，然后再查找相應的_。長度為255的表，采用分塊查找法，每塊的最佳長度是_。在散列函數(shù)H(key)=key % p中，p應取_。假設在有序線性表A1.20上進行二分查找，則比較一次查找成功的結點數(shù)為_10_，則比較二次查找成功的結點數(shù)為_5,15_，則比較三次查找成功的結點數(shù)為_2,7_12,18_，則比較四次查找成功的結點數(shù)為_1,3_,6,8,11,13,16,19_，則比較五次查找成功的結點數(shù)為_4,9,14,17,20_，平均查找長度為_3.7_。對于長度為n的線性表，若進行順序查找，則時間復雜度為_o(n)_；若采用二分法查找，則時間復雜度為_o(logn)_。在散列存儲中，裝填因子的值越小，則_發(fā)生沖突的機會越小_。內排序一選擇填空題在所有排序方法中，關鍵字比較的次數(shù)與記錄的初始排列次序無關的是_d_。A） 希爾排序 B） 起泡排序 C） 插入排序 D） 選擇排序設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用_d_排序法。A） 起泡排序 B） 快速排序 C） 堆排序 D） 基數(shù)排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是_a_。A） 插入排序 B） 選擇排序 C） 快速排序 D） 歸并排序一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為_b_。A） 79，46，56，38，40，80 B） 84，79，56，38，40，46C） 84，79，56，40，38 D） 84，56，79，40，46，38一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為_c_。A） 38，40，46，56，79，84 B） 40，38，46，79，56，84C） 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的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為_a_。A）16，25，35，48，23，40，79，82，36，72B）16，25，35，48，79，82，23，36，40，72C）16，25，48，35，79，82，23，36，40，72D）16，25，35，48，79，23，36，40，72，82排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為_c_。A） 希爾排序 B） 起泡排序 C） 插入排序 D） 選擇排序排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為_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，84則所采用的排序方法是_c_。A） 希爾排序 B） 歸并排序 C） 快速排序 D） 選擇排序下述幾種排序方法中，平均時間復雜度最小的是_a_。A） 快速排序 B） 歸并排序 C） 插入排序 D） 選擇排序下述幾種排序方法中，要求內存量最大的是_b_。A） 快速排序 B） 歸并排序 C） 插入排序 D） 選擇排序快速排序方法在_c_情況下最不利于發(fā)揮其長處。A） 要排序的數(shù)據(jù)量太大 B）要排序的數(shù)據(jù)中含有多個相同的值C） 要排序的數(shù)據(jù)已基本有序 D） 要排序的數(shù)據(jù)個數(shù)為奇數(shù)二填空題在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較_3_次。在堆排序，快速排序和歸并排序中，若只從存儲窨考慮，則應首先選取_堆排序_方法，其次選取_快速排序_方法，最后選取歸并排序_方法；若只從排序結果的穩(wěn)定性考慮，則應選取_歸并排序_方法；若只從平均情況下排序最快考慮，則應選取_快速排序_方法；若只從最壞情況下排序最快并且要節(jié)省內存考慮，則應選取_堆排序_方法。在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的