Question

数据结构试题，求解答。（很重要，不会就别乱回答了。会追加分的，万分感谢）

一，设n为正整数，分析下列各程序段中加下划线的语句的程序步数
(1) int i=1,k=0; （2）for (i=1;i<=n;i++)
while (i<n-1){ for (j=i;j<=n;j++)
k-1=10*i; S++;
i++ ____
——
}
二，有5个元素，其入栈的次序为A,B,C,D,E,问可能的出栈序列有多少种？其中是否有CDEAB和BDECA的出栈序列，如果不能说明为什么不能；如果能书名如何得到（即写出进栈或出栈的序列）
三，已知一颗二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这颗二叉树。
四，设有二维组A6*8，每个元素占5个字节存储，顺序存放，A的起始兆地址为1000，计算（1）数组A的体积（即存储量）（2）数组最后一个元素a5，7的起始地址（3）按列悠闲存放时a3,4的地址。
五，设待排序的排序码序列为{46,25,78,62,12,37,70,29}试写出使用快速排序方法每趟排序后的结果，并说明做了多少次排序码比较。

Answer 1

1、（1）循环判断条件为i<n-1，k不参与循环判定，每轮循环i++，所以程序步数为n-2
（2）i从1到n，j从i到n，第一轮第二个for循环循环了n次，第二轮循环了n-1次，直到最后一轮
i=n，则j=n，最后一轮第二个for循环只有一次满足循环的条件，执行了1次，所以程序的步
数为n+n-1+n-2+……+2+1=n(n+1)/2
2、每放进去一个数，我们都可以做出选择是不是立刻拿出来，如果不立刻拿出来，由于堆栈先进后出的特性，他的出栈位置就被确定了，而最后一个E，它进栈后是否立刻出栈不会影响出栈序列所以是2^4个序列,CDEAB不可能，因为这个序列中A比C后出栈，却比B先出栈，我们之前讲过，如果在刚把它放进去的那一刻，他不出站，那么他的位置就被确定下来了，B、A都比C后出栈，说明之前他们都没选择出栈，但是A想要在B之前出栈，那么A一定要选择在放进去的时候出栈。BDECA是可以的，没有违反条件的元素，栈列和输出如下所示
|A| |B| |A| |C| |D| |C| |E| |C| |A| B->BD->BDE->BDEC->BDECA
| | |A| | | |A| |C| |A| |C| |A| | |
| | | | | | | | |A| |A| | | | |
| | | | | | | | | | | | | | | | | |

3、他的思想是从前序里拿一个出来，作为下一个节点，从中序拿到直到拿出的字符一直到拿出的那个字符之间的，都属于左边，剩下的都是右边的，以此来判断生成2叉树，知道前序和中序或者知道后序和中序可以确定唯一的二叉树。前序序列和后序序列的第一个是头节点，根据这道题的前序和中序序列，二叉树为
A
╱ ╲
B F
╱ ╲ ╲
E C G
╲ ╱ ╲
D H J
╲
I

4、6*8=48 48*5=240字节
240化为16进制F0 地址为10F0
列优先则外层循环是j=0-7列，内层是i=0-5行，每次循环偏移量为（j*6+i+1）*5
a3,4是（4*6+4）*5=140 16进制为8C 地址为108C

5、我知道的快速排序版本就有3个，虽然算法几乎一摸一样的，不过对作支点的那个数的位置的互换略有不同，那么每轮的结果自然不一样，我好不容易找到原版教材的算法，是机械工业出版社的《数据结构、算法与应用 ——c++语言描述》版，但愿是一样的算法
1）、以46为支点 ：78，29 ——46，25，29，62，12 ，37，70，78
62，37——46，25，29，37 ，12， 62 ，70 ，78
62 ，12—break—12 ，25 ，29 ，37 ，46 ，62 ，70 ，78
2）、以12 ，46为支点：25 ，12—break—12 ，25 ，29 ，37 ，46 ，62 ，70 ，78
62 ，46—break—12 ，25 ，29 ，37 ，46 ，62 ，70 ，78
3）、由于右坐标小于左坐标，直接return（左右部分都是这种情况）
4）、如果2）.1发生了改变，那么根据递归调用，3）.1即第3轮要在2）.2之前变化

Answer 2

这个是原书

习题集

百度文库里有。如果没积分，评价就获得1分，每天3分，好像一个新号有送分的。由于你的分太少，我就不帮你下啦。
你也可以在百度文库搜搜其他不要分的。我看到好多的。