数据结构Ch10习题答案.doc

《数据结构Ch10习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章内部排序一、择题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次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比

2、1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插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．冒泡排

3、序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边

4、子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)8、设待排序关键码序列为（25、18、9、33、67、82、53、95、12、70），要按关键码值递增的顺序排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码表33被放到了第几个位置（D）。A．3B．5C．7D．99．若对一个已经排好了序的序列进行排序，在下列四方法中，哪种方法比较好（C）。A．冒泡排序法B．直接选择排序法C．直接插

5、入排序法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．用冒泡排序算法对下

6、列数据12，37，42，19，27，35，56，44，10进行从小到大排序，在将最大的数“沉”到最后时，数的顺序是（C）。A．12，37，42，19，27，35，44，10，56B．12，37，42，19，27，35，10，44，56C．12，37，19，27，35，42，44，10，56D．10，12，19，27，35，37，42，44，5614．快速排序方法在（C）情况下最不利于发挥其长处。A．被排序的数据量太大B．被排序的数据中含有多个相同值C．排序数据已基本有序D．被排序数据的数目为奇数15．具有12个记录的序

7、列，采用冒泡排序最少的比较次数是（C）。A．1B．144C．11D．6616．若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，其要进行（C）次比较。A．33B．45C．70D．9114618812162710264729412452比13次614812161810262729412447比12次6812141610182627292441比11次68121410161826272429比10次681210141618262427比9次681012141

8、6182426比8次68101214161824比7次17．在任何情况下，快速排序方法的时间性能总是最优的这种说法（B）。A．正确B．错误18．排序的重要目的是为了以后对已排序的数据元素进行（C）。A．打印输出B．分类C．查找D．合并19．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为（D）A．n2B．nlo