四、应用题(每小题6分，共24分)1.已知串a=′1234+-*′、b=′1+2-3*4′，请用串的各种基本运算将串a转换为串b。规定：运算中不能引入新的字符串，所有的字符串只能从串a中取得。
2.给定二叉树的中序遍历结果为abc，请画出能得到此中序遍历结果的二叉树的所有形态。
3.请画出下面无向图的邻接矩阵和邻接表。
4.已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
五、设计题(每小题6分，共12分)
1.
如下图所示，设有两个栈s1和s2共亨同一数组存储空间stack［1..m］，其中栈s1的栈底设在stack［1］处，而栈s2的栈底设在stack［m］处，请编写栈s1和s2的进栈操作push(i,x)和退栈操作pop(i)，其中i=1、2，分别表示栈s1和s2。要求：仅当整个空间stack［1..m］占满时才产生上溢。2.已知线性表的关键字集合{87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47}，已知散列函数为H(k)=k MOD 13，采用拉链法处理冲突，设计出该开散列表的结构。
考试问吧
