单链表试题解析
单链表是数据结构中的一种重要数据结构，它是一种链式存储结构，每个结点中都包含一个指向下一个结点的指针。下面我们将通过一系列试题来加深对单链表的理解。
一、选择题
1. 下面关于线性表的叙述中，错误的是（ ）
正确答案：d. 链表可以随机存取任一元素
解释：链表由于其链式存储结构，无法实现随机存取，需要从头结点开始遍历整个链表来访问某个结点。
2. 在表长为 n 的单链表中，算法时间复杂度为 O (n)的操作是（ ）
正确答案：a. 查找单链表中第 i 个节点
解释：查找单链表中第 i 个节点需要从头结点开始遍历，直到找到第 i 个节点，这个操作的时间复杂度为 O (n)。
3. 单链表的存储密度（ ）
正确答案：c. 小于１
解释：单链表由于每个结点中都包含一个指向下一个结点的指针，因此其存储密度小于 1。
4. 两指针 p 和 q ，分别指向单链表的两个元素， p 所指元素是 q所指元素的前驱的条件是（ ）
正确答案：a. p-next=q
解释：p-next=q 表示 p 指向的元素的下一个结点是 q 指向的元素，因此 p 指向的元素是 q 指向元素的前驱。
二、填空题
1. 单链表中每一个结点需要两个域，一个是数据域，另一个是（ ）
答案：指针域
解释：单链表中每个结点需要两个域，一个是数据域，用于存储结点的值，另一个是指针域，用于存储指向下一个结点的指针。
2. 链表相对于顺序表的优点是（ ）和（ ）操作方便。
答案：插入、删除
解释：链表相对于顺序表的优点是插入和删除操作方便，因为链表可以直接插入或删除结点，而不需要移动大量的数据。
3. 单链表 h 为空表的条件是（ ）
答案：h->next=null
解释：单链表 h 为空表的条件是头结点的下一个结点为空，即 h->next=null。
4. 带表头结点的单链表 h 为空表的条件是（ ）
答案：h->next->next=null
解释：带表头结点的单链表 h 为空表的条件是头结点的下一个结点的下一个结点为空，即 h->next->next=null。
三、简答题
1. 顺序表和链表各自的优点是什么？
答案：顺序表的优点是可以随机存取，链表的优点是插入和删除操作方便。
2. 试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。
答案：头指针是指向链表的第一个结点的指针，头结点是链表的第一个结点，开始结点是链表的第一个结点。头指针和头结点的作用是提供了访问链表的入口，方便了链表的遍历和操作。
四、算法设计题
2.3 作业：写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
答案：
算法步骤：
1. 创建一个空的哈希表，用于存储已经出现的结点值。
2. 遍历单链表，从头结点开始。
3. 对于每个结点，如果其值已经在哈希表中出现，则删除该结点。
4. 如果结点值不在哈希表中，添加到哈希表中。
5. 重复步骤 3-4，直到遍历整个链表。
6. 返回结果链表。
时间复杂度：O (n)，其中 n 是链表中的结点数。
空间复杂度：O (n)，用于存储哈希表。
