设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。

第1题：

设{an}为数列，对于“存在正数肘，对任意正整数n，有
的否定(即数列{an}无界)是( )。

A、存在正数M，存在正整数n，使得|an|＞M
B、对任意正数M，存在正整数n，使得|an|＞M
C、存在正数M，对任意正整数n，有|an|＞M
D、对任意正数M以及任意正整数n，有|an|＞M

答案：B

解析：

对任意正数M，存在正整数n，使得

则称数列{an}无界．

第2题：

设M是一个n行n列的0-1矩阵，每行的1都排在0的前面。 （1）设计一个最坏情况下O（nlogn)时间的算法找到M中含有1最多的行，说明算法的设计思想，估计最坏情况下的时间复杂度。 （2）对上述问题，能否找到一个最坏情况下O（n)时间的算法？

第3题：

在数组A[0,1,……，n-1]中查找给定值K的算法大致如下： i=n-1; While（i＞=0&&（A[i]!=k)) i--; return i; 该算法的时间复杂度为 （） A O（n) B 无法确定 C O（n-i) D O（n-i+1)

第4题：

设A是由n个非0实数构成的数组，设计一个算法重新排列的数组的数，使得负数都排列在正数的前面，要求算法使用O（n)的时间和O（1)的空间。

第5题：

设任意n个整数存放于数组A（1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0（n)）。 [题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。