1、与单链表相比，双链表的优点之一是（）。
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略表头指针或表尾指针
D.访问前后相邻节点更方便
正确答案：D
解析：在双链表中可以访问任一节点的前后相邻节点，而单链表中只能访问任一节点的下一个节点。
2、带头节点的双链表L为空表时应满足（）。
A.L==NULL
B.L->prior==L->next
C.L->prior==NULL
D.L->next==NULL
正确答案：D
3、在长度为n（n≥1）的双链表中插入一个节点（非尾节点）要修改（）个指针域。
A.1
B.2
C.3
D.4
正确答案：D
解析：需要修改插入节点的prior、next域，前驱节点的next域和后继节点的prior域。
4、对于长度为n（n≥1）的双链表L，在p所指节点之前插入一个新节点的算法的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
正确答案：A
解析：设新节点指针为q，操作是：p->prior->next=p; q-
>prior=p->prior; p->prior=q; q->next=p;
5、在长度为n（n≥1）的双链表中删除一个节点（非尾节点）要修改（）个指针域。
A.1
B.2
C.3
D.4
正确答案：B
解析：需要修改前驱节点的next域和后继节点的prior域。
6、与非循环单链表相比，循环单链表的主要优点是（）。
A.不再需要头指针
B.已知某个节点的位置后，能够容易找到它的前驱节点
C.在进行插入、删除操作时，能更好地保证链表不断开
D.从表中任意节点出发都能扫描到整个链表
正确答案：D
解析：循环单链表中可以循环扫描，因此从表中任意节点出发都能扫描到整个链表。
7、设有带头节点的循环单链表L，当这种链表成为空链表时，有（）。
A.表头节点指针域next为空
B.L的值为NULL
C.表头节点的指针域next与L的值相等
D.表头节点的指针域next与L的地址相等
正确答案：C
解析：带头节点的循环单链表L成为空链表时满足L->next==L，即表头节点*L的指针域next与L的值相等，而不是表头节点*L的指针域next与L的地址相等。
8、在长度为n（n≥1）的循环双链表L中，删除尾节点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
正确答案：A
解析：通过头节点指针直接找到尾节点，然后再删除该尾节点，对应的时间复杂度为O(1)。
9、将两个分别含有m、n个节点的有序单链表归并成一个有序单链表，要求不破坏原有的单链表，对应算法的空间复杂度是（）（MIN表示取最小值）。
A.O(n)
B.O(m)
C.O(m+n)
D.O(MIN(m,n))
正确答案：C
解析：将两个有序单链表B归并到C中时，通过比较B中的节点，将比较小的节点复制到C中，复制次数为m+n，即新建m+n个节点，对应的空间复杂度为O(m+n)。
10、已知两个长度分别为m 和n 的升序单链表，若将它们合并为一
个长度为m+n 的降序单链表，则时间复杂度是（）。
A.O(n)
B.O(m×n)
C.O(m)
D.O(m+n)
正确答案：D
11、在长度为n（n≥1）的双链表L中，删除p所指节点的时间复
杂度为（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
正确答案：A
解析：在双链表中，通过p所指节点可以找到前后节点，通过其
前后节点来删除p所指节点，对应的时间复杂度为O(1)。
12、在长度为n（n≥1）的循环单链表L中，删除尾节点的时间复
杂度为（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
正确答案：B
解析：通过L查找到尾节点的前驱节点，然后删除尾节点，对应
的时间复杂度为O(n)。
13、在只有尾节点指针rear没有头节点的非空循环单链表中，删除
尾节点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
正确答案：B
解析：通过rear查找到尾节点的前驱节点，然后删除尾节点，对
应的时间复杂度为O(n)。
14、在只有尾节点指针rear没有头节点的非空循环单链表中，删除
开始节点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
正确答案：A
解析：通过rear指针直接删除开始节点。
15、两个长度为n的双链表，节点类型相同，若以h1为头指针的双
链表是非循环的，以h2为头指针指针的双链表是循环的，则（）。
A.对于非循环双链表来说，删除首节点的操作，其时间复杂度都是
O(n)
