第二章
一选择题
1.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是( )
A.110
B.116
C.100
D.120
2. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。
A.64
B.63
C.63.5
D.7
3．在循环双链表的p所指接点之前插入s所指接点的操作是
A.p-> prior =s;s-> next t=p;p-> prior t->left=s;s-> prior =p-> prior;
B. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior;
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;
4．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。
A.n
B.n/2
C.(n-1)/2
D.(n+1)/2
5．线性表是具有n个（）的有限序列（n≠0）
A.表元素
B.字符
C.数据元素
D.数据项
6．非空的循环单链表head的尾结点（由P指向）满足
A. p->next=NULL
B. p=NULL
C. p->next=head
D.p=head
7．在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s 结点，则执行( )
A. s->next=p->next;p->next=s;
B.p->next=s->next;s->next=p;
C. q->next=s;s->next=p;
D.p->next=s;s->next=q;
8．已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为( )
A．[2*(n-1)+1]*d B.2*(n-1)*d C.[2*(n-1)-1]*d D.(n+1)*d
9．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n)
10．如果最常用的操作是提取第i个结点及其前驱，则采用( )存储方式最节省时间。
A．单链表 B.顺序表 C.循环链表 D.双链表
11．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n)之前插入一个新元素时，需要从后向前依次后移( )个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i
12．在一个长度为n的顺序存储线性表中，删除第i个元素(0≤i≤n-1)时，需要从后向
前依次前移( )个元素。
A.n-i
B.n-i+1
C. n-i-1
D.i
13．在单链表中删除结点的时间复杂度为( )
A.O(1)
B.O(n2 )
C.O(n) D(logn)
14．链表不具有的特点是( )。
A.可随机访问任一元素
B.插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
15．线性表L=(a1,a2,…an)，下列说法正确的是( )。
A.每个元素都有一个直接前驱和一个直接后继
B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是有小到大或者由大到小
D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。二填空题
1．写出循环链表L中某个结点*p为尾指针的条件______。
2．在一个带头节点的单向循环链表中，p指向尾节点的直接前驱，则指向头节点的指针head可用p表示为____________。
3．带头结点的单链表head为空的判定条件是______。
4．长度为0的线性表称为______。
5．在双链表中，删除p结点语句序列是______。
6．在单链表中，删除指针p所指结点的后继结点的语句是______。
7．已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_____ 。8．顺序表中逻辑上相邻的元素物理位置_____相邻，单链表中逻辑上相邻的元素物理位置______相邻。
9．线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_____。
10．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为C。
11．单链表是＿＿＿的链接存储表示。
12．在双链表中，每个结点有两个指针域，一个指向＿＿＿＿，另一个指向＿＿＿＿＿。三判断题
1.线性表采用链式存储结构时，其地址必须是连续的。（）
2.线性表中至少有一个元素（）
3.线性表中任何一个元素有且仅有一个直接前趋（）
4．线性表的长度是线性表所占用的存储空间的大小。（）
5．双循环链表中，任意一结点的后继指针均指向其逻辑后继。（）
6．线性表的唯一存储形式是链表。
