第1部分 第二章 §112 應(yīng)用創(chuàng)新演練
第1部分第二章§1 12應(yīng) 用創(chuàng)新演練1. 用折半插入排序方法將1插入有序列- 2,-1,3,5,8中,則第一次與該有序列中的哪個(gè) 數(shù)比較()A.-2B.-1C. 3D. 8解析:有序列的中間數(shù)據(jù)為3 ,.應(yīng)先與3 比較大小.答案:C2. 若將有序列3,2,1,0按照從小到大的順序 輸出,需要排序的次數(shù)為()A. 3B. 4C. 5D. 6rt解析:1.將 2 插入序列3,需排序1次,得2,3;2 將1插入序列23,需排序 2次,得1,2,3;3將 0 插入序列1,2,3,需排序 3 次,得0,1,2,3來源:1故需 1 + 2 + 3 = 6 次排序.答案:D3將數(shù)據(jù)15通過直接插入排序的方法插入F到有序列13,14,17,18,1920中,需要作比較大小的次數(shù)為()A. 3B4C5D6解析:15依次與20,19,18,17,14比較大小洪5次.答案:C4.用直接插入法把數(shù)a插入到由m個(gè)數(shù)組 成的有序列中,則最多需要比較的次數(shù)和最少需 要比較的次數(shù)分別為()Am,0Bm1,1m,1 來Cm1,0源:Zlxxlk.Com解析:由直接插入法的過程可知至少需要 比較一次,最多需要比較m次.答案:D5. 將數(shù)據(jù)41分別用“直接插入排序法”和 “折半插入排序法”插入到有序列19,27,31,50,92沖,所需要的排序次數(shù)分別為n次和次.答案:3 26. 若一個(gè)有序列有2n+1個(gè)數(shù)據(jù),則“中間位置”的數(shù)據(jù)指的是第 個(gè)數(shù);若有2n個(gè)數(shù)據(jù),則“中間位置”的數(shù)據(jù)指的是第 個(gè)數(shù).答案:n+1 n7.寫 出 將 56 插 入 有 序 列1,8,12,36,49,57,68,79中的算法.解:法一:1.56與79比較,56<79,56應(yīng)在79的左邊;2 .56與68比較,56<68,56應(yīng)在68的左邊;3 .56與57比較,56<57,56應(yīng)在57的左邊;4 .56與49比較,56>49,56應(yīng)在49的右邊因此將56插入到49與57之間,得到一個(gè)新的有序列,1,8,12,36,49,56,57,68,79.法二:56與中間位置的數(shù)36比較,56>36,故56應(yīng)該在36的右邊;2 將56與剩余的數(shù)的中間位置的數(shù)57比較,56<57,故56應(yīng)該在57的左邊;3再將 56與49比較,56>49,故56應(yīng)該在49與57之間.由 此 得 插 入 56 后 的 新 的 有 序 列 1,8,12,36,49,56,57,68,79來源:學(xué)§科§網(wǎng) Z§X §X§K8.中國乒乓球女隊(duì)原有11名隊(duì)員,她們的n身高由小到大分別為158,159,160,162,163,165,166,170,171,172,175(單E位:cm)現(xiàn)為備戰(zhàn)某項(xiàng)比賽,加入一名優(yōu)秀隊(duì)E員,這名隊(duì)員身高169 cm,請?jiān)O(shè)計(jì)用折半插入 排序法找出該隊(duì)員在序列中的位置,并用自然語 言表述算法解:要將169插入有序列 158,159,160,162,163,165,166,170,171,172,175, 共有11個(gè)數(shù)據(jù),列表為a”a“aa “a“12a.aA5a<aaQan1011346789來來來來來00L SIN 0m;0V69IP>gln窯fM宦 69IM、991A69I a® 99- H J Mss = e 二3 ksmbk sws r691 譽(yù)辰 E V 691 二卜IH f 20 -60 . . sws £ wi KIJH、S9IA 、SSHJ69I 黨、S9IH 9 s 體g、專lgJ>g耳ttlg薦盤a