第三章 栈、队列和数组名词解释：
1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵
填空题：
栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
栈的基本运算至少应包括________、________、________、________、________五种。
对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。
对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
一般地，栈和线性表类似有两种实现方法，即________实现和________实现。
top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。
以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。
int InitStack(SqStackTp *sq)
{ ________;
return(1);}
以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x)
{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}
else{________________:
________________=x;
return(1);}
}
以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。
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=________________;
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;
________________;
return(1)；
}else return(0);
}
15,以下运算实现在链栈上读栈顶元素，请在________________处用请适当句子予以填充。
Int Get Top(LstackTp *ls,DataType *x)
{ if(ls!=NULL){ ________________;return(1);}
else return(0);
}
16.必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下条件：
①被定义项在定义中的应用（即作为定义项的出现）具有________________；
②被定义项在最小“尺度”上的定义不是________________的。
17．队列简称________________。在队列中，新插入的结点只能添加到________________，被删除的只能是排在________________的结点。
18．队列以线性表为逻辑结构，至少包括________________、________________、________________、________________ ________________、五种基本运算。
19．顺序队的出、入队操作会产生“________________”。
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,DataType *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(sq.rear== ________________return(0);
else{ *x=sq.data[________________ ];
return(1);
}
25.链队在一定范围内不会出现________________的情况。当lq.front==lq.rear试，队中无元素，此时________________。
26．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。
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,以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。
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,以下运算实现在链队上读队头元素，请在________________处用适当句子予以填充。
Int GetHead(QueptrTp lq,DataType *x)
{ LqueueTp *p;
if(lq.rear==lq.front) return(0);
else{________________;
________________ =p->data;
return(1);
}
}
31．一般地，一个n维数组可视为其数据元素为___________维数组的线性表。数组通常只有___________和___________两种基本运算。
32，通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。C语言数组用的是以___________序为主序的存储方法；FORTRAN语言用的是以___________序为主序的存储方法
33．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。
34．对称方阵中有近半的元素重复,若为每一对元素只分配一个存储空间,则可将n2个元素压缩存储到___________个元素的存储空间中。
35．假设以一维数组M（1：n(n+1)/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为___________。
36．上三角矩阵中，主对角线上的第t行(1<=t<=n)有___________个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的前i-1行共有___________个元素，在第i行上,aij是该行的第___________个元素，M[k]和aij的对应关系是。
当i>j时，aij=c,c存放在M[___________]中。
37．下三角矩阵的存储和对称矩阵类似。M[K]和aij的对应关系是___________。
38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;
if(a.tu)
{ q=1;
for(col=1; ___________;col++)
for(p=1;p<=a.tu;p++)
if(___________==col)
{(*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
___________;
}
}
39．基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元组a.data的次序进行转置，请在___________处用适当的句子用以填充。
Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu=a.tu;
if(a.tu)
{for(col=1;___________;col++) num[col]=0;
for(t=1;t<=a,tu;t++) num[a.data[t].j]++;
cpot[1]=1;
for(col=2;col<=a.nu;col++) cpot[col]=___________;
for(p=1;p<=a.tu;p++)
{ col=a.data[p].j;
q=cpot[col];
(*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
__________________________;
}
}
}
40．栈称为___________线性表。 ;
41．队称为___________线性表。
42设一个链栈的栈顶指针为ls，栈中结点的格式为 info next,栈空的条件是___________；如果栈不为空，则退栈操作为p=ls; ___________;ls=ls->next;free(p)。
43．设有二为数组int M[10][20](注：m为0...10,n为0...20),每个元素（整数）栈两个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为___________，M[8][19]的存储值为___________。
44．在具有n个单元的循环队列中，队满时共有___________个元素。
45．___________可以作为实现递归函数调用的一种数据结构。
46．数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到0，从首的址EA开始连续存放在存储其中。若按行方式存放，元素M[8][5]的起始地址为___________；若按列优先方式存放，元素M[8][5]的地址为___________。
47．对带有头结点的列队列lq,判定队列中只有一个数据元素的条件是___________。
48．二维数组M的成员是6个字符（每个字符栈一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要___________个字节；M的第8列和第5行共占___________个字节；若M按行方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的___________元素的起始地址一致。
三、单项选择题
1．在以下栈的基本运算中，不是加工型运算的是 （ ）
①lnitStack(S) ②Push(S,X) ③Pop(S) ④empty(S)
2.以下说法正确的是 ( )
①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
3．在以下队列的基本运算中，不是加工型运算的是 （ ）
①InitQueue(Q) ②EnQueue(Q,X) ③OutQueu(Q,X) ④GetHead(Q,x)
4.顺序队列的人队操作应为 ( )
①sq.rear=sq.rear+1 sq.data[sq.rear]=x
②sq.data[sq.rear]=x sq.rear=sq.rear+1
③sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x
④sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize
5.循环队列的人队操作应为 ( )
①sq.rear=sq.rear+1 sq.data[sq.rear]=x
②sq.data[sq.rear]=x sq.rear=sq.rear+1
③sq.rear=(sq.rear+1)% maxsize sq.data[sq.rear]=x
④sq.data[sq.rear]=x sq.rear=(sq.rear+1)% maxsize
6,顺序队列的出队操作为 ( )
①sq.front=(sq.front+1)% maxsize
②sq.front=sq.front+1
③sq.rear=(sq.rear+1)% maxsize
④sq.rear=sq.rear+1
7,循环队列的出队操作为 ( )
①sq.front=(sq.ftont+1)% maxsize
②sq.front=sq.front+1
③sq.rear=(sq.rear+)% maxsize
④sq.rear=sq.rear+1
8.循环队列的队满条件为 ( )
①(sq.rear+1) % mazsize ==(sq.front+1) % maxsize;
②(sq.rear+1 % maxsize ==sq.front+1
③sq.(rear+1) % maxsize ==sq.front
④sq.rear ==sq.front
9.循环队列的队空条件为 ( )
①(sq.rear+1) % maxsize ==(sq.front+1) % maxsize
②(sq.rear+) % maxsize ==sq.front+1
③(sp.rear+1) % maxsize ==sq.front
④sq.rear == sq.front
10.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是 ( )
①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
③数组的读、写运算只能读取或修改一个数据元素的一部分
④数组的读、写运算只能读取或修改一个数据元素整体
11．对于以行序为主序的存储结构来说，在数组A[c1···d1，c2···d2]中，c1和d1分别为数组A的第一个下标的上、下界，c2…d2分别为第二各下标的上、下界，每个数据元素占K
个存储单元，二维数组中任一元素a[i,j]的存储位置可由( )式确定.
①Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k
②Loc[i,j]=loc[c1,c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k
③Loc{i,j}=A[c1,c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k
④Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k
12对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.
①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k
②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k
③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k
④Loc[i,j]=[(n+1)*i+j]*k
13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种（ ）的存储结构。
① 随机存取 ② 顺序存储
14．如果以链表作为栈的存储结构，则退栈操作是 ( )
①必须判别栈是否满 ②必须判别栈是否空
③判别栈元素的类型 ④对栈不做任何操作
15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( )
①按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu)
②按照A的三元组a.data的次序进行转置，算法的时间复杂度为O(nu*tu)
③按照矩阵A的列序来进行转置的方法称快速转置
④按照矩阵A的列序进行转置,对于tu<<mu x nu才有意义。
16．稀疏矩阵的压缩存储方法是只存储 ( )
①非零元素 ② 三元祖（i,j,aij） ③ aij ④ i,j
17．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定。
①非零元素 ②三元组(i,j,aij) ③ aij ④ i,j
18如果以链表作为栈的存储结构,则退栈操作时 ( )
①必须判别栈是否满 ②判别栈元素的类型
③必须判别栈是否空 ④ 队栈不做任何判别
19．设C语言数组Data[m+1]作为循环队列SQ的存储空间,front为队头指针，rear为队为指针，则执行出队操作的语句为 （ ）
①front=front+1 ② front=（front+1）%m
③rear=(rear+1)%m ④ front=(front+1)%(m+1)
20.三角矩阵可压缩存储到数组（ ）中。
①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2]
③M[n(n+1)/2+1] ④M[n(n+1)/2]
21.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是 （ ）
①2 ② 3 ③ 5 ④6
22．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是 （ ）
0 1 2 3 maxsize-1
a1
a2
a3
sq
↑top
①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1
23.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ）
①Top->next=s ② s->next=Top->next;Top->next=s
③s->next=Top;Top=s ④ s->next=Top;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．链栈与顺序栈相比，有一个比较明显的优点即 （ ）
①插入操作更方便 ② 通常不会出现栈满的情况
③不会出现栈空的情况 ④ 删除操作更方便
28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 （ ）
①正确 ②错误
29。二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素( )的起始地址相同。
①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4]
30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ）
① e d c b a ②d e c b a ③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．以下说法正确的是
①顺序队和循环队的队满和队空判断条件是一样的
②栈可以作为实现过程调用的一种数据结构
③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用
④在循环队列中，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,求：
用i、j表示k的下标变换公式；
用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);
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(&ls<p->data);
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．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。
7．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（..,[..,{..,}..,[..,]..,]..,(,.,[..,]..,)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。
8．已知Ackerman函数定义如下：
akm(m,n)=
试写出递归算法。
9．设函数f(m,n)按下式定义（ m,n为）0的整数）
f(m,n)=
试写出计算函数的递归过程。
10．设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1,w2,..,，wn.问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S.如果存在一种符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假），试用递归和非递归两种方法设计此背包问题的算法。
11．借助栈(可用栈的基本运算)来实现单链表的逆置运算。
1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵
填空题：
栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。
栈的基本运算至少应包括________、________、________、________、________五种。
对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。
对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。
一般地，栈和线性表类似有两种实现方法，即________实现和________实现。
top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。
以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。
int InitStack(SqStackTp *sq)
{ ________;
return(1);}
以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。
Int Push(SqStackTp *sq,DataType x)
{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}
else{________________:
________________=x;
return(1);}
}
以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。
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=________________;
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;
________________;
return(1)；
}else return(0);
}
15,以下运算实现在链栈上读栈顶元素，请在________________处用请适当句子予以填充。
Int Get Top(LstackTp *ls,DataType *x)
{ if(ls!=NULL){ ________________;return(1);}
else return(0);
}
16.必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下条件：
①被定义项在定义中的应用（即作为定义项的出现）具有________________；
②被定义项在最小“尺度”上的定义不是________________的。
17．队列简称________________。在队列中，新插入的结点只能添加到________________，被删除的只能是排在________________的结点。
18．队列以线性表为逻辑结构，至少包括________________、________________、________________、________________ ________________、五种基本运算。
19．顺序队的出、入队操作会产生“________________”。
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,DataType *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(sq.rear== ________________return(0);
else{ *x=sq.data[________________ ];
return(1);
}
25.链队在一定范围内不会出现________________的情况。当lq.front==lq.rear试，队中无元素，此时________________。
26．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。
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,以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。
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,以下运算实现在链队上读队头元素，请在________________处用适当句子予以填充。
Int GetHead(QueptrTp lq,DataType *x)
{ LqueueTp *p;
if(lq.rear==lq.front) return(0);
else{________________;
________________ =p->data;
return(1);
}
}
31．一般地，一个n维数组可视为其数据元素为___________维数组的线性表。数组通常只有___________和___________两种基本运算。
32，通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。C语言数组用的是以___________序为主序的存储方法；FORTRAN语言用的是以___________序为主序的存储方法
33．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。
34．对称方阵中有近半的元素重复,若为每一对元素只分配一个存储空间,则可将n2个元素压缩存储到___________个元素的存储空间中。
35．假设以一维数组M（1：n(n+1)/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为___________。
36．上三角矩阵中，主对角线上的第t行(1<=t<=n)有___________个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的前i-1行共有___________个元素，在第i行上,aij是该行的第___________个元素，M[k]和aij的对应关系是。
当i>j时，aij=c,c存放在M[___________]中。
37．下三角矩阵的存储和对称矩阵类似。M[K]和aij的对应关系是___________。
38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___________处用适当的句子用以填充。
Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;
if(a.tu)
{ q=1;
for(col=1; ___________;col++)
for(p=1;p<=a.tu;p++)
if(___________==col)
{(*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
___________;
}
}
39．基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元组a.data的次序进行转置，请在___________处用适当的句子用以填充。
Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b)
{ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu=a.tu;
if(a.tu)
{for(col=1;___________;col++) num[col]=0;
for(t=1;t<=a,tu;t++) num[a.data[t].j]++;
cpot[1]=1;
for(col=2;col<=a.nu;col++) cpot[col]=___________;
for(p=1;p<=a.tu;p++)
{ col=a.data[p].j;
q=cpot[col];
(*b).data[q].i=a.data[p].j;
(*b).data[q].j=a.data[p].i;
(*b).data[q].v=a.data[p].v;
__________________________;
}
}
}
40．栈称为___________线性表。 ;
41．队称为___________线性表。
42设一个链栈的栈顶指针为ls，栈中结点的格式为 info next,栈空的条件是___________；如果栈不为空，则退栈操作为p=ls; ___________;ls=ls->next;free(p)。
43．设有二为数组int M[10][20](注：m为0...10,n为0...20),每个元素（整数）栈两个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为___________，M[8][19]的存储值为___________。
44．在具有n个单元的循环队列中，队满时共有___________个元素。
45．___________可以作为实现递归函数调用的一种数据结构。
46．数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到0，从首的址EA开始连续存放在存储其中。若按行方式存放，元素M[8][5]的起始地址为___________；若按列优先方式存放，元素M[8][5]的地址为___________。
47．对带有头结点的列队列lq,判定队列中只有一个数据元素的条件是___________。
48．二维数组M的成员是6个字符（每个字符栈一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要___________个字节；M的第8列和第5行共占___________个字节；若M按行方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的___________元素的起始地址一致。
三、单项选择题
1．在以下栈的基本运算中，不是加工型运算的是 （ ）
①lnitStack(S) ②Push(S,X) ③Pop(S) ④empty(S)
2.以下说法正确的是 ( )
①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。
3．在以下队列的基本运算中，不是加工型运算的是 （ ）
①InitQueue(Q) ②EnQueue(Q,X) ③OutQueu(Q,X) ④GetHead(Q,x)
4.顺序队列的人队操作应为 ( )
①sq.rear=sq.rear+1 sq.data[sq.rear]=x
②sq.data[sq.rear]=x sq.rear=sq.rear+1
③sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x
④sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize
5.循环队列的人队操作应为 ( )
①sq.rear=sq.rear+1 sq.data[sq.rear]=x
②sq.data[sq.rear]=x sq.rear=sq.rear+1
③sq.rear=(sq.rear+1)% maxsize sq.data[sq.rear]=x
④sq.data[sq.rear]=x sq.rear=(sq.rear+1)% maxsize
6,顺序队列的出队操作为 ( )
①sq.front=(sq.front+1)% maxsize
②sq.front=sq.front+1
③sq.rear=(sq.rear+1)% maxsize
④sq.rear=sq.rear+1
7,循环队列的出队操作为 ( )
①sq.front=(sq.ftont+1)% maxsize
②sq.front=sq.front+1
③sq.rear=(sq.rear+)% maxsize
④sq.rear=sq.rear+1
8.循环队列的队满条件为 ( )
①(sq.rear+1) % mazsize ==(sq.front+1) % maxsize;
②(sq.rear+1 % maxsize ==sq.front+1
③sq.(rear+1) % maxsize ==sq.front
④sq.rear ==sq.front
9.循环队列的队空条件为 ( )
①(sq.rear+1) % maxsize ==(sq.front+1) % maxsize
②(sq.rear+) % maxsize ==sq.front+1
③(sp.rear+1) % maxsize ==sq.front
④sq.rear == sq.front
10.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是 ( )
①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
③数组的读、写运算只能读取或修改一个数据元素的一部分
④数组的读、写运算只能读取或修改一个数据元素整体
11．对于以行序为主序的存储结构来说，在数组A[c1···d1，c2···d2]中，c1和d1分别为数组A的第一个下标的上、下界，c2…d2分别为第二各下标的上、下界，每个数据元素占K
个存储单元，二维数组中任一元素a[i,j]的存储位置可由( )式确定.
①Loc[i,j]=[( d2-c2+1)(i- c1)+(j- c2)]*k
②Loc[i,j]=loc[c1,c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k
③Loc{i,j}=A[c1,c2]+[( d2- c2+1)(i- c1)+(j- c2)]*k
④Loc[i,j]=loc[0,0]+[( d2- c2+1)(i- c1)=(j- c2)]*k
12对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.
①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k
②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k
③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k
④Loc[i,j]=[(n+1)*i+j]*k
13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种（ ）的存储结构。
① 随机存取 ② 顺序存储
14．如果以链表作为栈的存储结构，则退栈操作是 ( )
①必须判别栈是否满 ②必须判别栈是否空
③判别栈元素的类型 ④对栈不做任何操作
15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( )
①按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu)
②按照A的三元组a.data的次序进行转置，算法的时间复杂度为O(nu*tu)
③按照矩阵A的列序来进行转置的方法称快速转置
④按照矩阵A的列序进行转置,对于tu<<mu x nu才有意义。
16．稀疏矩阵的压缩存储方法是只存储 ( )
①非零元素 ② 三元祖（i,j,aij） ③ aij ④ i,j
17．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定。
①非零元素 ②三元组(i,j,aij) ③ aij ④ i,j
18如果以链表作为栈的存储结构,则退栈操作时 ( )
①必须判别栈是否满 ②判别栈元素的类型
③必须判别栈是否空 ④ 队栈不做任何判别
19．设C语言数组Data[m+1]作为循环队列SQ的存储空间,front为队头指针，rear为队为指针，则执行出队操作的语句为 （ ）
①front=front+1 ② front=（front+1）%m
③rear=(rear+1)%m ④ front=(front+1)%(m+1)
20.三角矩阵可压缩存储到数组（ ）中。
①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2]
③M[n(n+1)/2+1] ④M[n(n+1)/2]
21.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是 （ ）
①2 ② 3 ③ 5 ④6
22．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是 （ ）
0 1 2 3 maxsize-1
a1
a2
a3
sq
↑top
①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1
23.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ）
①Top->next=s ② s->next=Top->next;Top->next=s
③s->next=Top;Top=s ④ s->next=Top;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．链栈与顺序栈相比，有一个比较明显的优点即 （ ）
①插入操作更方便 ② 通常不会出现栈满的情况
③不会出现栈空的情况 ④ 删除操作更方便
28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 （ ）
①正确 ②错误
29。二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列存储时元素( )的起始地址相同。
①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4]
30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ）
① e d c b a ②d e c b a ③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．以下说法正确的是
①顺序队和循环队的队满和队空判断条件是一样的
②栈可以作为实现过程调用的一种数据结构
③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用
④在循环队列中，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,求：
用i、j表示k的下标变换公式；
用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);
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(&ls<p->data);
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．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。
7．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（..,[..,{..,}..,[..,]..,]..,(,.,[..,]..,)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。
8．已知Ackerman函数定义如下：
akm(m,n)=
试写出递归算法。
9．设函数f(m,n)按下式定义（ m,n为）0的整数）
f(m,n)=
试写出计算函数的递归过程。
10．设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w1,w2,..,，wn.问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S.如果存在一种符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假），试用递归和非递归两种方法设计此背包问题的算法。
11．借助栈(可用栈的基本运算)来实现单链表的逆置运算。
