2023年數(shù)據(jù)結(jié)構(gòu)本形成性考核作業(yè)

數(shù)據(jù)結(jié)構(gòu)（本）形成性考核作業(yè)（四）分校名稱：學號：姓名：成績：日期：數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)4（本部分作業(yè)覆蓋教材第8-9章的內(nèi)容）一、單項選擇題1.順序查找方法適合于存儲結(jié)構(gòu)為（）的線性表。A．散列存儲B．索引存儲C．散列存儲或索引存儲D．順序存儲或鏈接存儲2．對線性表進行二分查找時，規(guī)定線性表必須（）。A．以順序存儲方式B．以鏈接存儲方式C．以順序存儲方式，且數(shù)據(jù)元素有序D．以鏈接存儲方式，且數(shù)據(jù)元素有序3．假如規(guī)定一個線性表既能較快地查找，又能動態(tài)適應變化規(guī)定，可以采用（）查找方法。A．順序B．分塊C．折半D．散列4.對于一個線性表，若規(guī)定既能進行較快地插入和刪除，又規(guī)定存儲結(jié)構(gòu)可以反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應當（）。A．以順序存儲方式B．以鏈接存儲方式C．以索引存儲方式D．以散列存儲方式5．采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。A．nB．n/2C．(n+1)/2D．(n-1)/26．采用折半查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。A．O(n*n)B．O(nlog2n)C．O(n)D．s(log2n)7．哈希函數(shù)有一個共同的性質(zhì)，即函數(shù)值應當以（）取其值域的每個值。A．最大約率B．最小概率C．平均概率D．同等概率8．有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A．29/10B．31/10C9．已知一個有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。A．3B．410．順序查找法與二分查找法對存儲結(jié)構(gòu)的規(guī)定是（）。A．順序查找與二分查找均只是合用于順序表B．順序查找與二分查找均既合用于順序表，也合用于鏈表C．順序查找只是合用于順序表D．二分查找合用于順序表11．有數(shù)據(jù){53,30,37,12,45,24,96}，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應當選擇的序列是（）。A．45,24,53,12,37,96,30B．37,24,12,30,53,45,96C．12,24,30,37,45,53,96D．30,24,12,37,45,96,5312．對有18個元素的有序表作二分（折半）查找，則查找A[3]的比較序列的下標也許為（）。A．1、2、3B．9、5、2、3C．9、5、3D．9、4、2、313.對于順序存儲的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，則查找元素26的比較次數(shù)是（）。A.3B.3C.4D.14.關(guān)于哈希查找的說法對的的是（）。A.除留余數(shù)法是最佳的B.哈希函數(shù)的好壞要根據(jù)具體情況而定C.刪除一個元素后，不管用哪種方法解決沖突，都只需簡樸地把該元素刪除掉D.由于沖突是不可避免的，所以裝填因子越小越好15.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（）。A.冒泡排序B.希爾排序C.直接選擇排序D.直接插入排序16.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的對的的位置上，此方法稱為（）A.插入排序B.選擇排序C.互換排序D.歸并排序17.從未排序序列中挑選元素，并將其放入已排序序列的一端，此方法稱為（）。A.插入排序B.互換排序C.選擇排序D.歸并排序18.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。 A.插入排序B.互換排序C.選擇排序D.歸并排序19.當兩個元素出現(xiàn)逆序的時候就互換位置，這種排序方法稱為（）。A.插入排序B.互換排序C.選擇排序D.歸并排序20.每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準記錄的關(guān)鍵字，這種排序稱為（）。A.插入排序B.快速排序C.堆排序D.歸并排序21.在正常情況下，直接插入排序的時間復雜度為（）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)22.在正常情況下，冒泡排序的時間復雜度為（）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)23.在歸并排序中，歸并趟數(shù)的數(shù)量級為（）。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)24.在待排序元素基本有序的情況下，效率最高的排序方法是（）。A.插入排序B.快速排序C.堆排序D.歸并排序25.下面幾種排序方法中，規(guī)定內(nèi)存量最大的是（）。A.插入排序B.互換排序C.選擇排序D.歸并排序26.在下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列秩序無關(guān)的是（）。A.希爾排序B.冒泡排序C.插入排序D.選擇排序27.快速排序方法在（）情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中具有多個相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個數(shù)為奇數(shù)28.下述幾種排序方法中，平均情況下占用內(nèi)存量最大的是（）方法。A.插入排序B.選擇排序C.快速排序D.歸并排序29.若構(gòu)造一棵具有n個結(jié)點的二叉樹排序，在最壞的情況下，其深度不會超過（）。A.n/2B.nC.(n1)/2D.n130.對數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結(jié)果時的結(jié)果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（）。A.插入排序法B.選擇排序法C.冒泡排序法D.堆積排序法31.對具有n個元素的任意序列采用插入排序法進行排序，排序趟數(shù)為（）。A.n-1B.nC.n+1D.log2n32.對序列（49，38，65，97，76，13，47，50）采用直接插入排序法進行排序，要把第七個元素47插入到已排序中，為尋找插入的合適位置需要進行（）次元素間的比較。A.3B.4C.5D.33.下面四種排序方法中，（）是一種穩(wěn)定性排序方法。A.插入排序法B.選擇排序法C.快速排序法D.希爾排序法34．一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），運用快速排序，以第一個關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為（）。A．40，38，46，79，56，84B．40，38，46，84，56，79C．40，38，46，56，79，84D．38，40，46，56，79，8435．一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），運用堆排序的方法建立的初始堆為（）。A．79，46，56，38，40，84B．84，79，56，38，40，46C．84，79，56，46，40，38，D．84，56，79，40，46，3836．一組記錄的關(guān)鍵字序列為（25，48，16，35，79，82，23，40，36，72），其中，具有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為（）。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，82，7237．已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到到大排序，通過一趟冒泡排序后的序列為（）。A．16，28，34，54，73，62，60，26，43，95B．28，16，34，54，62，73，60，26，43，95C．28，16，34，54，62，60，73，26，43，95D．16，28，34，54，62，60，73，26，43，9538．用某種排序的方法對線性表（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其所采用的排序方法是（）。A.希爾排序B.歸并排序C.快速排序D.直接選擇排序二、填空題1．在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是。2．假如對查找表只進行查詢某個特定的數(shù)據(jù)元素是否在查找表中，以及查找某個特定數(shù)據(jù)元素的各種屬性兩種類型的基本操作，而不進行插入和刪除操作數(shù)據(jù)元素的查找表稱為。3．假如在查找表中進行查詢的過程中，同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素，則稱此類查找表為。4．關(guān)鍵字是記錄某個，用它可以辨認、擬定一個。5．在一個查找表中，可以唯一地擬定一個記錄的關(guān)鍵字稱為。6．平均查找長度是指為擬定記錄在查找表中的位置，需要與給定值進行比較的關(guān)鍵字個數(shù)的。7．查找是一種最簡樸的查找方法。8．折半查找又稱為。使用該查找算法的前提條件是，查找表中記錄相應的關(guān)鍵字值必須按。9．折半查找只合用于的有序表。10．分塊查找又稱為，它是一種介于和折半查找之間的查找方法。11．二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的一棵二叉樹：（1）若左子數(shù)不空，則左子樹所有結(jié)點的值。（2）若右子數(shù)不空，則右子樹所有結(jié)點的值。（3）左右子樹又分別是。12．哈希表是用來存放查找表中記錄序列的表，每一個記錄的存儲位置是以該記錄得到關(guān)鍵字為，由相應哈希函數(shù)計算所得到的。13．在有序表A[1….18]中，采用二分查找算法查找元素值等于A[17]的元素，所比較過的元素的下標依次是。14．根據(jù)排序過程中所用的存儲器不同，可以將排序方法分為和。15．冒泡排序是一種比較簡樸的方法。16．在對一組記錄（50，40，95，20，15，70，60，45，80）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需要比較次。17．在歸并排序中，在第3趟歸并中，是把長度為的有序表歸并為長度為有序表。18．在堆排序和快速排序中，若原始記錄接近正序和反序，則選用，若原始記錄無序，則最佳選用。19．對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按_________排序結(jié)果是唯一的。20．按某關(guān)鍵字對記錄序列排序，若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。21．n個元素進行冒泡法排序，通常需要進行________趟冒泡，第j趟冒泡要進行______次元素間的比較。22．當從一個小根堆中刪除一個元素時，需要把元素填補到位置，然后再按條件把它逐層調(diào)整。三、綜合題1．已知序列（70，83，100，105，10，32，7，9），請寫出對此序列采用插入排序法進行升序排序時各趟的結(jié)果。2．已知序列（10，18，4，3，6，12，1，9，15，8），請寫出對此序列采用歸并排序法進行升序排序時各趟的結(jié)果。3．已知序列（17，18，60，40，7，32，73，65，85）請給出采用冒泡排序法對該序列作升序排列時的每一趟結(jié)果。4．已知序列（503，87，512，61，908，170，897，275，653，462）請給出采用快速排序法對該序列作升序排列時的每一趟結(jié)果。5．設(shè)一組記錄的關(guān)鍵字序列為（51，85，61，43，45，49），采用堆排序算法完畢以下操作：（規(guī)定小根堆，并畫出中間過程）（1）以二叉樹描述6個元素的初始堆（2）以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個元素、4個元素的堆6．設(shè)查找表為(20,19,24,57,68,11)(1)用冒泡對該表進行排序，規(guī)定寫出每一趟的排序過程，通常對n個元素進行冒泡排序要進行多少趟冒泡？第j趟要進行多少次元素間的比較？(2)在排序后的有序表的基礎(chǔ)上，畫出對其進行折半查找所相應的鑒定樹.(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)(3)求在等概率條件下,對上述有序表成功查找的平均查找長度。7．(1)設(shè)有查找表{8,17,5,9,21,10,7,19,6},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹.（2）說明如何通過序列的二叉排序樹得到相應序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果.四、程序