数据结构课后习题(第2章).docVIP

【课后习题】第2章 线性表?2011级 计科 (网工) 班 学号： 姓名： 题 号 一 二 三 四 总分 得 分 一、判断题（如果正确，在题号前打“(”，否则打“(”。每题2分，共10分) 线性表若采用存储表示时所有结点之间的存储单元地址连续。如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性。线性表的逻辑顺序与物理顺序总是一致的。 。 在一个长度为n的向量中删除第i（1≤i≤n）个元素时，需向前移动 个元素，算法的时间复杂度为 。 若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为 。删除其第i个元素的算法的时间复杂度为 。 线性表顺序存储结构的优点是可以实现 ，主要缺点是: 。 不带头结点的单链表L为空的条件是 ，带头结点的单链表L为空的条件是 ，带头结点的单循环链表L为空的条件是 。 两指针和，分别指向单链表的两个元素，所指元素是所指元素的前导的条件是data, prior, next），若指针p指向该链表的某个结点，则有下面的关系：p-next-prior= = 。 三、单项选择 1 2 3 4 5 6 7 8 9 10 答案 　 　 　 　 　 　 　 　 题号 11　 12　 　13 　14 15　 16　 17 18 19 20 答案 　 　 　 　 　 　 　 　 P和两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（??? ）。A.P= =Q?????????????? B.Q-﹥Next==PC.P-﹥Next==??????? D.Q-﹥==P 指针P指向线性链表L的首元素的条件是（??? ）。A.P= =L?????????? B.L-﹥Next==PC.P-﹥next==L???? D.P-﹥next==NULL指针p指向循环链表L 的首元素的条件是（??? ）。A.P= =L?????????? B.L-﹥Next==PC.P-﹥next==L???? D.P-﹥next==NULL指针P指向链表L的元素的条件是（??? ）。A.P= =L?????????? B.L-﹥Next==PC.P-﹥next==L???? D.P-﹥next==NULL指针P 所指的元素是双向循环链表L的尾元素的条件是（??? ）。A.P= =L??????????? B.P= =NULL ??? C. P-﹥ext==L D. P-﹥rior==L? 在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（??? ）。A.0(1)??? B.0(n)???? C.0(nlog2n)???? D.0(n2)顺序存储的线性表(a1,a2,…an)，在任一结点前插入一个新结点时所需移动结点的平均次数为（??? ）。A.n?????? B.n/2 ?????????? ?C.n+1?????? D.(n+1)/2A) i-1 B) i C) n-i D) n-i+1 在C语言中可用（ ）描述线性表。A、数组； B、指针； C、数组或指针； D、结构 链表不具有的特点是（ ）A) 插入、删除不需要移动元素 B) 可随机访问任一元素 C) 不必事先估计存储空间 D)所需空间与线性长度成正比 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( )A)p=p-next; B)p-next=p; C)p-next=p-next-next; D)p=p-next-next; 单链表的存储密度（ ）A)大于1； B)等于1； C) 不能确定； D) 小于1 非空的循环单链表first的尾结点（由p所指向）满足：A. p- next == NULL；　　B. p == NULL； C. p- next == first； 　D. p == first；100 a b c d e f … 3 2 5 1 6 4 10 … A、（c, a, b ,e, d, f,…）； B、； C、； D、。 在下列线性表如下图所示中将结点P