练习题及参考答案

练习题及参考答案 选择题

1．下述几种排序方法中，平均查找长度最小的是（ ）。

A．插入排序 B．选择排序 C．快速排序 D．归并排序 2．设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数是（ ）。 A．6 B．7 C．8 D．20

3．将5个不同的数据进行排序，至少需要比较（ ）次，至多需要比较（ ）次。A．4 B．5 C．6 D．7矚慫润厲钐瘗睞枥庑赖賃軔朧。矚慫润厲钐瘗睞枥庑赖賃軔朧碍鳝绢。 E．8 F．9 G．xx H．xx聞創沟燴鐺險爱氇谴净祸測樅。聞創沟燴鐺險爱氇谴净祸測樅锯鳗鲮。 4．下列排序算法中不稳定的有（ ）。

A．直接选择排序 B．直接插入排序 C．冒泡排序 D．二叉排序 E．Shell排序 F．快速排序 G．归并排序 H．堆排序 I．基数排序

5．内部排序多个关键字的文件，最坏情况下最块的排序方法是（ ），相应的时间复杂度为（ ），该算法是（ ）排序方法。残骛楼諍锩瀨濟溆塹籟婭骒東。残骛楼諍锩瀨濟溆塹籟婭骒東戇鳖納。 A．快速排序 B．插入排序 C．归并排序 D．简单选择排序

E．O(nlog2 n) F．O(n2) G．O(n2log2 n) H．O(n)酽锕极額閉镇桧猪訣锥顧荭钯。酽锕极額閉镇桧猪訣锥顧荭钯詢鳕驄。 I．稳定 J．不稳定 6．在文件“局部有序”（待排序元素序列基本有序）的情况下，最佳内部排序算法是（ ）。 A．直接插入排序 B．冒泡排序 C．直接选择排序 D．基数排序

7．对初始状态为递增的表按递增顺序排序，最省时间的是（ ）算法，最费时间的是（ ）算法。

A．堆排序 B．快速排序 C．插入排序 D．归并排序 8．下述几种排序方法中，要求内存量最大的是（ ）。

A．插入排序 B．选择排序 C．快速排序 D．归并排序

9．在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A．希尔排序 B．冒泡排序 C．插入排序 D．选择排序 xx．下列排序中，排序速度与数据的初始排列状态没有关系的有（ ）。

A．直接选择排序 B．基数排序 C．堆排序 D．直接插入排序 xx．排序趟数与数据的原始状态无关的排序方法是（ ）排序法。 A．希尔 B．选择 C．冒泡 D．快速

xx．若需在O(nlog2 n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。彈贸摄尔霁毙攬砖卤庑诒尔肤。彈贸摄尔霁毙攬砖卤庑诒尔肤亿鳔简。 A．快速排序 B．堆排序 C．归并排序 D．直接插入排序 xx．排序方法中，从未排序序列中依次取出元素与已排序序列（ ）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。謀荞抟箧飆鐸怼类蒋薔點鉍杂。

謀荞抟箧飆鐸怼类蒋薔點鉍杂篓鳐驱。 1 / 7

A．希尔排序 B．冒泡排序 C．插入排序 D．选择排序

xx．每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间元素的关键字均大于基准元素的关键字，则此排序方法叫做（ ）。厦礴恳蹒骈時盡继價骚卺癩龔。厦礴恳蹒骈時盡继價骚卺癩龔长鳏檷。 A．堆排序 B．快速排序 C．冒泡排序 D．Shell排序

xx．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。茕桢广鳓鯡选块网羈泪镀齐鈞。茕桢广鳓鯡选块网羈泪镀齐鈞摟鳎饗。 A．希尔排序 B．归并排序 C．插入排序 D．选择排序

xx．用某种排序方法对线性表（25，84，21，47，xx，27，68，35，20）进行排序时，元素序列的变化情况如下：鹅娅尽損鹌惨歷茏鴛賴縈诘聾。鹅娅尽損鹌惨歷茏鴛賴縈诘聾諦鳍皑。 （1）（25，84，21，47，xx，27，68，35，20） （2）（20，xx，21，25，47，27，68，35，84） （3）（xx，20，21，25，35，27，47，68，84） （4）（xx，20，21，25，27，35，47，68，84） 则所采用的排序方法是（ ）。

A．选择排序 B．希尔排序 C．归并排序 D．快速排序 xx．从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（ ）；从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ ）；依次将每两个相邻的有序表合并成一个有序表的排序方法叫做（ ）；当两个元素比较出现反序时（即逆序）就相互交换位置的排序方法叫做（ ）。籟丛妈羥为贍偾蛏练淨槠挞曉。籟丛妈羥为贍偾蛏练淨槠挞曉养鳌顿。 A．归并排序 B．选择排序 C．交换排序 D．插入排序 xx．一组记录的关键字为（25，50，xx，35，80，85，20，40，36，70），其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为（ ）。預頌圣鉉儐歲龈讶骅籴買闥龅。預頌圣鉉儐歲龈讶骅籴買闥龅绌鳆現。 A．（xx，25，35，50，20，40，80，85，36，70） B．（xx，25，35，50，80，20，85，40，70，36） C．（xx，25，50，35，80，85，20，36，40，70） D．（xx，25，35，50，80，20，36，40，70，85）

xx．n个记录的直接插入排序所需记录的关键码的最大比较次数为（ ）。

A．nlog2 n B．n2/2 C．(n+2)(n-1)/2 D．n-1渗釤呛俨匀谔鱉调硯錦鋇絨钞。渗釤呛俨匀谔鱉调硯錦鋇絨钞陉鳅陸。 20．n个记录的直接插入排序所需记录最小移动次数为（ ）。

A．2(n-1) B．n2/2 C．(n+3)(n-2)/2 D．2n铙誅卧泻噦圣骋贶頂廡缝勵罴。铙誅卧泻噦圣骋贶頂廡缝勵罴楓鳄烛。 21．对以下关键字序列用快速排序法进行排序，（ ）的情况排序最慢。 A．｛xx，23，3，xx，7，21，28｝ B．｛23，21，28，xx，xx，3，7｝ C．｛xx，7，xx，28，23，21，3｝ D．｛3，7，xx，xx，21，23，28｝

22．快速排序在（ ）情况下最不利于发挥其长处，在（ ）情况下最易发挥其长处。

A．被排序的数据量很大 B．被排序的数据已基本有序 C．被排序的数据完全无序

D．被排序的数据中最大的值与最小值相差不大

2 / 7

E．要排序的数据中含有多个相同值

23．在平均情况下，快速排序时间复杂度为（ ），空间复杂度为（ ）；在最坏情况下（如初始记录已有序），快速排序的时间复杂度为（ ），空间复杂度为（ ）。擁締凤袜备訊顎轮烂蔷報赢无。擁締凤袜备訊顎轮烂蔷報赢无貽鳃闳。 A．O(n) B．O(log2 n) C．O(nlog2 n) D．O(n2) 24．一组记录的关键字为（45，80，55，40，42，85），则利用快速排序的方法，以第一个记录为基准得到一次划分结果是（ ）。贓熱俣阃歲匱阊邺镓騷鯛汉鼉。贓熱俣阃歲匱阊邺镓騷鯛汉鼉匮鲻潰。 A．（40，42，45，55，80，85） B．（42，40，45，80，55，85） C．（42，40，45，55，80，85） D．（42，40，45，85，55，80）

25．对n个记录的线性表进行快速排序，为减少算法的递归深度，以下途述正确的是（ ）。

A．每次分区后，先处埋较短的部分 B．每次分区后，先处埋较长的部分 C．与算法每次分区后的处埋顺序无关 D．以上都不对

26．直接插入排序和冒泡排序的平均时间复杂度为（ ），若初始数据有序（即正序），则时间复杂度为（ ）。坛摶乡囂忏蒌鍥铃氈淚跻馱釣。坛摶乡囂忏蒌鍥铃氈淚跻馱釣缋鲸鎦。 A．O(n) B．O(log2 n) C．O(nlog2 n) D．O(n2)

27．在直接选择排序中，记录比较次数为（ ）数量级，记录的移动次数为（ ）数量级。

A．O(n) B．O(log2 n) C．O(n2) D．O(nlog2 n)蜡變黲癟報伥铉锚鈰赘籜葦繯。蜡變黲癟報伥铉锚鈰赘籜葦繯颓鲷洁。 28．在堆排序过程中，由n个待排序的记录建成初始需要（ ）次筛选；由初始堆到堆排序结束需要进行（ ）次筛选；在每次筛运算过程中，记录的比较和移动次数的数量级为（ ），堆排序算法的时间复杂度为（ ）。買鲷鴯譖昙膚遙闫撷凄届嬌擻。買鲷鴯譖昙膚遙闫撷凄届嬌擻歿鲶锖。 A．n B．n/2 C．log2 n D．n-1

E．O(log2 n) F．O(n) G．O(nlog2 n) H．O(n2)綾镝鯛駕櫬鹕踪韦辚糴飙钪麦。綾镝鯛駕櫬鹕踪韦辚糴飙钪麦蹣鲵殘。 29．一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立的初始堆为（ ）。驅踬髏彦浃绥譎饴憂锦諑琼针。驅踬髏彦浃绥譎饴憂锦諑琼针咙鲲鏵。 A．（80，45，55，40，42，85） B．（85，80，55，40，42，45） C．（85，80，55，45，42，40） D．（85，55，80，42，45，40） 30．下列序列中是堆的有（ ）。 A．（xx，70，33，65，24，56，48，92，86，33） B．（xx0，86，48，73，35，39，42，57，66，21） C．（1xx??，56，97，33，66，23，42，52，30，xx） D．（5，56，20，23，40，38，29，61，35，76）

31．设有xx00个无序的元素，希望用最快的速度挑选出前20个最大的元素，最好选用（ ）算法。

A．冒泡排序 B．归并排序 C．堆排序 D．基数排序 32．下列排序算法中，（ ）算法会出现下面情况：在最后一趟结束之前，所有元素不在其最终的位置上。

3 / 7

A．堆排序 B．冒泡排序 C．快速排序 D．插入排序 33．在含有n个元素的小根堆（堆顶元素最小）中，关键字最大的记录可能存储在（ ）位置上。 A．?n/2? B．?n/2??1 C．1

D．?n/2??3

34．在归并排序中，归并趟数的数量级表示为（ ），每趟需要进行记录的比较和移动次数的数量级表示为（ ），归并排序算法的时间复杂度为（ ）。猫虿驢绘燈鮒诛髅貺庑献鵬缩。猫虿驢绘燈鮒诛髅貺庑献鵬缩职鲱样。 A．O(n) B．O(log2 n) C．O(nlog2 n) D．O(n2) 35．在归并排序过程中，需归并的趟数为（ ）。 A．n B．n C．?log2n? D．?log2n?

36．已知数据表A中每个元素距其最终的位置不远，则采用（ ）排序算法最省时间。 A．堆排序 B．插入排序 C．直接选择排序 D．快速排序

37．下列排序算法中，某一趟（轮）结束后未必能选出一个元素放在其最终位置上的是（ ）。

A．堆排序 B．冒泡排序 C．直接插入排序 D．快速排序 38．快速排序算法在最好情况下的时间复杂度为（ ）。

A．O(n) B．O(n2) C．O(nlog2 n) D．O(log2 n)锹籁饗迳琐筆襖鸥娅薔嗚訝摈。锹籁饗迳琐筆襖鸥娅薔嗚訝摈馍鲰钵。 39．快速排序方法在（ ）情况下最不利于发挥其长处。

A．要排序的数据量太大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数 填空题

1．在对一组记录（50，40，95，20，xx，70，60，45，80）进行希尔排序时，假定取di?1??di/2?, 0≤i≤t-1，其中t=?log2n?、d0=n、dt=1，n为待排序记录的个数，则第二趟排序结束后前4条记录为＿＿＿＿＿＿。構氽頑黉碩饨荠龈话骛門戲鷯。構氽頑黉碩饨荠龈话骛門戲鷯瀏鲮晝。 2．在对一组记录（）进行直接插排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较＿＿＿＿＿＿次。輒峄陽檉簖疖網儂號泶蛴镧釃。輒峄陽檉簖疖網儂號泶蛴镧釃邊鲫釓。 3．在直接插入和直接选择排序中，若初始数据基本有序，则选用＿＿＿＿＿＿，若初始数据基本反序，则选用＿＿＿＿＿＿。尧侧閆繭絳闕绚勵蜆贅瀝纰縭。尧侧閆繭絳闕绚勵蜆贅瀝纰縭垦鲩换。 4 / 7

4．在对一组记录（50，40，95，20，xx，70，60，45，80）进行直接选择排序时，第4次交换和选择后，未排序记录（即无序表）为＿＿＿＿＿＿。识饒鎂錕缢灩筧嚌俨淒侬减攙。

识饒鎂錕缢灩筧嚌俨淒侬减攙苏鲨运。 5．在对一组记录（50，40，95，20，xx，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为＿＿＿＿＿＿，在整个排序过程中共需进行＿＿＿＿＿＿趟才可完成。凍鈹鋨劳臘锴痫婦胫籴铍賄鹗。凍鈹鋨劳臘锴痫婦胫籴铍賄鹗骥鲧戲。 6．n个记录的冒泡排序算法所需最大移动次数为＿＿＿＿＿＿，最小移动次数为＿＿＿＿＿＿。

7．如果n个记录的被排序文件的初始状态是逆序时，采用冒泡排序算法，则所需记录关键码的比较次数为＿＿＿＿＿＿，记录移动次数为＿＿＿＿＿＿。恥諤銪灭萦欢煬鞏鹜錦聰櫻郐。恥諤銪灭萦欢煬鞏鹜錦聰櫻郐燈鲦軫。 8．对n个元素的序列进行冒泡排序，最小的比较次数是＿＿＿＿＿＿，此时元素的排列情况＿＿＿＿＿＿，在＿＿＿＿＿＿的情况下比较次数最多，其比较次数为＿＿＿＿＿＿。鯊腎鑰诎褳鉀沩懼統庫摇饬缗。鯊腎鑰诎褳鉀沩懼統庫摇饬缗釷鲤怃。 9．设有字符序列（Q，H，C，Y，P，A，M，S，E，D，F，X）要求按字符升序排列，则： （1）采用初始步长为4的Shell排序，一趟扫描的结果是：＿＿＿＿＿＿。

（2）采用以首元素为分界元素的快速排序，一趟扫描的结果是：＿＿＿＿＿＿。 xx．对n个结点进行快速排序，最大比较次数是＿＿＿＿＿＿。

xx．利用快速排序方法记录（50，40，95，20，xx，70，60，45，80）进行快速排序，其需递归调用的次数为＿＿＿＿＿＿，其中第二次次递归调用是对＿＿＿＿＿＿一组记录进行快速排序。硕癘鄴颃诌攆檸攜驤蔹鸶胶据。硕癘鄴颃诌攆檸攜驤蔹鸶胶据实鲣赢。 xx．从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每一趟快速排序都将记录序列均匀地分割成长度相接近的两个序列，则栈的最大深度（含最外层也进栈）为＿＿＿＿＿＿；在最坏情况下，栈的深度为＿＿＿＿＿＿；如果每次先对较短的子序列进行快速排序，则栈的最大深度降为＿＿＿＿＿＿；所需要的附加空间为＿＿＿＿＿＿。阌擻輳嬪諫迁择楨秘騖輛埙鵜。阌擻輳嬪諫迁择楨秘騖輛埙鵜蔹鲢幟。 xx．在对一组记录（50，40，95，20，xx，70，60，45，80）进行（大根）堆排序时，根据初始记录构成初始堆后，最后4条记录为＿＿＿＿＿＿。氬嚕躑竄贸恳彈瀘颔澩纷釓鄧。氬嚕躑竄贸恳彈瀘颔澩纷釓鄧鳌鲡貼。 xx．在堆排序和快速排序中，若原始状态记录接近正序或反序，则选用＿＿＿＿＿＿，若原始记录无序，则最好选用＿＿＿＿＿＿。釷鹆資贏車贖孙滅獅赘慶獷緞。釷鹆資贏車贖孙滅獅赘慶獷緞瑋鲟将。 xx．对于直接插入排序，冒泡排序，简单选择排序，堆排序，快速排序有：

（1）当文件“局部有序”或文件长度较小的情况下，最佳的内部排序方法是＿＿＿＿＿＿。 （2）快速排序在最坏情况下时间复杂度是＿＿＿＿＿＿比＿＿＿＿＿＿性能差。 （3）就平均时间而言，＿＿＿＿＿＿最佳。

xx．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有＿＿＿＿＿＿。怂阐譜鯪迳導嘯畫長凉馴鸨撟。怂阐譜鯪迳導嘯畫長凉馴鸨撟鉍鲞谣。 xx．在内部排序中，平均比较次数最少的是＿＿＿＿＿＿，要求附加的内存容量最大的是＿＿＿＿＿＿，排序时不稳定的有＿＿＿＿＿＿等几种方法。谚辞調担鈧谄动禪泻類谨觋鸾。

谚辞調担鈧谄动禪泻類谨觋鸾帧鲜奧。 xx．在归并排序中，若待排序记录的个数为20，则共需要进行＿＿＿＿＿＿趟归并，在第三趟归并中是把长度为＿＿＿＿＿＿的有序表归并为长度为＿＿＿＿＿＿的序表。嘰觐詿缧

5 / 7

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库练习题及参考答案在线全文阅读。