第56题  关于链式存储结构,下列叙述中错误的是

­      A  结点含有两个指针域的链式存储结构可能是线性结构,也可能是非线性结构

­      B  在线性表的链式存储结构中,每个结点必须含有指向前趋和后继的两个指针

­      C  在线性表的链式存储结构中,每个结点可以含有两个指针

­      D  在线性表的链式存储结构中,叶结点的指针可空、也可不空

答案  B

解析

考查链式存储结构的特点。如果理解或记住了下面的知识点,就不难选择。

知识点

① 数据结构分为线性结构和非线性结构两大类。线性表是典型的线性结构,二叉树是典型的非线性结构,如下图所示:

choice2-01

其中,圆圈表示数据结点,有向线段表示结点之间的前趋后继关系。没有前趋的结点叫做根结点,没有后继的结点叫做终端结点或叶结点。在上图的线性表中,B是根结点,E是终端结点,X的前趋是U,X的后继是K。在上图的二叉树中,R是根结点,A、D、M、G都是叶结点,X的前趋是R,X的后继是C和D,结点C和D之间没有关系。任意两个结点之间要么没有关系,要么是前趋后继关系。

若一个数据结构只有一个根结点,其任一结点至多有一个前趋、至多有一个后继,则该数据结构称为线性结构。如果一个数据结构不是线性结构,就称为非线性结构。

② 如上图所示,用结点和有向线段的图所表示的数据结构,称为逻辑结构。逻辑结构在机器内存中的表示形式,称为存储结构。一种逻辑结构可有多种不同的存储结构。

在C语言中,若用结构体的数据域存储结点值,用结构体的指针域表示结点间的前趋后继关系,则这种存储结构叫做链式存储结构。下图给出线性表的三种常见链式存储结构:单向链表、单向循环链表和双向链表。下图还给出二叉树的一种常见链式存储结构,即二叉链表。在其它语言中,也有类似结构体的类型,用于实现链式存储结构。

choice56-01

在单向链表中,每个结点含有一个指针域且指向其后继结点,叶结点的指针域为空。另设一个根指针指向根结点,通常叫做头指针。

在单向循环链表中,每个结点含有一个指针域且指向其后继结点,叶结点的指针域不再空闲,而是指向根结点,从而形成一个环。在某些情况下,会更方便。

在双向链表中,每个结点含有两个指针域,一个指向其前趋结点,一个指向其后继结点,叶结点的后继指针域为空,根结点的前趋指针域为空。

在二叉树的二叉链表中,每个结点含有两个指针域,一个指向左孩子结点,一个指向右孩子结点,叶结点的两个指针域为空。另设一个根指针指向根结点。

③  双向链表和二叉链表的结点均含有两个指针,前者属线性结构,后者属非线性结构,所以选项A是正确的。

④  双向链表的结点含有两个指针,所以选项C是正确的。

⑤  在单向链表中,叶结点的指针域为空; 在单向循环链表中,叶结点的指针域非空,所以选项D是正确的。

⑥ 在单向链表和单向循环链表中,结点均含一个指针,所以选项B是错误的。

注:前趋后继关系,也可叫做前件后件关系。

练习题

试为自己设计一道孪生题,举一反三。

孪生题1  关于链式存储结构,下列叙述中错误的是

­      A  若有两个结点的同一指针域的值相等,则该结构一定是线性结构

­      B  若有两个结点的同一指针域的值相等,则该结构一定是非线性结构

­      C  结点含有两个指针域的链式存储结构可能是线性结构,也可能是非线性结构

­      D  在线性表的链式存储结构中,每个结点可以含有两个指针

答案:A

解:

若有两个结点的同一指针域的值相等,则表明这两个结点指向同一结点,也说明被指结点具有两个前趋,不符合线性结构的定义,因此,一定是非线性结构,即选项A错误,选项B正确。

双向链表和二叉链表的结点均含有两个指针,前者属线性结构,后者属非线性结构,所以选项C是正确的。

双向链表的结点含有两个指针,所以选项D是正确的。

孪生题2  关于链式存储结构,下列叙述中正确的是

­      A  ……

­      B  ……

­      C  结点含有两个指针域的链式存储结构可能是线性结构,也可能是非线性结构

­      D  ……

赞赏

返回