法是不稳定的() 19、堆排序是稳定的排序方法 20、在分配排序时,最高位优先分配法比最低位优先分配法简单 题二、(15分)试证明:若借助栈由输入序列1,2…n得到输出序列为pl-p2,,pn(它是输 入序列的一个排序),则在输出序列中不可能出现这样的情形:存在着I<j<k使 pj<pk<pi 题三、(12分)假定有下列n*n矩阵(n为奇数) an1 0.. 0 如果用一维数组B按行主次序存储A的非零元素,问1pA中非零元素的行下标与 列下标的关系; 2)给出A中非零元素可的下标(ij)与B中的下标R的关系 3)假定矩阵中每个元素占一个存储单元,且B的起始地址为A。,给出利用a的下标(ij) 定位在B中的位置公式。 题四(8分)试找出分别满足下面条件的所有二叉树: 1)前序序列和中序序列相同 2)中序序列和后序序列相同 3)前序序列和后序序列相同。 题五(15分)在二叉树中查找值为Ⅹ的结点,试编写算法(用C语言)打印值为Ⅹ 的结点的所有祖先,假定值为X的结点不多于1个,最后,试分析该算法的时间复杂 性。(若不加分析,直接写出结果,按零分算) 题六(10分)设如下带权有向图,试利用求每对顶点之间最短路径的 Floyd算法, 给出代价邻接矩阵,矩阵序列A"(i=1,2,3)以及最短路径PATH<ij>(1<=ij<=3)法是不稳定的（ ） １９、堆排序是稳定的排序方法（ ） ２０、在分配排序时，最高位优先分配法比最低位优先分配法简单（ ） 题二、（１５分）试证明：若借助栈由输入序列 1,2,…n 得到输出序列为 p1,p2,…pn,（它是输 入序列的一个排序），则在输出序列中不可能出现这样的情形：存在着 I<j<k,使 pj<pk<pi。 题三、（１２分）假定有下列 n*n 矩阵（n 为奇数） a11 0 …. 0 a1n 0 a22….a2,n-1 0 Ａ＝ . . . . . . an1 0…. 0 ann 如果用一维数组Ｂ按行主次序存储Ａ的非零元素，问 １）Ａ中非零元素的行下标与 列下标的关系； ２）给出Ａ中非零元素 aij 的下标（i,j）与Ｂ中的下标Ｒ的关系； ３）假定矩阵中每个元素占一个存储单元，且Ｂ的起始地址为Ａ０，给出利用 aij 的下标（i,j） 定位在Ｂ中的位置公式。 题四（８分）试找出分别满足下面条件的所有二叉树： １） 前序序列和中序序列相同； ２） 中序序列和后序序列相同； ３） 前序序列和后序序列相同。 题五（１５分）在二叉树中查找值为 X 的结点，试编写算法（用Ｃ语言）打印值为 X 的结点的所有祖先，假定值为 X 的结点不多于１个，最后，试分析该算法的时间复杂 性。（若不加分析，直接写出结果，按零分算） 题六（１０分）设如下带权有向图，试利用求每对顶点之间最短路径的 Floyd 算法， 给出代价邻接矩阵，矩阵序列Ａ（i） (i=1,2,3)以及最短路径 PATH<i,j> (1<=i,j<=3)