数据结构和算法|集11-yiteyi-C++库

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

null

1、考虑大小为七的哈希表，起始索引为0，哈希函数（3x＋4）为MOD7。假设哈希表最初是空的，那么当序列1、3、8、10使用闭合哈希插入到表中时，以下哪项是表的内容？请注意，“u”表示表中的一个空位置。（A） 8，，，，，，，，10 （B） 1,8,10,3, （C） 1，，，，，，，，3 （D） 1,10,8,3, 答复（B）请看 http://lcm.csa.iisc.ernet.in/dsa/node38.html 用于闭式散列和探测。让我们将值1、3、8、10放入大小为7的散列中。最初，哈希表是空的

    -    -    -   -   -   -   -    0    1   2   3   4   5   6

函数（3x+4）mod 7对于1的值是0，所以让我们把值设为0

    1    -    -   -   -   -   -    0    1   2   3   4   5   6

3的函数（3x+4）mod 7的值是6，所以让我们把值设为6

    1    -    -   -   -   -   3    0    1   2   3   4   5   6

8的函数（3x+4）mod 7的值为0，但0已经被占用，让我们将值（8）放在下一个可用空间（1）中

    1    8    -   -   -   -   3    0    1   2   3   4   5   6

10的函数（3x+4）mod 7的值是6，但6已经被占用，让我们把值（10）放在下一个可用空间（2）中

    1    8   10   -   -   -   3    0    1   2    3   4   5   6

2.在无权无向连通图中，根据时间复杂度，从节点S到每个其他节点的最短路径的计算效率最高 （A） Dijkstra的算法从s开始。（B）沃沙尔算法（C）从S开始执行DFS。（D）从S开始执行BFS。答复（D）

 * Time Complexity of the Dijkstra’s algorithm is O(|V|^2 + E)   * Time Complexity of the Warshall’s algorithm is O(|V|^3) * DFS cannot be used for finding shortest paths * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)

3.完整的n元树是每个节点有n个子节点或没有子节点的树。设I为完整n元树的内部节点数，L为叶数。如果L=41，I=10，n的值是多少？ （A）三, （B）四, （C）五, （D）六, 答复（C）对于每个节点都有n个子节点或没有子节点的n元树，以下关系成立

    L = (n-1)*I + 1

其中L是叶节点数，I是内部节点数。让我们找出给定数据的n值。

  L = 41 , I = 10  41 = 10*(n-1) + 1  (n-1) = 4  n = 5

4.在下面的C函数中，设n>=m。

C

                         int                                     gcd(n,m)                       
                         {                       
                                                 if                                     (n%m ==0)                                     return                                     m;                       
                                                 n = n%m;                       
                                                 return                                     gcd(m,n);                       
                         }                       

这个函数进行了多少次递归调用？ （A） Θ（logn）？（B） Ω（n）（C） Θ（logn）（D） Θ（sqrt（n））答复（A）以上代码是欧几里德算法用于寻找最大公约数（GCD）。请看 http://mathworld.wolfram.com/EuclideanAlgorithm.html 时间复杂性。 5.以下递归函数的时间复杂度是多少：

C

                         int                                     DoSomething (                                     int                                     n)                       
                         {                       
                                                 if                                     (n <= 2)                       
                                                 return                                     1;                       
                                                 else                       
                                                 return                                     (DoSomething (                                     floor                                     (                                     sqrt                                     (n))) + n);                       
                         }                       

（A） Θ（n）（B） Θ（nlogn）（C） Θ（logn）（D） Θ（logn）答复（D） DoSomething（）的递归关系为

  T(n) =  T(√n) + C1 if n > 2

我们忽略了地板的部分，因为它是地板还是天花板都无关紧要。

  Let n = 2^m,  T(n) = T(2^m)  Let T(2^m) =  S(m)  From the above two, T(n) = S(m)  S(m) = S(m/2) + C1  /* This is simply binary search recursion*/  S(m)  = O(logm)                = O(loglogn)  /* Since n = 2^m */    Now, let us go back to the original recursive function T(n)   T(n)  = S(m)           = O(LogLogn)

请看门角 所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。 如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章