目标

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

前置知识

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

答题进度已答 0/10正确 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)))))$

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

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

思考题

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