(完整word版)形考作業(yè)四及答案

形考作業(yè)四及答案（本部分作業(yè)覆蓋教材第8-9章的內(nèi)容）一、單項(xiàng)選擇題1、順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為（）的線(xiàn)性表。A．散列存儲(chǔ)B．索引存儲(chǔ)D．順序存儲(chǔ)或鏈接存儲(chǔ)C．散列存儲(chǔ)或索引存儲(chǔ)2、對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須（）。A．以順序存儲(chǔ)方式B．以鏈接存儲(chǔ)方式C．以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序D．以鏈接存儲(chǔ)方式，且數(shù)據(jù)元素有序3、對(duì)于一個(gè)線(xiàn)性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該（A．以順序存儲(chǔ)方式C．以索引存儲(chǔ)方式）。B．以鏈接存儲(chǔ)方式D．以散列存儲(chǔ)方式4、采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（）。A．nB．n/2D．(n-1)/2C．(n+1)/25、哈希函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（）取其值域的每個(gè)值。A．最大概率B．最小概率C．平均概率D．同等概率6、有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A．29/107、已知一個(gè)有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。A．3B．4C．5D．6B．31/10C．26/10D．29/98、順序查找法與二分查找法對(duì)存儲(chǔ)結(jié)構(gòu)的要求是（）。A．順序查找與二分查找均只是適用于順序表B．順序查找與二分查找均既適用于順序表，也適用于鏈表C．順序查找只是適用于順序表D．二分查找適用于順序表9、有數(shù)據(jù){53,30,37,12,45,24,96}，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉排序樹(shù)，若希望高度最小，應(yīng)該選擇的序列是（）。A．45,24,53,12,37,96,30C．12,24,30,37,45,53,96B．37,24,12,30,53,45,96D．30,24,12,37,45,96,5310、對(duì)有18個(gè)元素的有序表作二分（折半）查找，則查找A[3]的比較序列的下標(biāo)可能為（）。A．1、2、3C．9、5、3B．9、5、2、3D．9、4、2、311、對(duì)于順序存儲(chǔ)的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，則查找元素26的比較次數(shù)是（）。A.2B.312、在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無(wú)關(guān)的是（）。A.冒泡排序B.希爾排序C.直接選擇排序D.直接插入排序13、從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的C.4D.5位置上，此方法稱(chēng)為（）A.插入排序14、從未排序序列中挑選元素，并將其放入已排序序列的一端，此方法稱(chēng)為（A.插入排序B.交換排序C.選擇排序D.歸并排序15、依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱(chēng)為（）。B.選擇排序C.交換排序D.歸并排序）。A.插入排序B.交換排序C.選擇排序D.歸并排序16、當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱(chēng)為（A.插入排序B.交換排序C.選擇排序D.歸并排序17、每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的）。關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱(chēng)為（）。A.插入排序18、在正常情況下，直接插入排序的時(shí)間復(fù)雜度為（A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)19、在正常情況下，冒泡排序的時(shí)間復(fù)雜度為（A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)20、在待排序元素基本有序的情況下，效率最高的排序方法是（A.插入排序B.快速排序C.堆排序D.歸并排序21、在下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列秩序無(wú)關(guān)的是（）。A.希爾排序B.冒泡排序C.插入排序D.選擇排序22、下述幾種排序方法中，平均情況下占用內(nèi)存量最大的是（）方法。A.插入排序B.選擇排序C.快速排序D.歸并排序B.快速排序C.堆排序D.歸并排序）。）。）。23、對(duì)數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進(jìn)行排序，前三趟排序結(jié)果