niusouti.com
设计一个算法，实现将一维数组A（下标从1开始）中的元素循环右移k位，要求只用一个元素大小的辅助空间，并给出算法的时间复杂度。
题目
设计一个算法，实现将一维数组A（下标从1开始）中的元素循环右移k位，要求只用一个元素大小的辅助空间，并给出算法的时间复杂度。
相似考题
更多“设计一个算法，实现将一维数组A（下标从1开始）中的元素循环右移k位，要求只用一个元素大小的辅助空间，并给出算法的时间复杂度。”相关问题
-
第1题：
在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是()
A.O(n)
B.O(nlogn)
C.O(n(logn)2)
D.O(n3/2)
正确答案：A
-
第2题：
已知数组a中有n个元素，下列语句将数组a中从下标x1开始的k个元素移动到从下标x2开始的k个元素中，其中O＜=xl＜x2＜n，x2+k＜n，请将下列语句补充完整。
For(int i=x1+k-1；i＞=x1；i--)
a[______]=a[i]；
正确答案：X2+k-1
X2+k-1 解析：此题考查的是数组的操作。a[i]表示从下标x1开始的第i个元素，若为第一次循环，则i为xt+k-1，按照题目将数组a中从下标x1开始的k个元素移动到从下标x2开始的k个元素中的要求，所以将a[i]赋值给下标为X2+k-1的元素。 -
第3题：
阅读以下算法说明，根据要求回答问题1～问题3。
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1．分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
2．递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
3．合并：快速排序在原地排序，故无需合并操作。
下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。
A：待排序数组
p,r：数组元素下标，从p到r
q：划分的位置
x：枢轴元素
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值
j：循环控制变量，表示数组元素下标
正确答案：这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分即PARTITION操作：根据枢轴元素的值把一个较大的数组分成两个较小的子数组一个子数组的所有元素的值小于等于枢轴元素的值一个子数组的所有元素的值大于枢轴元素的值而子数组内的元素不排序。划分时以最后一个元素为枢轴元素从左到右依次访问数组的每一个元素判断其与枢轴元素的大小关系并进行元素的交换如图2-30所示。
在[问题1]所给出的伪代码中当for循环结束后A[p..i]中的值应小于等于枢轴元素值x而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素因此A[r]与A[i+1]进行交换得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置因此返回值为i+l。
这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分，即PARTITION操作：根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图2-30所示。
在[问题1]所给出的伪代码中，当for循环结束后，A[p..i]中的值应小于等于枢轴元素值x，而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素，因此A[r]与A[i+1]进行交换，得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置，因此返回值为i+l。
-
第4题：
假设用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30(数组下标)，则栈中具有的元素个数为（ ）。
A.50
B.19
C.1
D.20
正确答案：B
B。【解析】当前栈中的所有元素的个数就是用栈底指针减去栈顶指针。 -
第5题：
● 在数组A中，每一个数组元素A[i，j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是 （） 。 （） A．80 B．100 C．240 D．270
正确答案：C
8×10×3=240。 -
第6题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（请作答此空）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（ ）。A.分治
B.动态规划
C.贪心
D.回溯答案：A解析：快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。 -
第7题：
在n个数的数组中确定其第i（1≤i≤n）小的数时，可以采用快速排序算法中的划分思想,对n个元素划分，先确定第k小的数，根据i和k的大小关系,进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的（64）元素。此时，算法在最坏情况下的时间复杂度为（不考虑所有元素均相等的情况）（65）。A.第一个
B.最后一个
C.中位数
D.随机一个答案：C解析：本题考查数据结构基础知识。快速排序一种分治的排序方法，其思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的每一趟结果都是找到一个基准元素放置于线性表中部位置，将原来的线性表划分为前后两部分，前部分元素都小于基准元素，后部分元素都大于基准元素。快速排序总的关键字比较次数为Θ（nlog2n）,最坏情况下时间复杂度为Θ（n2），最好情况下的时间复杂度为Θ（nlog2n）；快速排序是不稳定的排序。最坏情况下需要的栈空间为Θ（n），其他需要Θ（nlog2n）。根据以上描述，本题依次选C、D选项。 -
第8题：
设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O（n）。
正确答案:操作步骤为：
①将所有元素出栈并入队；
②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；
③将奇数结点出栈并入队；
④将偶数结点出队并入栈；
⑤将所有元素出栈并入队；
⑥将所有元素出队并入栈即为所求。 -
第9题：
从n个数中选取最大元素（）。
- A、基本操作是数据元素间的交换
- B、算法的时间复杂度是O（n）
- C、算法的时间复杂度是O（n2）
- D、需要进行（n+1）次数据元素间的比较
正确答案:B -
第10题：
数组元素的下标从1开始。
正确答案:错误 -
第11题：
问答题给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。正确答案： 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j]
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。解析： 暂无解析 -
第12题：
问答题给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。正确答案： 我们把这种算法叫做快速选择（quickselect）。令〡Si〡为Si中元素的个数，快速选择的步骤如下：
1）如果〡S〡=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且〡S〡≤CUTOFF，则将S排序并返回第k个最小元。
2）选取一个枢纽元v∈S。
3）将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。
4）如果k≤〡S1〡，那么第K个最小元必然在S1中。在这种情况下，返回quickselect（S1，k），如果k=1+〡S1〡
，那么枢纽元就是第k个最小元，将它最为答案返回。否则，第k个最小元就在S2中，他是S2中的第（k-〡S1〡-1）个最小元。我们进行一次递归调用并返回quickselect（S2，k-〡S1〡-1）。
与快速排序对比，快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同，也就是O（N=2）。直观看来，这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候；于是，快速选择也就不是真的节省一次递归调用。不过平均运行时间是O（N）。具体分析类似快速排序的分析。
快速排序的实现甚至比抽象描述还要简单，当算法终止时，第k个最小元就在位置k-1上（因为数组开始于下标0）。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。解析： 暂无解析 -
第13题：
设二维数组a[1..m, 1..n] 含有m*n 个整数。 ① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes／no); ② 试分析算法的时间复杂度。参考答案：①判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次?在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p的for循环)，然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。
[算法描述]
int JudgEqual(ing a[m][n],int m,n)
//判断二维数组中所有元素是否互不相同，如是，返回1;否则，返回0。
{for(i=0;i
//只要有一个相同的，就结论不是互不相同
for(k=i+1;k
}// for(j=0;j
}//算法JudgEqual结束
②二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，……，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为 (m*n-1)+(m*n-2)+…+2+1=(m*n)(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为(m*n)(m*n-1)/4，总的时间复杂度是O(n4)。
-
第14题：
假设用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间，栈底指针bosom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30(数组下标)，则栈中具有______个元素。
正确答案：19。
19。 解析：当前栈中的所有元素的个数就是用栈底指针减去栈顶指针。 -
第15题：
下列关于算法复杂度描述正确的是（ ）。
A. 算法的时间复杂度是指算法执行的时间
B. 算法的空间复杂度是指执行这个算法所需的内存空间
C. 一个算法的空间复杂度大，则其时间复杂度必定大
D. 一个算法的空间复杂度大，则其时间复杂度必定小
正确答案：B
算法的时间复杂度是指执行算法所需的计算工作量。算法的空间复杂度是指执行这个算法所需的内存空间。在一个算法的空间复杂度大的情况下，其时间复杂度可能会很大，具体视情况而定；反之亦然。
-
第16题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为
，则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。A.分治
B.动态规划
C.贪心
D.回溯
正确答案：A
本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组，此时T(n)=2T(n/2)+解该递归式，可得时间复杂度为。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n-l个元素，此时T(n)=T(n/1)+解该递归式，可得时间复杂度为。 -
第17题：
假设用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30(数组下标)，则栈中具有【1】个元素。
正确答案：
20 -
第18题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（ ）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（请作答此空）。
答案：D解析：快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。 -
第19题：
给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
正确答案: 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j]
从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。 -
第20题：
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。
正确答案: 我们把这种算法叫做快速选择（quickselect）。令〡Si〡为Si中元素的个数，快速选择的步骤如下：
1）如果〡S〡=1，那么k=1并将S中的元素作为答案返回。如果正在使用小数组的截止方法且〡S〡≤CUTOFF，则将S排序并返回第k个最小元。
2）选取一个枢纽元v∈S。
3）将集合S-{v}分割成S1和S2，就像快速排序中所做的那样。
4）如果k≤〡S1〡，那么第K个最小元必然在S1中。在这种情况下，返回quickselect（S1，k），如果k=1+〡S1〡
，那么枢纽元就是第k个最小元，将它最为答案返回。否则，第k个最小元就在S2中，他是S2中的第（k-〡S1〡-1）个最小元。我们进行一次递归调用并返回quickselect（S2，k-〡S1〡-1）。
与快速排序对比，快速选择只进行了一次递归调用而不是两次。快速选择的最坏情形和快速排序的相同，也就是O（N=2）。直观看来，这是因为快速排序的最坏情形发生在S1和S2有一个是空的时候；于是，快速选择也就不是真的节省一次递归调用。不过平均运行时间是O（N）。具体分析类似快速排序的分析。
快速排序的实现甚至比抽象描述还要简单，当算法终止时，第k个最小元就在位置k-1上（因为数组开始于下标0）。这破坏了原来的排序；如果不希望这样，那么需要做一份拷贝。 -
第21题：
设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为（）。（数组元素的下标从1开始）
正确答案:i（i-1）/2+j -
第22题：
下列算法的时间复杂度与空间复杂度叙述中正确的是（）
- A、一个算法的空间复杂度大，则其时间复杂度也必定大
- B、一个算法的空间复杂度大，则其时间复杂度必定小
- C、一个算法的时间复杂度大，则其空间复杂度必定小
- D、算法的时间复杂度与空间复杂度没有直接关系
正确答案:D -
第23题：
填空题设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为（）。（数组元素的下标从1开始）正确答案： i（i-1）/2+j解析： 暂无解析 -
第24题：
单选题从n个数中选取最大元素（）。A基本操作是数据元素间的交换
B算法的时间复杂度是O（n）
C算法的时间复杂度是O（n2）
D需要进行（n+1）次数据元素间的比较
正确答案： B解析： 暂无解析