第2 章 线性表一 选择题 1．下述哪一条是顺序存储结构的优点？（ ）A. 存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构 的存储表示2. 下面关于线性表的叙述中，错误的是哪一个？（ ）A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链接存储，不必占用一片连续的存储单元D. 线性表采用链接存储，便于插入和删除操作3. 线性表是具有n个（）的有限序列（n〉0）A. 表元素 B.字符 C.数据元素 D.数据项 E.信息项4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则 利用（ ）存储方式最节省时间A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（ ）存储方式最节省运算时间A.单链表 B.仅有头指针的单循环链表 C.双链表 D •仅有尾指针的单循环链表 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点则采用 （ ）存储方式最节省运算时间A.单链表 B.双链表 C.单循环链表 D.带头结点的双循环链表9. 链表不具有的特点是（ ）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比10. 下面的叙述不正确的是（ ）A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关C. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比D. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ） （1<=i<=n+1）。
A. O（0） B. O（1） C. O（n） D. O（n2）14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）A. O（n） O（n） B. O（n） O（1） C. O（1） O（n） D. O（1） O（1）15. 线性表（al,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A. O（i） B. O（1） C. O（n） D. O（i-1）23. 在双向链表指针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-〉Rlink=p;q-〉Llink=p-〉Llink;p-〉Llink-〉Rlink=q;p-〉Llink=q;D. q-〉Llink=p-〉Llink;q-〉Rlink=q;p-〉Llink=q;p-〉Llink=q;24. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;25．对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是( )A. head==NULL B. head—next==NULL C. head—next二二head D. head!二NULL二、填空1. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取 线性表中的元素时，应采用 _存储结构。
2. 线性表L= (al,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一 个元素平均需要移动元素的个数是__ __3. 设单链表的结点结构为(data,next), next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行 以下语句:__ ;4. 在一个长度为n的顺序表中第i个元素(l〈=i〈=n)之前插入一个元素时，需向后移动— ___个元素5. 在单链表中设置头结点的作用是_主要是使插入和删除操作统一，在第一个元素之前插入元素和删除第一个结点不要另做判断另外不论链表是否为空，链表指针不变 6. 对于一个具有n个结点的单链表，在已知的结点*卩后插入一个新结点的时间复杂度为— , 在给定值为 x 的结点后插入一个新结点的时间复杂度为__ 7. 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成___ 和__ ；而又根据指针的连接方式，链表又可分成___ 和___ 8. 在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是 10. 链接存储的特点是利用___ 来表示数据元素之间的逻辑关系。
11. 顺序存储结构是通过 ___表示元素之间的关系的;链式存储结构是通过 表示元素之间的关系的12. 对于双向链表, 在两个结点之间插入一个新结点需修改的指针共 _ ___个，单链表为 2_个13. 循环单链表的最大优点是： 14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是： —15. 带头结点的双循环链表L中只有一个元素结点的条件是： 16. 在单链表L中，指针p所指结点有后继结点的条件是： 第2 章 线性表一．选择题l.A2.B3.C4.A5.D6.D7.D&C9.B1O.B,C11.1111.2I11.3E11.4B11.5C12.B13.C14.C15.C16.A17.A18.A19.D20.C21.B22.D23.C24.B25.B26.A27.D．填空题1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py4 ． n-i+15．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必 另作判断另外，不论链表是否为空，链表指针不变6．O(1)，O(n) 7．单链表，多重链表，(动态)链表，静态链表8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;9. plprior s".prior".next10． 指针 11．物理上相邻 指针 12．4 213.从任一结点出发都可访问到链表中每一个元素。
14 . u=p->next; p->next=u->next; free(u); 15 . L->next->next==L16. p->next!=null17. L->next==L && L->prior==L 18. s->next=p->next;p->next=s;。