从下列的 2 道试题(试题五至试题六)中任选 1 道解答。如果解答的试题数超过 1 道，则题号小的 1 道解答有效。

            试题五

            阅读下列程序说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。

            [程序 5.1 说明]

            “背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N

            件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于

            S 。

            如下程序均能求得“背包问题”的一组解，其中程序 5.1 是“背包问题”的递归解法，而程序 5.2 是“背包问题”的非递归解法。

            [程序 5.1]

            #include

            #define N 7

            #define S 15

            int w[N+1] = {0，1，4，3，4，5，2，7}；

            int knap ( int S， int n)

            { if(S == 0) return 1；

            if ( sO && n<1 )) return 0；

            if ( __(1)__ ) ) {

            printf( "4d"，w[n] )；return 1；

            } return __(2)__ ；

            }

            main() {

            if ( knap(S，N) ) printf( "OK!\n" )；

            else printf( "N0!\n" )；

            }

            [程序 5.2]

            #include

            #define N 7

            #define S 15

            typedef struct {

            int S；

            int n：

            int job；

            } KNAPTP；

            int w[N+1] = {0，1，4，3，4，5，2，7}；

            int knap(int S，int n)；

            main(){

            if ( knap(S，N) ) printf("0K!\n" )；

            else printf( "N0!\n" )；

            int knap( int S，int n )

            { KNAPTP stack[100]，x；

            int top， k， rep；

            x.s = s； x.n = n；

            x.job = 0；

            top = l； stack[top] = x；

            k = 0；

            while ( __(3)__ ) {

            x = stack[top]；

            rep = l；

            while ( !k && rep ) {

            if( x.s＝0 ) k = 1； /*已求得一组解*/

            else if ( x.S<0 || x.n<=0 ) rep = 0；

            else { x.s = __(4)__ ； x.job=1；

            __(5)__ = x；

            }

            }

            if ( !k ) {

            rep = 1；

            while ( top >= 1 && rep) {

            x = stack[top--]；

            if ( x.job＝1){

            x.s += w[x.n + 1]；

            x.job = 2；

            stack[++top] = x；

            __(6)__ ；

            }

            }

            }

            }

            if (k){ */输出一组解*/

            while ( top >= 1 ) {

            x = StaCk [ top-- ]；

            if ( x.job == 1 )

            printf ( "M\t，w[x.n+1] )；

            }

            }

            return k；

            }

            试题六

            阅读下列程序说明和 C++ 代码，将应填入__(n)__处的字句写在答卷的对应栏内。

            [程序 6 说明]

            本程序实现两个多项式的乘积运算。多项式的每一项由类 Item 描述，而多项式由类 List 描述。类 List 的成员函数有：

            createList()：创建按指数降序链接的多项式链表，以表示多项式。

            reverseList()：将多项式链表的表元链接顺序颠倒。

            multiplyList( List L1，List 12 )计算多项式 L1 和多项式 L2 的乘积多项式。

            [程序6]

            #include

            class List；

            class ltem {

            friend class List；

            private：

            double quot；

            int exp；

            Item *next；

            public：

            Item( double_quot，int_exp)

            {__(1)__；}

            }；

            class List{

            private:

            Item *list；

            public：

            List(){list：NULL；}

            void reverseList()；

            void multiplyList(List L1，List L2)；

            void createList()；

            }；

            void List::createList()

            { Item *p， *U， *pre；

            int exp；

            double quot；

            1ist = NULL；

            while __(1)__ {

            cout << "输入多项式中的一项(系数、指数)：" << endl；

            cin >> quot >> exp：

            if ( exp<0 ) break； //指数小于零，结束输入

            if ( quot=0 ) continue；

            p = list；

            while ( __(2)__ ) { //查找插入点

            pre = p；p = p->next；}

            if ( p != NULL && exp ＝ p->exp ) { p->quot += quot；continue；}

            u = __(3)__ ；

            if (p == list) list = u；

            else pre->next = u；

            u ->next = p；}

            }

            void List :: reverseList()

            { Item *p，*u；

            if ( 1ist＝NULL ) return；

            p = list ->next；list -> next = NULL；

            while ( p != NULL) {

            u = p -> next；p ->next = list；

            list = p； p = u；}

            }

            void List :: multiplyList ( List L1，List L2 )

            { Item *pLl，*pL2，*u；

            int k，maxExp；

            double quot；

            maxExp = __(4)__；

            L2.reverseList()； list=NULL

            for ( k = maxExp；k >= 0；k-- ){

            pLl = L1.1ist；

            while ( pLl != NULL && pLl -> exp > k ) pLl = pLl ->next；

            pL2 = L2.1ist

            while (pL2 NULL && __(5)__ pL2 = pL2 -> next；

            quot = 0.0；

            while (pLl != NULL && pL2 != NULL){

            if(pLl—>exp+pL2->exp’：k) {

            __(6)__ ；

            pLl = pLl -> next；pL2 = pL2 -> next；

            } else if ( pLl -> exp + pL2 -> exp > k ) pLl = pLl -> next；

            else pL2 = pL2 -> next；

            }

            if ( quot !=0.0 ){

            u = new ltem( quot，k )；

            u -> next = list；list = u；}

            }

            reverseList()； L2.reverseList()：

            }

            void main()

            { List L1，L2，L；

            cout << "创建第一个多项式链表\n"； L1.createList()；

            cout << "创建第二个多项式链表\n"； L2.createList()；

            L.multiplyList ( L1，L2)；

            }

百灵编辑：宝葵