等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。A．nB．(n-1)/2C．n/2D．(n+1)/2

题目

等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。

A．n

B．(n-1)/2

C．n/2

D．(n+1)/2

相似考题

1.在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？A．线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点B．线性表按链接方式存储，在线性表的第100个结点后面插入一个新结点C．线性表按顺序方式存储，删除线性表的第900个结点D．线性表按链接方式存储，删除指针P所指向的结点

2.在顺序表的某些位置插入和删除结点时不需移动其它结点。()此题为判断题(对，错)。

3.在包含1000个元素的线性表中实现如下各运算，所需的执行时间最长的是( )。A．线性表按顺序方式存储，性表的第100个结点后面插入一个新结点B．线性表按链接方式存储，性表的第100个结点后面插入一个新结点C．线性表按顺序方式存储，删除线性表的第900个结点D．线性表按链接方式存储，删除指针P所指向的结点

4.在任何情况下,顺序表中进行结点的插入操作时都不需要移动结点。()此题为判断题(对，错)。

参考答案和解析
(n-1)/2
更多“等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。”相关问题

  • 第1题：

    在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长?

    A)线性表按顺序方式存储，性表的第100个结点后面插入一个新结点

    B)线性表按链接方式存储，性表的第100个结点后面插入一个新结点

    C)线性表按顺序方式存储，删除线性表的第900个结点

    D)线性表按链接方式存储，删除指针P所指向的结点


    正确答案：A
    由于线性表采用的是顺序存储方式，用存储单元的邻接性体现线性表元素间的一维顺序关系，因此对线性表进行插入和删除运算时，可能需要移动大量的结点，以保持这种物理和逻辑的一致性。对于选项A)，后面的900个结点都要往后移动，对于选项C)，后面的100个结点都要往前移动。而对于线性表按链接方式存储，当进行插入与删除操作时，只改变相应的指针即可，所以比较4个选项的操作可易知，选项A)所需要的执行时间最长。 

  • 第2题：

    在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是()。A.访问第i个结点(1<=i<=n)和求第i个结点

    在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是()。

    A.访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)

    B.在第i个结点之后插入一个新结点(1<=i<=n)

    C.删除第i个结点(1<=i<=n)

    D.将n个结点从小到大排序


    正确答案：A

  • 第3题：

    对于长度为n的顺序存储的线性表,访问结点和插入、删除结点的平均时间复杂度为()。

    A.O(0)

    B.O(1)

    C.O(n)

    D.O(n2)


    正确答案：C

  • 第4题：

    在包含1000个元素的线性表中实现如下各运算，（ ）所需的执行时间最长。A．线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点B．线性表按链接序方式存储，在线性表的第100个结点后面插入一个新结点C．线性表按顺序方式存储，删除线性表的第900个结点D．线性表按链接方式存储，删除指针p所指向的结点


    正确答案：A
    线性表按顺序方式存储，对于插入和删除操作会比较麻烦，A项中要在线性表的第100个节点后面插入一个新节点，需要移动后面900元素的位置，因此执行的时间相对来说是最长的。

  • 第5题：

    在包括1000个元素的线性表示实现如下各运算，（ ）所需要的执行时间最长。A．线性表按顺序方式存储，在线性表的第10个结点后面插入一个新结点B．线性表按链接方式存储，在线性表的第10个结点后面插入一个新结点C．线性表按顺序方式存储，删除线性表的第990个结点D．线性表按链接方式存储，删除指针P所指向的结点


    正确答案：A
    根据顺序存储的特点，A项需移动990个元素，所以其花费的时间最长。

  • 第6题：

    在包含1000个元素的线性表中实现如下各运算，______所需的执行时间最长。

    A．线性表按顺序方式存储，性表的第10个结点后面插入一个新结点

    B．线性表按链接方式存储，性表的第10个结点后面插入一个新结点

    C．线性表按顺序方式存储，删除线性表的第990个结点

    D．线性表按链接方式存储，删除指针P所指向的结点


    正确答案：A
    解析：本题考查点是线性表的基本操作。选项A：线性表按顺序方式存储，性表的第10个结点后面插入一个新结点，需要将第11个元素到第1000个元素依次向后移动一个位置，然后在第11个元素位置处插入新结点，因此要移动990个元素，插入一个元素。选项B：线性表按链接方式存储，性表的第10个结点后面插入一个新结点，只需要修改新结点的指针域和第10个结点的指针域就可以实现，无须移动元素。选项C：线性表按顺序方式存储，删除线性表的第990个结点，需要将第991个元素到第1000个元素依次向前移动一个位置，因此要移动10个元素。选项D：线性表按链接方式存储，删除指针P所指向的结点，只需要修改指针P所指向的指针域就可以实现，无须移动元素。因此，选项A所需的执行时间最长。

  • 第7题：

    有n个结点的线性表采用顺序表作为存储结构，要在第i(l≤i≤n+l)个位置插入一个新结点时，需要移动的结点个数为【】

    A．i

    B．n-i

    C．i-n

    D．n-i+l


    正确答案：D
    [解析]因为采用顺序表作为存储结构，要插入一个新结点，就要为这个新结点准备一个位置， 要在第i个位置上插入，就要把第i个位置空出来，所以前面i-l上位置不用动，剩下的结点都要向后移动，共需移动n-(i-1)个结点．

  • 第8题：

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


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

  • 第9题：

    在等概率情况下，顺序表的插入操作要移动（）结点。

    • A、全部
    • B、一半
    • C、三分之一
    • D、四分之一

    正确答案:B

  • 第10题：

    在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。

    • A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
    • B、在第i个结点后插入一个新结点（1≤i≤n）
    • C、删除第i个结点（1≤i≤n）
    • D、将n个结点从小到大排序

    正确答案:A

  • 第11题：

    用顺序查找法对具有n个结点的线性表查找一个结点所需的平均查找时间为（）。

    • A、O（n*（以2为底n的对数））
    • B、O（n）
    • C、O（以2为底n的对数）
    • D、O（n*n）

    正确答案:B

  • 第12题：

    单选题
    等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。
    A

    n

    B

    （n-1）/2

    C

    n/2

    D

    （n+1）/2


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

  • 第13题：

    在一个具有n个结点的有序顺序表中插入一个新结点并仍然保持有序的时间复杂度是()

    A、O(1)

    B、O(n)

    C、O(n2)


    参考答案：B

  • 第14题：

    从有n个结点的顺序表中删除一个结点平均需要移动的结点个数是【 】。


    正确答案：n/2
    n/2 解析：本题主要考查了顺序表的相关知识。 从有n个结点的顺序表中删除一个结点平均需要移动的结点个数是n/2。

  • 第15题：

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

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D

  • 第16题：

    设顺序表中结点个数为n，向第i个结点后面插入一个新结点，设向每个位置插入的概率相等，则在顺序表中插入一个新结点平均需要移动的结点个数为( )。

    A．(n-1)/2

    B．n/2

    C．n

    D．(n+1)/2


    正确答案：B
    解析：若顺序表中结点个数为n，且往每个位置插入的概率相等，则插入一个结点平均需要移动的结点个数为n/2。

  • 第17题：

    在包括1000个元素的线性表中实现如下各运算，哪一个所需要的执行时间最长?

    A．线性表按顺序方式存储，性表的第10个结点后面插入一个新结点

    B．线性表按链接方式存储，性表的第10个结点后面插入一个新结点

    C．线性表按J顷序方式存储，删除线性表的第990个结点

    D．线性表按链接方式存储，删除指针P所指向的结点


    正确答案：A
    解析：对于A，由于是在第10个结点后插入—个新结点，所以后面的990个数据都要向后移动；对于B，在链表中进行这个操作，只需从头结点开始找10次得到第10个结点，然后修改结点的指针即可；对于C，顺序表中删除第990个结点，需要向前移动最后10个结点；对于D，在链式方式下，删除一个结点，需要从头指针开始找，找到待删结点的前驱结点指针，这个查找次数和待删结点的序号是有关系的，平均值应该是500。通过上面的比较可以看出，本题正确答案为选项A。

  • 第18题：

    有n个结点的线性表采用顺序表作为存储结构，要删除第i(l≤i≤n+1)个结点时，需要移动的结点个数为【】

    A．i

    B．n-i

    C．i-n

    D．n-i+l


    正确答案：B
    [解析]因为采用顺序表作为存储结构，要删除一个结点，就要将其后的n-i个结点向前移动．

  • 第19题：

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

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

    答案：D
    解析：

  • 第20题：

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

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

    正确答案:C

  • 第21题：

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


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

  • 第22题：

    等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。

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

    正确答案:C

  • 第23题：

    单选题
    在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。
    A

    访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

    B

    在第i个结点后插入一个新结点（1≤i≤n）

    C

    删除第i个结点（1≤i≤n）

    D

    将n个结点从小到大排序


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

  • 第24题：

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

    n/2

    B

    n

    C

    （n+1）/2

    D

    （n-1）/2


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

相关内容