数据结构课后习题.doc

【课后习题】第2章 线性表2011级 计科 (网工) 班 学号： 姓名： 题 号一二三四总分得 分一、判断题（如果正确，在题号前打“”，否则打“”。每题2分，共10分) ( ) 1. 线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。( ) 2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。( ) 3. 如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。( ) 4. 线性表的逻辑顺序与物理顺序总是一致的。( ) 5. 线性表的长度是指它所占存储空间的大小。二、填空题（每空1.5分，共21分)1. 从逻辑结构看，线性表是典型的 。2. 在一个长度为n的向量中在第i（1in+1）个元素之前插入一个元素时，需向后移动 个元素，算法的时间复杂度为 。3. 在一个长度为n的向量中删除第i（1in）个元素时，需向前移动 个元素，算法的时间复杂度为 。4. 若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为 。删除其第i个元素的算法的时间复杂度为 。5. 线性表顺序存储结构的优点是可以实现 ，主要缺点是: 。6. 不带头结点的单链表L为空的条件是 ，带头结点的单链表L为空的条件是 ，带头结点的单循环链表L为空的条件是 。7. 两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前导的条件是 。8. 设双向循环链表中结点的结构为（data, prior, next），若指针p指向该链表的某个结点，则有下面的关系：p-next-prior= = 。三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题2分，共40分)题号12345678910答案题号11121314151617181920答案1. P和Q两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（ ）。A.P= =Q B.Q-Next=PC.P-Next=Q D.Q-PRIOR=P2. 指针P指向不带头结点的线性链表L的首元素的条件是（ ）。A.P= =L B.L-Next=PC.P-next=L D.P-next=NULL3. 指针p指向带头结点的单循环链表L 的首元素的条件是（ ）。A.P= =L B.L-Next=PC.P-next=L D.P-next=NULL4. 指针P指向单链表L的尾元素的条件是（ ）。A.P= =L B.L-Next=PC.P-next=L D.P-next=NULL5. 指针P 所指的元素是双向循环链表L的尾元素的条件是（ ）。A.P= =L B.P= =NULL C. P-next=L D. P-prior=L6. 在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）。A.0(1) B.0(n) C.0(nlog2n) D.0(n2)7. 顺序存储的线性表(a1,a2,an)，在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）。A.n B.n/2 C.n+1 D.(n+1)/28. 删除长度为n的顺序表的第i(1in)个位置上的元素，元素的移动次数为( )A) i-1 B) i C) n-i D) n-i+19. 在C语言中可用（ ）描述线性表。A、数组； B、指针； C、数组或指针； D、结构10. 链表不具有的特点是（ ）A) 插入、删除不需要移动元素 B) 可随机访问任一元素 C) 不必事先估计存储空间 D)所需空间与线性长度成正比11. 在单链表中，指针p指向元素为x的结点，实现“删除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 = NULL； C. p- next = first； D. p = first；14. 下列静态链表没有设置空闲指针链，则其表示的线性表逻辑结构为（ ）。01234567100abcdef32516410 A、（c, a, b ,e, d, f,）； B、； C、； D、。15. 在下列线性表如下图所示中将结点P插入到Q结点之前采用的操作是（ ）。（已知：结点的前驱指针域为pre，后继指针域为next）。图1PeabdQD 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-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），且不带表头结点。若想在指针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-next = p-next; p-next-prior = s; p-next = s;17. 下列说法正确的是（ ）。A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的顺序存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算18. 关于线性结构的特性描述不恰当是（ ）。A、有唯一个被称作“第一个”的数据元素； B、有唯一个被称作“最后一个”的数据元素；C、除最后一个之外，线性表中每个数据元素都有后继； D、栈、队列、串和数组也属于线性表。19. 线性表中任一元素在（ ）中存储位置为，其中表示元素的存储首地址，为每一个元素占用的存储单元数。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-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-tl free(s);四、算法分析与设计（请将答案填在下表对应位置。共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 struct DuLNodeElemType data；struct DuLNode *prior；Struct DuLNode *next；DuLNode，*DuLinkList；请完成在带头结点的双向循环链表L中第i个位置之前插入元素e（1i表长+1）算法：status ListInsert_DuL(DuLinkList&L，int I；ElemType e) p=L；j=0； while(pp-next)&(jnext；j+； if(p= =L)&(i1)|(ji-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(“overflow);for ( i=L - length ; i0 & L-data i ; i-)L-data i+1 = ; / 比较并移动元素 =x; ;4、有一个不带头结点的单链表，其头指针为head，其结点的数据域值可能相同，编写一个函数统计数据域的值为x的结点个数。int countx (LinkList head, ElemType x)LinkList p; int n=0; while (p!=NULL) if (p-data= =x) return(n);【课后习题】第2章 线性表(参考答案)一、判断题（如果正确，在题号前打“”，否则打“”。每题2分，共10分) 1. 2. X3. X4. X5. X二、填空题（每空1.5分，共21分)1. 从逻辑结构看，线性表是典型的 线性结构 。2. 在一个长度为n的向量中在第i（1in+1）个元素之前插入一个元素时，需向后移动 n-i+1 个元素，算法的时间复杂度为 O(n) 。3. 在一个长度为n的向量中删除第i（1in）个元素时，需向前移动 n-i 个元素，算法的时间复杂度为 O(n) 。4. 若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为 O(n) 。删除其第i个元素的算法的时间复杂度为 O(n) 。5. 线性表顺序存储结构的优点是可以实现 随机存取 ，主要缺点是: 不利于插入或删除操作 。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分)题号12345678910答案BABDCBBCCB题号11121314151617181920答案CDCADDBCDB四、算法分析与设计（请将答案填在下表对应位置。共29分）第1题（7分）将第一个结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针第2题（8分）s-data=es-next p-prior-next=sp-prior=s第3题（8分） xL-dataiL-datai+1L-length+第4题（6分） p=head; n+;p=p-next;【课后习题】第2章 线性表(参考答案)一、判断题（如果正确，在题号前打“”，否则打“”。每题2分，共10分) 1.线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。x 2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。x 3.如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。x 4.线性表的逻辑顺序与物理顺序总是一致的。x 5.线性表的长度是指它所占存储空间的大小。二、填空题（每空2分，共18分)1. 从逻辑结构看，线性表是典型的 线性结构 。2. 在一个长度为n的向量中在第i（1in+1）个元素之前插入一个元素时，需向后移动 n-i+1 个元素，算法的时间复杂度为 O(n) 。3. 在一个长度为n的向量中删除第i（1in）个元素时，需向前移动 n-i 个元素，算法的时间复杂度为 O(n) 。4. 若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为 O(n) 。删除其第i个元素的算法的时间复杂度为 O(n) 。5. 线性表顺序存储结构的优点是可以实现 随机存取 ，主要缺点是: 不利于插入或删除操作 。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分)1. P和Q两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（ ）。A.P= =Q B.Q-Next=PC.P-Next=Q D.Q-PRIOR=P2. 指针P指向不带头结点的线性链表L的首元素的条件是（ ）。A.P= =L B.L-Next=PC.P-next=L D.P-next=NULL3. 指针p指向带头结点的单循环链表L 的首元素的条件是（ ）。A.P= =L B.L-Next=PC.P-next=L D.P-next=NULL4. 指针P指向单链表L的尾元素的条件是（ ）。A.P= =L B.L-Next=PC.P-next=L D.P-next=NULL5. 指针P 所指的元素是双向循环链表L的尾元素的条件是（ ）。A.P= =L B.P= =NULL C. P-next=L D. P-prior=L6. 在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）。A.0(1) B.0(n) C.0(nlog2n) D.0(n2)7. 顺序存储的线性表(a1,a2,an)，在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）。A.n B.n/2 C.n+1 D.(n+1)/28. 删除长度为n的顺序表的第i(1in)个位置上的元素，元素的移动次数为( )A) i-1 B) i C) n-i D) n-i+19. 在C语言中可用（ ）描述线性表。A、数组； B、指针； C、数组或指针； D、结构10. 链表不具有的特点是（ ）A) 插入、删除不需要移动元素 B) 可随机访问任一元素 C) 不必事先估计存储空间 D)所需空间与线性长度成正比11. 在单链表中，指针p指向元素为x的结点，实现“删除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 = NULL； C. p- next = first； D. p = first；14. 下列静态链表没有设置空闲指针链，则其表示的线性表逻辑结构为（ ）。01234567100abcdef32516410 A、（c, a, b ,e, d, f,）； B、； C、； D、。15. 在下列线性表如图1所示中将结点P插入到Q结点之前采用的操作是（ ）。（已知：结点的前驱指针域为pre，后继指针域为next）。图1PeabdQD 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-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），且不带表头结点。若想在指针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-next = p-next; p-next-prior = s; p-next = s;17. 下列说法正确的是（ ）。A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的顺序存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算18. 关于线性结构的特性描述不恰当是（ ）。A、有唯一个被称作“第一个”的数据元素； B、有唯一个被称作“最后一个”的数据元素；C、除最后一个之外，线性表中每个数据元素都有后继； D、栈、队列、串和数组也属于线性表。19. 线性表中任一元素在（ ）中存储位置为，其中表示元素的存储首地址，为每一个元素占用的存储单元数。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-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-tl free(s);四、算法分析与设计（请将答案填在下表对应位置。共29分） 第1题（7分）将第一个结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针第2题（8分）s-data=es-next=pp-prior-next=sp-prior=s第3题（8分） xL-dataiL-datai+1L-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;