其中a>1,b>1,a∈N,b∈N 为简单起见,设n为b的整数幂 5.快速排序的时间复杂度是多少?试推导之。 四.程序设计题(38) 1.假设有两个集合A和B,均以元素值递增有序排列的带头结点的单链表作 为存储结构。请编写算法求C=A∩B,要求C按元素值递增有序排列,并要 求利用原表(即表A和表B)的结点空间存放表C。(12) 2.从键盘上输入一串正整数,以一1为输入结束的标志,试设计一个算法,生 成一棵二叉排序树(即依次把该序列中的结点插入二叉排序树)。(12) 3.试设计一个算法,在中序线索二叉树中求指定结点P在后序遍历序列中的 前驱结点。要求算法为非递归的,空间复杂度为O(1)。(14)2 其中 a>1, b>1, aN, bN 为简单起见，设 n 为 b 的整数幂。 5．快速排序的时间复杂度是多少？试推导之。 四. 程序设计题（ 38’） 1．假设有两个集合 A 和 B，均以元素值递增有序排列的带头结点的单链表作 为存储结构。请编写算法求 C=AB，要求 C 按元素值递增有序排列，并要 求利用原表（即表 A 和表 B）的结点空间存放表 C。(12’) 2．从键盘上输入一串正整数，以—1 为输入结束的标志，试设计一个算法，生 成一棵二叉排序树（即依次把该序列中的结点插入二叉排序树）。(12’) 3．试设计一个算法，在中序线索二叉树中求指定结点 P 在后序遍历序列中的 前驱结点。要求算法为非递归的，空间复杂度为 O（1）。(14’)