《数据结构》习题集第2章线性表.doc

第2章线性表选择题表长为N的顺序表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均次数为(E),删除一个元素需要移动的元素个数为(A)。A.(N-1)/+-.(N+1)/2G.(N-2)/2线性表是具有N个(C)的有限序列。A、表元素B、字符C、数据元素D、数据项E、信息“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是(B)。A、正确的B、错误的C、不一定,与具体结构有关。线性表采用链式存储结构时,要求内存中可用存储单元的地址(D)。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。带头结点的单链表为空的判定条件是(B)。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL不带头结点的单链表head为空的判定条件是(A)。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL非空的循环单链表head的尾结点P满足(C)。A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)在一个单链表中,若删除P所指结点的后继结点,则执行(A)。A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;在一个单链表中,若在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;在一个单链表中,已知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;假设双链表结点的类型如下:typedefstructlinknode{intdata;//数据域structlinknode*llink;//指向前趋结点的指针域structlinknode*rlink;//指向后继结点的指针域}bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中,能正确完成此要求的语句段是(D)。A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;B、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llinkC、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q;D、以上都不对如上题结点结构,如在此非空循环双向链表的结点p之后插入结点s的操作序列是(D)。A、p->rlink=s;s->