1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__  __。
     A. 110      B. 108     C. 100    D. 120
2. 线性表的顺序存储结构是一种__ _的存储结构，而链式存储结构是一种__  _的存储结构。
A．随机存取     B．索引存取   C．顺序存取   D．散列存取
3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__  _。
A. 正确              B. 不正确
4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__  _。
A. 必须是连续的      B. 部分地址必须是连续的
C. 一定是不连续的    D. 连续或不连续都可以
5. 在以下的叙述中，正确的是__  _。
A. 线性表的顺序存储结构优于链表存储结构
B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构
6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__  _。
A. 正确           B. 不正确
7. 不带头结点的单链表head为空的判定条件是____。
A. head= =NULL              B. head->next= =NULL
C. head->next= =head          D. head!=NULL
8. 带头结点的单链表head为空的判定条件是____。
A. head= =NULL                B. head->next= =NULL
C. head->next= =head          D. head!=NULL
9. 非空的循环单链表head的尾结点（由p所指向）满足____。
A. p->next= =NULL          B. p= =NULL
C. p->next= =head            D. p= =head     
    10. 在双向循环链表的p所指结点之后插入s所指结点的操作是____。
A. p->right=s;  s->left=p;  p->right->left=s;  s->right=p->right;
B. p->right=s;  p->right->left=s;  s->left=p;  s->right=p->right;
C. s->left=p;  s->right=p->right;  p->right=s;  p->right->left=s;
D. s->left=p;  s->right=p->right;  p->right->left=s;  p->right=s;
    11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s->next=p->next;  p->next=s;    B. p->next=s->next;  s->next=p;
B. q->next=s;   s->next=p;        C.  p->next=s;   s->next=q;
12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A.  s->next=p;  p->next=s;      B. s->next=p->next;  p->next=s;
C.  s->next=p->next;  p=s;      C. p->next=s;  s->next=p;
13. 在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next；   B. p= p->next;  p->next= p->next->next；
C. p->next= p->next;          D. p= p->next->next；
14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。
A. n        B. n/2        C. (n-1)/2           D. (n+1)/2
    15. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__   __。
A. O(1)     B. O(n)       C. O (n2)         D. O (nlog2n)
    16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是__    __。
A. O(1)）         B. O(n)        C. O (n2)         D. O (n*log2n)
 

 填空题（将正确的答案填在相应的空中）

1. 单链表可以做__   __的链接存储表示。
2. 在双链表中，每个结点有两个指针域，一个指向____  __，另一个指向___ __。
3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：
q=head;
while (q->next!=p)  q=q->next;
s= new  Node;   s->data=e;
q->next=     ;    //填空
s->next=     ;    //填空
4. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：
q= p->next;
p->next= _   ___;   //填空
delete         ;    //填空
5. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__   __和p->next=____的操作。
    6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__    __；在给定值为x的结点后插入一个新结点的时间复杂度是__    __。
 

江苏农信社招聘网   习题答案

  2.1    1. B    2. A, C   3. B    4. D    5. C    6. A   7. A    8. B
          9. C    10. D   11.B     12.B    13.A     14.D     15.B    16.C
  2.2     1. 线性结表            2. 前驱结点、后继结点
          3.  s, p                4.  q->next,  q
          5.  p->next, s           6.   O (1)  , O (n)