精品文档
7．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。 8．已知Ackerman函数定义如下：
?n?1当m?0时?akm(m,n)=?akm(m?1,1)当m?0,n?0时
?akm(m?1,akm(m,n?1))当m?0,n?0时?试写出递归算法。
9．设函数f(m,n)按下式定义（ m,n为）0的整数）
?m?n?1当m*n?0时f(m,n)=?
f(m?1,f(m,n?1))当m*n?0时?试写出计算函数的递归过程。
10．设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1,w2,.. .，wn.问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S.如果存在一种符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假），试用递归和非递归两种方法设计此背包问题的算法。
11．借助栈(可用栈的基本运算)来实现单链表的逆置运算。
第 3 章 栈和队列 参考答案 一、名词解释（略） 二、填空题 1、 先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈 2、 初始化InitStack(S)、进栈Push(S,X), 退栈Pop(S)，读栈顶Top(S),判栈空Empty(S) 3、 下溢 4、 上溢 5、 顺序、链接 6、 栈空、下溢、栈满、上溢 7、 sq->top=0 8、 sq->top++,sq->data[sq->top] 9、 sq->data[sq->top],sq->top— 10、 sq->top= =0 11、 sq->top= =0,sq->data[sq->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,x) 19、 假溢出 20、 sq->front=0 21、 sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x 22、 sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x= sq->data[sq->rear] 23、 sq.rear= sq.front 24、 sq.front,(sq.front+1)%maxsize 25、 队满、队空 26、 lq->front=p,NULL 27、 p->data,p,lq->rear=p 28、 *x,s->next 29、 lq.rear= =lq.front 30、 p=lq.front->next,*x 31、先进后出（后进先出） 32、先进先出（后进后出） 33、ls= =NULL,*x=p->info 34、n-1 35、栈 36、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 data[sqstack_maxsize]; int top }SqStackTp 它有两个域：data和top。Data为一个一维数组，用于存储栈中元素，DataType为栈元素的数据类型。Top为int型，它的实际取值范围为0~sqstack_maxsize－1。 2、链栈的类型定义如下： 精品文档
精品文档
typedef stuct node { DataType data; struct node *next; }LstackTp; 单链表的第一个结点就是链栈栈顶结点，链栈由栈顶指针惟一确定。栈中的其它结点通过它们的next域链接起来不。栈底结点的next域为NULL。 3、顺序队列的类型定义如下： #define maxsize 顺序栈的容量 typedef struct sqqueue {DataType data[maxsize]; int fornt,rear }SqQueueTp SqQueueTp sq; 该类型变量有三个域：data,front,rear。其中data存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，实际取值范围为0~maxsize－1。 循环队列的类型定义如下： #define maxsize 循环队的容量 typedef struct cycqueue{ DataType data[maxsize] Int front,rear }CycqueueTp; CycqueueTp sq; 4、typedef struct linked_queue { DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr { LqueueTp *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 data[maxnum+1];/*这里假定三元组的下标的起始值为1*/ 精品文档
精品文档 }SpMatrixTp 6、int length(CycqueueTp sq) {len=(sq.rear-sq.front+maxsize)%maxsize; return(len); } 7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、2431 8、运行结果：ABCDEFGHIJKLM MLKJIHGFEDCBA 9、借助栈将一个带头结点的单链表倒置。 10 r’ r r’’ r’ r 4 5 r’’’ r’’ r’ r Top-> 1 2 3 4 5 rTop-> 2 3 4 5 rTop-> 3 r Top-> 4 r 5 r Top-> 5 rTop-> f(1)前 调用f(5)前 调用f(5)前 调用f(4)前 调用f(3)前 调用f(2)前 调用 r Top-> 2 3 4 5 r’’’ r’’ r’ r Top-> 3 4 5 r’’ r’ r Top-> 4 5 r’ r Top-> 5 后 五、算法设计 Top-> 返回f(1)后 返回f(2)后 返回f(3)后 返回f(4)后 返回f(5)1．本程序中，将客车类定义一个队KE，货车类定义一个队HE，过江渡船定义成一个栈DC。栈采用顺序存储结构，队采用链式存储结构。 #define sqstack_maxsize 10 typedef struct sqstack {DataType data[sqstack_maxsize]; int top; }SqStackTp; 精品文档
精品文档
typedef struct linked_queue {DataType data; struct linked_queue *next; }LqueueTp; typedef struct 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);} else {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 (lq.rear==lq.front) return(1); return(0); } int Push (SqStackTp *sq , DataType x) { if (sq ->top = =sqstack_maxsize-q) {return(0);} else {sq ->top++; sq->data[sq->top]=x; return(1);} } void main() { SqStackTp DC; //DC表示渡船 QueptrtTp KE ,HE; // KE表示客车E、HE表示货车 精品文档
数据结构练习题 第三章 栈、队列和数组 习题及答案讲解学习
