C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s

20．如果最常用的操作是取第i个结点及其前驱，则采用 D 存储方式最节省时间。

A．单链表 B．双链表 C．单循环链表 D． 顺序表

21．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B 。

A．O（1） B．O（n） C．O（n2） D．O（nlog2n）

22．在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C．在单链表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素

23．与单链表相比，双链表的优点之一是 D 。 A．插入、删除操作更简单 B．可以进行随机访问

C．可以省略表头指针或表尾指针 D．顺序访问相邻结点更灵活

5

24．如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 B 。 A．只有表头指针没有表尾指针的循环单链表 B．只有表尾指针没有表头指针的循环单链表 C．非循环双链表 D．循环双链表

25．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为： A 。

A．n – i + 1 B．n – i C．i D．i – 1

26．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 C 。

A．顺序表 B． 用头指针表示的循环单链表 C．用尾指针表示的循环单链表 D．单链表

27．下述哪一条是顺序存储结构的优点？ C 。

A插入运算方便 B可方便地用于各种逻辑结构的存储表示 C存储密度大 D删除运算方便

28．下面关于线性表的叙述中，错误的是哪一个？ B 。 A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作。

6

C线性表采用链式存储，不必占用一片连续的存储单元 D线性表采用链式存储，便于进行插入和删除操作。

29．线性表是具有n个 B 的有限序列。

A．字符 B．数据元素 C．数据项 D．表元素

30．在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是 A 。

A．访问第i（1<=i<=n）个结点和求第i个结点的直接前驱（1

31．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 C 。

A．O(0) B．O(1) C．O(n) D．O(n2)

32．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为 C 。

A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)

33．线性表（a1,a2, … ,an）以链式方式存储，访问第i位置元素的时间复杂度为 C 。

7

A．O(0) B．O(1) C．O(n) D．O(n2)

34．单链表中，增加一个头结点的目的是为了 C 。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方面运算的实现 D．说明单链表是线性表的链式存储

35．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是 B 。 A．p->next=s；s->next=p->next B． s->next=p->next ；p->next=s; C．p->next=s；p->next=s->next D．p->next=s->next；p->next=s

36．线性表的顺序存储结构是一种 A 。

A．随机存取的存储结构 B．顺序存取的存储结构 C．索引存取的存储结构 D．Hash存取的存储结构

37．栈的特点是 B ，队列的特点是 A 。 A．先进先出 B．先进后出

38．栈和队列的共同点是 C 。

A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点

39．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。 A．edcba B．decba C．dceab D．abcde

8