判断题

1-1 在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。F

如果是顺序表，则访问为O(1)，增加为O(N)

1-2 若用链表来表示一个线性表，则表中元素的地址一定是连续的。F

链表不一定是连续的

1-3 将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。F

时间复杂度为O(1),若是单链表

1-4 (neuDS)单链表不是一种随机存取的存储结构。 T

顺序表是一种随机存取的存储结构

选择题 2-1 设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是D A.h=t; t->next=h->next; B.t->next=h->next; h=t; C.h=t; t->next=h; D.t->next=h; h=t;

2-2 在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行C A.s->next=p; p->next=s; B.s->next=p->next; p=s; C.s->next=p->next; p->next=s; D.p->next=s; s->next=p;

s-＞link＝p-＞link；s的后继指向p的后继；p-＞link＝s；p的后继为s，这样实现在p后插入s结点的操作

2-3 带头结点的单链表h为空的判定条件是:B A.h == NULL; B.h->next == NULL; C.h->next == h; D.h != NULL;

带头结点判空表的条件 h->next == NULL 不带头结点判空表的条件 h == NULL;此时h是头指针

2-4 将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是： B A.1 B.N C.2N D.NlogN

最好的情况就是前面的链表有序，后面的链表也有序，则最少比较次数就是N

2-5 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 B A.必须是连续的 B.连续或不连续都可以 C.部分地址必须是连续的 D.一定是不连续的

2-6 在具有N个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(N) ? C A.在地址为p的结点之后插入一个结点 B.删除开始结点 C.遍历链表和求链表的第i个结点 D.删除地址为p的结点的后继结点

2-7 对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为 C A.O(1) B.O(N/2) C.O(N) D.O(N​平方)

在指定节点后插入节点需要遍历链表查找条件节点，再进行插入。所以复杂度为O(n)。

2-8 链表不具有的特点是： B A.插入、删除不需要移动元素 B.方便随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比

链表采用的是链式存储结构，它克服了顺序存储结构的缺点:它的节点空间可以动态申请和释放;它的数据元素的逻辑次序靠节点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处:①每个节点中的指针域需额外占用存储空间;②链式存储结构是一种非随机存储结构。 顺序表方便随机访问任意一个元素

2-9 (neuDS)在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C）。 A.O(1) B.O(log​2n) C.O(n) D.O(n2)

有序顺序表，可以用二分查找，复杂度为o(lgn) 而本题中为有序单链表，需要遍历找到插入的位置，复杂度为O(n)

2-10 将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（B）。 A.O(1) B.O(m) C.O(n) D.O(n+m)

要插入到长度为m的单链表，需要找到表尾，这个过程的时间复杂度为o(m)，连接的时间复杂度为o(1)，所以总的时间复杂度为o(m)，所以答案选B。

2-11 (neuDS)在单链表中，增加一个头结点的最终目的是为了(B)。 A.使单链表至少有一个结点 B.方便运算的实现 C.标识表结点中首结点的位置 D.说明单链表是线性表的链式存储

(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。 (2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。 说白了就是方便运算

2-12 在单链表中，要删除某一指定结点，必须先找到该结点的（A）。 A.直接前驱 B.自身位置 C.直接后继 D.直接后继的后继

2-13 以下关于链式存储结构的叙述中，（C）是不正确的。 A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的存储地址 D.插入、删除运算操作方便，不必移动结点

2-14 线性链表不具有的特点是（A）。 A.随机访问 B.不必事先估计所需存储空间大小 C.插入与删除时不必移动元素 D.所需空间与线性长度成正比

顺序表才能随机访问 记住其他三项

2-15 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以

2-16 对线性表，在下列情况下应当采用链表表示的是（B）。 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中的元素个数不变

用链表的形式表示的线性表最大的优势是能动态地、很方便地进行插入和删除操作。

2-17 不带表头附加结点的单链表为空的判断条件是头指针head满足条件（A） A.head==NULL B.head->next == NULL C.head->next == head D.head!=NULL

2-18 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是（B）。 A.可以加快对表的遍历 B.使空表和非空表的处理统一 C.节省存储空间 D.可以提高存取表元素的速度

同2-11，对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。