数据结构作业第2章.doc

《数据结构作业第2章.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表1.填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。⑶设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。⑷单链表中设置头结点的作用是（）。⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。⑺一个具有n个结点的单链表，在指针p

2、所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。⑻可由一个尾指针唯一确定的链表有（）、（）、（）。2.选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。A随机存取B顺序存取C索引存取D散列存取⑵线性表采用链接存储时，其地址（）。A必须是连续的　　　　　B部分地址必须是连续的C一定是不连续的　　　D连续与否均可以⑶单循环链表的主要优点是（）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表；C已知某个结点的位置后，能够容易找到它的直接前趋；D在进行插入、删除操作时，

3、能更好地保证链表不断开。⑷链表不具有的特点是（）。A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A顺序表B单链表C双向链表D单循环链表⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。A单链表B带头指针的单循环链表C双向链表D带尾指针的单循环链表⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。A单链表B循环双向链

4、表C单循环链表　　D带尾指针的单循环链表⑻在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。AO(1)BO(n)CO(n2)DO(nlog2n)⑼对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。AO(1)BO(n)CO(n2)DO(nlog2n)⑽使用双向链表存储线性表，其优点是可以（）。A提高查找速度B更方便数据的插入和删除C节约存储空间D很快回收存储空间⑾在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。As->next=p->next;p->next=s;Bq->nex

5、t=s;s->next=p;Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;⑿在循环双向链表的p所指结点后插入s所指结点的操作是（）。Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;Ds->prior=p;s->next=p->next;

6、p->next->prior=s;p->next=s3.判断题⑴线性表的逻辑顺序和存储顺序总是一致的。⑵线性表的顺序存储结构优于链接存储结构。⑶设p，q是指针，若p=q，则*p=*q。⑷线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。⑸在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。⑴若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。⑵如果n个线性表同时并存，并且在处理过程中各表的长度会

7、动态发生变化。⑶描述一个城市的设计和规划。5．算法设计思考⑴设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环左移k个位置。⑵已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。⑶试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。⑷试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。⑸假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。

8、⑹已知一单链表中的数据元