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

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

null

1.子集和问题定义如下。给定一组n个正整数，S={a1，a2，a3，…，an}和正整数W，有元素和W之和的S子集吗？解决这个问题的动态程序使用一个二维布尔数组X，有n行和W+1列。X[i，j]，1<=i<=n，0<=j<=W，当且仅当{a1，a2，…，ai}的一个子集的元素和为j时为真。以下哪项对2<=i<=n和ai<=j<=W有效？（A） X[i，j]=X[i-1，j]vx[i，j-ai] （B） X[i，j]=X[i-1，j]vx[i-1，j-ai] （C） X[i，j]=X[i-1，j]vx[i，j-ai] （D） X[i，j]=X[i-1，j]vx[i-1，j-ai]

答复（B）

如果以下任一项为真，则X[I，j]（2<=I<=n和ai<=j<=W）为真1）不包括ai的权重之和等于j，即如果X[i-1，j]为真。2）包括ai在内的权重之和等于j，也就是说，如果X[i-1，j-ai]为真，那么我们得到（j–ai）+ai作为j。 2.在问题1中，数组X的哪个条目（如果为真）表示存在元素和为W的子集？ （A） X[1，W] （B） X[n，0] （C） X[n，W] （D） X[n-1，n]

答复（C）如果我们得到条目X[n，W]为真，那么{a1，a2，…an}的一个子集的和为W。

参考： http://en.wikipedia.org/wiki/Subset_sum_problem

3、考虑下面的C程序，它试图使用二进制搜索来定位数组y[]中的元素X。这个程序是错误的。

                     1.   f(                               int                               Y[10],                               int                               x) {                   
                     2.                               int                               i, j, k;                   
                     3.     i = 0; j = 9;                   
                     4.                               do                               {                   
                     5.             k =  (i + j) /2;                   
                     6.                               if                               ( Y[k] < x)  i = k;                               else                               j = k;                   
                     7.         }                               while                               (Y[k] != x && i < j);                   
                     8.                               if                               (Y[k] == x)                               printf                               (                               "x is in the array "                               ) ;                   
                     9.                               else                               printf                               (                               " x is not in the array "                               ) ;                   
                     10. }                   

程序在Y和x的以下哪项内容上失败？ （A） Y是[12345678910]，x<10（B） Y是[1 3 5 7 9 11 13 15 17 19]，x<1（C） Y是[2]，x>2 （D） Y是[2 4 6 8 10 12 14 16 18 20]，2 4.在问题3中，为了使程序正常工作所需的更正是（A）将第6行改为：如果（Y[k]

                           f(                                        int                                        Y[10],                                        int                                        x) {                         
                                                     int                                        i, j, k;                         
                                                     i = 0; j = 9;                         
                                                     do                                        {                         
                                                     k =  (i + j) /2;                         
                                                     if                                        ( Y[k] < x)  i = k + 1;                                        else                                        j = k - 1;                         
                                                     }                                        while                                        (Y[k] != x && i < j);                         
                                                     if                                        (Y[k] == x)                                        printf                                        (                                        "x is in the array "                                        ) ;                         
                                                     else                                        printf                                        (                                        " x is not in the array "                                        ) ;                         
                           }                         

参考： http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementations

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

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

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

THE END

技术文章