第2章线性表(课堂作业).doc

第2章 线性表 1．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（ ）的有限序列（n0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3. 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7. 链表不具有的特点是（ ） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8. 在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。 A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; C. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q; D.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; 9. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A． s-next=p-next;p-next=s; B． p-next=s;s-next=p-next; C．p-next=s;p-next=s-next; D． p-next=s-next;p-next=s; 10 ．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 答案：1. B 2.C 3. C 4.C 5. C 6. B 7.A 8.D 9.A 10. B 作业一 1．线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 2．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。 3．一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法： （1）说明该算法的功能。（2）在空缺处填写相应的语句。 void unknown (BNODETP *L) { … p=L-next; q=p-next; r=q-next； while (q!=L) { while (p!=L) (p-dataq-data) p=p-prior； q-prior-next=r；(1) ______； q-next=p-next；q-prior=p； (2) ______；(3) ______； q=r；p=q-prior； (4) ______； } } 4．已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。 答案： 1．（1）选链式存储结构。它可