江南大学833c语言程序考什么方面的

2015年江南大学硕士研究生入学考试

《C语言程序》考试大纲

一、考试的总体要求

考察学生对计算机程序设计的重要概念、基本理论、基本知识的掌握程度，考生应熟练掌握C语言程序设计的基本内容、C语言程序设计的基本方法与编程技巧、数配谨据结构的基本内容和一般应用方法，并要求考生掌握运纤程序设计的一些常用算法,能利用及设计算法解决和处理实际问题。

二、考试的内容及比例

考试内容涉及面较广，主要包括三部分内容：

（1）C语言程序设计（占50%）；

（2）数据结构（占30%） ；

（3）计算机算法设计(占20%)。具体知识点的比例如下：

第一部分：C语言程序（占50%）

1．C语言的基本概念、基本语句和基本结构。例如： 运算与表达式、顺序结构、选择结构、循环结构等。（约10%）

2．C语言构造类型和指针类型数据。（约10%）

3．C语言函数。（约10%）

4．C语言的预处理。（约5%）

5．C语言文件的使用培悄基。（约5%）

6．C语言常用库函数的使用。（约10%）

第二部分：数据结构（占30%）

1．线性表（约6%）

2．栈、队列和数组（约6%）

3．树和二叉树（约10%）

4．查找和内排序（约8%）

第三部分：计算机算法设计（占20%）

1． 贪心、分治、动态规划、回溯、分支限界（10%）

2． 近似算法、网格算法、PRAM算法（10%）

三、试题类型及比例

1、选择题：20%－30%

2、程序填空题：20%－30%

3、综合应用编程题：40%－60%

四、考试形式及时间

考试形式为笔试。考试时间为3小时。

一.动态规划求解0-1背包问题

/************************************************************************/

/* 0-1背包问题：

/*给定n种物品和一个背包

/*物品i的重量为wi，其价值为vi

/*背包的容量为c

/*应如何选择装入背包的物品，使得装入背包中的物品

/*的总价值最大？

/*注：在选择装入背包的物品时，对物品i只有两种选择，

/*即装入或不装入背包。不能将物品i装入多次，也

/*不能只装入部分的物品i。

/*

/* 1. 0-1背包问题的形式化描述：

/*给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的

/*0-1向量(x1, x2, ..., xn), 使得：

/*max sum_{i=1 to n} (vi*xi),且满足如下约束：

/*(1) sum_{i=1 to n} (wi*xi) <= c

/*(2) xi∈{0, 1}, 1<=i<=n

/*

/* 2. 0-1背包问题的求解

/*0-1背包问题具有最优子结构性质和子问题重叠性质，适于

/*采用动态规划方法求解

/*

/* 2.1 最优子结构性质

/*设(y1,y2,...,yn)是给定0-1背包问题的尘并一个最优解，则必有

/*结论，(y2,y3,...,yn)是如下子问题的一个最优解：

/*max sum_{i=2 to n} (vi*xi)

/*(1) sum_{i=2 to n} (wi*xi) <= c - w1*y1

/*(2) xi∈{0, 1}, 2<=i<=n

/*因为如若不然，则该子问题存在一个最优解(z2,z3,...,zn)，

/*而(y2,y3,...,yn)不是其最优解。那么有：

/*sum_{i=2 to n} (vi*zi) >sum_{i=2 to n} (vi*yi)

/*且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c

/*进一步有：

/*v1*y1 + sum_{i=2 to n} (vi*zi) >sum_{i=1 to n} (vi*yi)

/*w1*y1 + sum_{i=2 to n} (wi*zi) <= c

/*这说明：(y1,z2,z3,...zn)是所给0-1背包问题的更优解，那么

/*说明(y1,y2,...,yn)不是问题的最优解，与前提矛盾，所以最优

/*子结构性质成立。

/*

/* 2.2 子问题重叠性质

/*设所给0-1背包问题的子问题 P(i,j)为：

/*max sum_{k=i to n} (vk*xk)

/*(1) sum_{k=i to n} (wk*xk) <= j

/*(2) xk∈{0, 1}, i<=k<=n

/*问题P(i,j)是背包容量为j、可选物品为i,i+1,...,n时的子问题

/*设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优

/*子结构性质，可以建立m(i,j)的递归式：

/*a. 递归初始 m(n,j)

/*//背橡蔽包容量为j、可选物品只有n，若背包容量j大于物品n的

/*//重量，则直接装入；否则无法装入。

/*m(n,j) = vn, j>=wn

/*m(n,j) = 0, 0<=j<wn

/*b. 递归式 m(i,j)

/*//背包容量为j、可选物品为i,i+1,...,n

/*//如果背包容量j<wi，则根本装不进物品i，所以有：

/*m(i,j) = m(i+1,j), 0<=j<wi

/*//如果j>=wi，则在不装物品派如迹i和装入物品i之间做出选择

/*不装物品i的最优值：m(i+1,j)

/*装入物品i的最优值：m(i+1, j-wi) + vi

/*所以：

/*m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi

/*

/************************************************************************/

#define max(a,b) (((a) >(b)) ? (a) : (b))

#define min(a,b) (((a) <(b)) ? (a) : (b))

template <typename Type>

void Knapsack(Type* v, int *w, int c, int n, Type **m)

{

//递归初始条件

int jMax = min(w[n] - 1, c)

for (int j=0j<=jMaxj++) {

m[n][j] = 0

}

for (j=w[n]j<=cj++) {

m[n][j] = v[n]

}

//i从2到n-1，分别对j>=wi和0<=j<wi即使m(i,j)

for (int i=n-1i>1i--) {

jMax = min(w[i] - 1, c)

for (int j=0j<=jMaxj++) {

m[i][j] = m[i+1][j]

}

for (j=w[i]j<=cj++) {

m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i])

}

}

m[1][c] = m[2][c]

if (c >= w[1]) {

m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1])

}

}

template <typename Type>

void TraceBack(Type **m, int *w, int c, int n, int* x)

{

for (int i=1i<ni++) {

if(m[i][c] == m[i+1][c]) x[i] = 0

else {

x[i] = 1

c -= w[i]

}

}

x[n] = (m[n][c])? 1:0

}

int main(int argc, char* argv[])

{

int n = 5

int w[6] = {-1, 2, 2, 6, 5, 4}

int v[6] = {-1, 6, 3, 5, 4, 6}

int c = 10

int **ppm = new int*[n+1]

for (int i=0i<n+1i++) {

ppm[i] = new int[c+1]

}

int x[6]

Knapsack<int>(v, w, c, n, ppm)

TraceBack<int>(ppm, w, c, n, x)

return 0

}

二.贪心算法求解0-1背包问题

1.贪心法的基本思路：

——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1).不能保证求得的最后解是最佳的；

2).不能用来求最大或最小解问题；

3).只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

2.例题分析

1).[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30

分析：

目标函数： ∑pi最大

约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占空间最小的物品装入是否能得到最优解？

（3）每次选取单位容量价值最大的物品，成为解本题的策略。

<程序代码:>(环境:c++)

#include<iostream.h>

#define max 100 //最多物品数

void sort (int n,float a[max],float b[max]) //按价值密度排序

{

int j,h,k

float t1,t2,t3,c[max]

for(k=1k<=nk++)

c[k]=a[k]/b[k]

for(h=1h<nh++)

for(j=1j<=n-hj++)

if(c[j]<c[j+1])

{t1=a[j]a[j]=a[j+1]a[j+1]=t1

t2=b[j]b[j]=b[j+1]b[j+1]=t2

t3=c[j]c[j]=c[j+1]c[j+1]=t3

}

}

void knapsack(int n,float limitw,float v[max],float w[max],int x[max])

{float c1//c1为背包剩余可装载重量

int i

sort(n,v,w)//物品按价值密度排序

c1=limitw

for(i=1i<=ni++)

{

if(w[i]>c1)break

x[i]=1//x[i]为1时，物品i在解中

c1=c1-w[i]

}

}

void main()

{int n,i,x[max]

float v[max],w[max],totalv=0,totalw=0,limitw

cout<<"请输入n和limitw:"

cin>>n >>limitw

for(i=1i<=ni++)

x[i]=0//物品选择情况表初始化为0

cout<<"请依次输入物品的价值："<<endl

for(i=1i<=ni++)

cin>>v[i]

cout<<endl

cout<<"请依次输入物品的重量："<<endl

for(i=1i<=ni++)

cin>>w[i]

cout<<endl

knapsack (n,limitw,v,w,x)

cout<<"the selection is:"

for(i=1i<=ni++)

{

cout<<x[i]

if(x[i]==1)

totalw=totalw+w[i]

}

cout<<endl

cout<<"背包的总重量为："<<totalw<<endl//背包所装载总重量

cout<<"背包的总价值为："<<totalv<<endl//背包的总价值

}

三.回溯算法求解0-1背包问题

1.0-l背包问题是子集选取问题。

一般情况下，0-1背包问题是NP难题。0-1背包

问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类

似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当

右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余

物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右

子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后

依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是

右子树中解的上界。

2.解决办法思路：

为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考

察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

2.算法框架：

a.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

b.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

3.运用回溯法解题通常包含以下三个步骤：

a.针对所给问题，定义问题的解空间；

b.确定易于搜索的解空间结构；

c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

#include<iostream>

using namespace std

class Knap

{

friend int Knapsack(int p[],int w[],int c,int n )

public:

void print()

{

for(int m=1m<=nm++)

{

cout<<bestx[m]<<" "

}

cout<<endl

}

private:

int Bound(int i)

void Backtrack(int i)

int c//背包容量

int n//物品数

int *w//物品重量数组

int *p//物品价值数组

int cw//当前重量

int cp//当前价值

int bestp//当前最优值

int *bestx//当前最优解

int *x//当前解

}

int Knap::Bound(int i)

{

//计算上界

int cleft=c-cw//剩余容量

int b=cp

//以物品单位重量价值递减序装入物品

while(i<=n&&w[i]<=cleft)

{

cleft-=w[i]

b+=p[i]

i++

}

//装满背包

if(i<=n)

b+=p[i]/w[i]*cleft

return b

}

void Knap::Backtrack(int i)

{

if(i>n)

{

if(bestp<cp)

{

for(int j=1j<=nj++)

bestx[j]=x[j]

bestp=cp

}

return

}

if(cw+w[i]<=c) //搜索左子树

{

x[i]=1

cw+=w[i]

cp+=p[i]

Backtrack(i+1)

cw-=w[i]

cp-=p[i]

}

if(Bound(i+1)>bestp)//搜索右子树

{

x[i]=0

Backtrack(i+1)

}

}

class Object

{

friend int Knapsack(int p[],int w[],int c,int n)

public:

int operator<=(Object a)const

{

return (d>=a.d)

}

private:

int ID

float d

}

int Knapsack(int p[],int w[],int c,int n)

{

//为Knap::Backtrack初始化

int W=0

int P=0

int i=1

Object *Q=new Object[n]

for(i=1i<=ni++)

{

Q[i-1].ID=i

Q[i-1].d=1.0*p[i]/w[i]

P+=p[i]

W+=w[i]

}

if(W<=c)

return P//装入所有物品

//依物品单位重量排序

float f

for( i=0i<ni++)

for(int j=ij<nj++)

{

if(Q[i].d<Q[j].d)

{

f=Q[i].d

Q[i].d=Q[j].d

Q[j].d=f

}

}

Knap K

K.p = new int[n+1]

K.w = new int[n+1]

K.x = new int[n+1]

K.bestx = new int[n+1]

K.x[0]=0

K.bestx[0]=0

for( i=1i<=ni++)

{

K.p[i]=p[Q[i-1].ID]

K.w[i]=w[Q[i-1].ID]

}

K.cp=0

K.cw=0

K.c=c

K.n=n

K.bestp=0

//回溯搜索

K.Backtrack(1)

K.print()

delete [] Q

delete [] K.w

delete [] K.p

return K.bestp

}

void main()

{

int *p

int *w

int c=0

int n=0

int i=0

char k

cout<<"0-1背包问题——回溯法 "<<endl

cout<<" by zbqplayer"<<endl

while(k)

{

cout<<"请输入背包容量(c)："<<endl

cin>>c

cout<<"请输入物品的个数(n)："<<endl

cin>>n

p=new int[n+1]

w=new int[n+1]

p[0]=0

w[0]=0

cout<<"请输入物品的价值(p)："<<endl

for(i=1i<=ni++)

cin>>p[i]

cout<<"请输入物品的重量(w)："<<endl

for(i=1i<=ni++)

cin>>w[i]

cout<<"最优解为(bestx)："<<endl

cout<<"最优值为(bestp)："<<endl

cout<<Knapsack(p,w,c,n)<<endl

cout<<"[s] 重新开始"<<endl

cout<<"[q] 退出"<<endl

cin>>k

}

四.分支限界法求解0-1背包问题

1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

#include <iostream.h>

struct good

{

int weight

int benefit

int flag//是否可以装入标记

}

int number=0//物品数量

int upbound=0

int curp=0, curw=0//当前效益值与重量

int maxweight=0

good *bag=NULL

void Init_good()

{

bag=new good [number]

for(int i=0i<numberi++)

{

cout<<"请输入第件"<<i+1<<"物品的重量:"

cin>>bag[i].weight

cout<<"请输入第件"<<i+1<<"物品的效益:"

cin>>bag[i].benefit

bag[i].flag=0//初始标志为不装入背包

cout<<endl

}

}

int getbound(int num, int *bound_u)//返回本结点的c限界和u限界

{

for(int w=curw, p=curpnum<number &&(w+bag[num].weight)<=maxweightnum++)

{

w=w+bag[num].weight

p=w+bag[num].benefit

}

*bound_u=p+bag[num].benefit

return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) )

}

void LCbag()

{

int bound_u=0, bound_c=0//当前结点的c限界和u限界

for(int i=0i<numberi++)//逐层遍历解树决定是否装入各个物品

{

if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树

upbound=bound_u//更改已有u限界,不更改标志

if( getbound(i, &bound_u)>bound_c )//遍历右子树

//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入

{

upbound=bound_u//更改已有u限界

curp=curp+bag[i].benefit

curw=curw+bag[i].weight//从已有重量和效益加上新物品

bag[i].flag=1//标记为装入

}

}

}

void Display()

{

cout<<"可以放入背包的物品的编号为："

for(int i=0i<numberi++)

if(bag[i].flag>0)

cout<<i+1<<" "

cout<<endl

delete []bag

}

旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有 个子集合(n!>O( ))。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。

枚举法思想：程序中采用深度优先策略。（采用隐式和显式两种形式）

枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。在解决旅行商问题时，以顶点1为起点和终点，然后求{2…N}的一个全排列，使路程1→{2…N}的一个全排列→1上所有边的权（代价）之和最小。所有可能解由（2，3，4，…，N）的不同排列决定。

为便于讨论，介绍一些关于解空间树结构的术语。在下面分析回溯法和分支限界法时都直接或间接用到解空间树。在解空间树中的每一个结点确定所求问题的一个问题状态（problem state）。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space）。解状态（solution states）表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态（answer states）表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件）。解空间的树结构称为状态空间树（state space tree）。

对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出。为了生成问题状态，采用两种根本不同的方法。如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子结点的活结点叫E-结点。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。在生成问题状态的两种方法中，都要用一张活结点表。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当与问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到死结点为止。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。如果旅行商问题要求找出全部解，则要生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法。E-结点一直保持到死为止的状态生成方法称为分支限界法。 为了应用回溯法，所要求的解必须能表示成一个n- 元组(x1,…,Xn)，其中x1是取自某个有穷集Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量。

假定集合Si的大小是mi，于是就有m=m1m2…Mn个n-元组可能满足函数P。所谓硬性处理是构造这m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。而回溯法的基本思想是，不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看乱猜其是否可能导致最优解。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素棚历组成的向量一概略去。因此回溯法作的次数比链陪搜硬性处理作的测试次数（m次）要少得多。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个约束条件，约束条件可以分为两种类型：显示约束和隐式约束。

分支限界法思想：本题采用FIFO分支限界法。

如前所述，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态控件树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。 贪心法是一种改进了的分级处理方法。它首先对旅行商问题进行描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。

获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。

---