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

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

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 行(1j 时，aij=c,c 存放在 M[___________]中。 37．下三角矩阵的存储和对称矩阵类似。M[K]和 aij 的对应关系是___________。 38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A 的列序来进行转置

若按列优先方式存放,元素M[8][5]的地址为 47.对带有头结点的列队列1q,判定队列中只有一个数据元素的条件是 48.二维数组M的成员是6个字符(每个字符栈一个存储单元)组成的串,行下标的范围从0到8,列下标j的范围从1到10,则存放M至少需要个字节;M的第列和第5行共占个字节;若M按行方式存储,元素M[8][5]的起始地址与当M 按列优先方式存储时的_ 元素的起始地址一致、单项选择题 1.在以下栈的基本运算中,不是加工型运算的是() ① InitStack(S)②Push(S,X)③Pop(S)④ empty(S) 2.以下说法正确的是() ①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算,则会发生“上溢 ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算,则会发生“下溢 3.在以下队列的基本运算中,不是加工型运算的是 ① InitQueue(Q)② EnQueue(Q,X)③ DOut Queu(Q,X)④ GetHead(Q,x) 4顺序队列的人队操作应为() ①sq.rear=sq.rear+1 sq data [sg. rear]=x 2sg data[sg. rear]=x sq rear=sg. rear+l 3sg. rear=(sg. rear+1)% maxsize ④4sq alsgrear」=x sq rear=(sg. rear+1)% maxsize 5.循环队列的人队操作应为() ①sq.rear=sq.rear+1 sq. data [sq. rear]=x ②sq.data[sq.rear]=x sq- rear=sq rear+1 3sg. rear=(sq. rear+1)% maxsize ④sq.data[sq.rear]=x sq. rear=(sq. rear+1)% maxsize 6.顺序队列的出队操作为() (sq. front=(sq front+1)% maxsize (2)sg front=sg. front+1 3sq. rear=(sq. rear+1)% maxsize ④sq.rear=sq.rear+1 7.循环队列的出队操作为() (sg. front=(sg. font+1)%maxsize 3sg. rear=(sq rear+)% maxsize ④sq.rear=sq.rear+1 8.循环队列的队满条件为() 1(sq. rear+1)% mazsize ==(sg front+1)% maxsize 2(sq rear+1 maxsize ==sq front+1 Osg. (rear+1)% maxsize =sq front ④sq.rear=sq. front 9.循环队列的队空条件为() ((sq. rear+1)% maxsize ==(sg. front+1)% maxsize 6

6 ___________；若按列优先方式存放，元素 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

(2(sg. rear+)% maxsize ==sq front+1 3(sp. rear+1)% maxsize ==sq front ④sq.rear 10.数组的数据元素类型 DataType可根据实际需要而定义。以下说法完全正确的是() ①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 ②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 ③数组的读、写运算只能读取或修改一个数据元素的一部分 ④数组的读、写运算只能读取或修改一个数据元素整体 11.对于以行序为主序的存储结构来说,在数组A[c1…d,c2…dl]中,c1和d1分别为数组A的第一个下标的上、下界,c2…d2分别为第二各下标的上、下界,每个数据元素占K 个存储单元,二维数组中任一元素a[i,j的存储位置可由()式确定 ①Loc[i,j=[(d2-c2+1)(i-c1)+(j-c2)]*k Loc[i, j]=loc[c, C2]+[( d2-C2+1)(i-c1+(j-c2)]=k lOci, j=ALCl, 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 @[i, j]=loc[0, 0]+[(m+n)*i+j]*k ③Loc[i,j=1oc[0,0]+[(n+1)*i+订*k OLoc[i, j]=[(n+1)=i+j]=*k 13.线性表的顺序存储结构是一种()的存储结构,线性表的链式存储结构是一种()的存储结构 ①随机存取 ②顺序存储 14.如果以链表作为栈的存储结构,则退栈操作是 ①必须判别栈是否满②必须判别栈是否空 ③判别栈元素的类型④对栈不做任何操作 15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ①按照矩阵A的列序来进行转置,算法的时间复杂度为0(nu+tu) ②按照A的三元组a.data的次序进行转置,算法的时间复杂度为0(mu*tu) ③按照矩阵A的列序来进行转置的方法称快速转置 ④按照矩阵A的列序进行转置,对于tu<<mxmu才有意义。 16.稀疏矩阵的压缩存储方法是只存储 ①非零元素 ②三元祖(i,j,a;) 17.基于三元组的稀疏矩阵,对每个非零元素a,可以用一个 )唯一确定。 ①非零元素 ②三元组(i,j,an)③ 18如果以链表作为栈的存储结构,则退栈操作时 ①必须判别栈是否满 ②判别栈元素的类型 ③必须判别栈是否空 ④队栈不做任何判别 19.设C语言数组Data[m+1]作为循环队列SQ的存储空间, front为队头指针,rear为队为指针,则执行出队操作的语句为 ① front= front+1 ② front=( front+1)%m ③rear=(rear+1)%m 4 front=(front+1)%(m+1) 20.三角矩阵可压缩存储到数组()中

7 ②(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[:n(n+1)/2+1] ②M[: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,则栈的容量至少应该是 ② ④6 22.设有一顺序栈已含3个元素,如下图所示,元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是 maxsize-l ↑te ④a4,a3,a2, 23.向一个栈顶指针为Top的链中插入一个s所指结点时,其操作步骤为 op->next=s @2 s->next=Top->next: Top->next=s ③s->next=Top;Top=s 4s->next=Top: Top=Top->next 24.从栈顶指针为Top的链栈中删除一个结点,并将被删节点的值保存到x中,其操作步骤为 (x=Top->data; Top=Top->next @Top=Top->next: x=Top->data 3x=Top: Top=Top->next ④x=Top->data 5.在一个链队中,若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.链栈与顺序栈相比,有一个比较明显的优点即 ①插入操作更方便 ②通常不会出现栈满的情况 ③不会出现栈空的情况 ④删除操作更方便 8.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点 ①正确 ②错误 9。二为数组M[i,j的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5。M按行存储时元素M[3,5]的起始地址与M按列存储时元素()的起始地址相同 ①M[2,4] ②M[3,4] ③M[3,5] ④M[4,4] 30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 ① d c b dec b ③ d cea b ④abcd 31.一个队列的人列序是1,2,3,4,则队列的输出系列是 ①4,3,2,1 ③1,4 ④3,2,4,1 32.设计一个判别表达式中左、右括号是否配对出线的算法,采用()数据结构最佳。 ①线性标的顺序存储结构 ②栈 ③队列 ④线性表的链式存储结构 33.若已知一个栈的输入序列为1,2,3,.,n,其输出序列为P1、P2、.P。若p=n,则 P1为 ① ③n-i+1 ④不确定

8 ①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 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 ④ 不确定 a1 a2 a3

10 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．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。 ······

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

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