多做题,通过考试没问题!

02331数据结构

睦霖题库>高等教育工学类自考>02331数据结构

在单链表、双链表和单循环表中,若仅知道指针p指向某结点,不知道头指针,能否将结点*p从相应的链表中删去?若可以,其时间复杂度各为多少?

正确答案:1.单链表。当我们知道指针p指向某结点时,能够根据该指针找到其直接后继,但是由于不知道其头指针,所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2.双链表。由于这样的链表提供双向链接,因此根据已知结点可以查找到其直接前趋和直接后继,从而可以删除该结点。其时间复杂度为O(1)。
3.单循环链表。根据已知结点位置,我们可以直接得到其后相邻的结点位置(直接后继),又因为是循环链表,所以我们可以通过查找,得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
答案解析:
进入题库查看解析

微信扫一扫手机做题