您好,欢迎访问三七文档
当前位置:首页 > 财经/贸易 > 资产评估/会计 > 数据结构练习题-第三章-栈、队列和数组-习题及答案
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.以下运算实现在顺序栈上的初始化,请在________处用适当的句子予以填充。intInitStack(SqStackTp*sq){________;return(1);}8.以下运算实现在顺序栈上的进栈,请在________处用适当的语句予以填充。IntPush(SqStackTp*sq,DataTypex){if(sp-top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈,请在________________用适当句子予以填充。IntPop(SqStackTp*sq,DataType*x){if(sp-top==0){error(“下溢”);return(0);}else{*x=________________;________________;return(1);}}10.以下运算实现在顺序栈上判栈空,请在________________处用适当句子予以填充。IntEmptyStack(SqStackTp*sq){if(________________)return(1);elsereturn(0);}11.以下运算实现在顺序栈上取栈顶元素,请在________________处用适当句子予以填充。IntGetTop(SqStackTp*sq,DataType*x){if(________________)return(0);2else{*x=________________;return(1);}}12.以下运算实现在链栈上的初始化,请在________________处用请适当句子予以填充。VoidInitStacl(LstackTp*ls){________________;}13.`以下运算实现在链栈上的进栈,请在处用请适当句子予以填充。VoidPush(LStackTp*ls,DataTypex){LstackTp*p;p=malloc(sizeof(LstackTp));________________;p-next=ls;________________;}14.以下运算实现在链栈上的退栈,请在________________处用请适当句子予以填充。IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x=________________;ls=ls-next;________________;return(1);}elsereturn(0);}15.以下运算实现在链栈上读栈顶元素,请在________________处用请适当句子予以填充。IntGetTop(LstackTp*ls,DataType*x){if(ls!=NULL){________________;return(1);}elsereturn(0);}16.必须注意,递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下条件:①被定义项在定义中的应用(即作为定义项的出现)具有________________;②被定义项在最小“尺度”上的定义不是________________的。17.队列简称________________。在队列中,新插入的结点只能添加到________________,被删除的只能是排在________________的结点。18.队列以线性表为逻辑结构,至少包括________________、________________、________________、________________________________、五种基本运算。19.顺序队的出、入队操作会产生“________________”。20.以下运算实现在循环队上的初始化,请在________________处用适当句子予以填充。VoidInitCycQueue(CycqueueTp*sq){________________;sq-rear=0;}21.以下运算实现在循环队上的入队列,请在________________处用请适当句子予以填充。IntEnCycQueue(CycquereTp*sq,DataTypex)3{if((sq-rear+1)%maxsize==________________){error(“队满”);return(0);else{________________;________________________________;return(1);}22.以下运算实现在循环队上的出队列,请在________________处用适当句子予以填充。IntOutCycQueue(CycquereTp*sq,DataType*x){if(sq-front==________________){error(“队空”);return(0);}else{________________;________________;return(1);}}23.以下运算实现在循环队上判队空,请在________________处用适当句子予以填充。IntEmptyCycQueue(CycqueueTpsq){if(________________)return(1);elsereturn(0);}24.以下运算实现在循环队上取队头,请在________________处用适当句子予以填充。IntGetHead(CycqueueTpsq,DataType*x){if(sq.rear==________________return(0);else{*x=sq.data[________________];return(1);}25.链队在一定范围内不会出现________________的情况。当lq.front==lq.rear试,队中无元素,此时________________。26.以下运算实现在链队上的初始化,请在________________处用适当句子予以填充。voidInitQueue(QueptrTp*lp){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));________________;lq-rear=p;(lq-front)-next=________________;}27.以下运算实现在链队上的入队列,请在________________处用适当句子予以填充。VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));________________=x;p-next=NULL;(lq-rear)-next=________________;________________;}428.以下运算实现在链队上的出队列,请在________________处用适当句子予以填充。intOutQueue(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.以下运算实现在链队上判队空,请在________________处用适当句子予以填充intEmptyQueue(QueptrTp*lq){if(________________)return(1);elsereturn(0);}30.以下运算实现在链队上读队头元素,请在________________处用适当句子予以填充。IntGetHead(QueptrTplq,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的对应关系是。当ij时,aij=c,c存放在M[___________]中。37.下三角矩阵的存储和对称矩阵类似。M[K]和aij的对应关系是___________。38.基于三元组的稀疏矩阵转置的处理方法有两种,以下运算按照矩阵A的列序来进行转置,5请在___________处用适当的句子用以填充。Trans_Sparmat(SpMatrixTpa,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.基于三元组的稀疏矩阵
本文标题:数据结构练习题-第三章-栈、队列和数组-习题及答案
链接地址:https://www.777doc.com/doc-4525101 .html