2. 计算机
  3. 阅读以下说明和流程图，填补流程图中的空缺(1)～(9)，将解答填入对应栏内。 【说明】 假设数组A中的各元素A(1)，A(2)，…，A(M)已经按从小到大排序(M≥1)；数组B中的各元素B(1)，B(2)，…，B(N)也已经按从小到大排序(N≥1)。

阅读以下说明和流程图，填补流程图中的空缺(1)～(9)，将解答填入对应栏内。 【说明】 假设数组A中的各元素A(1)，A(2)，…，A(M)已经按从小到大排序(M≥1)；数组B中的各元素B(1)，B(2)，…，B(N)也已经按从小到大排序(N≥1)。

admin2009-05-15  22
问题 阅读以下说明和流程图，填补流程图中的空缺(1)～(9)，将解答填入对应栏内。
【说明】
   假设数组A中的各元素A(1)，A(2)，…，A(M)已经按从小到大排序(M≥1)；数组B中的各元素B(1)，B(2)，…，B(N)也已经按从小到大排序(N≥1)。执行下面的流程图后，可以将数组A与数组B中所有的元素全都存入数组C中，且按从小到大排序 (注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组A中有元素：2，5， 6，7，9；数组B中有元素2，3，4，7：则数组C中将有元素：2，2，3，4，5，6，7， 7，  9。
【流程图】
选项
答案(1)1 (2)A(i) (3)B(j) (4)i (5)j (6)B(j) (7)A(i) (8)j (9)i
解析 这是最常见的一种合并排序方法。为对较大的序列进行排序，先将其分割成容量相当的几个部分，分别进行排序，最后再合并在一起。当然，这些排序要么都是升序，要么都是降序。本题全部是按升序排序的。
   例如，为了将整副扑克牌按升序进行排序，先将其分割成两个部分(数量大致相当)，对每个部分完成升序排序后，就形成了两叠已排序的牌。如何将其合并呢?办法如下。
   每次都比较各叠最上面的两张牌，取出比较小的，放入新堆，再继续比较。直到其中一堆空了，就将另一堆剩余的牌逐张放入新堆。新堆就是合并后的已完成排序的序列。
   在数据排序时，遇到相同的数比较时，任取一个就可以了。
   对本题来说，i、j、k是数组A、B、C的下标，初始时，都应该是1。因此，空(1)处应填写1。
   将A(i)与B(j)进行比较后，如果A(i)≤B(j)，那么应该将A(i)→C(k)。这是升序的要求。因此，空(2)处应填A(i)。如果A(i)＞B(j)，则应将B(j)→C (k)。因此，空(3)处应填B(j)。
   在A(i)→C(k)后，i应增加1，为下次取A(i)再比较做准备(k也需要增加1，为下次存入C(k)做准备)。这时，需要比较数组A是否已经取完，即判断i＞M是否成立。如果i＞M，则表示数组A中的元素已经全部取出，需要将数组B中剩余的元素逐个移入C(k)。因此，空(4)处应填i，空(6)处应填B(j)。数组B处的元素何时移完呢?这就需要判断i＞N是否成立。因此，空(8)处应填j。
   同样，空(3)处将B(j)存入C(k)，直到，j＞N时数组B中的元素取完。此时，需要将数组A中剩余的元素逐个移入C(k)，直到i＞M时全部完成。因此，空(5)处应填j，空(7)处应填A(i)，空(9)处应填i。
转载请注明原文地址:https://kaotiyun.com/show/TIjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)