完美 WORD 格式
1
、 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答:开始结点是指链表中的
第一个结点,也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针
定,因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后,头指针指向头结点,不
论链表否为空,头指针总是非空。而且头指针的设置使得对链表的第一个 位置上的操作与在表其他位置上的操
作一致
(
都是在某一结点之后
)
。
?
(
没有头结点时
)
,单链表由头指针唯一确
2
、 何时选用顺序表、何时选用链表作为线性表的存储结构为宜
答:在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几
方面的考虑:
1)
基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为 了节约存储空间,
宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采 用动态链表作为存储结构为好。
2)
基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采
用顺序表做存储结构为宜;反之,
示的单循环链表为宜。
若需要对线性表进行频繁地插入或删除等操作时,宜采
则采用尾指针表用链表做存储结构。 并且,若链表的插入和删除主要发生在表的首尾两端,
3
、在顺序表中插入和删除一个结点需平均移动多少个结点 因素
?
?
具体的移动次数取决于哪两个
答:在等概率情况下,顺序表中插入一个结点需平均移动 移动
(n-1)
/2
个结点。具体的移动次数取决于顺序表的长度 越接近
n
则所需移
n/2
个结点,删除一个结点需平均
动的结点数越少。
4
、为什么在单循环链表中设置尾指针比设置头指针更好
?
n
以及需插入或删除的位置
i
。
i
答:尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和 终端结点都很方便,
设一带头结点的单循环链表,其尾指针为
点的位置分别是
rear-
〉
next-
〉
next
和
rear,
查找时间都是
0(1)
。
若用头指针来表示该链表,则查找终端结点的时间为
O(n)
。
rear
,则开始结点和终端结
5
、在单链表、双链表和单循环链表中,若仅知道指针
p
指向某结点,不知道头指针,能否
?
将结点
*p
从相应的链表中删去
?
若可以,其时间复杂度各为多少
答:我们分别讨论三种链表的情况。
1)
单链表。当我们知道指针
p
指向某结点时,能够根据该指针找到其直接后继,但是
由于不知道其头指针,所以无法访问到
p
指针指向的结点的直接前趋。
2)
双链表。由于这样的链表提供双向链接,
因此无法删去该结点。
因此根据已知结点可以查找到其直接前趋
O(1)
。
(
直接后
和直接后继,从而可以删除该结点。其时间复杂度为
3)
单循环链表。根据已知结点位置,我们可以直接得到其后相邻的结点位置
继
)
,又因为是循环链表,所以我们可以通过查找,得到
p
所指结点。其时间复杂度应为
O(n)
。
p
结点的直接前趋。因此可以删去
专业整理知识分享