数据结构研究复习.doc

1在线索二叉树中如何求先序、中序的前驱、后继，为什么后续线索二叉树是不完备的？ 先序前驱：若左标志为1，则左链为线索，指示其前驱；否则 a) 若该结点是二叉树的根，则其前驱为空；b) 若该结点是其双亲的左孩子或是其双亲的右孩子且其双亲没有左子树，则其前驱为其双亲；c) 若该结点是其双亲的右孩子且其双亲有左子树，则其前驱为其双亲的左子树中的先序遍历列出的最后一个结点。 先序后继：若右标志为1，则右链为线索，指示其后继；否则，如果有左子树则遍历左子树第一个访问的结点，为其后继；如果没有左子树则遍历右子树第一个访问的结点，为其后继； 中序前驱：若左标志为1，则左链为线索，指示其前驱；否则，遍历其左子树最后访问的结点，为其前驱 中序后继：若右标志为1，则右链为线索，指示其后继；否则，遍历其右子树第一个访问的结点，为其后继 后续后继： a) 若该结点是二叉树的根，则其后继为空；b) 若该结点是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继为其双亲；c) 若该结点是其双亲的左孩子且其双亲有右子树，则其后继为其双亲的右子树中的后序遍历列出的第一个结点。 求后续后继需要知道双亲结点，而二叉链表无法找到双亲，因此不完备： 5如果只想得到一个序列中前k（k=5）个最小元素的部分排序序列,可以采用哪些排序方法，最好采用哪种排序方法？ 1插入、快速、归并需要全体排序不合适 2起泡、简单选择、堆可以。 堆完成查找总时间：4n+klogn,起泡和简单选择总时间kn,因此堆较好。 5荷兰国旗 问题分析： 这个问题我们可以将这个问题视为一个数组排序问题，这个数组分为前部，中部和后部三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。由于红、白、蓝三色小球数量并不一定相同，所以这个三个区域不一定是等分的，也就是说如果我们将整个区域放在[0,1]的区域里，由于三色小球之间数量的比不同（此处假设1:2:2），可能前部为[0,0.2)，中部为[0.2,0.6)，后部为[0.6,1]。我们的思路如下：将前部和后部各排在数组的前边和后边，中部自然就排好了。具体的： 设置两个标志位begin和end分别指向这个数组的开始和末尾，然后用一个标志位current从头开始进行遍历： 1）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前进，begin也向前进（表示前边的已经都排好了）。 2）若遍历到的位置为1，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前进。 3）若遍历到的位置为2，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向后退1。 void?swap?(int?var1,?int?var2)?? {???????? ????int?temp?=?var1;?????? ????var1?=?var2;???????? ????var2?=?temp;??? }?? ?? void?shuffle(int?*array)??? {???????? ????int?current?=?0;??????? ????int?end?=?N-1;???????? ????int?begin?=?0;???????? ????while(?current=end?)??????? ????{????????????? ????????if(?array[current]?==0?)???????????? ????????{????????????????? ????????????swap(array[current],array[begin]);?? ????????????current++;?????????????????? ????????????begin++;??? ????????}????????????? ????????else?if(?array[current]?==?1?)?? ????????{?????????????????? ????????????current++;????????????? ????????}????????????? ????????else{//When?array[current]?=2 ?? ????????????swap(array[current],array[end]);?? ????????????end--;?? ????????}???????? ????}??? }?? 8对含有n个互不相同的元素的线性表，能否以低