第二輪排序和查找算法綜合1行政班：教學班：姓名：學號：課本上的排序算法，補充完整冒泡排序變量n代表數組兀素的個數選擇排序:升序排序升序排序：Fori=1Ton-1Fori=1Ton-1k二iForj=nToi+1Step-1Forj=i+1TonIfa(j)<a(j-1)ThenIfa(j)<a(k)Thenk=jt=a(j):a(j)=a(j-1):a(j-1)=tNextjEndIfIfi<>kThenNextjt=a(i):a(i)=a(k):a(k)=tNextiEndIfNexti根據課本上的排序算法和查找算法回答-6題：1．【加試題】有一個數組，采用冒泡排序，第一遍排序后的結果為：4，10，5，32，6，79，17，24那么該數組的原始順序不．可．能．的是()A．10，5，32，6，7，9，17，24，4B．10，5，32，6，7，9，4，17，24C．10，5，32，4，6，7，9，17，24D．4，10，5，32，17，9，24，6，7【加試題】對下列數據序列進行冒泡升序排序，排序效率最低的序列()31，29，24，20，15，10B.10，15，20，24，29，31C.29，10，31，15，20，24D.24，29，31，20，15，10【加試題2】數組變量d(1)到d(8)的值依次為87、76、69、66、56、45、37、23,用“對分查找”找到“69”的過程中，依次被訪問到的數據是()A.69B.66、69C.66、76、69D.56、66、76、69【加試題2】用對分查找法和順序查找法在數字序列“1,2,3,5,8,13,21,34，55”中查找數字13,兩種方法都能訪問到的數字是()A.3B.5C.8D.34【加試題2】在有序單詞序列“bike,cake,data,easy,feel,great,hive,mark,sweet”中，用對分查找算法找到“easy”過程中，依次被訪問到的數據為()A.feel,data,easyB.great,data,easyC.bike,cake,dada,easyD.feel,cake,data,easy【加試題2】下列有關查找的說法,正確的是()進行對分查找時，被查找的數據必須已按升序排列進行對分查找時，如果查找的數據不存在，則無需輸出結果在新華字典中查找某個漢字，最適合使用順序查找對規模為n的數據進行順序查找，平均查找次數是口2【加試題】實現某排序算法的部分VB程序如下：數組元素a(l)到a(5)的數據依次為"38,70,53,57,30”。經過下列程序“加工”后數組元素a(l)到a(5)的數據應該是()Fori=1To1Forj=5Toi+1Step-1Ifa(j)>a(j-1)Thent=a(j)a(j)=a(j-1)a(j-1)=tEndIfNextjNextiA.70，57，38，53，30B.30,38，70，53，57C.70，38，57，53，30D.30,38，57，53，70【加試題】有如下程序段：Fori=1To2Forj=1To6-iIfa(j)<a(j+1)Thenk=a(j):a(j)=a(j+1):a(j+1)=kEndIfNextjNexti數組元素a(1)到a(6)的值依次為“71,54,58,29,31,78”，經過該程序段“加工”后,數組元素a(1)到a(6)的值依次為()A.29,31,54,58,71,78B.78,71,58,54,31,29C.54,29,31,58,71,78D.71,58,54,78,31,29【加試題】對數組a中的5個數據“5,10,6,30,9”進行排序，部分程序如下：Fori=1To4Forj=5Toi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tEndIfNextjNexti下列說法正確的是()A.升序排序，實線框中的語句共執行了2次B.升序排序，實線框中的語句共執行了3次C.降序排序，實線框中的語句共執行了5次D.降序排序，實線框中的語句共執行了6次【加試題】有如下程序段：tot=0Fori=1To4Forj=5Toi+1Step-1Ifa(j)>a(i)Thentot=tot+1t=a(j):a(j)=a(i):a(i)=tEndIfNextjNexti數組元素a(1)到a(5)的值依次為“33,24,4,16,77”，經過該程序段“加工”后，變量tot的值為()A.2B.3C.4D.5【2015年9月測試卷加試題,知識點1】采用如下選擇排序算法對數組a中5個數據“23,86,98,65,2”按從小到大的順序進行排序。Fori=1To4k=iForj=i+1To5Ifa(j)<a(k)Thenk=jNextjIfk<>iThent=a(i)：a(i)=a(k):a(k)=tEndIfNexti整個排序過程中,數組中的數據比較次數和交換次數分別是()A.10次和3次B.10次和4次C.15次和3次D.15次和10次答案D.【解析】第一遍排序后的結果為：4,10,5,32,6,7,9,17,24；可知為升序排序。按照冒泡排序規則，D選項無法滿足要求。答案A.【解析】交換次數越多，排序效率越低。A選項是數據已經是降序，轉變為升序交換次數最多。答案C.【解析】第一次查找區間【1,8】中點為4,第二次查找區間為【1,3】中點為2,第三次查找區間為【3,3】查找成功答案C.【解析】對分查找訪問到的數字為8、21、3,順序查找訪問到的數字為1,2,3,5,8,13。兩者共同為8答案D.【解析】字符比較大小，首先比較第一個字符，第一個字符相同再比較第二個字符。第一次查找區間【1,9】中點為5,即feel；第二次查找區間為【1,4】中點為2,即cake；第三次查找區間為【3,4】中點為3,即data；第四次查找區間為【4,4】中點為4,即easy；查找成功答案D.【解析】對分查找的數組必須有序(升序或降序)。如果找不到，程序應該要輸出未找到的相關提示信息。字典按字母順序排列,適合用對分查找。順序查找至少查找1次，最多查找n次，平均為(1+n)/2。答案C.【解析】分析可知為冒泡排序，Ifa(j)>a(j-1)Then可知為降序排序，排序一趟。&答案D.【解析】此題為冒泡排序變形，降序排序。從前往后，兩兩比較。答案B.【解析】此題為冒泡排序，由Ifa(j)<a(j-1)Ther可知為升序排序，總共交換次數為3次答案B.【解析】此題為選