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

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

null

1.下面给出了使用两个堆栈S1和S2的队列Q的实现：

                     void                               insert(Q, x) {                   
                                         push (S1, x);                   
                     }                   
                             
                     void                               delete                               (Q){                   
                                         if                               (stack-empty(S2)) then                   
                                         if                               (stack-empty(S1)) then {                   
                                         print(“Q is empty”);                   
                                         return                               ;                   
                                         }                   
                                         else                               while                               (!(stack-empty(S1))){                   
                                         x=pop(S1);                   
                                         push(S2,x);                   
                                         }                   
                                         x=pop(S2);                   
                     }                   

设n insert和m（<=n）delete操作在空队列Q上以任意顺序执行。设x和y分别为该过程中执行的推送和弹出操作的数量。以下哪一项适用于所有m和n？ （A） n+m<=x<2n和2m<=y<=n+m（B） n+m<=x<2n和2m<=y<=2n（C） 2m<=x<2n和2m<=y<=n+m（D） 2m<=x<2n和2m<=y<=2n答复（A）插入和删除操作的执行顺序在这里很重要。 最好的情况是： 插入和删除操作交替执行。在每个删除操作中，执行2个pop和1个push操作。因此，总共执行了m+n次推送（n次推送用于插入（），m次推送用于删除（））操作和2m次弹出操作。 最坏的情况是： 首先插入n个元素，然后删除m个元素。在第一次删除操作中，执行n+1 pop操作和n push操作。除了第一次，在所有删除操作中，执行一次pop操作。因此，总共执行了m+n个pop操作和2n个push操作（n个push用于insert（）和m个push用于delete（））

2、考虑下面的图表： 以下哪一项不能是使用Kruskal算法按顺序添加到最小生成树的边序列？ （A）（A-b）、（d-f）、（b-f）、（d-c）、（d-e）（B）（a-B）、（d-f）、（d-c）、（B-f）、（d-e）（C）（d-f）、（a-b）、（d-C）、（b-f）、（d-e）（D）（D-f）、（a-b）、（b-f）、（D-e）、（D-c）

答复（D）边（d-e）不能在中的（d-c）之前考虑 Kruskal最小生成树算法因为Kruskal的算法在每一步从当前的边集合中选取权重最小的边。

3.n元素的中值可以在O（n）时间内找到。以下哪一项关于快速排序的复杂性是正确的，即选择中值作为枢轴？ （A） Θ（n）（B） Θ（nlogn）（C） Θ（n^2）（D） Θ（n^3）

答复（B）如果中位数总是用作轴心，那么在所有情况下，递归仍然是T（n）=2T（n/2）+cn，其中cn是中位数查找和划分的组合时间。因此，这种快速排序的最坏情况时间复杂度变为Θ（nlogn）。然而，在实际实现中，这种变体的平均速度要慢得多（参见 http://en.wikipedia.org/wiki/Quicksort#Selection-基于旋转的 )

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

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

THE END

技术文章