单项选择(1999北京航空航天大学)

若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为【 】。(1≤i≤n+1)

A、O(0)

B、O(1)

C、O(n)

D、O(n2)

答案解析

C

【解析】

顺序存储结构下线性表插入算法的时间复杂度只与线性表长度有关。

讨论

表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为_______,删除一个元素需要移动元素的平均个数为_______。供选择的答案:A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

在含有n个元素的顺序表中,算法时间复杂度为O(1)的操作是【 】

设A是一个线性表(a1,a1,...,an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(0≤i≤n-1)的概率为,则平均每插入一个元素所要移动的元素个数又是多少?

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

含有n个元素的线性表采用顺序存储方式时,对其运算速度最快的操作是【 】。

含有n个元素的线性表采用顺序存储,等概率删除其中任一个元素,平均需要移动【 】个元素。

对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个元素平均需要移动的元素数为【 】。

顺序表存储方式只能用于存储线性结构。

假设线性表的长度为n,且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时,插入一个数据元素需要移动元素的平均个数为【 】。

表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为_______,删除一个元素需要移动元素的平均个数为_______。供选择的答案:A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

在含有n个元素的顺序表中,算法时间复杂度为O(1)的操作是【 】

设A是一个线性表(a1,a1,...,an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(0≤i≤n-1)的概率为,则平均每插入一个元素所要移动的元素个数又是多少?

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

含有n个元素的线性表采用顺序存储方式时,对其运算速度最快的操作是【 】。

含有n个元素的线性表采用顺序存储,等概率删除其中任一个元素,平均需要移动【 】个元素。

对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个元素平均需要移动的元素数为【 】。

顺序表存储方式只能用于存储线性结构。

假设线性表的长度为n,且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时,插入一个数据元素需要移动元素的平均个数为【 】。

线性表的静态链表存储结构与顺序存储结构相比优点是【 】

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

下列描述中,正确的是【 】

线性表是具有n个【 】的有限序列。

线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。【 】

双向链表的优势是____________________。

将下图所示的s所指点加到p所指点之后,其语句应为【 】

现有非空双向链表 L,其结点结构为:prer|data|next。prer 是指向前直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点( 非尾结点) 之后插入指针 s 指向的新结点, 则在执行了语句序列: “s->next=p->next;p->next=s”后,还要执行【 】

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转,即将原链表看成由两部分组成,已经完成逆置的部分和未完成逆置的部分,令s指向未逆置部分的第一个结点,并将该结点插入已完成部分的表头(头结点之后),直到全部结点的指针域都修改完成为止。例如,某单链表如图所示,逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下:typedef struct Node{ int data, struct Node *next;}Node, *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置, headptr为头指针 LinkList p,s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

线性表选用顺序存储结构表示的适用场合是____________________。