算法与数据结构--张乃孝-前三章习题课.ppt

《算法与数据结构--张乃孝-前三章习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、首元结点、头结点、头指针的区别习题选讲栈与队列树与二叉树首元结点、头结点、头指针的区别首元结点：链表中存储线形表中第一个数据元素的结点头结点：在链表首元结点之前附设一个结点。该结点的数据域不存储数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针：是指向链表中第一个结点（头结点或首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的头指针为空。2.1单项选择题1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_

2、___。A.110B.108C.100D.1202.线性表的顺序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。A．随机存取B．索引存取C．顺序存取D．散列存取3.线性表的逻辑顺序与存储顺序总是一致的，这种说法___。A.正确B.不正确4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以BACBD5.在以下的叙述中，正确的是___。线性表的顺序存储结构优于链表存储结构线性表的顺序存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储

3、结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构优于顺序存储结构6.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法___。A.正确B.不正确7.不带头结点的单链表head为空的判定条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL8.带头结点的单链表head为空的判定条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULLCAAB9.非空的循环单链表head的尾结点（

4、由p所指向）满足____。A.p->next==NULLB.p==NULLC.p->next==headD.p==head10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。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=

5、p;s->right=p->right;p->right->left=s;p->right=s;11.在一个单链表中，已知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;CDC12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。A.s->next=p;p->next=s;B.s->next=p

6、->next;p->next=s;C.s->next=p->next;p=s;C.p->next=s;s->next=p;13.在一个单链表中，若删除p所指结点的后续结点，则执行____。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；14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。A.nB.n/2C.(n-1)/2D.(n+1)/2BAD15.在一个具有n个结

7、点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)1.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.C12.B13.A14.D15.BB首元结点、头结点、头指针的区别首元结点：链表中存储线形表中第一个数据元素的结点头结点：在链表首元结点之前附设一个结点。该结点的数据域不存储数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针：是指向链表中第一个结点（头结点或首元结点）的指针。若链表中附设头结点，则不管线性表是否为

8、空表，头指针均不为空，否则表示空表的头指针为空。linklistcreater(){charc