东北大学：《数据结构》课程教学资源（学习资料）第三章 栈、队列和数组

第三章栈、队列和数组 、名词解释 1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队 7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上(下) 三角矩阵 、填空题 1.栈修改的原则是 或称 ,因此,栈又称为」 线性表。在栈顶 进行插入运算,被称为 或,在栈顶进行删除运算,被称为 或 2.栈的基本运算至少应包括 五 种 3.对于顺序栈,若栈顶下标值top=0,此时,如果作退栈运算,则产生 4.对于顺序栈而言,在栈满状态下,如果此时在作进栈运算,则会发生“ 5.一般地,栈和线性表类似有两种实现方法,即 实现和实现 6.top=0表示 此时作退栈运算,则产生“ top=sqstack maxsize-l 表示 ,此时作进栈运算,则产生“ 7.以下运算实现在顺序栈上的初始化,请在处用适当的句子予以填充 int InitStack(SqStackTp *sq) return(1): K 以下运算实现在顺序栈上的进栈,请在 处用适当的语句予以填充 Int Push(SqStackTp *sq, DataType x) if(sp->top=sqstack maxsize-1l ferror("tit"): return(O) return (1): 1 9.以下运算实现在顺序栈上的退栈,请在 用适当句子予以填充。 op(sqstackTp *sg, Data Type *x) {if(sp->top==0) error(下溢"); return(0) else(*x= 10.以下运算实现在顺序栈上判栈空,请在 处用适当句子予以填充。 Int EmptyStack(SqStackTp *sg) lif return(1) else return(O) 11.以下运算实现在顺序栈上取栈顶元素,请在 处用适当句子予以填 充。 Int GetTop(sqStackTp *sg, Data Type *x) return

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

return(1): I 2.以下运算实现在链栈上的初始化,请在 处用请适当句子予以填充 Void InitStacl (LstackTp * Is 13.以下运算实现在链栈上的进栈,请在处用请适当句子予以填充 Void Push(LStackTp *ls, DataType x) I LstackTp *p; p=malloc(sizeof(LstackTp)) p->next=ls 14.以下运算实现在链栈上的退栈,请在 处用请适当句子予以填充 Int Pop(lstackTp * ls, Data Type *x) (LstackTp *p f(ls!=NULL Is=ls->next return (1) helse return(O) 15.以下运算实现在链栈上读栈顶元素,请在 处用请适当句子予以填 充。 Int Get Top (lstackTp * ls, Data Type *x) I if(ls!=NULL)( return(1): 1 else return(O) 16.必须注意,递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下 条件: ①被定义项在定义中的应用(即作为定义项的出现)具有 ②被定义项在最小“尺度”上的定义不是 17.队列简称 。在队列中,新插入的结点只能添加到」 被删除的只能是排在 的结点 18.队列以线性表为逻辑结构,至少包括 五种基本运算 19.顺序队的出、入队操作会产生 0.以下运算实现在循环队上的初始化,请在 处用适当句子予以填充 Void InitCyc Queue(Cycqueue Tp *sg) sq->rear=0; 1 21.以下运算实现在循环队上的入队列,请在 处用请适当句子予以填 充 Int EnCycQueue(CycquereTp *sq, DataType x)

2 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)

I if((sq->rear+1)%maxsize= eror(“队满”); return(0) return(1) 22.以下运算实现在循环队上的出队列,请在 用适当句子予以填充。 Int Out Queue(CycquereTp *sg, DataType * x) lif(sg>front== ){eror(“队空”); return(0) return(1) 23.以下运算实现在循环队上判队空,请在」 处用适当句子予以填充 Int Empt yCycQueue( Cycqueue Tp sg) lif( else return(O) 24.以下运算实现在循环队上取队头,请在」 处用适当句子予以填充。 Int Get Head(Cycqueue Tp sq, DataType *x) (if(sg. rear== return(0) return (1) 25链队在一定范围内不会出现 的情况。当lq. front=1q.rear试,队 中无元素,此时 26.以下运算实现在链队上的初始化,请在 处用适当句子予以填充。 void InitQueue(QueptrTp *lp) queue p=(LqueueTp *)malloc(sizeof(LqueueTp)) lg>rear=p (lq->front)->next= 27.以下运算实现在链队上的入队列,请在 处用适当句子予以填充。 Void EnQueue( QueptrTp *lg, Data Type x) p=(LqueueTp *)malloc (sizeof(LqueueTp (lg->rear)->next= 3

3 { 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 *lg, Data Type *x) LqueueTp *s if(1 g->front==1q-rear)eroe(“队空”); return(0);} else s=(lg->front)->next =s->data (lq->front)->next f(s->next==NULL) lg->rear=lg->front return(1) 9.以下运算实现在链队上判队空,请在 处用适当句子予以填充 int Empt yQueue(QueptrTp * lg) return(I else return(O) 30.以下运算实现在链队上读队头元素,请在 处用适当句子予以填充 Int GetHead(QueptrTp lg, DataType *x) queue if(lg. rear==lg front)return(0) p->data return(1) 31.一般地,一个n维数组可视为其数据元素为 维数组的线性表。数组通常只有 和 两种基本运算。 ,通常采用 存储结构来存放数组。对二维数组可有两种存储方法:一种是以 为主序的存储方式,另一种是以_ 为主序的存储方式。C语言数组用 的是以 序为主序的存储方法; FORTRAN语言用的是以 序为主序的存 储方法 33.需要压缩存储的矩阵可分为 矩阵和 矩阵两种。 34.对称方阵中有近半的元素重复,若为每一对元素只分配一个存储空间,则可将n2个元 素压缩存储到 个元素的存储空间中 5.假设以一维数组M(1:n(n+1)/2)作为n阶对称矩阵A的存储结构,以行序为主序存储 其下三角(包括对角线)中的元素,数组M和矩阵A间对应的关系为 6.上三角矩阵中,主对角线上的第t行(1<=t<=n)有 个元素,按行优先顺序存 放上三角矩阵中的元素a时,a之前的前i-1行共有 个元素,在第i行上,ai 是该行的第 个元素,M[k]和a的对应关系是。 当ij时,a=c,c存放在M 7.下三角矩阵的存储和对称矩阵类似。M[K]和a;的对应关系是 38.基于三元组的稀疏矩阵转置的处理方法有两种,以下运算按照矩阵A的列序来进行转置

4 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 for(p=l: p<=a. tu: p++) [(b). data[gl. i=a data lp] (=*b).data[g]. j=a data[p].i ). datalv=a data] 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 Ifor(col=1 1++)num[col for(t=l: t<=a, tu; t++) num[a data[t]. j]++ for(col=2; col<=a. nu: col++) cpot [col for(p=1: p<=a. tu; p++) I col=a. datalp] g=cpot [col] (*b). data[q]. i=a data lp (*b). data[]. j=a data lp].i (*b). data[]. v=a data [p].v 40.栈称为 线性表 41.队称为 线性表 42设一个链栈的栈顶指针为1s,栈中结点的格式为 info next,栈空的条件是 如果栈不为空,则退栈操作为p=ls Is=ls->next: free(p) 43.设有二为数组intM[10][20](注:m为0..10,n为0..20),每个元素(整数) 栈两个存储单元,数组的起始地址为2000,元素M[5][10]的存储位置为 M[8][19] 的存储值为 44.在具有n个单元的循环队列中,队满时共有」 个元素 可以作为实现递归函数调用的一种数据结构。 46.数组M中每个元素的长度是3个字节,行下标i从1到8,列下标j从1到0,从 首的址EA开始连续存放在存储其中。若按行方式存放,元素M[8][5]的起始地址为

5 请在___________处用适当的句子用以填充。 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]的起始地址为