java职位面试10篇

2019-05-14    面经大全   

面试经验1

面试公司:盛大 职位: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=㏒2(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、右子树上所有结点的数据值均大于或等于根结点的数据值;
3、左子树、右子树本身又各是一棵二叉排序树。
二、叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程,它是二叉排序树作媒介,将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是:
1、以待排序的数据的第一个数据构成根结点;
2、对以后的各个数据,逐个插入结点,而且规定:在插入过程的每一步,原有树结点位置不再变动,只是将新数据的结点作为一个叶子结点插入到合适的位置,使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。
所以有2可知,明显我们应该选择出C,因为只有C项的两个子树是以60,120为对应根节点的,其他的三个是以80,120作为子树根节点的。
10:实现发送到某个email链接的Html代码是【】?
A:< mail>xxx@yyy< /mail>
B:< mail href="xxx@yyy"/>
C:< a href="mailto:xxx@yyy">
D:< a href="xxx@yyy">
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)

前缀表示法
前缀表示法中,操作符写在操作数的前面。这种表示法经常用于计算机科学,特别是编译器设计方面。为纪念其发明家 ― 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
详细解释:这题要说难难在那里哪?就是二分法比较的时候,当数列个数是偶数的时候到底是应该去哪个值,也就是说第一次比较的值应该是43,还是56,如果是43,那么这题就是1,3这个结果,那么恭喜你,你答对了,要使56,那么这道题就是3,1.结果正好相反。像本篇日志所涉及的第一道题就讲到了查找方法:二分法,其中还提供一个链接://www.emcad.com/Teaching/DS-DB/Search.htm,其实这个链接中举的例子是错误的,因为在算法实现中(1+n)/2并不会四舍五入,因为c和c++都是取整的,也就是说本题(1+8)/2=4,也就是43而不是56!!!另外还有一种理解方法,有8个数(偶数),那么8/2=4,所以比较的是第四个数。这么理解也是对的。同类其他面试题 点击新一篇或旧一篇可浏览全部同类面试题


旧一篇:2012年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=㏒2(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、右子树上所有结点的数据值均大于或等于根结点的数据值;
3、左子树、右子树本身又各是一棵二叉排序树。
二、叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程,它是二叉排序树作媒介,将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是:
1、以待排序的数据的第一个数据构成根结点;
2、对以后的各个数据,逐个插入结点,而且规定:在插入过程的每一步,原有树结点位置不再变动,只是将新数据的结点作为一个叶子结点插入到合适的位置,使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。
所以有2可知,明显我们应该选择出C,因为只有C项的两个子树是以60,120为对应根节点的,其他的三个是以80,120作为子树根节点的。
10:实现发送到某个email链接的Html代码是【】
A:< mail>xxx@yyy< /mail>
B:< mail href="xxx@yyy"/>
C:< a href="mailto:xxx@yyy">
D:< a href="xxx@yyy">
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)

前缀表示法
前缀表示法中,操作符写在操作数的前面。这种表示法经常用于计算机科学,特别是编译器设计方面。为纪念其发明家 ― 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
详细解释:这题要说难难在那里哪?就是二分法比较的时候,当数列个数是偶数的时候到底是应该去哪个值,也就是说第一次比较的值应该是43,还是56,如果是43,那么这题就是1,3这个结果,那么恭喜你,你答对了,要使56,那么这道题就是3,1.结果正好相反。像本篇日志所涉及的第一道题就讲到了查找方法:二分法,其中还提供一个链接://www.emcad.com/Teaching/DS-DB/Search.htm,其实这个链接中举的例子是错误的,因为在算法实现中(1+n)/2并不会四舍五入,因为c和c++都是取整的,也就是说本题(1+8)/2=4,也就是43而不是56!!!另外还有一种理解方法,有8个数(偶数),那么8/2=4,所以比较的是第四个数。这么理解也是对的。同类其他面试题 点击新一篇或旧一篇可浏览全部同类面试题


旧一篇:2012年Java面试宝典 –精心收集 持续补充中

-------------------------------------------------------

面试经验2

面试公司:文思创新(vanceinfo) 职位:java
当天去了文思创新,面试他们的java dev,
错了,是笔试+面试
笔试的题目,个人觉得没有什么新意,不过考的还算全面
不是全部的题目都会,有两个彻底没有感觉
后来还有一个设计模式的题目,这个彻彻底底的没有感觉
我都没有看过这方面的呢
面试的结果呢,是我被鉴定为Junior类别了
不过她问我的那些都是我没有接触的,
也没有听别人说过,只有开源框架的,在网上听说过
不过最近也在看了,因为没有方向,也不知道到底应不应该看
现在看来,不管是不是有方向,
都应该看看这方面的东西了
他们招聘的人员是出差到南京华为的
4K+30*40差不多5k左右,税前的
现在还没有具体的结果呢,
一方面想去试试,另一方面,想留在上海
唉,有点为难呢
不知大该怎么办...
不管了,有了信儿再说吧!
面试官的提问:简单的自我介绍,之后随便聊聊

-------------------------------------------------------

面试经验3

面试公司:用友软件 职位:java
的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大减反馈的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大减反馈的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大减反馈的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大减反馈的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大减反馈的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大减反馈
面试官的提问:的房间看电视飞机考虑的是风口浪尖了多少积分积极健康刀剑封肯德基疯狂大减疯狂大减疯狂大减疯狂大减疯狂大

-------------------------------------------------------

面试经验4

面试公司:惠普(HP) 职位:Java
ReentrantLock实例化
ReentrantLock有个属性sync,实际上对Lock接口的实现都是包装了一下这个sync的实现
如果是公平模式则创建一个FairSync对象,否则创建一个NonfairSync对象,默认是不公平模式
1. lock() 调用sync.lock()
公平模式下:直接走AQS的acquire函数,此函数的逻辑走一次tryAcquire,如果成功
线程拜托同步器的控制,否则加入NODE链表,进入acquireQueued的tryAcquire,休眠,被唤醒的轮回
不公平模式下和公平模式下逻辑大体上是一样的,不同点有两个:
a. 在执行tryAcquire之前的操作,不公平模式会直接compareAndSetState(0, 1)原子性的设置AQS的资源
0表示目前没有线程占据资源,则直接抢占资源,不管AQS的NODE链表的FIFO原则
面试官的提问:ReentrantLock实例化
ReentrantLock有个属性sync,实际上对Lock

-------------------------------------------------------

面试经验5

面试公司:1号店 职位:Java
大概流程如下:
1.去武汉研发中心,先做40分钟的一个逻辑测试题目
2.武汉项目经理1v1的面试,主要聊离职原因,项目管理,做过什么项目,以前的工作经历,未来的职业和发展规划等。比较轻松,感觉挺好的。然后直接通知等技术复试。
3.上海技术主管电话面试,主要考察技术问题,包括,Java基础知识,缓存技术,多线程,事务处理等,做过的项目,并发处理机制等,大部分回答还可以,少部分没答好。
4.上海项目经理面试,主要考察项目管理能力,包括软件开发周期,模型,软件开发过程,RUP理论等,怎样带领一个团队,碰到一些问题怎么解决,这块我确实比较薄弱,所以实话实说,估计是这块能力不够,没通过。
面试官的提问:1.缓存刷新机制
2.cookie与session区别
3.多线程并发处理方式
4

-------------------------------------------------------

面试经验6

面试公司:samsung 职位:java
一轮电话面试,初选,挺简单的,
二面,在上海cisco,时间挺长的,中午12点半,一直到下午4点半,一直没停,没累死哥,先做一份笔试题
主要考察java的一些原理和主要的类库,接下来有5个面试官,轮流来面试你(不是一起来的,一个一个来)主要问数据结构,SNMP,web相关的主要问了ioc,hibernate的分页和缓存,其他的还问了rmi,java容器相关的(考察你对java容器的熟悉程度,以及对于数据结构的理解程度)数据库相关,perl shell和c shell,根据我的工作经验,还问了一些web balance相关,特别说明一下的是,其中有以为面试官会拿英文和你交流,语速不快,词汇不生僻,不用担心~
面试官的提问:数据结构,SNMP,web相关的主要问了ioc,hibernate的分页和缓存,其他的还问了rmi,

-------------------------------------------------------

面试经验7

面试公司:优街网 职位:java
公司谈薪资的人事非常傻逼,自己公司交不起全额社保,一个劲说全额社保不好,说什么本人扣的多了,养老保险不能全取出来,傻逼的,
社保只有养老保险吗?傻逼一个!
一个劲的吹嘘自己公司的技术人员多厉害,你他妈懂技术吗?真她妈傻逼。
牛逼的会接受这待遇? 给不起钱他妈的别自己上网拉人面试,又是笔试又是面试的浪费老子时间。傻逼的。
谁投你们简历了,还压价,还来个试用期80%!真她妈弱智!妈个逼的。
多少正规上市公司给个1万老子都没去,去你们个傻逼弱智不正规公司?傻逼的。
还以为别人找工作时间长了就找不到工作,没见过这么傻逼的人事了。傻逼!
面试官的提问:狗屎

-------------------------------------------------------

面试经验8

面试公司:北京环世财富科技 职位:java
公司谈薪资的人事非常傻逼,自己公司交不起全额社保,一个劲说全额社保不好,说什么本人扣的多了,养老保险不能全取出来,傻逼的,
社保只有养老保险吗?傻逼一个!
一个劲的吹嘘自己公司的技术人员多厉害,你他妈懂技术吗?真她妈傻逼。
牛逼的会接受这待遇? 给不起钱他妈的别自己上网拉人面试,又是笔试又是面试的浪费老子时间。傻逼的。
谁投你们简历了,还压价,还来个试用期80%!真她妈弱智!妈个逼的。
多少正规上市公司给个1万老子都没去,去你们个傻逼弱智不正规公司?傻逼的。
还以为别人找工作时间长了就找不到工作,没见过这么傻逼的人事了。傻逼!
面试官的提问:狗屎

-------------------------------------------------------

面试经验9

面试公司:上海大智慧软件 职位:Java
先是笔试,出了30道题目,都是主观题,根据自己的理解答题,比较人性化,然后是两人的面试,聊技术和经验,大概1个小时。之后是人事谈薪水。但是试用期有6个月,比较不好。先是笔试,出了30道题目,都是主观题,根据自己的理解答题,比较人性化,然后是两人的面试,聊技术和经验,大概1个小时。之后是人事谈薪水。但是试用期有6个月,比较不好。先是笔试,出了30道题目,都是主观题,根据自己的理解答题,比较人性化,然后是两人的面试,聊技术和经验,大概1个小时。之后是人事谈薪水。但是试用期有6个月,比较不好。
面试官的提问:介绍项目经理。
介绍自己做过的最好的最复杂的项目。和自己在其中的角色。

-------------------------------------------------------

面试经验10

面试公司:PPS网络电视 职位:java
网站访问统计系统是站长们必备的系统之一。目前网上有许多免费的统计系统,例如中国站长站(http:www.cnzz.com)、51(//www.51.la)等。这些系统已经十分成熟,但是并不能为免费用户保存大量的历史数据,也不能根据需要自定义某些功能,例如用户访问追踪等。本系统使用Spring、Struts1、Hibernate构架。记录用户的IP地址、实际地址、访问的网页URL及标题、访问来源、屏幕分辨率、颜色位数、浏览器、操作系统、访问时间等。如果用户通过搜索引擎访问被监听的网页,系统还会记录下搜索引擎页面以及搜索词。
面试官的提问:没问题

-------------------------------------------------------
相关文章
热点文章
推荐文章