武汉大学数据结构MOOC第3周测验

1单选(2分)与单链表相比，双链表的优点之一是（ ）。 A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.访问前后相邻节点更方便 正确答案：D 解析： D、在双链表中可以访问任一节点的前后相邻节点，而单链表中只能访问任一节点的下一个节点。

课本考据：由于双链表的每个结点既包含一个指向后继结点的指针，又包含一个指向前驱结点的指针，所以当访问过一个结点后既可以依次向后访问每一个结点，也可以依次向前访问每一个结点。（双链表中每个结点有指向前后结点的指针即可访问前后结点）

2单选(2分)带头节点的双链表L为空表时应满足（ ）。 A.L == NULL B.L->prior == L->next C.L->prior == NULL D.L->nex t == NULL 正确答案：D

课本考据：除了插入和删除结点，双链表其他运算的算法与单链表中相应的算法相同。

3单选(2分)在长度为n（n≥1）的双链表中插入一个节点（非尾节点）要修改（ ）个指针域。 A.1 B.2 C.3 D.4 正确答案：D 解析： D、需要修改插入节点的prior、next域，前驱节点的next域和后继节点的prior域。

课本考据：原理参考第二题，如图 操作语句如下：

4单选(2分)对于长度为n（n≥1）的双链表L，在p所指节点之前插入一个新节点的算法的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 正确答案：A 解析： A、设新节点指针为q，操作是：p->prior->next=p; q->prior=p->prior; p->prior=q; q->next=p;

5单选(2分)在长度为n（n≥1）的双链表中删除一个节点（非尾节点）要修改（ ）个指针域。 A.1 B.2 C.3 D.4 正确答案：B 解析： B、需要修改前驱节点的next域和后继节点的prior域。

6单选(2分)与非循环单链表相比，循环单链表的主要优点是（ ）。 A.不再需要头指针 B.已知某个节点的位置后，能够容易找到它的前驱节点 C.在进行插入、删除操作时，能更好地保证链表不断开 D.从表中任意节点出发都能扫描到整个链表 正确答案：D 解析： D、循环单链表中可以循环扫描，因此从表中任意节点出发都能扫描到整个链表。

7单选(2分)设有带头节点的循环单链表L，当这种链表成为空链表时，有（ ）。 A.表头节点指针域next为空 B.L的值为NULL C.表头节点的指针域next与L的值相等 D.表头节点的指针域next与L的地址相等 正确答案：C 解析： C、带头节点的循环单链表L成为空链表时满足L->next==L，即表头节点L的指针域next与L的值相等，而不是表头节点L的指针域next与L的地址相等。

8单选(2分)在长度为n（n≥1）的循环双链表L中，删除尾节点的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 正确答案：A 解析： A、通过头节点指针直接找到尾节点，然后再删除该尾节点，对应的时间复杂度为O(1)。

9单选(2分)将两个分别含有m、n个节点的有序单链表归并成一个有序单链表，要求不破坏原有的单链表，对应算法的空间复杂度是（ ）（MIN表示取最小值）。 A.O(n) B.O(m) C.O(m+n) D.O(MIN(m,n)) 正确答案：C 解析： C、将两个有序单链表A、B归并到C中时，通过比较A、B中的节点，将比较小的节点复制到C中，复制次数为m+n，即新建m+n个节点，对应的空间复杂度为O(m+n)。

10单选(2分)已知两个长度分别为m 和n 的升序单链表，若将它们合并为一个长度为m+n 的降序单链表，则时间复杂度是（ ）。 A.O(n) B.O(m×n) C.O(m) D.O(m+n) 正确答案：D

11单选(2分)在长度为n（n≥1）的双链表L中，删除p所指节点的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 正确答案：A 解析： A、在双链表中，通过p所指节点可以找到前后节点，通过其前后节点来删除p所指节点，对应的时间复杂度为O(1)。

12单选(2分)在长度为n（n≥1）的循环单链表L中，删除尾节点的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 正确答案：B 解析： B、通过L查找到尾节点的前驱节点，然后删除尾节点，对应的时间复杂度为O(n)。

13单选(2分)在只有尾节点指针rear没有头节点的非空循环单链表中，删除尾节点的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 正确答案：B 解析： B、通过rear查找到尾节点的前驱节点，然后删除尾节点，对应的时间复杂度为O(n)。

14单选(2分)在只有尾节点指针rear没有头节点的非空循环单链表中，删除开始节点的时间复杂度为（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 正确答案：A 解析： A、通过rear指针直接删除开始节点。

15单选(2分)两个长度为n的双链表，节点类型相同，若以h1为头指针的双链表是非循环的，以h2为头指针指针的双链表是循环的，则（ ）。 A.对于非循环双链表来说，删除首节点的操作，其时间复杂度都是O(n) B.对于循环双链表来说，删除首节点的操作，其时间复杂度都是O(n) C.对于非循环双链表来说，删除尾节点的操作，其时间复杂度都是O(1) D.对于循环双链表来说，删除尾节点的操作，其时间复杂度都是O(1) 正确答案：D 解析： D、对于这两个双链表来说，删除首节点的操作的时间复杂度都是O(1)。对于非循环双链表来说，删除尾节点的操作的时间复杂度都是O(n)，对于循环双链表来说，删除尾节点的操作的时间复杂度都是O(1)。