数据结构课后习题

1、网络工程2011级1班、计算机科学与技术 2011级2班算法与数据结构课后习题(第 2章)【课后习题】第2章线性表2011 级计科(网工)班 学号： 姓名：题号一一三四总分得分一、判断题(如果正确，在题号前打“寸'，否则打“ X”。每题2分，共10分)()1.线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。()2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。()3.如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。()4.线性表的逻辑顺序与物理顺序总是一致的。()5.线性表的长度是指它所占存储空间的大小。二、填空题(每空1.5分，共21分)

2、1. 从逻辑结构看，线性表是典型的 。2. 在一个长度为 n的向量中在第i (Ki< n+1)个元素之前插入一个元素时，需向后移动 个元素，算法的时间复杂度为 。3. 在一个长度为n的向量中删除第i (1 <i< n)个元素时，需向前移动 个元素，算 法的时间复杂度为 。4. 若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为 。删除其第i个元素的算法的时间复杂度为 。5. 线性表顺序存储结构的优点是可以实现,主要缺点6. 不带头结点的单链表 L为空的条件是 ,带头结点的单链表 L为空的条件是，带头结点的单循环链表L为空的条件是 。7.

3、两指针p和q,分别指向单链表的两个元素，p所指元素是q所指元素的前导的条件8.设双向循环链表中结点的结构为(data, prior, next)，若指针p指向该链表的某个结点，则有下面的关系： p->next->prior= = 。题号12345678910答案题号11121314151617181920答案2分，共40分）三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1.P和Q两个指针分别指向双向循环表 件是L的两个元素，P所指元素是Q所指元素的后继的条2.A.P= =QB.Q- > Next=PC.P- > Next=QD.Q- > PRIOR=

4、P指针P指向不带头结点的线性链表L的首元素的条件是（A.P= =LB.L- > Next=PC.P- > next=LD.P- > next=NULL第6页共5页B.L- > Next=P4.C.P- > next=L指针P指向单链表A.P= =LC.P- > next=LD.P- > next=NULLL的尾元素的条件是B.L- > Next=PD.P- > next=NULL3.指针p指向带头结点的单循环链表L的首元素的条件是（A. P= =L5.指针P所指的元素是双向循环链表L的尾元素的条件是A.P= =LB.P= =NULLC. P

5、- > next=LD. P- > prior=L6.在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的 时间复杂性量级为（）。A.0(1)B.0(n)C.0(nlog 2n)D.0(n 2)7.顺序存储的线性表（a1,a2, an）,在任一结点前插入一个新结点时所需移动结点的平均次 数为（）。A.nB.n/2C.n+1D.（n+1）/28.删除长度为n的顺序表的第i（1 < i< n）个位置上的元素，元素的移动次数为 （）A) i-1B) iC) n-iD) n-i+19. 在C语言中可用（）描述线性表。A、数组；B、指针；C10. 链表不

6、具有的特点是（）A）插入、删除不需要移动元素C）不必事先估计存储空间、数组或指针；D、结构B）可随机访问任一元素D）所需空间与线性长度成正比x的后继”的语句是（11. 在单链表中，指针p指向元素为x的结点，实现“删除A) p=p->next; B)p->next=p; C)p->next=p->next->next; D)p=p->next->next;12. 单链表的存储密度（A）大于1; B）等于1 ;C）不能确定；D）小于113. 非空的循环单链表first 的尾结点（由p所指向）满足：。A. p-> next = NULL ; B. p

7、= NULL ; C. p-> next = first ; D. p = first14. 下列静态链表没有设置空闲指针链，则其表示的线性表逻辑结构为（）。01234567,100abcdef,32516410,A、(c, a, b ,e, d, f,)； B、(c, a,b,e,d, f) ； C、(a,b,c, d ,e, f,)；D、(a,b,c, d, e, f)。）。（已知:15. 在下列线性表如下图所示中将结点P插入到Q结点之前采用的操作是（结点的前驱指针域为pre ,后继指针域为next ）。图1A、P->next=Q->next ; P->pre=P-

8、>next->pre ; P->next->pre=P->pre ; P->pre->next=P ;B、P->next=Q ; P->next->pre=P->pre ; P->pre->next=P ; P->pre=P->next->pre ;C、P->pre=P->next->pre ; P->next->pre=P->pre ; P->pre->next=P ; P->next=Q ;D、P->next=Q ; P->pre

9、=P->next->pre ; P->next->pre=P ; P->pre->next=P。16.设双向循环链表中结点的结构为( data, prior, next )，且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？A) p->next = s; s->prior = p; p->next->prior = s; s->next = p->next;B) p->next = s; p->next->prior = s; s->prior = p; s->

10、;next = p->next;C) s->prior = p; s->next = p->next; p->next = s; p->next->prior = s;D) s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;17. 下列说法正确的是（）。A. 线性表的逻辑顺序与存储顺序总是一致的B. 线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C. 线性表的顺序存储结构优于链式存储结构D. 每种数据结构都具有

11、插入、删除和查找三种基本运算18. 关于线性结构的特性描述不恰当是（）。A、有唯一个被称作“第一个”的数据元素；B、有唯一个被称作"最后一个”的数据元素；C、除最后一个之外，线性表中每个数据元素都有后继；D、栈、队列、串和数组也属于线性表。19.线性表（4*2,，an,an）中任一元素ai（i =0,1,2、，n）在（ ）中存储位置为L0C（a1）+（i）*l,其中LOC（aJ表示元素 a1的存储首地址，l为每一个元素占用的存储单元数。A、线性表逻辑结构；B、线性表存储结构；C、线性表链式存储结构；D、线性表顺序存储结构。20.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1

12、 ,则删除双链表中指针s所指结点的操作为（）。A.s- > tl- >r1=s-> tl;s-> rl- > tl=s- > rl;free(s);B.s- > tl- >rl=s-> rl;s-> rl- > tl=s- > tl;free(s);C.s- > rl=s-> tl-> rl;s-> tl=s- > rl- > tl;free(s);D.s- > tl=s-> tl-> rl;s-> rl=s- > rl- > tlfree(s);四、

13、算法分析与设计（请将答案填在下表对应位置。共 29分）第1题（7分）第2题（8分）第3题（8分）第4题（6分）；1、已知无头结点的单链表L,简述下列对L链表操作算法的功能。LinkList Demo(LinkList L) / L是无头结点单链表ListNode *Q,*P;if(L&&L->next)Q=L; L=L->next; P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L;/ Demo2、已知线性表的带头结点双向循环链表存储结构如下所示:typedef st

14、ruct DuLNodeElemType data; struct DuLNode *prior; Struct DuLNode *next;DuLNode , *DuLinkList ;请完成在带头结点的双向循环链表L中第i个位置之前插入元素e (K i v表长+1)算法:status ListInsert_DuL(DuLinkList&L , int I; ElemType e)(P=L ; j=0 ；while(p<>p->next)&&(j<i-1)p=p->next ; j+ ; if(p= =L)&&(i<

15、>1)|(j>i-1) return ERROR ;p=p->next;if(!(s=(DuLinkList)malloc(sizeof(DuLNode) rerurn ERROR ; = p ;s->prior=p->prior ; return OK ;/ListInsert_DuL3、设顺序表L是一个递增有序表，试写一算法，将 x插入L中，并使L仍是一个有序表。void InsertIncreaseList( Seqlist *L , Datatype x ) int i;if ( L->length>=ListSize)Error( “over

16、flow");for ( i=L -> length ; i>0 && L->data i ; i-)L->data i+1 = ® /比较并移动元素=x;4、有一个不带头结点的单链表，其头指针为 统计数据域的值为x的结点个数。int countx ( LinkList head, ElemType x)LinkList p; int n=0;while (p!=NULL) if (p->data= =x)head,其结点的数据域值可能相同，编写一个函数 return(n);网络工程2011级1班、计科2011级2班算法与数据结

17、构课后习题(第 2章)参考答案【课后习题】第2章 线性表（参考答案）2014-10-16第8页、判断题（如果正确，在题号前打“ 否则打“ X”。每题2分，共10分）1.2. X3. X 4. X 5. X、填空题（每空 1.5分，共21分）1. 从逻辑结构看，线性表是典型的线性结构。2. 在一个长度为n的向量中在第i （K i< n+1）个元素之前插入一个元素时，需向后移动n-i+1个元素，算法的时间复杂度为O（n） 。3. 在一个长度为n的向量中删除第i （1 <i < n）个元素时，需向前移动n-i个元素,算法的时间复杂度为O（n）。4.若长度为n的线性表采用链式存储结构

18、，在其第 i个结点前插入一个新的元素的算法的时 间复杂度为 O（n）。删除其第i个元素的算法的时间复杂度为O（n）。5.线性表顺序存储结构的优点是可以实现随机存取，主要缺点是：不利于插入或删除操作。6.不带头结点的单链表L为空的条件是_L=NULL_ ，带头结点的单链表L为空的条件是L->next=NULL，带头结点的单循环链表L为空的条件是 L->next=L 。7. 两指针p和q,分别指向单链表的两个元素，p所指元素是q所指元素的前导的条件是止> next=q 。8. 设双向循环链表中结点的结构为（ data, prior, next），若指针p指向该链表的某个结点，则有

19、下面的关系:p->next->prior= = p （或 p->prior->next ）。、单项选择（请将正确答案的代号填写在下表对应题号下面。每题 2分，共40分）题号12345678910答案BABDCBBCCB题号11121314151617181920答案CDCADDBCDB四、算法分析与设计（请将答案填在下表对应位置。共 29分）第1题（7分）将第一个结点摘卜链接到终端结点之后成为新的终端结点，而原来的第二个结点 成为新的开始结点，返回新链表的头指针第2题（8分） s->data=e s->next p->prior->next=s

20、p->prior=s第3题（8分）>x L->datai L->datai+1 L->length+第4题（6分） p=head; n+; p=p->next;【课后习题】第2章 线性表（参考答案）、判断题（如果正确，在题号前打“寸，否则打“ X”。每题2分，共10分）寸1.线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。x 2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。x 3.如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。x 4.线性表的逻辑顺序与物理顺序总是一致的。x 5.线性表的长度是指它所占存储空间

21、的大小。、填空题（每空 2分，共18分）1. 从逻辑结构看，线性表是典型的线性结构。2. 在一个长度为n的向量中在第i （K i< n+1）个元素之前插入一个元素时，需向后移动n-i+1个元素，算法的时间复杂度为O（n） 。3. 在一个长度为n的向量中删除第i （1 <i < n）个元素时，需向前移动n-i个元素,算法的时间复杂度为O（n）。4. 若长度为n的线性表采用链式存储结构，在其第 i个结点前插入一个新的元素的算法的时间复杂度为O（n）。删除其第i个元素的算法的时间复杂度为O（n）。5. 线性表顺序存储结构的优点是可以实现随机存取 ，主要缺点是：不利于插入或删除操作

22、。6. 不带头结点的单链表L为空的条件是 L=NULL ,带头结点的单链表 L为空的条件是L->next=NULL，带头结点的单循环链表L为空的条件是L->next=L 。7. 两指针p和q,分别指向单链表的两个元素，p所指元素是q所指元素的前导的条件是p- > next=q 。8. 设双向循环链表中结点的结构为（ data, prior, next），若指针p指向该链表的某个结点，则有下面的关系:p->next->prior= = p （或 p->prior->next ）。:、单项选择（请将正确答案的代号填写在下表对应题号下面。每题 2分，共40分

23、）1. P和Q两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（）。A. P= =QB.Q- > Next=P C.P-> Next=Q D.Q- > PRIOR=P2. 指针P指向不带头结点的线性链表L的首元素的条件是（）。A.P= =LB.L-> Next=PC.P- > next=LD.P-> next=NULL3. 指针p指向带头结点的单循环链表L的首元素的条件是（）。A.P= =LB.L-> Next=PC.P- > next=LD.P-> next=NULL4. 指针P指向单链表L的尾元素的条件是（）

24、。网络工程2011级1班、计科2011级2班算法与数据结构课后习题（第 2章）参考答案5.6.7.8.9.10.11.12.13.14.A、A.P= =LC.P- > next=LB.L- > Next=PD.P- > next=NULL指针P所指的元素是双向循环链表L的尾元素的条件是A.P= =LB.P= =NULLC. P- > next=L)。D. P- > prior=L在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时 间复杂性量级为（）。A.0(1)B.0(n)C.0(nlog 2n)D.0(n 2)顺序存储的线性表（a1

25、,a2, an），在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）。A.n删除长度为A） i-1B.n/2C.n+1D.(n+1)/2n的顺序表的第i（1 < i < n）个位置上的元素，元素的移动次数为（）B） i在C语言中可用（A、数组；B、指针;C) n-iD) n-i+1）描述线性表。C、数组或指针;D、结构链表不具有的特点是（A）插入、删除不需要移动元素C）不必事先估计存储空间B）可随机访问任兀系D）所需空间与线性长度成正比在单链表中，指针p指向元素为x的结点，实现“删除 xA）p=p->next; B）p->next=p;C)p->next=

26、p->next->next;的后继”的语句是（）D）p=p->next->next;单链表的存储密度（A）大于1 ; B）等于非空的循环单链表 firstA. p-> next = NULL ;)1；C）不能确定;D）小于1的尾结点（由p所指向）满足：B. p = NULL ; C. p-> next = first卜列静态链表没有设置空闲指针链，则其表示的线性表逻辑结构为（D. p = first ;01234567,100abcdef,32516410,(c, a, b ,e, d, f,)； B、(c, a, b,e,d, f) ； C、(a,b,c,

27、 d,e, f,)；D、(a,b,c,d,e,15.在下列线性表如图1所示中将结点P插入到Q结点之前采用的操作是（ 的前驱指针域为 pre，后继指针域为next ）。）。（已知：结点第3页P 2014-10-16网络工程2011级1班、计科2011级2班算法与数据结构课后习题(第 2章)参考答案A、P->next=Q->next ; P->pre=P->next->pre ; P->next->pre=P->pre ; P->pre->next=P ;B、P->next=Q ; P->next->pre=P->

28、pre ; P->pre->next=P ; P->pre=P->next->pre ;C、P->pre=P->next->pre ; P->next->pre=P->pre ; P->pre->next=P ; P->next=Q ;D、P->next=Q ; P->pre=P->next->pre ; P->next->pre=P ; P->pre->next=P。16.设双向循环链表中结点的结构为( data, prior, next )，且不带表头结点。若

29、想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？A) p->next =s;s->prior= p; p->next->prior =s;s->next = p->next;B) p->next =s;p->next->prior = s;s->prior =p;s->next = p->next;C) s->prior =p;s->next= p->next;p->next =s;p->next->prior = s;D) s->prior =p;s->n

30、ext= p->next;p->next->prior = s; p->next = s;17. 下列说法正确的是（）。A. 线性表的逻辑顺序与存储顺序总是一致的B. 线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C. 线性表的顺序存储结构优于链式存储结构D. 每种数据结构都具有插入、删除和查找三种基本运算18. 关于线性结构的特性描述不恰当是（）。A、有唯一个被称作“第一个”的数据元素；B、有唯一个被称作"最后一个”的数据元素；C、除最后一个之外，线性表中每个数据元素都有后继;D、栈、队列、串和数组也属于线性表。19. 线性表（a

31、，a2,，ana,an）中任一元素a（i =0,1,2" ,n）在（）中存储位置为LOC（a（1）*l?其中 LOC（q） 表示元素a的存储首地址，l为每一个元素占用的存储单元数。A、线性表逻辑结构；B、线性表存储结构；C、线性表链式存储结构；D、线性表顺序存储结构。20. 设双链表中结点的前趋指针和后继指针的域名分别为t1和r1,则删除双链表中指针 s所指结点的操作为（）。A.s- > tl- > r1=s- > tl;s-> rl- > tl=s- > rl;free(s);B.s- > tl- > rl=s- > rl;s-

32、 > rl- > tl=s- > tl;free(s);C.s- > rl=s- > tl- > rl;s- > tl=s- > rl- > tl;free(s);D.s- > tl=s- > tl- > rl;s- > rl=s- > rl- > tlfree(s);四、算法分析与设计（请将答案填在下表对应位置。共 29分）第1题（7分）将第一个结点摘卜链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针第2题（8分） s->data=e s->next=p p->prior->next=s p->prior=s第3题（8分） >x L->datai L->datai+1 L->length+第4题（6分） p=head; n+; p=p->next;1、已知无表头的单链表L,简述下列对L链表操作算法的功能。LinkList Demo(LinkList L)( / L是无头结点单链表ListNode *Q,*P;if(L&&L->next)Q=L; L=L->next; P=L;while (P->nex