●在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个 元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于(63)策略的算法。(63)A．分治B．动态规划C．贪心D．回溯

题目

●在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个 元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于(63)策略的算法。

(63)

A．分治

B．动态规划

C．贪心

D．回溯

相似考题

1.在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分操作找第k－i小的数。该算法是一种基于()策略的算法。A.分治B.动态规划C.贪心D.回溯

2.若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作是（ ）A.查找与给定值相匹配的元素的位置 B.查找并返回第i个元素的值（1≤i≤n） C.删除第i个元素（1≤i D.在第i个元素（1≤i≤n）之前插入一个新元素

3.在n个数的数组中确定其第i（1≤i≤n）小的数时，可以采用快速排序算法中的划分思想,对n个元素划分，先确定第k小的数，根据i和k的大小关系,进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的（64）元素。此时，算法在最坏情况下的时间复杂度为（不考虑所有元素均相等的情况）（65）。A.Θ（n） B.Θ（lgn） C.Θ（nlgn） D.Θ（n2）

4.若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作是 （ ）。A.查找与给定值相匹配的元素的位置 B.查找并返回第i个元素的值（1≤i≤n） C.删除第i个元素（1≤iD.在第i个元素（1≤i≤n）之前插入一个新元素

更多“●在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个 元素r,用划分操作确 ”相关问题

  • 第1题：

    在n个数的数组中确定其第i（1≤i≤n）小的数时，可以采用快速排序算法中的划分思想,对n个元素划分，先确定第k小的数，根据i和k的大小关系,进一步处理，最终得到第i小的数。划分过程中，最佳的基准元素选择的方法是选择待划分数组的（64）元素。此时，算法在最坏情况下的时间复杂度为（不考虑所有元素均相等的情况）（65）。

    A.第一个
    B.最后一个
    C.中位数
    D.随机一个

    答案：C
    解析：
    本题考查数据结构基础知识。快速排序一种分治的排序方法，其思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的每一趟结果都是找到一个基准元素放置于线性表中部位置，将原来的线性表划分为前后两部分，前部分元素都小于基准元素，后部分元素都大于基准元素。快速排序总的关键字比较次数为Θ（nlog2n）,最坏情况下时间复杂度为Θ（n2），最好情况下的时间复杂度为Θ（nlog2n）；快速排序是不稳定的排序。最坏情况下需要的栈空间为Θ（n），其他需要Θ（nlog2n）。根据以上描述，本题依次选C、D选项。

  • 第2题：

    【TEST-2-1-4】设线性表有n个元素且采用顺序存储表示，算法的时间复杂度为O（1)的操作是（）。

    A．访问第i个元素和求第i个元素的直接前趋(2≤i≤n)

    B．在第i(1≤i≤n)个元素后面插入一个新元素

    C．删除数组第i个元素

    D．顺序查找与给定值k相等的元素


    A

  • 第3题：

    对于用一维数组 d [1..n]顺序存储的线性表，其算法时间复杂度为O（1)的操作是_____ 。

    A．将n个元素从小到大排序

    B．从线性表中删除第i个元素（1≤i≤n）

    C．查找第i个元素（1≤i≤n）

    D．向线性表的第i个元素之后插入一个元素（0≤i≤n）


    查找第 i 个元素（ 1≤ i ≤ n ）

  • 第4题：

    【2-1-4】设线性表有n个元素且采用顺序存储表示，算法的时间复杂度为O（1)的操作是（）。

    A．访问第i个元素和求第i个元素的直接前趋(2≤i≤n)

    B．在第i(1≤i≤n)个元素后面插入一个新元素

    C．删除数组第i个元素

    D．顺序查找与给定值k相等的元素


    A

  • 第5题：

    对于用一维数组d[0..n-1]顺序存储的线性表，其算法的时间复杂度为O（1)的操作是（）。

    A．将n个元素从小到大排序

    B．从线性表中删除第i个元素(1≤i≤n)

    C．查找第i个元素(1≤i≤n)

    D．在线性表中第i个元素之后插入一个元素


    C

相关内容