数据结构与算法-考研试题(北京工业大学 2011 顺序表)

单项选择（2011北京工业大学）

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

A、n

B、(n-1)/2

C、(n+1)/2

D、n/2

答案解析

D

【解析】

平均概率条件下，每个位置插入的概率都是1/(n+1)；在第i个位置插入时，需要移动的数据元素个数为n-i+1（1≤i≤n+1），所以平均移动元素的个数为（1+2+...+n）/(n+1)=n/2.

讨论

顺序表

表长为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的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为_______，删除一个元素需要移动元素的平均个数为_______。供选择的答案：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的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

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

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

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

双向链表的优势是____________________。

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

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

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

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