《数据结构线性表习题.docx》由会员分享，可在线阅读，更多相关《数据结构线性表习题.docx（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构线性表习题第二章作业题1求单链表中当前结点的后继和前驱的时间复杂度分别是（）AO（n）和O（1）BO（1）和O（1）CO（1）和O（n）DO(n)和O（n）2非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（）Arear-next= =head Brear-next-next= =headChead-next= =rear Dhead-next-next= =rear3在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且aA插入B删除C排序D定位5.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一
2、个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( ) A.q-next=s-next；s-next=p； B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；6若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）A无头结点的双向链表B带尾指针的循环链表C无头结点的单链表D带头指针的循环链表7.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）A.访问第i个元素的前驱（1i）B.在第i个元素之后插入一个新元素(n1)iC.删除第i个元素(n)i
3、1D.对顺序表中元素进行排序8.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作_。8链式存储结构的特点是借助_来表示数据元素之间的逻辑关系。10在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_。11假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是_ _；_。12已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2,a3,a4,a n）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：（1）写出执行下列程序段后的顺序表A中的数据元素；（2）简要叙述该程序段的功能。if(head-n
4、ext!=head)p=head-next;A-length=0;while(p-next!=head)p=p-next;A-dataA-length +=p-data;if(p-next!=head)p=p-next;(1)(2)13已知链串的存储结构描述如下：#define NodeSize 4typedef struct Node char data NodeSize;struct Node * next; * LinkStr;阅读下列算法，并回答问题：（1）t1和t2的串值分别为Chinese和China时，写出f31(t1,t2)的返回值；（2）t1和t2的串值分别为Japan和Ja
5、panese时，写出f31(t1,t2)的返回值；（3）t1和t2的串值都为string时，写出f31(t1,t2)的返回值；（4）简述函数f31的功能。inf f31(LinkStr t1,LinkStr t2)/串值以0为结束符int i;while (1)for (i=0;iif (t1-datai= =0&t2-datai= =0return 0;if(t1-datai= =0)return 1;if(t2-datai= =0)return 1;if(t1-datait2-dataireturn 1;if(t1-datait1=t1-next;t2=t2-next;(1)(2)(3)(
6、4)14已知用有序链表存储整数集合的元素。阅读算法f30，并回答下列问题：（1）写出执行f30（a,b）的返回值，其中a和b分别为指向存储集合2，4，5，7，9，12和2，4，5，7，9的链表的头指针；（2）简述算法f30的功能；（3）写出算法f30的时间复杂度。int f30(LinkList ha,LinkList hb)/LinkList是带有头结点的单链表/ha和hb分别为指向存储两个有序整数集合的链表的头指针LinkList pa,pb;pa=ha-next;pb=hb-next;while(pa & pb & pa-data=pb-data) pa=pa-next;pb=pb-next;if(pa=NULL & pb=NULL) return 1;else return 0;(1)(2)(3)15假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct nodeDataType data;struct node *nextLinkNode, *LinkList;编写算法，从有序表A中删除所有和有序表B中元素相同的结点。16.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A.head= =NULLB.headnext= =NULLC.head!=NULLD.headnext= =head
