國家開放大學電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡課形考任務4作業(yè)及答案

國家開放大學電大《數(shù)據(jù)結(jié)構(gòu)》網(wǎng)絡課形考任務4作業(yè)及答案題目1題目2題目3題目4題目5選擇一項：題目6對于順序存儲的有序表{5,12,20,26,37,42,46,50,64},若采用折半查找，則查找元素26的比較次數(shù)是()。題目7在所有的排序方法中，關鍵字比較的次數(shù)與記錄初始排列秩序無關的是()。A.希爾排序B.直接選擇排序D.直接插入排序題目8從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的選擇一項：A.插入排序B.選擇排序C.歸并排序D.交換排序題目9依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為()。A.交換排序B.歸并排序題目14C.插入排序D.選擇排序題目10當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為()。選擇一項：A.選擇排序B.插入排序C.歸并排序D.交換排序題目11每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關鍵字均小于等于基準記錄的關鍵字，右區(qū)間中記錄的關鍵字均大于等于基準記錄的關鍵字，這種排序稱為()。選擇一項：A.插入排序B.快速排序C.堆排序D.歸并排序題目12一組記錄的關鍵字序列為(46,20,30,79,56,38,40,84,90,110),利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為()。選擇一項：A.40,20,30,38,46,56,79,84,90,1題目13在有序表{10,14,34,43,47,64,75,80,90}中，用折半查找法查找值80時，經(jīng)()次比較后查找成功。選擇一項：對序列(49,38,65,97,76,13,47,50)采用直接插入排序法進行排序，要把第七個元素47插入到已排序中，為尋找插入的合適位置需要進行()次元素間的比較。題目15排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為()排序。A.插入B.快速C.歸并題目16一組記錄的關鍵字序列為(26,59,36,18,20,25),利用堆排序的方法建立的初始小根堆為()。選擇一項：題目17一組記錄的關鍵字序列為(25,48,16,35,79,82,23,40,36,72),其中，含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為()。題目18已知10個數(shù)據(jù)元素為(54,28,16,34,73,62,95,60,26,43),對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為()。選擇一項：題目19一組記錄的關鍵字序列為(46,79,56,38,40,84),利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為()。選擇一項：題目20一組記錄的關鍵字序列為(80,57,41,39,46,47),利用堆排序(堆頂元素是最小元素)的方法建立的初始堆為(選擇一項：題目21以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指針p(查找成功p指向查到的樹結(jié)點，不成功p指向為NULL)完成程序中的空格k題目22列a[1],…a[i-1]中。j=i-1;j=m-1for(k=i-1;k>=j+1;k--)n三、綜合題(每小題8分，共40分)題目23找到元素14,需要依次與元素C÷√進行比較。(2)在等概率條件下，成功查找的平均比較次數(shù)為B=題目24(1)一組記錄的關鍵字序列為(47,80,57,39,41,46),利用堆排序的方法建立的初始堆為B÷(1)一組記錄的關鍵字序列為(47,80,57,39,41,46),利用堆排序的方法建立的初始堆為B÷C.39,47,46,80,41,57D.39,41,57,80,46,47(2)輸出堆頂元素后，調(diào)整后的堆為A÷√C.41,57,80,47,46D.41,80,46,47,57題目25(1)對關鍵字序列(56,51,71,54,46,106),利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結(jié)果C.46,51,54,56,71,106D.56,51,46,54,71,106(2)一組記錄的關鍵字序列為(60,47,80,57,39,41,46,30),利用歸并排序的方法，經(jīng)過(2,2)歸并的題目26(1)對關鍵字序列(36,69,46,28,30,74)采用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果序列為D=C.28,30,46,36,69,74D.30,28,36,46,69,74(2)用冒泡法對上述序列排序，經(jīng)兩趟冒泡的結(jié)果序列為A÷√。C.38,36,30,46,69,74D.28,36,,30,46,69,74題目27題目27(1)一組記錄的關鍵字序列為{45,40,65,43,35,95)寫出利