单项选择题(2012北京工业大学)

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

A、将n个元素按照从小到大的顺序重新排列

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

C、访问第i个元素(1≤i≤n)

D、删除第i个元素(1≤i≤n)

答案解析

C

【解析】

顺序表支持随机访问,其时间复杂度和问题规模n无关,即为O(1);

插入和删除算法和操作位置有关,时间复杂度为O(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个【 】的有限序列。

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

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

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

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

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

在非空双向循环链表中q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步:p->llink=q;p->rlink=q->rlink;q->rlink=p;第4步应该是____________________;(写出该步对应的语句)。

已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->rlink=q且q->llink=p),请写出删除q所指结点的程序段。