数据结构和算法|集10

在2007门CS考试中提出了以下问题。

1.二叉树的高度是任何根到叶路径中的最大边数。高度为h的二叉树中的最大节点数为： （A） 2^h-1 （B） 2^（h-1）–1 （C） 2^（h+1）-1 （D） 2*（h+1）

答复（C） 一棵完整的树将有最大数量的节点。 高度为h=1+2+2^2+2*3+的完整树中的节点数…。2^h=2^（h+1）–1

2：可由三个未标记节点形成的二叉树的最大数量为： （A） 一, （B） 五, （C） 四, （D） 三,

答复（B）

             O
          /     
        O        O
           (i)

            O             
          /                             
       O                 
     /                      
   O                         
        (ii)

         O
       / 
     O
        
          O
       (iii)

  O                      
                             
       O                     
                            
           O                                                         
    (iv)

       O
          
            O
          /
       O               
    (v)

请注意，节点未标记。如果节点被标记，我们会得到更多的树。

3.以下哪种排序算法的最坏情况复杂度最低？ （A） 合并排序 （B） 气泡排序 （C） 快速排序 （D） 选择排序

答复（A）

上述排序算法的最坏情况复杂性如下： 合并排序-nLogn 冒泡排序-n^2 快速排序-n^2 选择排序-n^2

4.使用堆栈计算以下带有一位数操作数的后缀表达式：

              8 2 3 ^ / 2 3 * + 5 1 * - 

（A） 6,1 （B） 5,7 （C） 3,2 （D） 1,5

答复（A） 计算任何后缀表达式的算法都非常简单：

1. While there are input tokens left
    o Read the next token from input.
    o If the token is a value
       + Push it onto the stack.
    o Otherwise, the token is an operator 
      (operator here includes both operators, and functions).
       * It is known a priori that the operator takes n arguments.
       * If there are fewer than n values on the stack
        (Error) The user has not input sufficient values in the expression.
       * Else, Pop the top n values from the stack.
       * Evaluate the operator, with the values as arguments.
       * Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
    o That value is the result of the calculation.
3. If there are more values in the stack
    o (Error)  The user input has too many values.

算法来源： http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm

让我们对给定的表达式运行上述算法。 前三个标记是值，所以它们只是被推送。按下8、2和3后，堆栈如下所示

    8, 2, 3  

读取^时，将弹出前两个，并计算功率（2^3）

    8, 8 

读取/时，会弹出前两个并执行除法（8/8）

    1 

接下来的两个标记是值，所以它们只是被推送。按下2和3后，堆栈如下所示

    1, 2, 3

当*出现时，将弹出前两个并执行乘法。

    1, 6

5.二叉树的顺序遍历和前序遍历分别是dbeafcg和abdecfg。二叉树的后序遍历是： （A） d e b f g c A （B） e d B g f c a （C） e d b f g C a （D） D e f g b c a

答复（A）

Below is the given tree.
                              a 
                           /    
                        /          
                      b             c
                   /             /   
                 /             /       
               d         e    f          g

请看 门角 所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。