《数据结构课后习题(第2章)》由会员分享，可在线阅读，更多相关《数据结构课后习题(第2章)（12页珍藏版）》请在金锄头文库上搜索。
1、网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班算法与数据结构课后习题（第 2 章）第 1 页 共 5 页【课后习题课后习题】第第 2 2 章章 线性表线性表2011 级 计科 (网工) 班 学号： 姓名： 题 号一二三四总分得 分一、判断题（如果正确，在题号前打一、判断题（如果正确，在题号前打“ ” ，否则打，否则打“ ” 。每题。每题 2 2 分，共分，共 1010 分分) ) ( ) 1.线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。( ) 2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。( ) 3.如果某个数据结构的每一个元素都是最多只
2、有一个直接前驱，则必为线性结构。( ) 4.线性表的逻辑顺序与物理顺序总是一致的。( ) 5.线性表的长度是指它所占存储空间的大小。二、填空题（每空二、填空题（每空 1.51.5 分，共分，共 2121 分分) )1.从逻辑结构看，线性表是典型的 。2.在一个长度为 n 的向量中在第 i（1in+1）个元素之前插入一个元素时，需向后移动 个元素，算法的时间复杂度为 。3.在一个长度为 n 的向量中删除第 i（1in）个元素时，需向前移动 个元素，算法的时间复杂度为 。4.若长度为 n 的线性表采用链式存储结构，在其第 i 个结点前插入一个新的元素的算法的时间复杂度为 。删除其第 i 个元素的算
3、法的时间复杂度为 。5.线性表顺序存储结构的优点是可以实现 ，主要缺点是: 。6.不带头结点的单链表 L 为空的条件是 ，带头结点的单链表 L 为空的条件是 ，带头结点的单循环链表 L 为空的条件是 。7.两指针 p 和 q，分别指向单链表的两个元素，p 所指元素是 q 所指元素的前导的条件是 。8.设双向循环链表中结点的结构为（data, prior, next） ，若指针 p 指向该链表的某个结点，则有下面的关系：p-next-prior= = 。网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班算法与数据结构课后习题（第 2 章）第 2 页 共 5 页三、单项选择（请
4、将正确答案的代号填写在下表对应题号下面。每题三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题 2 2 分，共分，共 4040 分分) )题号12345678910答案题号11 12 13 1415 16 17181920答案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 指
5、向带头结点的单循环链表 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=L 6.在一个具有 n 个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作 的时间复杂性量级为（ ） 。A.0(1) B.0(n) C.0(nlog2n)
6、 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 语言中可用（ ）描述线性表。网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班算法与数据结构课后习题（第 2 章）第 3 页 共 5 页A、数组； B、指针； C、数组或指针； D、结构10. 链表不具有的特点是（ ） A) 插入、删除不需要移动元素 B)
7、 可随机访问任一元素 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；1
8、4. 下列静态链表没有设置空闲指针链，则其表示的线性表逻辑结构为（ ） 。01234567100abcdef32516410A、 （c, a, b ,e, d, f,） ； B、； C、； D、),(fdebac),(Lfedcba。),(fedcba15. 在下列线性表如下图所示中将结点 P 插入到 Q 结点之前采用的操作是（ ） 。 （已知： 结点的前驱指针域为 pre，后继指针域为 next） 。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
9、-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; 图 1PeabdQD网络工程
10、 2011 级 1 班、计算机科学与技术 2011 级 2 班算法与数据结构课后习题（第 2 章）第 4 页 共 5 页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.线性表的链式存储结构中
11、，要求内存中可用的存储单元可以是连续的，也可以不连续 C.线性表的顺序存储结构优于链式存储结构 D.每种数据结构都具有插入、删除和查找三种基本运算18. 关于线性结构的特性描述不恰当是（ ） 。 A、有唯一个被称作“第一个”的数据元素； B、有唯一个被称作“最后一个”的数据元素； C、除最后一个之外，线性表中每个数据元素都有后继； D、栈、队列、串和数组也属于线性表。19. 线性表中任一元素在（ ）中存储位置为),(121nnaaaaL),2 , 1 , 0(niaiL，其中表示元素的存储首地址， 为每一个元素占用的liaLOC*) 1()(1)(1aLOC1al存储单元数。 A、线性表逻辑结
12、构； 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);四、算法分析与设计（请将答案填在下表对应位置。共四、算法分析与设计（请将答案填在下表对应位置。共
13、 29 分）分）第 1 题（7 分）第 2 题（8 分）第 3 题（8 分）第 4 题（6 分） ;1、已知无头结点的单链表 L，简述下列对 L 链表操作算法的功能。网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班算法与数据结构课后习题（第 2 章）第 5 页 共 5 页LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(L L=L-next; P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo2、已知线性表的带头结点双向循环链表存储
14、结构如下所示：typedef struct DuLNodeElemType data；struct DuLNode *prior；Struct DuLNode *next；DuLNode，*DuLinkList；请完成在带头结点的双向循环链表 L 中第 i 个位置之前插入元素 e（1i表长+1）算法：status ListInsert_DuL(DuLinkListif ( L-length=ListSize)Error(“overflow“);for ( i=L - length ; i0 i-)L-data i+1 = ; / 比较并移动元素网络工程 2011 级 1 班、计算机科学与技术
