用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。

题目

用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。

相似考题

1.若一个栈以向量V[1..n]存储,初始栈顶指针top设为n＋1,则元素x进栈的正确操作是()。A.top++;V[top]=x;B.V[top]=x;top++;C.top--;V[top]=x;D.V[top]=x;top--;

2.两个递增序列A和B的长度分别为m和n(m＜n)，将两者归并为一个长度为m+n的递增序列时，______，归并过程中元素的比较次数最少。A．当A的最大元素大于B的最大元素时B．当A的最大元素小于B的最小元素时C．当A的最小元素大于B的最小元素时D．当A的最小元素小于B的最大元素时A．B．C．D．

3.阅读下列说明、流程图和算法，将应填入(n)处的字句写在对应栏内。【流程图说明】下图所示的流程图5.3用N-S盒图形式描述了数组Array中的元素被划分的过程。其划分方法；以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于Array[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。【算法说明】将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int Array[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组Ar ray中的下标。递归函数void sort(int Array[]，int L，int H)的功能是实现数组Array中元素的递增排序。【算法】void sort(int Array[]，int L，int H){if (L＜H) {k=p(Array，L，H)；/*p()返回基准数在数组Array中的下标*/sort((4))；/*小于基准数的元素排序*/sort((5))；/*大于基准数的元素排序*/}}

4.阅读下列说明、流程图和算法，将应填(n)处的字句写在对应栏内。[说明]下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为 low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：[流程图][算法说明]将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数int p(int A[]，int low，int hieh)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。[算法]void sort(int A[]，int L，int H) {if (L＜H) {k=p(A，L，R)； //p()返回基准数在数组A中的下标sort((4))； //小于基准敷的元素排序sort((5))； //大于基准数的元素排序}}

更多“用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。”相关问题

  • 第1题：

    以下属于VisualBasic合法的数组元素是( )。

    A．x8

    B．x[8]

    C．s(0)

    D．v[8]


    正确答案：C

  • 第2题：

    快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（ ）算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（请作答此空）。


    答案：D
    解析：
    快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下，即初始序列按关键字有序或者基本有序时，快速排序的时间复杂度为O(n2)。

  • 第3题：

    快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。

    A.O（n）和O（nlgn）
    B.O（n）和O（n2）
    C.O（nlgn）和O（nlgn）
    D.O（nlgn）和O（n2）

    答案：D
    解析：
    将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。

  • 第4题：

    设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为（）。（数组元素的下标从1开始）
    i（i-1）/2+j
    略

  • 第5题：

    在普通碳钢中加入各种合金元素，可提高钢的高温强度，其中以（）等元素最明显。

    • A、Mo，V，Ti
    • B、Mo，V，Cr
    • C、S，V，Ti
    • D、S，V，Cr

    正确答案:A

  • 第6题：

    若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。

    • A、top++； V[top]=x；
    • B、V[top]=x； top++；
    • C、top--； V[top]=x；
    • D、V[top]=x； top--；

    正确答案:C

  • 第7题：

    钢中元素Mn、P、V、W是促进奥氏体晶粒长大的元素。


    正确答案:错误

  • 第8题：

    钢材中含有C、P、N、S、O、Cu、Si、Mn、V等元素,其中（）为有害的杂质元素。


    正确答案:N、O

  • 第9题：

    可以通过（）建立一个新的控件数组元素。

    • A、Ctrl+ V
    • B、Ctrl+V和Ctrl+C
    • C、Ctrl+C
    • D、Ctrl+A

    正确答案:B

  • 第10题：

    单选题
    海相石油微量元素镍（Ni）和钒（V）含量具有何种特征？（）
    A

    Ni/V大于1；

    B

    V/Ni大于1；

    C

    Ni/V等于1；

    D

    V/Ni等于2


    正确答案： D
    解析： 暂无解析

  • 第11题：

    填空题
    设有n阶对称矩阵A，用数组s进行压缩存储，当i≥j时，A的数组元素aij相应于数组s的数组元素的下标为（）。（数组元素的下标从1开始）

    正确答案： i（i-1）/2+j
    解析： 暂无解析

  • 第12题：

    填空题
    钢材中含有C、P、N、S、O、Cu、Si、Mn、V等元素,其中（）为有害的杂质元素。

    正确答案： N、O
    解析： 暂无解析

  • 第13题：

    试题三（共15分）

    阅读以下说明和C函数，回答问题 l和问题 2，将解答填入答题纸的对应栏内。

    【说明】

    对于具有n个元素的整型数组a，需要进行的处理是删除a中所有的值为 0的数组元素，并将a中所有的非 O元素按照原顺序连续地存储在数组空间的前端。下面分别用函数CompactArr_v1 和CompactArr v2来实现上述处理要求，函数的返回值为非零元素的个数。 函数CompactArr_vl(int a[]，int n)的处理思路是：先申请一个与数组a的大小相同的动态数组空间，然后顺序扫描数组a的每一个元素，将遇到的非O元素依次复制到动态数组空间中，最后再将动态数组中的元素传回数组a中。

    函数CompactArr_v2(int a[]，int n)的处理思路是：利用下标i（初值为 0）顺序扫描数组a的每一个元素，下标k（初值为0）表示数组 a中连续存储的非0元素的下标。扫描时，每遇到一个数组元素，i就增 1，而遇到非 0元素并将其前移后k才增 1。

    【问题1】 (12分)

    请根据说明中函数CompactArr_v1的处理思路填补空缺(1)～(3)，根据CompactArr_v2的处理

    思路填补空缺(4)。

    【问题2】（3分）

    请说明函数CompactArr vl存在的缺点。


    正确答案：
    试题三参考答案（共 15分）
    【问题 1】 (12分)
    (1) sizeof(int) （3分）
    若考生解答为一个正整数，则给 2分
    (2)temp[k++] 或*(temp+k++)或等价表示 （3分）
    (3) ik 或等价表示 （3分）
    (4)a[k++] 或*（a+k++）或等价表示 （3分）
    【问题 2】（3分）
    可能由于动态内存申请操作失败而导致函数功能无法实现，时间和空间效率低。
    注：考生仅回答出运行速度慢则给 2分，其他含义相同的描述可给满分或酌情给分。

  • 第14题：

    设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。


    答案：C
    解析：
    数组是随机存取的结构，所以读取第i个节点的时间复杂度为0(1)。

  • 第15题：

    快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。

    A.分治
    B.动态规划
    C.贪心
    D.回溯

    答案：A
    解析：
    将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。

  • 第16题：

    下列元素中最难原子化的元素是（）。

    • A、pb
    • B、cu
    • C、k
    • D、v

    正确答案:D

  • 第17题：

    下面哪一组元素全部是非金属元素（）。

    • A、C、Si、Mn
    • B、Cr、Ni、Cu
    • C、Nb、V、Pb
    • D、N、O、H

    正确答案:D

  • 第18题：

    用数组Q表示一个环形队列，f为当前对头元素的钱一位置，r为队尾元素的位置。假定队列中元素个数总小于n，求队列中元素个数公式是（）。


    正确答案:（r-f+n）%n

  • 第19题：

    海相石油微量元素镍（Ni）和钒（V）含量具有何种特征？（）

    • A、Ni/V大于1；
    • B、V/Ni大于1；
    • C、Ni/V等于1；
    • D、V/Ni等于2

    正确答案:B

  • 第20题：

    以下属于VisualBasic合法的数组元素是（）

    • A、x8
    • B、x［8］
    • C、s（0）
    • D、v[8]

    正确答案:C

  • 第21题：

    问答题
    用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。

    正确答案： 至少需要对每个元素进行一次比较运算，运算时间是O（n）。
    解析： 暂无解析

  • 第22题：

    单选题
    可以通过（）建立一个新的控件数组元素。
    A

    Ctrl+ V

    B

    Ctrl+V和Ctrl+C

    C

    Ctrl+C

    D

    Ctrl+A


    正确答案： B
    解析： 暂无解析

  • 第23题：

    填空题
    用数组Q表示一个环形队列，f为当前对头元素的钱一位置，r为队尾元素的位置。假定队列中元素个数总小于n，求队列中元素个数公式是（）。

    正确答案： （r-f+n）%n
    解析： 暂无解析

相关内容