数据结构练习题第三章栈、队列和数组习题及答案.pdf

《数据结构练习题第三章栈、队列和数组习题及答案.pdf》由会员分享，可在线阅读，更多相关《数据结构练习题第三章栈、队列和数组习题及答案.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 栈、队列和数组 一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队 10.随机存储结构 11.特殊矩阵 12.稀疏矩阵 13.对称方阵 14.上（下）三角矩阵 二、填空题：1.栈修改的原则是_或称_，因此，栈又称为_线性表。在栈顶进行插入运算，被称为_或_，在栈顶进行删除运算，被称为_或_。2.栈的基本运算至少应包括_、_、_、_、_五种。3.对于顺序栈，若栈顶下标值 top=0,此时，如果作退栈运算，则产生“_”。4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“_”。5.

2、一般地，栈和线性表类似有两种实现方法，即_实现和_实现。6.top=0 表示_，此时作退栈运算，则产生“_”；top=sqstack_maxsize-1表示_，此时作进栈运算，则产生“_”。7.以下运算实现在顺序栈上的初始化，请在_处用适当的句子予以填充。int InitStack(SqStackTp*sq)_;return(1);8.以下运算实现在顺序栈上的进栈，请在_处用适当的语句予以填充。Int Push(SqStackTp*sq,DataType x)if(sp-top=sqstack_maxsize-1error(“栈满”);return(0);else_:_=x;return(1)

3、;9.以下运算实现在顺序栈上的退栈，请在_用适当句子予以填充。Int Pop(SqStackTp*sq,DataType*x)if(sp-top=0)error(“下溢”);return(0);else*x=_;_;return(1);10.以下运算实现在顺序栈上判栈空，请在_处用适当句子予以填充。Int EmptyStack(SqStackTp*sq)if(_)return(1);else return(0);11.以下运算实现在顺序栈上取栈顶元素，请在_处用适当句子予以填充。Int GetTop(SqStackTp*sq,DataType*x)if(_)return(0);else*x=_

4、;return(1);12.以下运算实现在链栈上的初始化，请在_处用请适当句子予以填充。Void InitStacl(LstackTp*ls)_;13.以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。Void Push（LStackTp*ls,DataType x）LstackTp*p;p=malloc(sizeof(LstackTp);_;p-next=ls;_;14以下运算实现在链栈上的退栈，请在_处用请适当句子予以填充。Int Pop(LstackTp*ls,DataType*x)LstackTp*p;if(ls!=NULL)p=ls;*x=_;ls=ls-next;_;retu

5、rn(1)；else return(0);15.以下运算实现在链栈上读栈顶元素，请在_处用请适当句子予以填充。Int Get Top(LstackTp*ls,DataType*x)if(ls!=NULL)_;return(1);else return(0);16.必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下条件：被定义项在定义中的应用（即作为定义项的出现）具有_；被定义项在最小“尺度”上的定义不是_的。17 队列简称_。在队列中，新插入的结点只能添加到_，被删除的只能是排在_的结点。18队列以线性表为逻辑结构，至少包括_、_、_、_ _、五种基本运算。19顺序队的

6、出、入队操作会产生“_”。20 以下运算实现在循环队上的初始化，请在_处用适当句子予以填充。Void InitCycQueue(CycqueueTp*sq)_;sq-rear=0;21.以下运算实现在循环队上的入队列，请在_处用请适当句子予以填充。Int EnCycQueue(CycquereTp*sq,DataType x)if(sq-rear+1)%maxsize=_)error(“队满”);return(0);else _;_ _;return(1);22.以下运算实现在循环队上的出队列，请在_处用适当句子予以填充。Int OutCycQueue(CycquereTp*sq,DataTy

7、pe*x)if(sq-front=_)error(“队空”);return(0)；else _;_;return(1);23.以下运算实现在循环队上判队空，请在_处用适当句子予以填充。Int EmptyCycQueue(CycqueueTp sq)if(_)return(1);else return(0);24.以下运算实现在循环队上取队头，请在_处用适当句子予以填充。Int GetHead(CycqueueTp sq,DataType*x)if=_return(0);else*x=_;return(1);25.链队在一定范围内不会出现_的情况。当=试，队中无元素，此时_。26以下运算实现在链

8、队上的初始化，请在_处用适当句子予以填充。void InitQueue(QueptrTp*lp)LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp)；_；lq-rear=p;(lq-front)-next=_;27.以下运算实现在链队上的入队列，请在_处用适当句子予以填充。Void EnQueue(QueptrTp*lq,DataType x)LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp);_=x;p-next=NULL;(lq-rear)-next=_;_;28.以下运算实现在链队上的出队列，请在_处用

9、适当句子予以填充。int OutQueue(QuetrTp*lq,DataType*x)LqueueTp*s;if(lq-front=lq-rear)erroe(“队空”)；return(0);else s=(lq-front)-next;_=s-data;(lq-front)-next=_；if(s-next=NULL)lq-rear=lq-front;free(s);return(1);29.以下运算实现在链队上判队空，请在_处用适当句子予以填充 int EmptyQueue(QueptrTp*lq)if(_)return(1)；else return(0);30.以下运算实现在链队上读队

10、头元素，请在_处用适当句子予以填充。Int GetHead(QueptrTp lq,DataType*x)LqueueTp*p;if=return(0);else_;_=p-data;return(1);31一般地，一个 n 维数组可视为其数据元素为_维数组的线性表。数组通常只有_和_两种基本运算。32，通常采用_存储结构来存放数组。对二维数组可有两种存储方法：一种是以_为主序的存储方式，另一种是以_为主序的存储方式。C 语言数组用的是以_序为主序的存储方法；FORTRAN 语言用的是以_序为主序的存储方法 33需要压缩存储的矩阵可分为_矩阵和_矩阵两种。34对称方阵中有近半的元素重复，若为每

11、一对元素只分配一个存储空间，则可将 n2 个元素压缩存储到_个元素的存储空间中。35假设以一维数组 M（1：n(n+1)/2）作为 n 阶对称矩阵 A 的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组 M 和矩阵 A 间对应的关系为_。36上三角矩阵中，主对角线上的第 t 行(1=tj 时，aij=c,c 存放在 M_中。37下三角矩阵的存储和对称矩阵类似。MK和 aij的对应关系是_。38 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A 的列序来进行转置，请在_处用适当的句子用以填充。Trans_Sparmat(SpMatrixTp a,SpMatrixTp*

12、b)(*b).mu=;(*b).nu=;(*b).tu=;if q=1;for(col=1;_;col+)for(p=1;p=;p+)if(_=col)(*b).dataq.i=p.j;(*b).dataq.j=p.i;(*b).dataq.v=p.v;_;39基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵 A 的三元组的次序进行转置，请在_处用适当的句子用以填充。Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b)(*b).mu=;(*b).nu=;(*b).tu=;if for(col=1;_;col+)numcol=0;for(t=1;t

13、=a,tu;t+)numt.j+;cpot1=1;for(col=2;col=;col+)cpotcol=_;for(p=1;pnext;free(p)。43设有二为数组 int M1020(注：m 为 0.10,n 为 0.20),每个元素（整数）栈两个存储单元，数组的起始地址为 2000，元素 M510的存储位置为_，M819的存储值为_。44在具有 n 个单元的循环队列中，队满时共有_个元素。45_可以作为实现递归函数调用的一种数据结构。46数组 M 中每个元素的长度是 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 0，从首的址 EA 开始连续存放在存储其中。若按行方式

14、存放，元素 M85的起始地址为_；若按列优先方式存放，元素 M85的地址为_。47对带有头结点的列队列 lq,判定队列中只有一个数据元素的条件是_。48二维数组 M 的成员是 6 个字符（每个字符栈一个存储单元）组成的串，行下标 i的范围从 0 到 8，列下标 j 的范围从 1 到 10，则存放 M 至少需要_个字节；M 的第 8 列和第 5 行共占_个字节；若 M 按行方式存储，元素 M85的起始地址与当M 按列优先方式存储时的_元素的起始地址一致。三、单项选择题 1在以下栈的基本运算中，不是加工型运算的是 （）lnitStack(S)Push(S,X)Pop(S)empty(S)2.以下说

15、法正确的是 ()因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。3在以下队列的基本运算中，不是加工型运算的是 （）InitQueue(Q)EnQueue(Q,X)OutQueu(Q,X)GetHead(Q,x)4.顺序队列的人队操作应为 ()=+1 =x=x =+1=+1)%maxsize;=x sqrear=x =+1)%maxsize 5.循环队列的人队操作应为 ()=+1

16、=x=x =+1=+1)%maxsize =x=x =+1)%maxsize 6.顺序队列的出队操作为 ()=+1)%maxsize =+1=+1)%maxsize=+1 7.循环队列的出队操作为 ()=+1)%maxsize=+1=+)%maxsize=+1 8.循环队列的队满条件为 ()+1)%mazsize=+1)%maxsize;+1%maxsize=+1 sq.(rear+1)%maxsize=9.循环队列的队空条件为 ()+1)%maxsize=+1)%maxsize+)%maxsize=+1+1)%maxsize=10.数组的数据元素类型 DataType 可根据实际需要而定义。

17、以下说法完全正确的是 ()数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 数组的读、写运算只能读取或修改一个数据元素的一部分 数组的读、写运算只能读取或修改一个数据元素整体 11对于以行序为主序的存储结构来说，在数组 Ac1 d1，c2 d2中，c1 和 d1 分别为 数组 A 的第一个下标的上、下界，c2d2分别为第二各下标的上、下界，每个数据元素占 K 个存储单元，二维数组中任一元素 ai,j的存储位置可由()式确定.Loci,j=(d2-c2+1)(i-c1)+(j-c2)*k Loci,j=locc

18、1,c2+(d2-c2+1)(i-c1)+(j-c2)*k Loci,j=Ac1,c2+(d2-c2+1)(i-c1)+(j-c2)*k Loci,j=loc0,0+(d2-c2+1)(i-c1)=(j-c2)*k 12 对于 C 语言的二维数组 DataType Amn,每个数据元素占 K 个存储单元，二维数组中任意元素 ai,j 的存储位置可由()式确定.Loci,j=Am,n+(n+1)*i+j*k Loci,j=loc0,0+(m+n)*i+j*k Loci,j=loc0,0+(n+1)*i+j*k Loci,j=(n+1)*i+j*k 13.线性表的顺序存储结构是一种()的存储结构,

19、线性表的链式存储结构是一种（）的存储结构。随机存取 顺序存储 14如果以链表作为栈的存储结构，则退栈操作是 ()必须判别栈是否满 必须判别栈是否空 判别栈元素的类型 对栈不做任何操作 15 对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ()按照矩阵 A 的列序来进行转置，算法的时间复杂度为 0(nu+tu)按照 A 的三元组的次序进行转置，算法的时间复杂度为 O(nu*tu)按照矩阵 A 的列序来进行转置的方法称快速转置 按照矩阵 A 的列序进行转置,对于 tunext=s s-next=Top-next;Top-next=s s-next=Top;Top=s s-next=Top;

20、Top=Top-next 24.从栈顶指针为 Top 的链栈中删除一个结点，并将被删节点的值保存到 x 中，其操作步骤为（）x=Top-data;Top=Top-next Top=Top-next;x=Top-data x=Top;Top=Top-next x=Top-data 25.在一个链队中，若 f,r 分别为队首、队尾指针，则插入 s 所指结点的操作为（）f-next=c;f=s r-next=s;r=s s-next=r;r=s s-next=f;f=s 26 常对数组进行的两种基本操作是 （）建立与删除 索引与修改 查找与修改 查找与索引 27链栈与顺序栈相比，有一个比较明显的优点

21、即 （）插入操作更方便 通常不会出现栈满的情况 不会出现栈空的情况 删除操作更方便 28若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 （）正确 错误 29。二为数组 Mi,j的元素是 4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 O 到 4，列下标 j 的范围从 O 到 5。M 按行存储时元素 M3,5 的起始地址与 M 按列存储时元素()的起始地址相同。M 2,4 M3,4 M3,5 M4,4 30.一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 （）e d c b a d e c b a

22、d c e a b a b c d e 31.一个队列的人列序是 1，2，3，4，则队列的输出系列是 （）4，3，2，1 1，2，3，4，1，4，3，2 3，2，4，1 32设计一个判别表达式中左、右括号是否配对出线的算法，采用（）数据结构最佳。线性标的顺序存储结构 栈 队列 线性表的链式存储结构 33若已知一个栈的输入序列为 1，2，3，.,n,其输出序列为 P1、P2、.Pn。若 p1=n,则 P1为 i n=i n-i+1 不确定 34以下说法正确的是 a1 a2 a3 顺序队和循环队的队满和队空判断条件是一样的 栈可以作为实现过程调用的一种数据结构 插人和删除操作是数据结构中最基本的两

23、种操作，所以这两种操作在数组中也经常使用 在循环队列中，front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队列为满的条件 front=rear 35.以下说法正确的是 数组是同类型值的集合 数组是一组相继的内存单元 数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间 四、简答及应用 1简述顺序栈的类型定义。2简述链栈的类型定义。3简述顺序队列、循环队列的类型定义。4简述链队的类型定义。5，写出基于三元组的稀疏矩阵的类型说明。6对于循环队列，试写出求队列长度的算法。7设有编号为 t，2，3，4

24、的四辆列车。顺序进入一个占世界共的展台，试写出这四两列车开出车站的所有可能的顺序。8 设有上三角矩阵(aij)n*n,将其上三角元素逐行存于数组 B(1:m)中（m 充分大），使得 Bk=aij,且 k=f1(i)+f2(j)+c。是推导出函数 f1,f2和常数 c(要求 f1和 f2中不含常数项)。9 设有三对角矩阵（aij）n*n,将其三条对角线上的元素逐行存于数组 B(1:3n-2)中，使得 Bk=aij,求：（1）用 i、j 表示 k 的下标变换公式；（2）用 k 表示 i、j 的下标变换公式.10.阅读下列程序，写出程序的运行结果。#define sqstack_maxsize 40

25、 typedef struct sqstack char datasqstack_maxsize;int top;SqStackTp;main()SqStackTp sq;int i;char ch;InitStack(&sq);For(ch=A;chnext;While(p!=NULL)Push(&lsdata);p=p-next;p=head-next;While(!EmptyStack(&ls)Pop(&l,&x);p-data=x;p=p-next;12，对下列函数，按照数据结构导论课本的图 3-5 失利，画出调用 f(5)是引起的工作栈状态变化情况。Int f(int I)if(n=

26、1)return(10);else return(f(I-1)+2);五、算法设计 1.某汽车轮渡口，过江渡船每次能载 10 辆车过江。过江车辆分为客车类和货车类，上渡船的有如下规定：同类车先到先上船；且每上 4 辆客车，才允许上一辆货车；若等待客车不足 4 辆，则以火车代替，若无货车等待允许客车都上船。试写一算法模拟渡口管理。可以在一个数组中保存两个栈：一个栈以数组的第一个单元作为栈底，另一个栈以数组的最后一个单元作为栈底（如下图所示）。设S是其中一个占，是分别编写过程push(S,X)(元素 X 入栈)，出栈 pop(S)和取栈顶元素 Top(S).题示：设其中一个栈为 0，另一栈为 1。

27、0 1 2 M-1 M M+1 栈 0 底 栈 0 顶 栈 1 顶 栈 1 底 3假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列和出队列算法。4假设以数组 cycquem(假设数组范围在 0.m)存放循环队列的元素，同时设变量 rear 和quelen 分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。5编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。6 稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。7假设一个算术表达

28、式中可以包含三中括号：圆括号“（”和“）”，方括号“”和“”以 及 花 括 号 与“”和“”，且 这 三 种 括 号 可 按 任 意 的 次 序 嵌 套 试 用，如（.(.)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。8已知 Ackerman 函数定义如下：akm(m,n)=时当时当时当0n,0m)1n,m(akm,1m(akm0n,0m)1,1m(akm0m1n 试写出递归算法。9设函数 f(m,n)按下式定义（m,n 为）0 的整数）f(m,n)=时当时当0n*m)1n,m(f,1m(f0n*m1nm 试写出计算函数的递归过程。10

29、设有一个背包可以放入的物品重量为 S，现有 n 件物品，重量分别为 w1,w2,.，wn.问能否从这 n 件物品中选择若干件放入此背包，使得放入的重量之和正好为 S.如果存在一种符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假），试用递归和非递归两种方法设计此背包问题的算法。11借助栈(可用栈的基本运算)来实现单链表的逆置运算。第 3 章 栈和队列 参考答案 一、名词解释（略）二、填空题 1、先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈 2、初始化 InitStack(S)、进栈 Push(S,X),退栈 Pop(S)，读栈顶 Top(S),判栈空 Emp

30、ty(S)3、下溢 4、上溢 5、顺序、链接 6、栈空、下溢、栈满、上溢 7、sq-top=0 8、sq-top+,sq-datasq-top 9、sq-datasq-top,sq-top 10、sq-top=0 11、sq-top=0,sq-datasq-top 12、ls=NULL 13、p-data=x,ls=p 14、p-data,free(p)15、*x=ls-data 16、更小的“尺度”、递归 17、队、队尾、队头 18、队列初始化 InitQueue(Q)、入队列 EnQueue(Q,X)、出队 OutQueue(Q,X)、判队列空EmptyQueue(Q)、读队头 ead(Q

31、,x)19、假溢出 20、sq-front=0 21、sq-front,sq-rear=(sq-rear+1)%maxsize,sq-datasq-rear=x 22、sq-rear,sq-fornt=(sq-rear+1)%maxsize,*x=sq-datasq-rear 23、=24、,+1)%maxsize 25、队满、队空 26、lq-front=p,NULL 27、p-data,p,lq-rear=p 28、*x,s-next 29、=30、p=next,*x 31、先进后出（后进先出）32、先进先出（后进后出）33、ls=NULL,*x=p-info 34、n-1 35、栈 36

32、、lq-front-next=lq-rear 三、单项选择题 1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、四、简答及应用 1、顺序栈类型定义如下：#define sqstack_maxsize 顺序栈的容量 typedef struct sqstack DataType datasqstack_maxsize;int top SqStackTp 它有两个域：data 和 top。Data 为一个一维数组，用于存储栈中元素，DataType 为栈元素的数据类型。Top 为 int 型，它的实际取值范围为 0s

33、qstack_maxsize1。2、链栈的类型定义如下：typedef stuct node DataType data;struct node *next;LstackTp;单链表的第一个结点就是链栈栈顶结点，链栈由栈顶指针惟一确定。栈中的其它结点通过它们的 next 域链接起来不。栈底结点的 next 域为 NULL。3、顺序队列的类型定义如下：#define maxsize 顺序栈的容量 typedef struct sqqueue DataType datamaxsize;int fornt,rear SqQueueTp SqQueueTp sq;该类型变量有三个域：data,fron

34、t,rear。其中 data 存储队中元素的一维数组。队头指针 front和队尾指针 rear 定义为整型变量，实际取值范围为 0maxsize1。循环队列的类型定义如下：#define maxsize 循环队的容量 typedef struct cycqueue DataType datamaxsize Int front,rear CycqueueTp;CycqueueTp sq;4、typedef struct linked_queue DataType data;struct linked_queue*next;LqueueTp;typedef struct queueptr Lque

35、ueTp *front,*rear;QueptrTp;QueptrTp lq;5、#define maxnum 非零元素的容量 typedef struct node int i,j;/*非零元素所在的行号、列号*/DataType v;/*非零元素的值*/NODE;typedef struct spmatrix int mu,nu,tu;/*行数、列数、非零元素的个数*/NODE datamaxnum+1;/*这里假定三元组的下标的起始值为 1*/SpMatrixTp 6、int length(CycqueueTp sq)len=、1234、4321、2143、3421、3241、1324、

36、1432、1342、1243、3214、2134、2314、2341、2431 8、运行结果：ABCDEFGHIJKLM MLKJIHGFEDCBA 9、借助栈将一个带头结点的单链表倒置。10 Top-Top-Top-Top-Top-Top-1 r 2 r 2 r 3 r 3 r 3 r 4 r 4 r 4 r 4 r 5 r 5 r 5 r 5 r 5 r 调用 f(5)前 调用 f(5)前 调用 f(4)前 调用 f(3)前 调用 f(2)前 调用 f(1)前 Top-Top-Top-Top-Top-2 r 3 r 3 r 4 r 4 r 4 r 5 r 5 r 5 r 5 r 返回 f(

37、1)后 返回 f(2)后 返回 f(3)后 返回 f(4)后 返回 f(5)后 五、算法设计 1本程序中，将客车类定义一个队 KE，货车类定义一个队 HE，过江渡船定义成一个栈 DC。栈采用顺序存储结构，队采用链式存储结构。#define sqstack_maxsize 10 typedef struct sqstack DataType datasqstack_maxsize;int top;SqStackTp;typedef struct linked_queue DataType data;struct linked_queue*next;LqueueTp;typedef struct

38、queueptr LqueueTp *front,*rear;QueptrTp;int InitStack(SqStackTp *sq)sq-top=0;return(1);void InitQueue(QueptrTp *lp)LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp);lq-front=p;lq-rear=p;(lq-front)-next=NULL;int QutQueue(QueptrTp*lp,Data Type*x)LqueueTp *s;if(lq-front=lq-rear)error(“队空”);return(0);el

39、se s=(lq-front)-nest;*x=s-data;(lq-front)-next=s-next;if(s-next=NULL)lq-rear=llq-front;free(s);return(1);int EmptyQueue(QueptrTp lq)if=return(1);return(0);int Push(SqStackTp*sq,DataType x)if(sq-top=sqstack_maxsize-q)return(0);else sq-top+;sq-datasq-top=x;return(1);void main()SqStackTp DC;表达式已存入字符数组

40、An中。Void prool(An)Initstack(d);I=0;flag=true;while(I0,n1。背包问题如果有解，其选择只有两种可能：一种是选择的一组物品中不包含 Wn，这样 Knap(S,n)的解就是 Knap(S,n-1)的解，另一种是选择中包含 Wn，这时 Knap(S,n)的解就是 Knap(S-Wn,n)的解。另外可以定义：当 S=0 时，背包问题总有解，即 Knap(0,n)=true，只要不选择任何物品放入背包即可：当 S0 时，背包问题无解，即 Knap(S,n)=false，因为无论怎样选择总不能使重量之和为负值，当 S0 但 n1 时，背包问题也无解，即

41、Knap(S,n)=false，因为不取任何东西就要使重量为正值总是办不到的。从而，背包问题可以递归定义如下：|true,当 S=0|false,当 S0 Knap(S,n)=0 且 n0 且 n=1|上述递归定义是确定的，因为每递归一次 n 都减 1，S 也可能减少 ，所以递归若干次以后，一定会出现 S0 或者 n=0，无论哪种情况都可由递归出口明确定值。Int knap(int s,int n)if(s=0)return(1);else if(s0&n1)return(0);else if(knap(s-wn,n-1)printf(“%d”,wn);return(1);else return(knap(s,n-1);9.方法是先依次让单链表上的元素进栈，然后再依次出栈。Void invert(lklist head)LstackTp s;initstack(s);p=head;while(pnull)Push(s,p-data);p=p-next;p=head;while(not emptystack(s)pop(s,p-data);p=p-next;