从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较_ 个结点。A．n/2B．nC．(n+1)/2D．(n-1)/2

题目

从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较_ 个结点。

A．n/2

B．n

C．(n+1)/2

D．(n-1)/2

相似考题

1.对具有n个结点的线性表进行顺序查找，最坏情况下需要的比较次数为_______。

2.在具有n个结点的单链表中,实现()的操作，其算法的时间复杂度是O。A.求链表的第i个结点B.在地址为P的结点之后插入一个结点C.删除表头结点D.删除地址为P的结点的后继结点

3.在一个长度为n(n>1)的带头结点的单链表head上,另设有尾指针r(指向尾结点),执行()操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的尾结点C.在单链表的第一个元素前插入一个新结点D.在单链表的最后一个元素后插入一个新结点

4.在具有n个结点的单链表上查找值为y的元素时,其时间复杂度为()。A、O(n)B、O(1)C、O(n2)D、O(n-1)

更多“从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较_ 个结点。”相关问题

  • 第1题：

    从一个具有n个结点的单链表中查找其值等于k的结点时，在查找成功的情况下，需平均比较 ______个结点。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D
    解析：在n个结点的单链表中，查找第i个结点需要比较关键词的次数是i，所以，在查找成功的情况下，需平均比较的结点个数为(1+2+…+n)/n，即(n+1)/2。

  • 第2题：

    用二分查找法对具有n个结点的线性表查找一个结点，所需的平均比较次数为（ ）。A．O（n2）B．O（nlog2n）C．O（n）D．O（log2n）


    正确答案：D
    二分查找的优点是比较次数少，查找速度快，平均检索长度小，经过log2n次就可以完成查找过程。

  • 第3题：

    在一个n个结点的单链表中查找某个元素，若查找成功，则平均比较次数为( )。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D
    解析：对单链表结构的查找，每次比较都必须从头结点开始，因此最好情况为比较一次得到查找的元素，最坏情况为比较到最后一个结点需要n次才找到，平均比较次数为 (1+2+3+...+n)/n次， 即为(n+1)/2次。

  • 第4题：

    从一个包含2000个结点的散列表A[1..2000]中查找结点的平均比较次数( )从一个包含200个结点的散列表B[1..200]中查找结点的平均比较次数。

    A．大于

    B．小于

    C．等于

    D．不确定


    正确答案：D

  • 第5题：

    在具有n个结点的单链表中，实现()的操作，其算法的时间复杂度都是O(n)。

    A.遍历链表和求链表的第i个结点
    B.在地址为P的结点之后插入一个结点
    C.删除开始结点
    D.删除地址为P的结点的后继结点

    答案：A
    解析：
    A项，由于单链表是非随机存取的存储结构，遍历链表和求链表的第i个结点都必须从头指针出发寻找，其时间复杂度为0(n)；B项，由于已知待插入结点的前驱结点，可以直接实现插入，其时间复杂度为0(1)；CD两项，可以直接实现删除操作，其时间复杂度为O(1)。

  • 第6题：

    对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为（），在给定值为x的结点后插入一个新结点的时间复杂度为（）


    正确答案:O（1）；O（n）

  • 第7题：

    对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为（）；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为（）


    正确答案:O（1）；O（n）

  • 第8题：

    从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明（），若元素的值小于根结点的值，则继续向（）查找，若元素的大于根结点的值，则继续向（）查找。


    正确答案:找到；左子树；右子树

  • 第9题：

    从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。

    • A、n/2
    • B、n
    • C、（n+1）/2
    • D、（n-1）/2

    正确答案:C

  • 第10题：

    填空题
    从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明（），若元素的值小于根结点的值，则继续向（）查找，若元素的大于根结点的值，则继续向（）查找。

    正确答案： 找到,左子树,右子树
    解析： 暂无解析

  • 第11题：

    单选题
    从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个元素结点。
    A

    n/2

    B

    n

    C

    （n+1）/2

    D

    （n-1）/2


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

  • 第12题：

    填空题
    对于一个具有n个结点的单链表中，在已知的结点后插入一个新结点的时间复杂度为（）在给定值为X的结点后插入一个新结点的时间复杂度为（）。

    正确答案： O(1),O（n）
    解析： 暂无解析

  • 第13题：

    从一个具有n个结点的单链表中查找值为x的结点时，在查找成功的情况下，需平均比较(45)个结点。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D

  • 第14题：

    在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为()。

    A.50

    B.51

    C.100

    D.101


    正确答案：B

  • 第15题：

    设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有()个，比较两次查找成功有结点数有()个。


    正确答案：1 2

  • 第16题：

    从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D

  • 第17题：

    从一个具有N个结点的单链表中查找其值等于X结点时，查找成功的情况下，需平均比较()结点。

    A.N
    B.N/2
    C.(N-1)/2
    D.(N+1)/2

    答案：D
    解析：

  • 第18题：

    要访问具有n个结点的单链表中任意一个结点的时间复杂度是（）


    正确答案:O(n)

  • 第19题：

    从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明（），若元素的值小于根结点的值，则继续向（）查找，若元素的值大于根结点的值，则继续向（）查找。


    正确答案:查找成功；左子树；右子树

  • 第20题：

    一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。


    正确答案:O（1）；O（n）

  • 第21题：

    对于一个具有n个结点的单链表中，在已知的结点后插入一个新结点的时间复杂度为（）在给定值为X的结点后插入一个新结点的时间复杂度为（）。


    正确答案:O(1)；O（n）

  • 第22题：

    填空题
    一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。

    正确答案： O（1）,O（n）
    解析： 在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο（1）；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο（n）。

  • 第23题：

    填空题
    从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明（），若元素的值小于根结点的值，则继续向（）查找，若元素的值大于根结点的值，则继续向（）查找。

    正确答案： 查找成功,左子树,右子树
    解析： 暂无解析

  • 第24题：

    填空题
    对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为（），在给定值为x的结点后插入一个新结点的时间复杂度为（）

    正确答案： O（1）,O（n）
    解析： 暂无解析

相关内容