數(shù)據(jù)結(jié)構(gòu)--圖練習(xí)含答案.doc

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