数据结构Ch10习题答案

.第10章内部对齐首先，选择问题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插169号，2号把90插1把94插1C.(32，40，21，46，69，94，90，80)40号，1号21号，3号46号，1号69号，1号把94插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 .气泡排序以下三个问题基于以下代码：for(I=2；I=n；I) x=AI；j=I-1；While(j0Ajx) Aj 1=Aj；j-；Aj 1=x3.此代码片段中描述的排序方法称为(a)。A.插入排序b .冒泡排序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.左侧子表的长度小于右侧子表的长度。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.3 B.5 C.7 D.99.排序有序顺序时，以下四种方法中的哪一种更好(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，7C.7，11，19，23，25，27，32 D.27，25，32，19，23，7，1112.在所有排序方法中，键码比较的次数与记录的初始排序顺序无关(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、56b.12、37、42、19、27、35、10、44、56C.12、37、19、27、35、42、44、10、56 D.10、12、19、27、35、37、42、44、5614.快速排序方法在(c)情况下发挥优势不是最好的方法。A.排序的数据量太大。b .排序的数据具有多个相同的值C.排序的数据基本上是排序的d。排序的数据数是奇数15.具有最少气泡排序的12条记录的序列为(c)。A.1 B.144 C.11 D.6616.使用气泡排序方法比较序列18，14，6，27，8，12，16，52，10，26，47，29，41，24按从小到大的顺序排序时的(c)。A.33b.45c.70d.9114 6 18 8 12 16 27 10 26 47 29 41 24 52比13次6 14 8 12 16 18 10 26 27 29 41 24 47比12次6 8 12 14 16 10 18 27 29 24 41比11次6 8 12 14 10 16 26 27 24 29比10次6 8 12 10 14 16 18 26 24 27比9次6 8 10 12 14 16 18 24 26比8次6 8 10 12 14 16 18 24比7次17.在任何情况下，快速排序方法的时间性能总是最佳的表示(b)。A.有效的b .错误18.排序的重要目的是稍后(c)执行排序的数据元素。A.打印输出b .分类c .查找d .合并19.如果初始序列已经指定了关键点值的顺序，则必须使用直接插入算法排序的次数为(d)A.n2b.nlog2sc.log2nd.n-120.由10万个无序的、不相等的正整数序列组成的顺序列存储方法，要最快地找到前10个最大的正整数，则(d)方法更好。A.快速排序b .排序shell c .选择排序d .排序堆21.以下四种排序方法中平均查找长度最小的是(c)。A.插入对齐b .选择对齐c .快速对齐d .堆叠对齐22.如果文件本地对齐，或文件长度较小，则最好的对齐方法是(a)A.排序直接插入b .冒泡排序c .简单选择排序d .无效23.使用排序(分类)方法对线性表(25、48、21、47、15、27、68、35、20)进行排序时，节点顺序会发生以下变化：(1)25 84 21 47 15 27 68 35 20；(2)20 15 21 25 47 27 68 35 84；(3)15 20 21 25 35 27 47 68 84；(4)15 20 21 25 27 35 47 68 84。使用的对齐方法是(d)。A.排序选项b .排列定位台阶c .排列堆d .快速排序24.最坏情况下，快速排序的时间复杂度为(b)。A.o (nlog2n) b.o (N2) c.o (n3) D。全部无效25.如果“排序至”列在默认情况下已排序，则键代码应使用的排序方法(b)来比较移动次数和移动次数。A.堆排序b .排序直接插入c .排序直接选择d .快速排序26.可用于解决每个节点存储整数(a)的3000个单个链接列表中的3，000个整数排序问题，无需对算法进行重大更改。A.排序方法直接插入b .简单选择排序方法c .快速排序方法d .堆排序方法27.有1000个无序的元素，以最快的速度选出其中10个最大的元素的最佳方法是(c)。A.气泡排序b .快速排序c .堆排序d .按标准排序28.在要排序的元素序列基本上已排序的前提下，最有效的排序方法是(a)。A.插入对齐b .选择对齐c .快速对齐d .堆叠对齐29.记录组的排序代码为(46、79、56、38、40、84)。使用堆排序方法，初始堆为(b)。A.79、46、56、38、40、84b.84、79、56、38、40、46C.84、79、56、46、40、38 D.84、56、79、40、46、3830.如果记录组的排序代码为(46、79、56、38、40、84)，则使用快速排序方法基于第一条记录的分解结果为(c)。A.38、40、46、56、79、84b.40、38、46、79、56、84 c.40、38、46、56、79、84 d.40、31.在排序方法从未排序的序列中，将元素与已排序序列(最初为空)中的元素进行比较，并将其放入已排序序列中的正确位置的方法称为(d)。A.跟部对齐b .气泡对齐c .插入对齐d .选择对齐32.在排序方法中，从排序顺序中选择元素并将其放在已排序序列(最初为空)的一端，称为(d)。A.跟部对齐b .气泡对齐c .插入对齐d .选择对齐33.要排序5个不同的数字，必须至少比较(a)次。A.4 B.5 C.6 D.734.如果一个序列中有多个元素，而您只想对其中第I个元素之前的某些元素进行排序，则最好使用(c)排序方法。A.快速排序b .排序堆c .排序插入d .排序shell35.如果对记录集的键代码46，79，56，38，40，84采用堆，则初始化堆后的最后一个元素是(BA)。A.84 b.46 c.56 d.3836.填写可选答案的正确答案。(1)可以通过多种方式排序(分类)。方法从排序顺序中按顺序删除元素，并将元素与排序顺序中的元素进行比较，将其放在排序列中的正确位置。方法从没有从顺序中选择元素，放在顺序的一端。交换排序方法通过对序列中的元素进行一系列比较，在比较的两个元素反向顺序时交换。您可以选择答案排序选择快速排序插入排序气泡排序(2)记录组的关键字为(46，79，56，38，40，84)，使用快速排序方法基于第一记录的分割结果为c。a、38、40、46、56、79、84b、40、38、46、79、56、84c、40、38、46、56、79、84d、40、38、46、84、56、79(3)在以下排序算法中，当按顺序处理初始数据时，c算法可能需要最长的时间。a、堆排序b、气泡排序c、快速排序d、shell排序二、填空1.L1=(55，61，68，70，75，65，78，81，93，98，84)，L2=(75，70，65，84)2.当前内部对齐的时间复杂性T(n)的范围为(o (nlogin)到O(n2)。3.内部排序可以将要排序的记录放在(计算机随机存储)上，根据排序期间的工作量进行区分，分为三类：(简单排序方法)、(高级排序方法)和(基数排序)。4.指定n个元素起泡的顺序时，最少的比较为(n-1)。5.在对堆进行排序和快速排序中，如果原始记录以正向或反向顺序访问，请选择(对堆进行排序)。如果原始记录未排序，请选择(快速排序)。6.在插入排序和选择排序中，如果初始数据基础是正顺序，则选择(插入排序)；如果数据是默认相反顺序，则选择(选择排序)。7.插入对齐、对齐定位台阶、选择对齐、冒泡对齐、快速对齐、堆对齐中的对齐不稳定(定位台阶对齐、快速对齐、堆对齐)。8.已知关键字序列51，28，86，70，90，7，30，按气泡排序，前三次排序的结果为(28，51，70，86，7，30，90)，具有9、9个元素的关键字的顺序为26、5、71、1、61、11、59、15、48。按堆顺序选择