数据结构与算法-考研试题(中科院软件所 2001 线性表)

单项选择（2001中科院软件所）

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

A、所有的操作算法实现简单

B、便于随机存取

C、便于插入和删除

D、便于利用零散的存储器空间

答案解析

C

【解析】

随机存取的前提是每个元素可根据逻辑地址计算物理地址，显然这是顺序表的特点，链表不支持。但链表更便于插入和删除操作，因为基于链表的插入和删除不需要移动数据，只需要修改指针即可。

讨论

数据结构与算法

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

算法的空间复杂度是指【】

从逻辑上可以把数据结构分为【】两大类。

下面说法错误的是【】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低

下面关于算法说法错误的是【】

一个算法应该是【】

算法必须具备【】这三个特性。

计算机算法指的是【】

算法的时间复杂度取决于【】

算法的计算量的大小称为计算的【】

线性表

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

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

线性表是具有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

双向链表的优势是____________________。

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

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

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

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

#tts_2#

#tis_2#