数据结构(线性表习题含答案)

《数据结构(线性表习题含答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第二章线性表习题含答案说明：顺序存储的线性表称为向量。一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。A)110B)108C)100D)120线性结构通常采用的两种存储结构是__①A___。A)顺序存储结构和链式存储结构B)散列方式和索引方式C)链表存储结构和数组D)线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.A)head==NULLB)head->next==NULLC)head->next==headD)head!=NULL带头结点的单链表head为空的判定条件是

2、__①B___。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在循环双链表的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

3、->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所指结点

4、不是最后结点，在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,假设双链表结点的类型如下：typedefstructlinknode{

5、intdata,/*数据域*/structlinknode*llink;/*llink是指向前驱结点的指针域*/structlinknode*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

6、->rlink=p;p->llink->rlink=q;p->llink=q;以上都不对,12,从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较__①_d__个结点。A)nB)n/2C)(n-1)/2D)(n+1)/2一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__①_b__。A)O(1)B)O(n)C)O(n2)D)O(nlog2n)给定有n个元素的向量，建立一个有序单链表的时间频度是__①_d__。A)nB)n/2C)(n-1)/2D)(n+1)/2二.填空题(将正确的答案填在相应的空中)单链表是_线性表____

7、的链接存储表示。向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动__n-i___个元素。可以使用_二叉链表____表示树形结构。在双链表中，每个结点有两个指针域，一个指向__直接前驱___，另一个指向_直接后继____。在一个单链表中的p所指结点之前插入一个s所指结点时，可执行哪些操作_____。在一个单链表中删除p所指结点时，应执行的操作_____。带有一个头结点的单链表head为空的条件是head->next==NULL_____。在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_p