数据结构Ch10习题.docx

第十章内部排序 一、择题 1．用直接插入排序法对下边四个表进行（由小到大）排序，比较次数最少的是（B）。 A．（94，32，40，90，80，46，21，69） 插32，比2次插40，比2次插90，比2次 插80，比3次插46，比4次插21，比7次插69，比4次 插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次 插90，比1次插94，比1次 插40，比1次插21，比3次插46，比1次插69，比1次 插94，比1次插90，比2次插80，比3次 插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次 2．以下排序方法中，哪一个是稳固的排序方法（BD）。 A．希尔排序B．直接选择排序C．堆排序D．冒泡排序 以下3题鉴于以下代码： for(i=2;i<=n;i++) {x=A[i];j=i-1;while(j>0&&A[j]>x) {A[j+1]=A[j];j--; } A[j+1]=x } 3．这一段代码所描绘的排序方法称作（A）。 A．插入排序 B．冒泡排序 C ．选择排序 D ．迅速排序 4．这一段代码所描绘的排序方法的均匀履行时间为（ D） 2 B ．O(n) C ．O(nlog 2 D 2 A．O(logn) n) ．O(n) 5．假定这段代码开始履行时，数组 A中的元素已经按值的递加次序排好了序，则这段代码的履行时间为（ B）。 A．O(log2n) B ．O(n) C ．O(nlog2n) D ．O(n2) 6．在迅速排序过程中，每次被区分的表（或了表）分红左、右两个子表，考虑这两个子表，以下结论必定正确是（ B）。 A．左、右两个子表都已各自排好序 B ．左侧子表中的元素都不大于右侧子表中的元素 C．左侧子表的长度小于右侧子表的长度 D ．左、右两个子表中元素的均匀值相等 7．对n个记录进行堆排序，最坏状况下的履行时间为（ C）。 2 B ．O(n) C 2 D 2 A．O(logn) ．O(nlogn) ．O(n) 8、设待排序重点码序列为（ 25、18、9、33、67、82、53、95、12、70），要按重点码值递加的次序排序，采纳以第一 个重点码为分界元素的迅速排序法，第一趟排序达成后重点码表 33被放到了第几个地点（D）。 A．3B ．5C ．7 D ．9 9．若对一个已经排好了序的序列进行排序，在以下四方法中，哪一种方法比较好（ C）。 A．冒泡排序法 B ．直接选择排序法 C．直接插入排序法 D．堆排序法 10．迅速排序的时间复杂度是（A） A．O(nlog2n) B ．O(n2)C ．O(n3)D．O(log2n) 11．以下重点字序列用迅速排序法进行排序，速度最慢的是（ C） A．{23，27，7，19，11，25，32} B ．{23，11，19，32，27，35，7} C．{7，11，19，23，25，27，32} D ．{27，25，32，19，23，7，11} 12．在全部排序方法中，重点码比较的次数与记录的初始排序次序没关的是（ D）。 A．希尔排序 B ．冒泡排序 C ．直接插入排序 D．直接选择排序 13．用冒泡排序算法对以下数据 12，37，42，19，27，35，56，44，10进行从小到大排序，在将最大的数“沉”到最 后时，数的次序是（ C）。 A．12，37，42，19， 27，35，44，10， 56 B ．12，37，42，19，27，35，10，44，56 C．12，37，19，27， 35，42，44，10， 56 D ．10，12，19，27，35，37，42，44，56 14．迅速排序方法在（ C）状况下最不利于发挥其优点。 A．被排序的数据量太大 B ．被排序的数据中含有多个同样值 C．排序数据已基本有序 D ．被排序数据的数量为奇数 15．拥有12个记录的序列，采纳冒泡排序最少的比较次数是（ C）。 A．1 B ． 144 C ． 11 D ．66 16．若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24 从小到大进行排序，其要进行（ C）次比较。 A．33 B ． 45 C ． 70 D ．91 比13次 比12次 比11次 比10次 比9次 比8次 比7次 17．在任何状况下，迅速排序方法的时间性能老是最优的这类说法（B）。 A．正确B．错误 18．排序的重要目的是为了此后对已排序的数据元素进行（ C）。 A．打印输出 B ．分类 C ．查找 D ．合并 19．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（ D） A．n2 B ．nlog2nC ．log2n D ．n-1 20．用10万个无序且互不相等的正整数序列，采纳次序