如，ABC变为BCA的操作步骤XXSXSS。（5分）2．现有某二叉树，按先根遍历的序列为ABDEFCGH，按中根遍历的序列为DEFBGHCA，试画出此二叉树。（6分）3．给定表192218153020423516，按数据元素在表中的次序构造一棵二叉排序树。（6分）4．已知序列70，83，100，65，10，32，7，9，请给出采用直接插入排序法对该序列作升序排序时的每一趟结果。（7分）5．已知无向图G的邻接表如下，请画出其所有的连通分量。（6分）
四、设计题共14分1．设字符串仅由圆括号“（”和“）”，方括号“”和“”，花括号“”和“”组成，利
用链栈的操作编写一个检查括号是否正确配对的算法：i
tMatcherLstackTPls。例如（）（）是正确的，而（（）））则不正确。设链栈定义如下：（6分）
typedefstruct
ode
chardata
struct
ode
extLStackTp；2．利用一维数组a可以对
个整数进行排序，其中一种排序算法的处理思想是：将
个整数分别作为数组a的
个元素的值，每次（即第i次）从元素ai到a
中挑出最小的一个元素aki≤k≤
，然后将ak与ai换位。这样反复
1次完成排序。编写实现上述算法的函数voidsorti
tai
t
。（8分）
3
fr