数据结构第二章
线性表习题含答案
说明：顺序存储的线性表称为向量。
一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。
A) 110 B) 108 C) 100 D) 120
线性结构通常采用的两种存储结构是__①A___。
A) 顺序存储结构和链式存储结构B) 散列方式和索引方式
C) 链表存储结构和数组D) 线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.
A) head==NULL B) head->next==NULL
C) head->next==head D) head!=NULL
带头结点的单链表head为空的判定条件是__①B___。
A) head==NULL B) head->next==NULL
C) head->next==head D) head!=NULL
非空的循环链表head的尾结点（由p所指向）满足__①_C__。
A) p->next==NULL B) p==NULL
C) P->next==head D) p==head
在循环双链表的p所指结点之后插入s所指结点的操作是___①_C_。
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;
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点, 则执行__①c___。
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;
在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行__①b___。
A) s->next=p; p->next=s; B) s->next=p->next; p->next=s;
C) s->next=p->next; p=s; D) p->next=s; s->next=p;
在一个单链表中，若删除p所指结点的后续结点，则执行__①_a__。
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;
10,假设双链表结点的类型如下：
typedef struct linknode
{
int data,/*数据域*/
struct linknode * llink; /*llink是指向前驱结点的指针域*/
struct linknode * rlink; /*rlink是指向后续结点的指针域*/
} bnode
要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，其算法是__①_c__。
q->rlink=p; q->llink=p->llink; p->llink=q; p->llink->rlink=q;
p->llink=q; q->llink=p; p->llink->rlink=q; q->llink=p->llink;
q->llink=p->llink; q->rlink=p; p->llink->rlink=q; p->llink=q;
以上都不对,
12,从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较
__①_d__个结点。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__①_b__。A) O(1) B) O(n) C) O(n2) D) O(nlog2n)
给定有n个元素的向量，建立一个有序单链表的时间频度是__①_d__。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
二.填空题(将正确的答案填在相应的空中)
单链表是_线性表____的链接存储表示。
向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动__n-i___个元素。
可以使用_二叉链表____表示树形结构。
在双链表中，每个结点有两个指针域，一个指向__直接前驱___，另一个指向_直接后继____。在一个单链表中的p所指结点之前插入一个s所指结点时，可执行哪些操作_____。
在一个单链表中删除p所指结点时，应执行的操作_____。
带有一个头结点的单链表head为空的条件是head->next==NULL_____。
在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_p->next______和p->next=_s________的操作。
9,非空的循环链表head的尾结点（由p所指向），满足条件__p->next=head___。
10,对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__o(1)___；在给定值为x的结点后插入一个新结点的时间复杂度是_o(n)____。
栈和队列个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是__c___。
A) edcba B) dceba C) dceab D) abcde
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi 为__c___。
A) i B) n-i C) n-i+1 D) 不确定
判定一个栈ST（最多元素为m0）为空的条件是_b____。
A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0
判定一个栈ST（最多元素为m0）为栈满的条件是_d____。
A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0
栈的特点是__①b___，队列的特点是__②_a__。
A) 先进先出B) 先进后出在以下的叙述中，正确的是__①_c__。
A) 线性表的线性存储结构优于链表存储结构B) 栈的操作方式是先进先出
C) 二维数组是其数据元素为线性表的线性表D) 队列的操作方式是先进后出一个队列的
