某游戏部的Java工程师笔试题
一位JavaEye的朋友easonfans刚刚进行了某公司游戏部的笔试，并在博客中分享了此次Java工程师笔试题中的一些注意事项。解释的比较基础细致，希望对于那些正在准备Java工程师笔试的朋友们有一些帮助。
一、选择题：
5：既希望较快的查找又便于线性表动态变化的查找方法是【】？
A：顺序查找 B：折半查找 C：索引顺序查找 D：哈希法查找
ans：C
详细解释：
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。
顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
分块查找也称为索引顺序查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：① 键域存放相应块的最大关键字；② 链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。
哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点（1≤i≤n），keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有：addr(Ri)=H(keyi)，addr(Ri)为哈希函数。
| 查找算法 | 优点 | 缺点 | 运算效率 |
| 顺序查找 | 最简单的，查找表的存储结构：既适用于顺序存储结构，也适用于链式存储结构。 | 顺序查找效率低，当n过大时，应避免使用。 | 1若查找成功:(n+1)/2; 2若查找失败：n+1; 3设查找成功的概率为p,查找不成功的概率为q=(1-p),则平均比较次数为：E(n)=p*(n+1)/2+q*(n+1)=p*(n+1)/2+(1-p)*(n+1)=(n+1)*(1-p/2); 4若成功和失败的概率各占50%,平均性能:3*(n+1)/4; |
| 二分查找 | 查找速度快； 但表必须有序。 | 频繁插入和删除不方便，二分法查找适于表中元素很少变化而查找频繁的情况。 | 二分法查找的过程可用二叉树来描述，中间结点是二叉树的根，左子表相当于左子树，右子表相当于右子树，由此得到的二叉树便为描述二分法查找的判定树。二分法查找的过程是走了一条从根结点到叶子结点的过程，不论查找成功与失败，查找长度均不超过树的高度，h= log2(n+1) ,那个2是log的下缀； 等概率时，折半查找的平均长度为： 当n很大时，ASL = log2(n+1)-1。 |
| 分块查找（索引顺序查找） | 分块查找综合了顺序查找和二分法查找的优点，既有动态结构，又适于快速查找。 | 设待查找文件有n个记录，平均分成b块，每块有s个记录。若只考虑查找成功的概率，且在块内和索引表中均用顺序查找，则平均查找长度为： E(n)=Eb+Ew=(b+1)/2 +(s+1)/2 =(s^2+2*s+n)/(2*s)； 若s= √n，则平均查找长度取最小值：√n+1 若对索引表采用二分法查找，则平均查找长度为： E(n)=Eb+Ew=S2(b+1) +(s+1)/2 | |
| 哈希表查找 | 不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级 | 哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。 要面临冲突处理问题。 | 基本是：O（1） |
；6：分别以下列构造二叉排序树，与用其他三个序列所构造的结果不同的是【】？
A：（100，80，90，60，120，110，130）
B：（100，120，110，130，80，60，90）
C：（100，60，80，90，120，110，130）
D：（100，80，60，90，120，130，110）
ans：C
这道题我答错了，我选得B，回来一看应该选择C项，有余长时间没有看过操作系统了，好多东西我都忘记了，这道题真真的是蒙的。
详细解释：
一、二叉排序树的定义
二叉排序树或者是空树，或者是具有如下性质的二叉树：
１、左子树上所有结点的数据值均小于根结点的数据值；
２、右子树上所有结点的数据值均大于或等于根结点的数据值；
３、左子树、右子树本身又各是一棵二叉排序树。
二、叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是：
1、以待排序的数据的第一个数据构成根结点；
2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。
所以有2可知，明显我们应该选择出C，因为只有C项的两个子树是以60，120为对应根节点的，其他的三个是以80，120作为子树根节点的。
10：实现发送到某个email链接的Html代码是【】?
A:xxx＠yyy
B:
C:mailto:xxx＠yyy">
D:
ans:C
详细解释：
^_^，这题我做对了，其实我不懂这个Html代码,我做到这道题的时候使用Html语言的逻辑猜的，看A和B，我使用排除法，要使A对，那么要是按照Html的逻辑，那么B也对，所以我知道A和B不对，另外对于D，明显是超链接的语句啊，所以我选得C，回来一看果然对了，蒙也要技术的。
或者自己使用dreamweaver的插入－－电子邮件标签都看的到。
二、填空题：
2.多个线程互斥使用资源，对应的信号量的变化范围【 】？
ans:[0,1]
详细解释：一般信号量为0，1就可以了，若某个资源一次最多可以n个线程可以访问，那么信号量的范围就为【0～（n-1）】
3.对于资源静态分配法来避免死锁，主要是打破了死锁四个条件的那个【】？
ans：部分分配条件
详细解释：
死锁的条件
1、互斥条件（Mutual exclusion）：资源不能被共享，只能由一个进程使用。
2、请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。
3、非剥夺条件（也称为部分分配条件）（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。
4、循环等待条件（Circular wait）：系统中若干进程组成环路，改环路中每个进程都在等待相邻进程正占用的资源
死锁预防的方法：
（1）打破"不剥夺条件：强迫那些请求新资源而没有立即得到满足的进程，释放它已保持的其它资源。即一个进程已占用的资源在运行过程中可能要暂时释放。
（2）打破"部分分配"条件：对某进程所要求的资源一次性地分配完毕。这样，进程在运行过程中就不再需要新的资源。这种方法又称为预先静态分配法。但在做静态分配时，只要有一种资源不能满足，该进程就必需等待．
（3）打破"环路等待"条件：在资源的分配过程中，对资源的请求作出某种限制，使环路不可能出现--有序资源分配法
4.当一个进程独占处理器顺序执行的时候，具有两个特性【】和可再现性。
ans：封闭性
详细解释：
程序顺序执行的特征：
a.顺序性：每一操作必须在下一操作开始之前结束
b.封闭性：程序运行时独占全机资源，资源的状态（除初始状态外）只有本程序才能改变，程序一旦执行，其结果不受外界影响
c.可再现性：程序执行环境和初始条件相同，重复执行时，结果相同
我开始写的是可预见性……我也不从哪里看到这个说法的……
9.中级表达式3+x*(2.4/5+6)所对应的后缀表达式为【】？
ans：3x2.45/6-*+
详细解释：
表达式表示法
算术表达式中最常见的表示法形式有 中缀、前缀和 后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。
中缀表示法
中缀表示法是算术表达式的常规表示法。称它为 中缀表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。
Syntax: operand1 operator operand2 Example: (A+B)*C-D/(E+F)
前缀表示法
前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家 D Jan Lukasiewicz，这种表示法也称 波兰表示法。
Syntax : operator operand1 operand2 Example : -*+ABC/D+EF
后缀表示法
在后缀表示法中，操作符位于操作数后面。后缀表示法也称 逆波兰表示法（reverse Polish notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。
Syntax : operand1 operand2 operator Example : AB+C*DEF+/-
前缀和后缀表示法有三项公共特征：
◆操作数的顺序与等价的中缀表达式中操作数的顺序一致
◆不需要括号
◆操作符的优先级不相关
要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。 优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。
Left associativity : A+B+C = (A+B)+C Right associativity : A^B^C = A^(B^C)
详细步骤：
设以’＠’字符作为结束符的中缀算术表达式已经保存在s1字符串中，转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知：转换前后，表达式中的数值项的次序不变，而运算符的次序发生了变化，由处在两个运算对象的中间变为处在两个运算对象的后面，同时去掉了所有的括号。为了使转换正确，必须设定一个运算符栈，并在栈底放入一个特殊算符，假定为‘＠’字符，让它具有最低的运算符优先级，假定为数值0，此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符，待它的两个运算对象都放入到后缀表达式以后，再令其出栈并写入到后缀表达式中。
把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。若遇到的是空格则认为是分隔符，不需要进行处理；若遇到的是数字或小数点，则直接写入到s2中，并在每个数值的最后写入一个空格；若遇到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；若遇到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；若遇到的是运算符，当该运算符的优先级大于栈顶运算符的优先级（加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的特殊运算符‘＠’和’(’的优先级设定为0)时，表明该运算符的后一个运算对象还没有被扫描并放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再另其出栈并写入s2串中；若遇到的运算符的优先级小于等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后另该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符‘＠’时，把栈中剩余的运算符依次退栈并写入到后缀表达式中，再向s2写入表达式结束符‘＠’和字符串结束符’{post.content}’，整个转换过程就处理完毕，在s2中就得到了转换成的后缀表达式。
或者：
转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：
初始化一个空堆栈，将结果字符串变量置空。
从左到右读入中缀表达式，每次一个字符。
如果字符是操作数，将它添加到结果字符串。
如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
如果字符是个开括号，把它压入堆栈。
如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。
一个例子：
例如，设中缀算术表达式s1为：10+(18+9*3)/15-6＠，使用的运算符栈用R表示，则转换过程如下：
（1）开始时存放后缀表达式的字符串s2为空，R中压入有’＠’算符，它具有最低的优先级0：＠
（2）当扫描到s1中的左括号时，s2和R中的数据变化如下：
1 0 ＠ + (
（3）当扫描到s1中的数值3时，s2和R中的数据变化为：
1 0 1 8 9 3 ＠ + ( + *
（4）当扫描到s1中的右括号时，s2和R变为：
1 0 1 8 9 3 * + ＠ +
（5）当扫描到s1中的数值15时，s2和R又变为：
1 0 1 8 9 3 * + 1 5 ＠ + /
（6）当扫描到s1中的’＠’字符时，s2和R为：
1 0 1 8 9 3 * + 1 5 / + 6 ＠ -
（7）当整个处理过程结束后，R栈为空，s2为：1 0 1 8 9 3 * + 1 5 / + 6 - ＠ ù
10.在一个带头节点的单循环链表中，P指向尾结点的直接前驱，则指向头结点的指针head可用P表示为head＝【 】？
ans：P->next->next
详细解释：其实这道题不难，不过我忘记怎么使用链表指向下一个node了，我写的是P.P.P，无语了……
12有序表（12，18，30，43，56，78，82，95）中以此二分查找43和56元素时，其查找长度分别为【 】和【 】？
ans：1，3