2. 计算机
  3. (2012年上半年上午试题65)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_________。 i=0；j=n-1 while i＜1

(2012年上半年上午试题65)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_________。 i=0；j=n-1 while i＜1

admin2021-01-13  26
问题 (2012年上半年上午试题65)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下，则该算法的时间和空间复杂度为_________。
i=0；j=n-1
while i＜1  do
    while A＜0 do
    i=i+1;
    while A[j]＞0 do
    j=j-1；
    if i＜1  do
    交换A和A[j]
选项 A、Θ(n)和Θ(n)
B、Θ(1)和Θ(n)
C、Θ(n)和Θ(1)
D、Θ(1)和Θ(1)
答案C
解析 算法中用到了两个辅助变量i和i，算法的空间复杂度为Θ(1)。在重新排列过程中，从数组的两端进行比较，从i=0开始判断A是否为负数，i为负数的时候，i=i+1，直到A为正数；从j=n-1开始判断A是否为正数，如果为正数，j=j-1，直到A[j]为负数。当i和A[j]的值，然后继续判断A和A[j]的值。数组A中的元素个数为n，A＜0和A[j]＞的比较次数共为n+2次，i=i+l和j=j-1执行的次数最多为n+2次，if语句中的i＜j的比较和交换A和A[j]的操作分别最多执行n-1次，While循序的条件判断至多执行n次。可见，算法的时间复杂度为Θ(n)。
转载请注明原文地址:https://kaotiyun.com/show/itCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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