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

34．以下说法正确的是

①顺序队和循环队的队满和队空判断条件是一样的 ②栈可以作为实现过程调用的一种数据结构

③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用 ④在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件front=rear 35. 以下说法正确的是 ①数组是同类型值的集合 ②数组是一组相继的内存单元

③数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 ④使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间 四、简答及应用

1．简述顺序栈的类型定义。 2．简述链栈的类型定义。

3．简述顺序队列、循环队列的类型定义。 4．简述链队的类型定义。

5，写出基于三元组的稀疏矩阵的类型说明。 6．对于循环队列，试写出求队列长度的算法。

7．设有编号为t，2，3，4的四辆列车。顺序进入一个占世界共的展台，试写出这四两列车开出车站的所有可能的顺序。

8设有上三角矩阵(aij)n*n,将其上三角元素逐行存于数组B(1:m)中（m充分大），使得B[k]=aij,且k=f1(i)+f2(j)+c。是推导出函数f1,f2和常数c(要求f1和f2中不含常数项)。

9．设有三对角矩阵（aij）n*n,将其三条对角线上的元素逐行存于数组B(1:3n-2)中，使得B[k]=aij,求：

（1） 用i、j表示k的下标变换公式； （2） 用k表示i、j的下标变换公式. 10.阅读下列程序，写出程序的运行结果。 # define sqstack_maxsize 40 typedef struct sqstack

{ char data[sqstack_maxsize]; int top; } SqStackTp; main()

{ SqStackTp sq; int i; char ch;

InitStack(&sq);

For(ch=’A’;ch<=’A’+12;ch++) { Push(&sq,ch);

printf(“%c”,ch); }

printf(“\\n”);

while(!EmptyStack(sq))

{ Pop(&sq,&ch);

9

printf(“&c”,ch); } printf(“\\n”);

}

11.阅读下列算法，写出其完整的功能。 Void reverse_list( LinkedListTP *head) { LstackTP ls,p; DataType x; InitStack(&ls); p=head->next; 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==1) return(10);

else return(f(I-1)+2); }

五、算法设计

1.某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，

上渡船的有如下规定：同类车先到先上船；且每上4辆客车，才允许上一辆货车；若等待客车不足4辆，则以火车代替，若无货车等待允许客车都上船。试写一算法模拟渡口管理。

可以在一个数组中保存两个栈：一个栈以数组的第一个单元作为栈底，另一个栈以

数组的最后一个单元作为栈底（如下图所示）。设S是其中一个占，是分别编写过程push(S,X)(元素X入栈)， 出栈pop(S)和取栈顶元素Top(S).题示：设其中一个栈为0，另一栈为1。

0 1 2 M-1 M M+1

······

栈0底 栈0顶 栈1顶 栈1底 3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列和出队列算法。

4．假设以数组cycque[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。

5．编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。 6．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

10

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、 队、队尾、队头

11

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、 = 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、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、链栈的类型定义如下： 12