廣東開放大學數(shù)據(jù)結(jié)構(gòu)實操實訓-第八章形成性考核八（10）答案

1、試卷總分:100 得分:95對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)最多為（ ）。（難度系數(shù)：易 ）nn+1n-1n(n-1)/2答案:D2.堆排序的空間復雜度為O（ ）（難度系數(shù)：易 ）3n21答案:D3.在堆排序和快速排序中，若原始記錄無序，則最好選用 # 。答案:快速排序4.快速排序在下列（ ）情況下最易發(fā)揮其長處。被排序的數(shù)據(jù)已基本有序被排序的數(shù)據(jù)中含有多個相同排序碼被排序的數(shù)據(jù)完全無序被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案:C5.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（ ）。（難度系數(shù)：易 ）歸并排序插入排序交換排序選擇排序答案:A6.在插入排

2、序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是 # 。答案:快速排序7.在插入排序和選擇排序中，若初始數(shù)據(jù)基本反序，則選用 # 。答案:選擇排序8.堆的形狀是一棵（ ）。（難度系數(shù)：易 ）滿二叉樹二叉排序樹平衡二叉樹完全二叉樹答案:D9.高度為8的平衡二叉樹至少有 # 個結(jié)點。答案:5410.對于關(guān)鍵字序列（12，13，11，18，60，15，7，20，25，100），用篩選法建堆，必須從鍵值為 # 的關(guān)鍵字開始。答案:6011.堆是一種（ ）排序。（難度系數(shù)：易 ）交換插入選擇歸并答案:C12.下述幾種排序方法中，（ ）不是穩(wěn)定的排序方法。（難度系數(shù)

3、：易 ）快速排序希爾排序簡單選擇排序冒泡排序答案:ABC13.有數(shù)據(jù)，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（ ）。（難度系數(shù)：易 ） ?45,24,53,12,37,96,3030,24,12,37,45,96,5312,24,30,37,45,53,9637,24,12,30,53,45,96答案:D14.從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（ ）。（難度系數(shù)：易 ）選擇排序歸并排序插入排序冒泡排序答案:A15.對n個記錄的表r1n進行簡單選擇排序，所需要進行的關(guān)鍵字間的比較次數(shù)為 # 。答案:n(n1)/2

4、16.從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（ ）。（難度系數(shù)：易 ）插入排序選擇排序冒泡排序歸并排序答案:A17.在平均情況下，快速排序法最快，堆積排序法最節(jié)省空間。答案:正確18.下述幾種排序方法中，（）不是穩(wěn)定的排序方法。（難度系數(shù)：易 ）堆排序快速排序簡單選擇排序歸并排序答案:ABC19.若一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（ ）。79，46，56，38，40，8484，79，56，38，40，4684，79，56，46，40，3884，56，79，40，46，38答案:B20.