数据结构线性表习题

1、第二章作业题1 .求单链表中当前结点的后继和前驱的时间复杂度分别是（）A. 0 (n)和 0 (1)B. 0 (1 )和 0( 1)C. 0 (1 )和 0 (n)D. 0(n)和 0 (n)2 .非空的单循环链表的头指针为head,尾指针为rear,则下列条件成立的是（)A. rear->next= =headB. rear->next->next= =headC. head->next= =rearD. head->next->next= =rear3.在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b,且a<b

2、，编写算法删除链表L中元素值大于a且小于b的所有结点。4 在线性表的下列运算中，不.改变数据元素之间结构关系的运算是（）A 插入B.删除C.排序D .定位5已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在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

3、->next;6 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）A .无头结点的双向链表B.带尾指针的循环链表C.无头结点的单链表D .带头指针的循环链表7在下列对顺序表进行的操作中，算法时间复杂度为0（1）的是（）A. 访问第i个元素的前驱（1<r<n ）B. 在第i个元素之后插入一个新元素（1心岂n ）C. 删除第i个元素（1n ）D. 对顺序表中元素进行排序8在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作。&链式存储结构的特点是借助 来表示数据元素之间的逻辑关系。10. 在一个长度为 n的单链表L中，删除链

4、表中*p的前驱结点的时间复杂度为 。11. 假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是; 。12 .已知head为带头结点 的单循环链 表的头指针，链表中的 数据元素依 次为（a1 , 32,a3,a4,an） ,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：（1） 写出执行下列程序段后的顺序表A中的数据元素；（2）简要叙述该程序段的功能。if(head->n ext!=head)p=head->n ext;A->le ngth=O;while(p->n ext!=head)p=p->n ext;A->

5、;dataA->le ngth +=p->data;if(p->n ext!=head)p=p->n ext;(1)13. 已知链串的存储结构描述如下：#define NodeSize 4typedef struct Node char data NodeSize;structNode * n ext; * Li nkStr;阅读下列算法，并回答问题：(1) t1和t2的串值分别为Chinese''和 China时，写出f31(t1,t2)的返回值；(2) t1和t2的串值分别为"Japan"和"Japanes6'时

6、，写出f31(t1,t2)的返回值;(3) t1和t2的串值都为string"时，写出f31(t1,t2)的返回值；(4 )简述函数f31的功能。inf f31(L in kStr t1,L i nkStr t2)/串值以0'为结束符int i;while (1)for (i=0;i<NodeSize;i+)if (t1->datai= = ' 0 ' &&t2->datai= =' 0' return 0;if(t1->datai= = ' 0' )return -;if(t2->

7、datai= = ' 0' )return 1;if(t1->datai>t2->dataireturn 1;if(t1->datai<t2->dataireturn -;t1=t1-> next;t2=t2-> next; (1)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(Li nk

8、List ha,L in kList hb)/LinkList是带有头结点的单链表/ha和hb分别为指向存储两个有序整数集合的链表的头指针Lin kList pa,pb;pa=ha->n ext;pb=hb->n ext;while(pa && pb && pa->data=pb->data)pa=pa->n ext;pb=pb->n ext;if(pa=NULL && pb=NULL) return 1;else return 0;(1)15. 假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedef struct no deDataType data;struct node *n extLi nkNode, *Li nkList;编写算法，从有序表A中删除