目标

辨析广义表的递归定义，掌握表头、表尾、长度、深度的计算，理解头尾链表与扩展线性链表两种存储结构的取舍。

前置知识

建议先阅读 3.4 广义表与递归算法正文，掌握表头表尾、长度深度，以及头尾链表与扩展线性链表存储。

答题进度已答 0/20正确 0

第 1 题

难度★考点广义表、基本概念

广义表与线性表的本质区别在于（ ）。

请选择一个答案

A广义表的元素既可以是原子，也可以是子表；线性表的元素只能是原子

B广义表不能是空表

C线性表不能共享或递归引用自身

D广义表只能采用链式存储

第 2 题

难度★考点广义表、表头、表尾

下面关于广义表的说法中，不正确的是（ ）。

请选择一个答案

A广义表的表头总是一个广义表

B广义表的表尾总是一个广义表

C广义表难以用顺序存储结构表示

D广义表可以是一个多层次的结构

第 3 题

难度★考点广义表、表头

广义表 $((a,b,c),d)$ 的表头是（ ）。

请选择一个答案

A$a$

B$()$

C$(a,b,c,d)$

D$(a,b,c)$

第 4 题

难度★考点广义表、表尾

广义表 $L=(a,(b,c))$，进行 $Tail(L)$ 操作后的结果为（ ）。

请选择一个答案

A$c$

B$b,c$

C$(b,c)$

D$((b,c))$

第 5 题

难度★★考点广义表、长度、深度

设广义表 $L=((a,b,c),d)$，则 $L$ 的长度和深度分别为（ ）。

请选择一个答案

A1 和 2

B2 和 2

C2 和 3

D1 和 3

第 6 题

难度★★考点广义表、深度

设广义表 $F=(a,(b,(c,d)))$，则 $depth(F)$ 为（ ）。

请选择一个答案

A1

B2

C3

D4

第 7 题

难度★★★考点广义表、表头、表尾

设广义表 $A=(a,b,(c,d),(e,(f,g)))$，则 $Head(Tail(Head(Tail(Tail(A)))))$ 的值为（ ）。

请选择一个答案

A$(g)$

B$(d)$

C$c$

D$d$

第 8 题

难度★★考点广义表、存储结构

关于广义表的存储，下列说法错误的是（ ）。

请选择一个答案

A头尾链表与扩展线性链表都用标志位区分原子与子表

B头尾链表中空表用空指针表示

C扩展线性链表比头尾链表更节省空间

D扩展线性链表用 $next$ 指针串起同一层元素

第 9 题

难度★考点广义表、递归、基本概念

设广义表 $E=(a,E)$，下列说法正确的是（ ）。

请选择一个答案

A$E$ 的长度为 2，含原子 $a$ 和它本身的引用，是递归表

B$E$ 是空表

C$E$ 的长度为 1

D$E$ 是不合法的广义表

第 10 题

难度★★★考点广义表、表头、表尾

设广义表 $L=((x,y,z),a,(u,t,w))$，从 $L$ 中取出原子 $t$ 的运算是（ ）。

请选择一个答案

A$Head(Tail(Tail(L)))$

B$Tail(Head(Tail(L)))$

C$Head(Tail(Head(Tail(L))))$

D$Head(Tail(Head(Tail(Tail(L)))))$

第 11 题

难度★考点广义表、表尾

对非空广义表 $L$ 执行 Tail(L)，结果一定是（ ）。

请选择一个答案

A一个表

B一个原子

C一个整数

D空指针以外的原子

第 12 题

难度★考点广义表、表尾

Tail((a)) 的结果是（ ）。

请选择一个答案

A()

Ba

C(a)

D((a))

第 13 题

难度★考点广义表、表头

Head(((a,b),c)) 的结果是（ ）。

请选择一个答案

A(a,b)

B((a,b))

Cc

D()

第 14 题

难度★考点广义表、长度

广义表 $L=(a,(b,c),d)$ 的长度是（ ）。

请选择一个答案

A3

B4

C2

D5

第 15 题

难度★★考点广义表、深度

按本文约定，原子的深度为（ ）。

请选择一个答案

A0

B1

C-1

D原子个数

第 16 题

难度★考点广义表、深度

按本文约定，空表 () 的深度是（ ）。

请选择一个答案

A1

B0

C-1

D无法定义

第 17 题

难度★考点广义表、递归

求广义表深度时，递归应在哪些对象处终止？

请选择一个答案

A原子和空表

B所有非空表

C只有根表

D只有原子

第 18 题

难度★★考点广义表、头尾链表

在头尾链表表示中，List 节点的 hp 和 tp 分别指向（ ）。

请选择一个答案

A表头和表尾

B表尾和表头

C同层下一个元素和父表

D行和列

第 19 题

难度★考点广义表、存储结构

广义表结点需要 tag 标志位的主要原因是（ ）。

请选择一个答案

A区分当前结点是原子还是子表

B记录元素的排序位置

C保存表的长度

D避免使用指针

第 20 题

难度★★考点广义表、表尾

Tail((a,(b,c))) 的序列化结果是（ ）。

请选择一个答案

A((b,c))

B(b,c)

Cb

D(a)

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：A
3. 第 3 题：D
4. 第 4 题：D
5. 第 5 题：B
6. 第 6 题：C
7. 第 7 题：D
8. 第 8 题：C
9. 第 9 题：A
10. 第 10 题：D
11. 第 11 题：A
12. 第 12 题：A
13. 第 13 题：A
14. 第 14 题：A
15. 第 15 题：A
16. 第 16 题：A
17. 第 17 题：A
18. 第 18 题：A
19. 第 19 题：A
20. 第 20 题：A

思考题

1. 为什么表尾一定是一个表（可能是空表）？它比直觉多一层括号的原因是什么？
2. 空表、原子的深度约定分别是多少？深度与长度有何区别？
3. 头尾链表与扩展线性链表各适合什么场景？为什么？