免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2018年上半年 数据库系统工程师 上午试卷 综合知识
  第5题      
  知识点:      中间代码   算术运算
  关键词:   表达式   后缀式   算术运算        章/节:   计算机软件基础知识       

 
算术表达式采用后缀式表示时不需要使用括号,使用(5)就可以方便地进行求值。a-b(c+d)(其中,-、+、*表示二元算术运算减、加、乘)的后缀式为(6),与该表达式等价的语法树为(7)。
 
 
  A.  队列
 
  B.  数组
 
  C.  栈
 
  D.  广义表
 
 
 

 
  第5题    2019年上半年  
   36%
令序列X、Y、Z的每个元素都按顺序进栈,且每个元素进栈和出栈仅一次。则不可能得到的出栈序列是( )。
  第7题    2021年上半年  
   54%
( )是一种先进先出的线性表,只允许在表的一端插入元素,而在表的另一端删除元素。
  第5题    2020年下半年  
   34%
在常见的数据结构中,(5)是只能通过访问它的端来实现数据存储和检索的一种线性数据结构,它的修改遵循先进后出的原则;(6)是..
 
  第21题    2011年上半年  
   50%
算术表达式采用逆波兰式表示时不用括号,可以利用(20)进行求值。与逆波兰式ab-cd+*对应的中缀表达式是(21)。
  第20题    2011年上半年  
   35%
算术表达式采用逆波兰式表示时不用括号,可以利用(20)进行求值。与逆波兰式ab-cd+*对应的中缀表达式是(21)。
  第21题    2010年上半年  
   69%
逻辑表达式“ a∧b∨ c∧(b ∨ x > 0 )”的后缀式为(21)。(其中∧、∨分别表示逻辑与、逻辑..
   知识点讲解    
   ·     · 中间代码    · 算术运算
 
       栈
               栈的定义及基本运算
               栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说,栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出(FILO)或后进先出(LIFO)的线性表。在栈中进行插入和删除操作的一端称为栈顶(top),相应地,另一端称为栈底(bottom)。不含数据元素的栈称为空栈。栈的基本运算如下:
               ①初始化栈initStack(S):创建一个空栈S。
               ②判栈空isEmpty(S):当栈S为空栈时返回“真”值,否则返回“假”值。
               ③入棧push(S,x):将元素x加入栈顶,并更新栈顶指针。
               ④出栈pop(S):将栈顶元素从栈中删除,并更新栈顶指针。若需要得到栈顶元素的值,可将pop(S)定义为一个函数,它返回栈顶元素的值。
               ⑤读栈顶元素top(S):返回栈顶元素的值,但不修改栈顶指针。
               栈的存储结构
               (1)栈的顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下,需要预先定义或申请栈的存储空间,也就是说栈空间的容量是有限的。因此在顺序栈中,当一个元素入栈时,需要判断是否栈满(栈空间中没有空闲单元),若栈满,则元素入栈会发生上溢现象。
               (2)栈的链式存储。为了克服顺序存储的栈可能存在上溢的不足,可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行,因此不必设置头结点,链表的头指针就是栈顶指针。
               栈的应用
               栈的典型应用包括表达式求值、括号匹配等,在计算机语言的实现以及将递归过程转变为非递归过程的处理中,栈有重要的作用。
 
       中间代码
        从原理上讲,对源程序进行语义分析之后就可以直接生成目标代码,但由于源程序与目标代码的逻辑结构往往差别很大,特别是考虑到具体机器指令系统的特点,要使翻译一次到位很困难,而且用语法制导方式机械生成的目标代码往往是烦琐和低效的,因此有必要设计一种中间代码,将源程序首先翻译成中间代码表示形式,以利于进行与机器无关的优化处理。由于中间代码实际上也起着编译器前端和后端的分水岭作用,所以使用中间代码也有助于提高编译程序的可移植性。常用的中间代码有后缀式、四元式和树等形式。
        (1)后缀式(逆波兰式)。逆波兰式是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面,例如,把a+b写成ab+,所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算,不需要使用括号,也便于用栈实现求值。对于表达式x:=(a+b)*(c+d),其后缀式为xab+cd+*:=。
        (2)树形表示。例如,表达式x:=(a+b)*(c+d)的树形表示如下图所示。
        
        表达式的树形表示
        (3)四元式表示。四元式是一种普遍采用的中间代码形式,其组成成分为运算符OP、第一运算对象ARG1、第二运算对象ARG2和运算结果RESULT。其中,运算对象和运算结果有时指用户自定义的变量,有时指编译程序引入的临时变量,RESULT总是一个新引进的临时变量,用来存放运算结果。例如,表达式x:=(a+b)*(c+d)的四元式表示为:
        ①(+,a,b,t1)②(+,c,d,t2)③(*,t1,t2,t3)④(:=,t3,_,x)
 
       算术运算
               二进制算术运算规则
               (1)加法:二进制加法的进位规则是“逢二进一”。
               0+0=01+0=10+1=11+1=0(有进位)
               (2)减法:二进制减法的借位规则是“借一当二”。
               0-0=01-0=11-1=00-1=1(有借位)
               (3)乘法:
               0×0=01×0=00×1=01×1=1
               机器数的加减运算
               在计算机中,可以只设置加法器,而将减法运算转换为加法运算来实现。
               (1)补码加法的运算法则是:和的补码等于补码求和,即[X+Y]=[X]+[Y]
               (2)补码减法的方法是:差的补码等于被减数的补码加上减数取负后的补码。因此,在补码表示中,可将减法运算转换为加法运算,即[X-Y]补=[X]+[-Y]
               (3)由[X]求[-X]的方法是:[X]的各位取反(包括符号位),末尾加1。
               溢出及判定
               在确定了运算的字长和数据的表示方法后,数据的范围也就确定了。一旦运算结果超出所能表示的数据范围,就会发生溢出。发生溢出时,运算结果肯定是错误的。
               只有当两个同符号的数相加(或者是相异符号数相减)时,运算结果才有可能溢出。
               机器数的乘除运算
               在计算机中实现乘除法运算,通常有如下三种方式。
               (1)纯软件方案,在只有加法器的低档计算机中,没有乘、除法指令,乘除运算是用程序来完成的。这种方案的硬件结构简单,但进行乘除运算时速度很慢。
               (2)在现有的能够完成加减运算的算术逻辑单元ALU的基础上,通过增加少量的实现左、右移位的逻辑电路,来实现乘除运算。与纯软件方案相比,这种方案增加硬件不多,而乘除运算的速度有了较大提高。
               (3)设置专用的硬件阵列乘法器(或除法器),完成乘(除)法运算。该方案需付出较高的硬件代价,可获得最快的执行速度。
               浮点运算
                      浮点加减运算
                      设有浮点数X=M×2iY=N×2j,求X±Y的运算过程如下。
                      (1)对阶。使两个数的阶码相同。令K=|i-j|,把阶码小的数的尾数右移K位,使其阶码加上K
                      (2)求尾数和(差)。
                      (3)结果规格化并判溢出。若运算结果所得的尾数不是规格化的数,则需要进行规格化处理。当尾数溢出时,需要调整阶码。
                      (4)舍入。在对结果进行右移时,尾数的最低位将因移出而丢掉。另外,在对阶过程中也会将尾数右移使最低位丢掉。这就需要进行舍入处理,以求得最小的运算误差。舍入处理的方法如下。
                      ①截断法。将要保留的数据末位右边的数据全都截去,不管数据是0还是1。
                      ②末位恒1法。将要保留的末位数据恒置1,不管右移丢掉的数据是0还是1。
                      ③0舍1入法。舍去的数据为0时,保持末位原始状态。若舍去的数据为1,则将末位加1。这类似于十进制中的四舍五入。但当数据为0.1111…1,即在尾数全为1的特殊情况下,这种舍入会再次产生溢出。遇到这种情况可用硬件判断,并在舍去1时末位不再加1。
                      (5)溢出判别。以阶码为准。若阶码溢出(超过最大值),则运算结果溢出;若阶码下溢(小于最小值),则结果为0,否则结果正确无溢出。
                      浮点乘除运算
                      浮点数相乘,其积的阶码等于两乘数的阶码相加,积的尾数等于两乘数的尾数相乘。浮点数相除,其商的阶码等于被除数的阶码减去除数的阶码,商的尾数等于被除数的尾数除以除数的尾数。乘除运算的结果都需要进行规格化处理并判断阶码是否溢出。
   题号导航      2018年上半年 数据库系统工程师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第5题    在手机中做本题