Question

Java数据结构疑问

1.某二叉树的前序遍历顺序为abdgcefh,中序遍历顺序为dgbaechf,则后序顺序为多少？
2.设某散列表长度为100，散列函数H(k)=k%p,则p通常情况下最好选择( )
A.91 B.93 C.97 D.99
3.下面程序段的时间复杂度为( )
for(int i=0;i<n;i++)
for(int j=1;j<m;j++)
a[i][j]=0;
A.O(m*n) B.O(m+n) C.O(m+n-1) D.O(n)
4.设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5、E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5、E1，则栈S的容量至少应该是( )
A.2 B.3 C.4 D.6

求解JAVA高手解答并说出详细步骤，谢谢。

Answer 1

数据结构好几年了，都忘了，只能解决两问题。

第一个问题：

前序遍历的话，是先根节点，后是左右节点。

中序遍历是先左节点，后是根节点，最后是右节点。

前序遍历a是第一个，所以整个二叉树的根节点是a；

所以中序遍历的a节点前的节点（dgb）都是二叉树的左子树的节点，a后的节点（echf）为右子树的节点；

前序遍历是，左子树的顺序是：bdg，则b肯定是左子树的根节点，即为a的左节点；

左子树剩下dg节点，由于中序遍历时dg节点在b前，所以dg节点肯定是b节点的左子树节点，又因为不管是前序遍历还是中序遍历，顺序都是dg，所以d是b的左节点，g是d的右节点。

右子树的节点（echf），前序（cefh）时c在最前，所以c是a的右节点，中序（echf）在c前的节点为c的左子树节点，只有e，所以e为c的左节点；

只剩下hf节点，前序（fh）和中序（hf）顺序不一致，则只能是如图所示结果。

如图所示，后序遍历(遍历顺序，左子树，右子树，根)的顺序为：gdbehfca

问题四：

E1最后出的，说明E1一直在栈中，E2第一个出的，则E2是进入栈后就出来，此时容量至少是2；

E4第二个出的，说明E3进入栈后没有直接出来直到E4进入栈并出来之后，E3才出来，此时容量至少是3；

随后出来的是E6，则说明E5进入栈后也没直接出来，也是E6出来才轮到E5，此时容量至少也是3。

所以答案是3。

Answer 2

后select * from tableA where value =‘用户输入的单词’
把返回值处理显示呗~~~~~。
这么做，因为表比较少，会导致表中的单词量比较大，select速度也是问题。
但是因为是课设，就不考虑那么多了
不然再根据第二个字母，把每张表分成两张也可以 。
不涉及数据库的话，就是把对应的txt里的信息用IO流读出来，存在map中，key是单词，value是词条信息，直接用map.get(“用户单词”);