考试必过 数据结构题集 算法设计答案汇总

数据结构习题集（C语言版本）

算法设计题目答案

第一章绪论

1.16

void print_descending(int x,int y,int z)//

按从大到小顺序输出三个数

{

scanf("%d,%d,%d",&x,&y,&z);

if(xy; //<->为表示交换的双目运算符,以下同

if(yz;

if(xy; //冒泡排序

printf("%d %d %d",x,y,z);

}//print_descending

1.17

Status fib(int k,int m,int &f)//求k 阶斐波那契序列的第m 项的值f {

int tempd;

if(k<2||m<0) return ERROR;

if(m

else if (m==k-1) f=1;

else

{

for(i=0;i<=k-2;i++) temp[i]=0;

temp[k-1]=1; //初始化

for(i=k;i<=m;i++) //求出序列第k 至第m 个元素的值

{

sum=0;

for(j=i-k;j

temp[i]=sum;

}

f=temp[m];

}

return OK;

}//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).

1.18

typedef struct{

char *sport;

enum{male,female}

gender;

char schoolname; //校名为'A','B','C','D'或'E'

char *result;

int score;

} resulttype;

typedef struct{

int malescore;

int femalescore;

int totalscore;

} scoretype;

void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中

{

scoretype score ;

i=0;

while(result[i].sport!=NULL)

{

switch(result[i].schoolname)

{

case 'A':

score[ 0 ].totalscore+=result[i].score;

if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;

else score[ 0 ].femalescore+=result[i].score;

break;

case 'B': score.totalscore+=result[i].score;

if(result[i].gender==0) score.malescore+=result[i].score;

else score.femalescore+=result[i].score;

break;

…… …… ……

}

i++；

}

for(i=0;i<5;i++)

{

printf("School %d:\n",i);

printf("Total score of male:%d\n",score[i].malescore);

printf("Total score of female:%d\n",score[i].femalescore);

printf("Total score of all:%d\n\n",score[i].totalscore);

}

}//summary

1.19

Status algo119(int a[ARRSIZE])//求i!*2^i 序列的值且不超过maxint {

last=1;

for(i=1;i<=ARRSIZE;i++)

{

a[i-1]=last*2*i;

if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;

last=a[i-1];

return OK;

}

}//algo119

分析:当某一项的结果超过了maxint 时,它除以前面一项的商会发生异常.

1.20

void polyvalue()

{

float ad;

float *p=a;

printf("Input number of terms:");

scanf("%d",&n);

printf("Input the %d coefficients from a0 to a%d:\n",n,n);

for(i=0;i<=n;i++) scanf("%f",p++);

printf("Input value of x:");

scanf("%f",&x);

p=a;xp=1;sum=0; //xp 用于存放x 的i次方

for(i=0;i<=n;i++)

{

sum+=xp*(*p++);

xp*=x;

}

printf("Value is:%f",sum);

}//polyvalue

第二章线性表

2.10

Status DeleteK(SqList &a,int i,int k)//删

除线性表 a 中第i 个元素起的k 个元素

{

if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;

for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件

a.elem[i+count-1]=a.elem[i+count+k-1];

a.length-=k;

return OK;

}//DeleteK

2.11

Status Insert_SqList(SqList &va,int x)//把x 插入递增有序表va 中

{

if(va.length+1>va.listsize) return ERROR;

va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)

va.elem[i+1]=va.elem[i];

va.elem[i+1]=x;

return OK;

}//Insert_SqList

2.12

int ListComp(SqList A,SqList B)//比较字符表A 和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A

{

for(i=1;A.elem[i]||B.elem[i];i++)

if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];

return 0;

}//ListComp

2.13

LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针

{

for(p=l->next;p&&p->data!=x;p=p->next);

return p;

}//Locate

2.14

int Length(LinkList L)//求链表的长度

{

for(k=0,p=L;p->next;p=p->next,k++);

return k;

}//Length

2.15

void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb 接在ha 后面形成链表hc

{

hc=ha;p=ha;

while(p->next) p=p->next;

p->next=hb;

}//ListConcat

2.16

见书后答案.

2.17

Status Insert(LinkList &L,int i,int b)//在无头结点链表L 的第i 个元素之前插入元素b {

p=L;q=(LinkList*)malloc(sizeof(LNode));

q.data=b;

if(i==1)

{

q.next=p;L=q; //插入在链表头部

}

else

{

while(--i>1) p=p->next;

q->next=p->next;p->next=q; //插入在第i 个元素的位置

}

}//Insert

2.18

Status Delete(LinkList &L,int i)//在无头结点链表L 中删除第i 个元素

{

if(i==1) L=L->next; //删除第一个元素

else

{

p=L;

while(--i>1) p=p->next;

p->next=p->next->next; //删除第i 个元素

}

}//Delete

2.19

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L 中值大于mink 且小于maxk 的所有元素

{

p=L;

while(p->next->data<=mink) p=p->next; //p 是最后一个不大于mink的元素

if(p->next) //如果还有比mink 更大的元素

{

q=p->next;

while(q->datanext; //q是第一个不小于maxk 的元素

p->next=q;

}

}//Delete_Between

2.20

Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L 中所有值相同的元素

{

p=L->next;q=p->next; //p,q 指向相邻两元素

while(p->next)

{

if(p->data!=q->data)

{

p=p->next;q=p->next; //当相邻两元素不相等时,p,q 都向后推一步

}

else

{

while(q->data==p->data)

{

free(q);

q=q->next;

}

p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素

}//else

}//while

}//Delete_Equal

2.21

void reverse(SqList &A)//顺序表的就地逆置

{

for(i=1,j=A.length;i

A.elem[i]<->A.elem[j];

}//reverse

2.22

void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2

{

p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next)

{

q->next=p;p=q;

q=s;s=s->next; //把L 的元素逐个插入新表表头

}

q->next=p;s->next=q;L->next=s;

}//LinkList_reverse

分析:本算法的思想是,逐个地把L 的当前元素q 插入新的链表头部,p 为新表表头. 2.23

void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A 和B 合并为C,A 和B 的元素间隔排列,且使用原存储空间

{

p=A->next;q=B->next;C=A;

while(p&&q)

{

s=p->next;p->next=q; //将B 的元素插入

if(s)

{

t=q->next;q->next=s; //如A 非空,将A 的元素插入

}

p=s;q=t;

}//while

}//merge1

2.24

void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A 和B 合并为C,且C中元素递减排列,使用原空间

{

pa=A->next;pb=B->next;pre=NULL; //pa 和pb 分别指向A,B 的当前元素

while(pa||pb)

{

if(pa->datadata||!pb)

{

pc=pa;q=pa->next;pa->next=pre;pa=q; //将A 的元素插入新表

}

else

{

pc=pb;q=pb->next;pb->next=pre;pb=q; //将B 的元素插入新表

}

pre=pc;

}

C=A;A->next=pc; //构造新表头

}//reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把 A 和B 的元素插入新表的头部pc 处,最后处理A 或B 的剩余元素.

2.25

void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A 和B 的元素的交集并存入C 中

{

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j])

{

if(A.elem[i]

if(A.elem[i]>B.elem[j]) j++;

if(A.elem[i]==B.elem[j])

{

C.elem[++k]=A.elem[i]; //当发现了一个在A,B 中都存在的元素,

i++;j++; //就添加到C 中

}

}//while

}//SqList_Intersect

2.26

void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题

{

p=A->next;q=B->next;

pc=(LNode*)malloc(sizeof(LNode));

while(p&&q)

{

if(p->datadata) p=p->next;

else if(p->data>q->data) q=q->next;

else

{

s=(LNode*)malloc(sizeof(LNode));

s->data=p->data;

pc->next=s;pc=s;

p=p->next;q=q->next;

}

}//while

C=pc;

}//LinkList_Intersect

2.27

void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A 和B 的元素的交集并存回A 中

{

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j])

{

if(A.elem[i]

else if(A.elem[i]>B.elem[j]) j++;

else if(A.elem[i]!=A.elem[k])

{

A.elem[++k]=A.elem[i]; //当发现了一个在A,B 中都存在的元素

i++;j++; //且C 中没有,就添加到C中

}

}//while

while(A.elem[k]) A.elem[k++]=0;

}//SqList_Intersect_True

2.28

void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题

{

p=A->next;q=B->next;pc=A;

while(p&&q)

{

if(p->datadata) p=p->next;

else if(p->data>q->data) q=q->next;

else if(p->data!=pc->data)

{

pc=pc->next;

pc->data=p->data;

p=p->next;q=q->next;

}

}//while

}//LinkList_Intersect_True

2.29

void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)

{

i=0;j=0;k=0;m=0; //i 指示A 中元素原来的位置,m 为移动后的位置while(i

{

if(B.elem[j]

else if(B.elem[j]>C.elem[k]) k++;

else

{

same=B.elem[j]; //找到了相同元素same

while(B.elem[j]==same) j++;

while(C.elem[k]==same) k++;

//j,k 后移到新的元素while(i

A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置

while(i

i++; //跳过相同的元素

}

}//while

while(i

A.elem[m++]=A.elem[i++]; //A 的剩余元素重新存储。

A.length=m;

}// SqList_Intersect_Delete

分析:先从 B 和 C 中找出共有元素,记为same,再在 A 中从当前位置开始, 凡小于same 的元素均保留(存到新的位置),等于same的就跳过,到大于same 时就再找下一个same.

2.30

void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题{

p=B->next;q=C->next;r=A-next;

while(p&&q&&r)

{

if(p->datadata) p=p->next;

else if(p->data>q->data) q=q->next;

else

{

u=p->data; //确定待删除元素u

while(r->next->datanext; //确定最后一个小于u 的元素指针r

if(r->next->data==u)

{

s=r->next;

while(s->data==u)

{

t=s;s=s->next;free(t); //确定第一个大于u 的元素指针s

}//while

r->next=s; //删除r 和s 之间的元素

}//if

while(p->data=u) p=p->next;

while(q->data=u) q=q->next;

}//else

}//while

}//LinkList_Intersect_Delete

2.31

Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s 的直接前驱{

p=s;

while(p->next->next!=s) p=p->next; //找到s 的前驱的前驱p

p->next=s;

return OK;

}//Delete_Pre

2.32

Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre 域

{

for(p=L;!p->next->pre;p=p->next) p->next->pre=p;

return OK;

}//DuLNode_Pre

2.33

Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L 的元素按类型分为三个循环链表.CiList 为带头结点的单循环链表类型.

{

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A;

B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点

while(s)

{

if(isalphabet(s->data))

{

p->next=s;p=s;

}

else if(isdigit(s->data))

{

q->next=s;q=s;

}

else

{

r->next=s;r=s;

}

}//while

p->next=A;q->next=B;r->next=C; //完成循环链表

}//LinkList_Divide

2.34

void

Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值

{

p=L.left;pre=NULL;

while(p)

{

printf("%d",p->data);

q=XorP(p->LRPtr,pre);

pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针

}

}//Print_XorLinkedList

2.35

Status

Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L 的第i 个元素前插入元素x

{

p=L.left;pre=NULL;

r=(XorNode*)malloc(sizeof(XorNode));

r->data=x;

if(i==1) //当插入点在最左边的情况

{

p->LRPtr=XorP(p.LRPtr,r);

r->LRPtr=p;

L.left=r;

return OK;

}

j=1;q=p->LRPtr; //当插入点在中间的情况

while(++j

{

q=XorP(p->LRPtr,pre);

pre=p;p=q;

}//while //在p,q 两结点之间插入

if(!q) return INFEASIBLE; //i 不可以超过表长

p->LRPtr=XorP(XorP(p->LRPtr,q),r);

q->LRPtr=XorP(XorP(q->LRPtr,p),r);

r->LRPtr=XorP(p,q); //修改指针

return OK;

}//Insert_XorLinkedList

2.36

Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L 的第i 个元素{

p=L.left;pre=NULL;

if(i==1) //删除最左结点的情况

{

q=p->LRPtr;

q->LRPtr=XorP(q->LRPtr,p);

L.left=q;free(p);

return OK;

}

j=1;q=p->LRPtr;

while(++j

{

q=XorP(p->LRPtr,pre);

pre=p;p=q;

}//while //找到待删结点q

if(!q) return INFEASIBLE; //i 不可以超过表长

if(L.right==q) //q 为最右结点的情况

{

p->LRPtr=XorP(p->LRPtr,q);

L.right=p;free(q);

return OK;

}

r=XorP(q->LRPtr,p); //q 为中间结点的情况,此时p,r 分别为其左右结点

p->LRPtr=XorP(XorP(p->LRPtr,q),r);

r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针

free(q);

return OK;

}//Delete_XorLinkedList

2.37

void OEReform(DuLinkedList &L)//按1,3,5,...4,2 的顺序重排双向循环链表L中的所有结点

{

p=L.next;

while(p->next!=L&&p->next->next!=L)

{

p->next=p->next->next;

p=p->next;

} //此时p 指向最后一个奇数结点

if(p->next==L) p->next=L->pre->pre;

else p->next=l->pre;

p=p->next; //此时p 指向最后一个偶数结点

while(p->pre->pre!=L)

{

p->next=p->pre->pre;

p=p->next;

}

p->next=L; //按题目要求调整了next链的结构,此时pre 链仍为原状

for(p=L;p->next!=L;p=p->next) p->next->pre=p;

L->pre=p; //调整pre 链的结构,同2.32方法

}//OEReform

分析:next 链和pre 链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.

2.38

DuLNode *

Locate_DuList(DuLinkedList &L,int x)//带freq 域的双向循环链表上的查找

{

p=L.next;

while(p.data!=x&&p!=L) p=p->next;

if(p==L) return NULL; //没找到

p->freq++;q=p->pre;

while(q->freq<=p->freq) q=q->pre; //查找插入位置

if(q!=p->pre)

{

p->pre->next=p->next;p->next->pre=p->pre;

q->next->pre=p;p->next=q->next;

q->next=p;p->pre=q; //调整位置

}

return p;

}//Locate_DuList

2.39

float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值

{

PolyTerm *q;

xp=1;q=P.data;

sum=0;ex=0;

while(q->coef)

{

while(exexp) xp*=x0;

sum+=q->coef*xp;

q++;

}

return sum;

}//GetValue_SqPoly

2.40

void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1 减P2 的差式P3

{

PolyTerm *p,*q,*r;

Create_SqPoly(P3); //建立空多项式P3

p=P1.data;q=P2.data;r=P3.data;

while(p->coef&&q->coef)

{

if(p->expexp)

{

r->coef=p->coef;

r->exp=p->exp;

p++;r++;

}

else if(p->expexp)

{

r->coef=-q->coef;

r->exp=q->exp;

q++;r++;

}

else

{

if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3 中

{

r->coef=p->coef-q->coef;

r->exp=p->exp;r++;

}//if

p++;q++;

}//else

}//while

while(p->coef) //处理P1 或P2 的剩余项

{

r->coef=p->coef;

r->exp=p->exp;

p++;r++;

}

while(q->coef)

{

r->coef=-q->coef;

r->exp=q->exp;

q++;r++;

}

}//Subtract_SqPoly

2.41

void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L 求导

{

p=L->next;

if(!p->data.exp)

{

L->next=p->next;p=p->next; //跳过常数项

}

while(p!=L)

{

p->data.coef*=p->data.exp--;//对每一项求导

p=p->next;

}

}//QiuDao_LinkedPoly

2.42

void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L 拆成只含奇次项的A 和只含偶次项的B

{

p=L->next;

A=(PolyNode*)malloc(sizeof(PolyNode));

B=(PolyNode*)malloc(sizeof(PolyNode));

pa=A;pb=B;

while(p!=L)

{

if(p->data.exp!=2*(p->data.exp/2))

{

pa->next=p;pa=p;

}

else

{

pb->next=p;pb=p;

}

p=p->next;

}//while

pa->next=A;pb->next=B;

}//Divide_LinkedPoly

第三章栈与队列

3.15

typedef struct{

Elemtype *base[2];

Elemtype *top[2];

}BDStacktype; //双向栈类型

Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m 的双向栈tws

{

tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));

tws.base[1]=tws.base[0]+m;

tws.top[0]=tws.base[0];

tws.top[1]=tws.base[1];

return OK;

}//Init_Stack

Status push(BDStacktype &tws,int i,Elemtype x)//x 入栈,i=0 表示低端栈,i=1 表示高端栈{

if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件

if(i==0) *tws.top[0]++=x;

else if(i==1) *tws.top[1]--=x;

else return ERROR;

return OK;

}//push

Status pop(BDStacktype &tws,int i,Elemtype &x)//x 出栈,i=0 表示低端栈,i=1 表示高端栈{

if(i==0)

{

if(tws.top[0]==tws.base[0]) return OVERFLOW;

x=*--tws.top[0];

}

else if(i==1)

{

if(tws.top[1]==tws.base[1]) return OVERFLOW;

x=*++tws.top[1];

}

else return ERROR;

return OK;

}//pop

3.16

void Train_arrange(char *train)//这里用字符串train 表示火车,'H'表示硬席,'S'表示软席{

p=train;q=train;

InitStack(s);

while(*p)

{

if(*p=='H') push(s,*p); //把'H'存入栈中

else *(q++)=*p; //把'S'调到前部

p++;

}

while(!StackEmpty(s))

{

pop(s,c);

*(q++)=c; //把'H'接在后部

}

}//Train_arrange

3.17

int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0

{

InitStack(s);

while((e=getchar())!='&')

push(s,e);

while((e=getchar())!='@')

{

if(StackEmpty(s)) return 0;

pop(s,c);

if(e!=c) return 0;

}

if(!StackEmpty(s)) return 0;

return 1;

}//IsReverse

3.18

Status Bracket_Test(char *str)//判别表达式中小括号是否匹配

{

count=0;

for(p=str;*p;p++)

{

if(*p=='(') count++;

else if(*p==')') count--;

if (count<0) return ERROR;

}

if(count) return ERROR; //注意括号不匹配的两种情况

return OK;

}//Bracket_Test

3.19

Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配{

InitStack(s);

for(p=str;*p;p++)

{

if(*p=='('||*p=='['||*p=='{') push(s,*p);

else if(*p==')'||*p==']'||*p=='}')

{

if(StackEmpty(s)) return ERROR;

pop(s,c);

if(*p==')'&&c!='(') return ERROR;

if(*p==']'&&c!='[') return ERROR;

if(*p=='}'&&c!='{') return ERROR;

//必须与当前栈顶括号匹配

}

}//for

if(!StackEmpty(s)) return ERROR;

return OK;

}//AllBrackets_Test

3.20

typedef struct {

int x;

int y;

} coordinate;

void Repaint_Color(int g[m][n],int i,int j,int color)//把点(i,j)相邻区域的颜色置换为color {

old=g[i][j];

InitQueue(Q);

EnQueue(Q,{I,j});

while(!QueueEmpty(Q))

{

DeQueue(Q,a);

x=a.x;y=a.y;

if(x>1)

if(g[x-1][y]==old)

{

g[x-1][y]=color;

EnQueue(Q,{x-1,y}); //修改左邻点的颜色

}

if(y>1)

if(g[x][y-1]==old)

{

g[x][y-1]=color;

EnQueue(Q,{x,y-1}); //修改上邻点的颜色

}

if(x

if(g[x+1][y]==old)

{

g[x+1][y]=color;

EnQueue(Q,{x+1,y}); //修改右邻点的颜色

}

if(y

if(g[x][y+1]==old)

{

g[x][y+1]=color;

EnQueue(Q,{x,y+1}); //修改下邻点的颜色

}

}//while

}//Repaint_Color

分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢?

3.21

void NiBoLan(char *str,char *new)//把中缀表达式str 转换成逆波兰式new

{

p=str;q=new; //为方便起见,设str 的两端都加上了优先级最低的特殊符号

InitStack(s); //s 为运算符栈

while(*p)

{

if(*p 是字母)) *q++=*p; //直接输出

else

{

c=gettop(s);

if(*p 优先级比c 高) push(s,*p);

else

{

while(gettop(s)优先级不比*p 低)

{

pop(s,c);*(q++)=c;

}//while

push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则

}//else

}//else

p++;

}//while

}//NiBoLan //参见编译原理教材

3.22

int GetValue_NiBoLan(char *str)//对逆波兰式求值

{

p=str;InitStack(s); //s 为操作数栈

while(*p)

{

if(*p 是数) push(s,*p);

else

{

pop(s,a);pop(s,b);

r=compute(b,*p,a); //假设compute为执行双目运算的过程

push(s,r);

}//else

p++;

}//while

pop(s,r);return r;

}//GetValue_NiBoLan

3.23

Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str 转换为波兰式new

{

p=str;Initstack(s); //s 的元素为stringtype 类型

while(*p)

{

if(*p 为字母) push(s,*p);

else

{

if(StackEmpty(s)) return ERROR;

pop(s,a);

if(StackEmpty(s)) return ERROR;

pop(s,b);

c=link(link(*p,b),a);

push(s,c);

}//else

p++;

}//while

pop(s,new);

if(!StackEmpty(s)) return ERROR;

return OK;

}//NiBoLan_to_BoLan

分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).

3.24

Status g(int m,int n,int &s)//求递归函数g 的值s

{

if(m==0&&n>=0) s=0;

else if(m>0&&n>=0) s=n+g(m-1,2*n);

else return ERROR;

return OK;

}//g

3.25

Status F_recursive(int n,int &s)//递归算法

{

if(n<0) return ERROR;

if(n==0) s=n+1;

else

{

F_recurve(n/2,r);

s=n*r;

}

return OK;

}//F_recursive

Status F_nonrecursive(int n,int s)//非递归算法

{

if(n<0) return ERROR;

if(n==0) s=n+1;

else

{

InitStack(s); //s 的元素类型为struct {int a;int b;} while(n!=0)

{

a=n;b=n/2;

push(s,{a,b});

n=b;

}//while

s=1;

while(!StackEmpty(s))

{

pop(s,t);

s*=t.a;

}//while

}

return OK;

}//F_nonrecursive

3.26

float Sqrt_recursive(float A,float p,float e)//求平方根的递归算法

{

if(abs(p^2-A)<=e) return p;

else return sqrt_recurve(A,(p+A/p)/2,e);

}//Sqrt_recurve

float Sqrt_nonrecursive(float A,float p,float e)//求平方根的非递归算法

{

while(abs(p^2-A)>=e)

p=(p+A/p)/2;

return p;

}//Sqrt_nonrecursive

3.27

这一题的所有算法以及栈的变化过程请参见《数据结构(pascal 版)》,作者不再详细写出.

3.28

void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q

{

Q=(CiLNode*)malloc(sizeof(CiLNode));

Q->next=Q;

}//InitCiQueue

void EnCiQueue(CiQueue &Q,int x)//把元素x 插入循环链表表示的队列Q,Q指向队尾元素,Q->next 指向头结点,Q->next->next 指向队头元素

{

p=(CiLNode*)malloc(sizeof(CiLNode)

);

p->data=x;

p->next=Q->next; //直接把p 加在Q 的后面

Q->next=p;

Q=p; //修改尾指针

}

Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q 头部删除元素x

{

if(Q==Q->next) return INFEASIBLE; //队列已空

p=Q->next->next;

x=p->data;

Q->next->next=p->next;

free(p);

return OK;

}//DeCiQueue

3.29

Status EnCyQueue(CyQueue &Q,int x)//带tag 域的循环队列入队算法

{

if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0 表示"空",1 表示"满"

return OVERFLOW;

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE;

if(Q.front==Q.rear) Q.tag=1; //队列满

}//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带tag 域的循环队列出队算法

{

if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;

Q.front=(Q.front+1)%MAXSIZE;

x=Q.base[Q.front];

if(Q.front==Q.rear) Q.tag=1; //队列空

return OK;

}//DeCyQueue

分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.

3.30 Status EnCyQueue(CyQueue &Q,int x)//带length 域的循环队列入队算法

{

if(Q.length==MAXSIZE) return OVERFLOW;

Q.rear=(Q.rear+1)%MAXSIZE;

Q.base[Q.rear]=x;

Q.length++;

return OK;

}//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带length 域的循环队列出队算法

{

if(Q.length==0) return INFEASIBLE;

head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释

x=Q.base[head];

Q.length--;

}//DeCyQueue

3.31

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 {

InitStack(S);InitQueue(Q);

while((c=getchar()!='@')

{

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b) return ERROR;

}

return OK;

}//Palindrome_Test

3.32

void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1 项{

InitCyQueue(Q); //其MAXSIZE 设置为k

for(i=0;i

Q.base[k-1]=1; //给前k 项赋初值

for(i=0;i

for(i=k;i<=n;i++)

{

m=i%k;sum=0;

for(j=0;j

Q.base[m]=sum; //求第i 项的值存入队列中并取代已无用的第一项printf("%d",sum);

}

}//GetFib_CyQueue

3.33

Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作{

if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //队列满

avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2;

if(x>=avr) //根据x 的值决定插入在队头还是队尾

{

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE;

} //插入在队尾

else

{

Q.front=(Q.front-1)%MAXSIZE;

Q.base[Q.front]=x;

} //插入在队头

return OK;

}//EnDQueue Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作

{

if(Q.front==Q.rear) return INFEASIBLE; //队列空

x=Q.base[Q.front];

Q.front=(Q.front+1)%MAXSIZE;

return OK;

}//DeDQueue

3.34

void Train_Rearrange(char *train)//这里用字符串train 表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH 的顺序排列

{

r=train;

InitDQueue(Q);

while(*r)

{

if(*r=='P')

{

printf("E");

printf("D"); //实际上等于不入队列,直接输出P 车厢

}

else if(*r=='S')

{

printf("E");

EnDQueue(Q,*r,0); //0 表示把S 车厢从头端入队列

}

else

{

printf("A");

EnDQueue(Q,*r,1); //1 表示把H 车厢从尾端入队列

}

}//while

while(!DQueueEmpty(Q))

{

printf("D");

DeDQueue(Q);

}//while //从头端出队列的车厢必然是先S 后H 的顺序

}//Train_Rearrange

第四章串

4.10

void String_Reverse(Stringtype s,Stringtype &r)//求s 的逆串r

{

StrAssign(r,''); //初始化r 为空串

for(i=Strlen(s);i;i--)

{

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s 的字符从后往前添加到r 中

}

}//String_Reverse

4.11

void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)

//求所有包含在串s 中而t 中没有的字符构成的新串r

{

StrAssign(r,'');

for(i=1;i<=Strlen(s);i++)

{

StrAssign(c,SubString(s,i,1));

for(j=1;j

if(i==j)

{

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t 中

if(k>Strlen(t)) StrAssign(r,Concat(r,c));

}

}//for

}//String_Subtract

4.12

int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S 中所有子串T替换为V,并返回置换次数

{

for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i 的取值范围

if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T 匹配的子串

{ //分别把T 的前面和后面部分保存为head 和tail

StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));

StrAssign(S,Concat(head,V));

StrAssign(S,Concat(S,tail)); //把head,V,tail 连接为新串

i+=Strlen(V); //当前指针跳到插入串以后

n++;

}//if

return n;

}//Replace

分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?

4.13

int Delete_SubString(Stringtype &s,Stringtype t)//从串s 中删除所有与t相同的子串,并返回删除次数

{

for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++)

if(!StrCompare(SubString(s,i,Strlen(t)),t))

{

StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));

StrAssign(S,Concat(head,tail)); //把head,tail 连接为新串

n++;

}//if

return n,

}//Delete_SubString

4.14

Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new

{

Initstack(s); //s 的元素为Stringtype 类型

for(i=1;i<=Strlen(str);i++)

{

r=SubString(str,i,1);

if(r 为字母) push(s,r);

else

{

if(StackEmpty(s)) return ERROR;

pop(s,a);

if(StackEmpty(s)) return ERROR;

pop(s,b);

StrAssign(t,Concat(r,b));

StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b 连接为新子前缀表达式c push(s,c);

}

}//for

pop(s,new);

if(!StackEmpty(s)) return ERROR;

return OK;

}//NiBoLan_to_BoLan 分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对 3.23 题给出的程序.

4.15

void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars 给串T 赋值,Stringtype 的定义见课本

{

for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i];

}//StrAssign

4.16

char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t 时返回正数,s=t 时返回0,s

{

for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);

if(i>s[0]&&i>t[0]) return 0;

else if(i>s[0]) return -t[i];

else if(i>t[0]) return s[i];

else return s[i]-t[i];

}//StrCompare

4.17

int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T 替换为V,并返回置换次数

{

for(n=0,i=1;i<=S[0]-T[0]+1;i++)

{

for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);

if(k>T[0]) //找到了与T 匹配的子串:分三种情况处理

{

if(T[0]==V[0])

for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换

S[i+l-1]=V[l];

else if(T[0]

{

for(l=S[0];l>=i+T[0];l--)

S[l+V[0]-T[0]]=S[l];

for(l=1;l<=V[0];l++)

S[i+l-1]=V[l];

}

else //新子串长度小于原子串时:先将后部左移

{

for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)

S[l]=S[l-V[0]+T[0]];

for(l=1;l<=V[0];l++)

S[i+l-1]=V[l];

}

S[0]=S[0]-T[0]+V[0];

i+=V[0];n++;

}//if

}//for

return n;

}//String_Replace

4.18

typedef struct {

char ch;

int num;

} mytype;

void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数

{

mytype T[MAXSIZE]; //用结构数组T存储统计结果

for(i=1;i<=S[0];i++)

{

c=S[i];j=0;

while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c 是否已记录过

if(T[j].ch) T[j].num++;

else T[j]={c,1};

}//for

for(j=0;T[j].ch;j++) printf("%c: %d\n",T[j].ch,T[j].num);

}//StrAnalyze

4.19

void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)

//求所有包含在串s 中而t 中没有的字符构成的新串r

{

r[0]=0;

for(i=1;i<=s[0];i++)

{

c=s[i];

for(j=1;j

if(i==j)

{

for(k=1;k<=t[0]&&t[k]!=c;k++); //判断当前字符是否包含在t 中

if(k>t[0]) r[++r[0]]=c;

}

}//for

}//Subtract_String

4.20

int SubString_Delete(Stringtype &s,Stringtype t)//从串s 中删除所有与t相同的子串,并返回删除次数

{

for(n=0,i=1;i<=s[0]-t[0]+1;i++)

{

for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++);

if(j>m) //找到了与t 匹配的子串

{

for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除

《计算机算法设计与分析》习题及答案

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法

11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分，共20 分)

算法设计与分析课后部分习题答案

算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中

for(i=0;i=0;row--)//从上往下递归计算 for(int col=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; else triangle[row][col]+=triangle[row+1][col+1]; out=fopen("output.txt","w"); fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 } 算法实现题4-9 汽车加油问题 问题描述： 一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产出一个最优解。编程任务： 对于给定的n和k个加油站位置，编程计算最少加油次数。数据输入： 由文件input.txt给出输入数据。第1行有2个正整数n和k ，表示汽车加满油后可行驶nkm，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第

北京理工大学《数据结构与算法设计》实验报告实验一

《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名：

一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ |ai∈D,i=1,2,……,n} 基本操作： create(&L,n) 操作结果：构造一个有n个结点的单向环表L。 show(L) 初始条件：单向环表L已存在。 操作结果：按顺序在屏幕上输出L的数据元素。 Josephf( L,m,s,n) 初始条件：单向环表L已存在， s>0,n>0，s

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法分析与设计试卷

《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。

算法设计与实验报告讲解

算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月

目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4)

3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6)

作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系：

(完整版)算法设计与分析期末考试卷及答案a

一．填空题(每空 2 分，共30分) 1．算法的时间复杂性指算法中的执行次数。 2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。 3．设D n表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中，g(n)表示。 5. 分治算法的基本步骤包括。6．回溯算法的基本思想是。 7．动态规划和分治法在分解子问题方面的不同点是。 8．贪心算法中每次做出的贪心选择都是最优选择。 9．PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级 10．选择排序、插入排序和归并排序算法中，算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法，只要在步骤3 前加入随机 化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。 算法QUICKSORT 输入：n 个元素的数组A[1..n] 。 输出：按非降序排列的数组 A 中的元素

1. quicksort(1, n) end QUICKSORT ＿ ＿ 过程 quicksort(A, low, high) ＿ ＿ // 对 A[low..high] 中的元素按非降序排序。 ＿ 号 学 2. if low

算法设计与分析试卷(2010)

内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

算法设计与分析第2版 王红梅 胡明 习题答案

精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)

银行家算法设计实验报告

银行家算法设计实验报告

银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。

（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14

南京邮电大学算法设计实验报告——动态规划法

实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++

三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。

算法分析与设计复习题及答案

算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do

算法设计与分析试卷及答案

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人

算法与设计实验报告

算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明

实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角

问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1;

System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j