數(shù)據(jù)結構與算法第十二單元測試題附答案

數(shù)據(jù)結構與算法第十二單元測試題1、排序可以分為四大類，主要包含有()。A插入排序(正確答案)B交換排序(正確答案)C選擇排序(正確答案)D歸并排序(正確答案)2、按照排序中具有相同關鍵字的記錄在排序前后的相對位置是否發(fā)生改變，排序分為()。A穩(wěn)定排序(正確答案)B不穩(wěn)定排序(正確答案)C外部排序D內部排序3、排序是穩(wěn)定排序或不穩(wěn)排序的插入排序是()。A希爾排序(正確答案)B直接插入排序(正確答案)C堆排序D快速排序4、屬于插入排序的有()。A希爾排序(正確答案)B直接插入排序(正確答案)C冒泡排序D簡單選擇排序5、直接插入排序是()。A內排序(正確答案)B穩(wěn)定排序(正確答案)C時間復雜度為O(nn)的排序(正確答案)D插入排序(正確答案)6、序列(12,9,14,7,8)經(jīng)過一趟直接排序，結果不可能是()。A12,9,14,7,8(正確答案)B9,12,14,7,8C7,8,9,12,14(正確答案)D9,7,8,12,14(正確答案)7、直接插入排序最好、最壞兩種情況的時間復雜度分別是()。AO(nlog2n)BO(nn)(正確答案)CO(log2n)DO(n)(正確答案)8、按照待排記錄是否全部在內存中，排序可分為()。A內排序(正確答案)B外排序(正確答案)C穩(wěn)定排序D不穩(wěn)定排序9、希爾排序就穩(wěn)定性和內外排序而言，屬于()。A穩(wěn)定排序B不穩(wěn)定排序(正確答案)C內排序(正確答案)D外排序10、希爾排序的時間復雜度不可能是()。AO(nn)(正確答案)BO(nlog2n)(正確答案)CO(n)(正確答案)DO(n3/2)11、下列排序中屬于插入排序的有()。A希爾排序(正確答案)B直接插入排序(正確答案)C快速排序D簡單選擇排序12、12個待排記錄，使用直接插入排序需要()趟能完成全部排序。A11(正確答案)B12C10D都不對13、所有的記錄不可能存放在內存中，排序過程中必須在內、外存之間進行數(shù)據(jù)交換，這樣的排序稱為()。A外部排序(正確答案)B內部排序C插入排序D交換排序14、數(shù)組中有25個元素，若使用直接插入排序對其進行排序，則需要()趟才能完成排序。A24(正確答案)B25C26D2315、N個記錄采用直接插入排序的最好的情況是記錄完全有序，只要比較()次，不需要插入就可以排序完成。ANBN-1(正確答案)CN-2DN(N-1)/216、哪種排序可能發(fā)生：在最后一趟排序開始之前，所有記錄均不在其最終位置上()。A直接插入排序(正確答案)B簡單選擇排序C冒泡排序D快速排序17、所有的記錄都能存放在內存中進行排序，稱為()。A外部排序B內部排序(正確答案)C插入排序D交換排序18、直接插入排序的穩(wěn)定性和時間復雜度分別是()。A穩(wěn)定排序且時間復雜度是O(nn)(正確答案)B不穩(wěn)定排序且時間復雜度是O(n)C穩(wěn)定排序且時間復雜度是O(log2n)D不穩(wěn)定排序且時間復雜度是O(log2n)19、直接插入排序的時間復雜度和順序查找的時間復雜度分別是()。AO(n)和O(log2n)BO(nn)和O(n)(正確答案)CO(1)和)O(n)DO(n)和O(1)20、在排序中，對于關鍵字相等的記錄，排序前后相對位置不變。這時稱排序為()。A"穩(wěn)定排序"(正確答案)B不穩(wěn)定排序C不確定是穩(wěn)定排序還是不穩(wěn)定排序D基數(shù)排序21、數(shù)組中有30個元素，若使用直接插入排序對其進行排序，則需要()趟才能完成排序。A29(正確答案)B30C28D2722、N個記錄采用直接插入排序(按從小到大排序)的最好的情況是記錄完全有序，只要比較N-1次，不需要插入就可以排序完成，這種情況是()。A記錄初始狀態(tài)已經(jīng)按照從小到大有序排列了。(正確答案)B記錄初始狀態(tài)已經(jīng)按照從大到小有序排列了。C記錄初始狀態(tài)是亂序D記錄初始狀態(tài)前一半是有序，后一半是亂序23、排序前序列為：3415886672問經(jīng)過一趟直接插入排序(按從小到大排序)后的序列是()。A1534886672(正確答案)B3415886672C1534667288D153466887224、直接插入排序的時間復雜度和穩(wěn)定性分別是()。A時間復雜度是O(nn)且穩(wěn)定排序(正確答案)B間復雜度是O(n)且是不穩(wěn)定排序C時間復雜度是O(log2n)且是穩(wěn)定排序D間復雜度是O(log2n)且是不穩(wěn)定排序25、直接插入排序的時間復雜度和折半查找的時間復雜度分別是()。AO(nn)和O(log2n)(正確答案)BO(nn)和O(n)CO(1)和)O(n)DO(n)和O(1)26、19個記錄進行排序，使用直接插入排序需要()趟能完成全部排序。A18(正確答案)B19C17D都不對27、就排序記錄所在位置而言，希爾排序排序屬于()。A外排序B內排序(正確答案)C穩(wěn)定排序D交換排序28、希爾排序是一種插入排序，希爾排序又稱為()。A縮小增量排序(正確答案)B多路插入排序C直接插入排序D冒泡排序29、下列選項關于內外排序說法正確的是()。A所有的記錄都能存放在內存中進行排序，稱為外部排序B所有的記錄都能存放在內存中進行排序，稱為內部排序(正確答案)C所有的記錄都能存放在內存中進行排序，稱為插入排序D所有的記錄都能存放在內存中進行排序，稱為交換排序30、下列選項關于直接插入排序思想說法正確的是()。A將第一個記錄看成有序的，將之后的記錄逐一插入，是有序序列擴大，直到全部有序是冒泡排序的思想B將第一個記錄看成有序的，將之后的記錄逐一插入，是有序序列擴大，直到全部有序是直接插入排序的思想(正確答案)C將第一個記錄看成有序的，將之后的記錄逐一插入，是有序序列擴大，直到全部有序是簡單選擇排序的思想31、下列選項關于直接插入排序的分類說法正確的是()。A直接插入排序屬于四大排序類型中的插入排序(正確答案)B直接插入排序屬于四大排序類型中的選擇排序C直接插入排序屬于四大排序類型中的交換排序D直接插入排序屬于四大排序類型中的歸并排序32、下列選項關于直接插入排序比較次數(shù)說法正確的是()。AN個記錄采用直接插入排序的最好的情況是記錄倒序只要比較N-1次，不需要插入就可以排序完成BN個記錄采用直接插入排序的最好的情況是記錄有序只要比較N-1次，不需要插入就可以排序完成(正確答案)CN個記錄采用直接插入排序的最好的情況是記錄亂序只要比較N-1次，不需要插入就可以排序完成DN個記錄采用直接插入排序的最好的情況是記錄順序只要比較N-1次，不需要插入就可以排序完成33、關于直接插入排序的排序趟數(shù)下面說法正確的是()。A數(shù)組中有25個元素，若使用直接插入排序對其進行排序，則需要24趟才能完成排序(正確答案)B數(shù)組中有25個元素，若使用直接插入排序對其進行排序，則需要25趟才能完成排序C數(shù)組中有25個元素，若使用直接插入排序對其進行排序，則需要26趟才能完成排序D數(shù)組中有25個元素，若使用直接插入排序對其進行排序，則需要23趟才能完成排序34、N個記錄采用直接插入排序說法正確的是()。AN個待排記錄，使用直接插入排序需要N-1趟能完成全部排序(正確答案)BN個待排記錄，使用直接插入排序需要N趟能完成全部排序CN個待排記錄，使用直接插入排序需要N-2趟能完成全部排序35、直接插入排序的時間復雜度是()。AO(nlog2n)BO(nn)(正確答案)CO(log2n)DO(n)36、直接插入排序的穩(wěn)定性如何()。A是穩(wěn)定排序(正確答案)B是不穩(wěn)定排序C有時是穩(wěn)定的，有時不穩(wěn)定D以上說法都不對37、下列選項中關于穩(wěn)定排序說法正確的是()。A穩(wěn)定排序是指對于關鍵字相等的記錄，排序前后相對位置不變(正確答案)B穩(wěn)定排序是指對于關鍵字相等的記錄，排序前后相對位置可以變化C穩(wěn)定排序是指排序是指將記錄變成無序的38、排序前序列為：11101389問經(jīng)過一趟直接插入排序(按從小到大排序)后的序列是()。A10111389(正確答案)B10118913C11108913D8910111339、希爾排序就分類而言屬于()。A歸并排序B選擇排序C交換排序D插入排序(正確答案)40、就性能而言，希爾排序的時間復雜度是()。AO(nn)BO(nlog2n)CO(n)DO(n3/2)(正確答案)41、希爾排序又稱為()。A縮小增量排序(正確答案)B二分插入排序C多路歸并排序D錦標賽排序42、希爾排序是根據(jù)增量，將所有記錄分為若干個組，每組采用()排序進行排序。A直接插入排序(正確答案)B冒泡排序C快速排序D簡單選擇排序43、關于希爾排序的描述正確的是()。A希爾排序是穩(wěn)定排序B希爾排序是交換排序的一種C希爾排序是一種插入排序(正確答案)D希爾排序的時間復雜度是O(nn)44、希爾排序是一種不穩(wěn)定排序，那么原因是()。A存在不相鄰記錄的交換(正確答案)B存在相鄰記錄的交換C存在相同關鍵字的記錄D存在著記錄順序的一次調換45、希爾排序與直接插入排序相同之處是()。A它們都是穩(wěn)定排序B它們的時間復雜度是一樣的C它們都是插入排序大類里的(正確答案)D它們都是縮小增量排序46、直接插入排序的穩(wěn)定性和希爾排序的穩(wěn)定性是()。A一樣的B不一樣(正確答案)C可能一樣也可能不一樣D不確定47、希爾排序就穩(wěn)定性而言屬于()。A穩(wěn)定排序B不穩(wěn)定排序(正確答案)C可能是穩(wěn)定的也可能是不穩(wěn)定，根據(jù)情況不同而不同D其它選項都不對48、希爾排序屬于不穩(wěn)定排序，而直接插入排序是穩(wěn)定排序，他們都是插入排序。對(正確答案)錯49、排序只有外部排序沒有內部排序。對錯(正確答案)50、直接插入排序是一種不穩(wěn)定排序。對錯(正確答案)51、直接插入排序是不穩(wěn)定排序而且時間復雜度是O(nn)。對錯(正確答案)52、直接插入排序必須需要使用switch語句才能實現(xiàn)。對錯(正確答案)53、在直接插入排序中可以使用循環(huán)嵌套來完成。對(正確答案)錯54、就排序穩(wěn)定性而言，希爾排序是不穩(wěn)定排序。對(正確答案)錯55、希爾排序的時間復雜度是O(nn)。對錯(正確答案)56、希爾排序又叫縮小增量排序，屬于交換排序的一種。對錯(正確答案)57、希爾排序屬于不穩(wěn)定排序，而直接插入排序是穩(wěn)定排序。對(正確答案)錯58、直接插入排序必須需要使用continue才能實現(xiàn)。對錯(正確答案)59、在直接插入排序中可以使用for循環(huán)來完成。對(正確答案)錯60、直接插入排序是不穩(wěn)定排序。對