Question

数据结构

1.在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度为（）AO(n）BO(n/2）CO(1）DO(根号下n）
2.所说的表头指针到底是什么数据类型 是指针还是结构体 经常会看到这样的说法 指针p所指向的结点，这里的指针p到底是什么数据类型 是结构体吗 如果是结构体那让p=head怎样理解
3 在双向指针中会有这样的说法 p所指向的结点 这里的p跟他的前一个结点的后驱指针是不是一样呢
4。在双向链表中，p->pior->next 到底指向什么
各位大侠帮忙解释一下 越详细越好 好的我可以追加分 我自学数据结构学来学去学了个稀里糊涂 希望高手指点一下 谢谢啦

Answer 1

1、A，因为需要找到该点的前驱，链表为顺序访问，时间复杂度为O(n)
2、表头指针为结构体指针，p指向的结点指p指向的目标，同样的，p=head就是指针p也指向表头结点了
3、p所指向的结点是结构体，但是p存放的是该结构体的地址，同样地，该结构体中的一个数据域存放着其前驱或者后继的地址，这个地址当然就是指针了
4、p->prior->next就是该结点的前驱的后继，就是自己，打个比方说，独生子女的双亲的孩子是谁？肯定就是自己了

Answer 2

社 严蔚敏主编的。
还想学深的话 就学《算法设计与分析》 也是清华大学出版的 王晓东主编。这两本如果你够能掌握，你就不是一般水平了。
之所以推荐清华的是因为清华大学出版社在其网站上提供电子课件免费下载，配合教材效果会好很多,清华教授的水平就不用说了。
如果有时间建议你学数据结构前先把《离散数学》学一下。其实数据结构之是要求要先学完《离散数学》和《概率论》的。

Answer 3

A

Answer 4

1.A