数据结构期末复习 第三章 数组和广义表一、选择题1若让元素123依次进栈则出栈顺序不可能为C。A321 B213C312 D1322一个队列的入队序列是1234。则队列的输出序列是B。A4321 B1234C1432 D32413. 一个栈的进栈序列是1020304050则栈的不可能输出序列是B进栈出栈可以交替进行。A10,20,30,40,50 B40,30,50,10,20C40,50,30,20,10 D50,40,30,20,104. 元素46810按顺序依次进栈按该栈的可能输出序列依次入队列该队列的可能输出序列是D进栈出栈可以交替进行。A10846 B10648C84610 D108645向顺序栈中压入新元素时应当A。A先移动栈顶指针再存入元素B先存入元素再移动栈顶指针C先后次序无关紧要D同时进行6在一个栈顶指针为top的链栈中将一个p指针所指的结点入栈应执行C。Atop-nextp;Bp-nexttop-next; top-nextp;Cp-nexttop; topp;Dp-nexttop-next; toptop-next;7在一个栈顶指针为top的链栈中删除一个结点时用 x保存被删结点的值则执行D。Axtop;toptop-next;Bxtop-data;Ctoptop-next; xtop-data;Dxtop-data; toptop-next;8一般情况下将递归算法转换成等价的非递归算法应该设置A。A栈 B队列C堆栈或队列 D数组9表达式a*(bc)-d的后缀表达式是B。Aabcd*- Babc*d- Cabc*d- D-*abcd10判断一个顺序队列sq最多元素为m为空的条件是C。Asq-rear-sq-front m Bsq-rear-sq-front-1 mCsq-frontsq-rear Dsq-frontsq-rear111判断一个循环队列Q最多元素为m为满的条件是C。AQ-frontQ-rear BQ-front!Q-rearCQ-front(Q-rear1)% m DQ-front! (Q-rear1)% m12判断栈s满元素个数最多n个的条件是C。As-top0 Bs-top!0Cs-topn-1 Ds-top!n-113一个队列的入队顺序是a,b,c,d则离队的顺序是B。Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a14如果以链表作为栈的存储结构则退栈操作时C。A必须判断栈是否满 B判断栈元素类型C必须判断栈是否空 D对栈不作任何判断解析以链表作为栈的存储结构链栈时退栈出栈操作需要删除栈顶结点。如果栈为空即栈顶指针为NULL则无法执行退栈操作否则会发生错误。因此退栈前必须判断栈是否空。15在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区主机将要输出的数据依次写入缓冲区中而打印机则从缓冲区中取出数据打印该缓冲区应该是一个B结构。A堆栈 B队列 C数组 D先性表16一个递归算法必须包括B。A递归部分 B终止条件和递归部分C迭代部分 D终止条件和迭代部分17从一个栈顶指针为top的链栈中删除一个结点时用变量x保存被删结点的值则执行A。Axtop-data; toptop-next; Bxtop-data;Ctoptop-next; xtop-data; Dtoptop-next; xdata;18在一个链队中假设f和r分别为队头和队尾指针则删除一个结点的运算为C。Arf-next; Brr-next; Cff-next; Dfr-next;19在一个链队中假设f和r分别为队头和队尾指针则插入s所指结点的运算为B。Af-nexts; fs; Br-nexts;rs;Cs-nextr;rs; Ds-nextf;fs;20在一个不带头结点的链队中假设f和r分别为队头和队尾指针则从该对列中删除一个结点并把结点的值保存在变量x中的运算为C。Axr-datarr-next; Brr-next; xr-dataCxf-dataff-next; Dff-next; xf-data21栈和队列的共同特点是C。A都是先进后出 B元素都可以随机进出C只容许在端点处插入和删除元素 D都是先进先出22栈的插入和删除操作在A进行。A栈顶 B栈底C任意位置 D指定位置23在一个顺序队列中队首指针指向队首元素的C位置。A前一个 B后一个C当前 D后面24当利用大小为n的数组顺序存储一个队列时该队列的最大长度为( B )。A. n-2 B. n-1 C. n D. n125从一个顺序存储的循环队列中删除一个元素时首先需要( C )。A. 队头指针加一 B. 队头指针减一C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素二、判断题1. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。√2. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。×3. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。√解析顺序存取指存取元素时只能按照某种特定的顺序进行不能像数组一样随机访问。如果表述为“栈和队列都是顺序存储的线性表,但它们对存取位置的限制不同。“就是错误的4. 若让元素1,2,3依次进栈则出栈次序1,3,2是不可能出现的情况。×5. 在用单链表表示的链式队列Q中队头指针为Q-front队尾指针为Q-rear则队空条件为Q-front Q-rear。√6. 递归定义的数据结构通常用递归算法来实现对它的操作。√7. 递归的算法简单、易懂、容易编写而且执行效率也高。×8. 递归调用算法与相同功能的非递归算法相比主要问题在于重复计算太多而且调用本身需要分配额外的空间和传递数据和控制所以时间与空间开销通常都比较大。√9. 用非递归方法实现递归算法时一定要使用递归工作栈。×10. 栈是限定在表的一端进行插入和删除操作的线性表又称为先进后出表。√11. 队列的特性是先进后出。×12. 往栈中插入元素的操作方式是先写入元素后移动栈顶指针。×13.循环队列队头指针在队尾指针前一个位置队列是“满”状态。√解析表述为“队头指针在队尾指针下一个位置”更没有歧义14. 在队列的顺序存储结构中当插入一个新的队列元素时尾指针后移当删除一个元素队列时头指针后移。√15. 向一个栈顶指针为h的链栈(结点的指针域为next)中插入一个s所指结点时先执行s-nexth再执行hs操作。√16. 一个递归算法不必包括递归终止条件。×17. 在一个链式队列中若队头指针与队尾指针的值相同则表示该队列至多有1个结点。×18. 在用循环单链表表示的链式队列中可以不设队头指针仅在链尾设置队尾指针。√解析在循环单链表中如果只设置队尾指针rear不设队头指针front队尾指针rear指向最后一个结点第一个结点队头是rear-next因为是循环链表因此通过队尾指针可以访问到队头结点不需要单独设队头指针。三、程序选择题1在下面空格处填写一条语句以使下面的链式队列全部元素出队的算法完整。int write(LinkQueue *q){QueueNode *p;if (q-frontq-rear) /*队空*/{printf(“队空无元素可取”);exit(0);}while (q-front-next ! NULL){pq-front-next;q-front-nextp-next;/*出队*/printf(“%4d”,p-data);free(p); /*释放已出队结点*/}_______C________ /*队空时头尾指针指向头结点*/}A. q-frontq-rear;B. qq-next;C. q-rearq-front;D. pp-next;解析多次执行q-front-nextp-next;后q-front并不会被改变改变的是next的值实际上front始终指向头结点。2. 在下面空格处填写适当的语句以使下面的循环队列的入队和出队算法完整。define MAXSIZE 100;typedef char Elemtype;typedef struct{Elemtype queue [MAXSIZE];int front,rear;}sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x){if ((Q-rear1)%MAXSIZEQ-front){printf(“队列已满!\n”);return 1;}else{Q-rear(Q-rear1)%MAXSIZE;(1)return 0;}} /*入队算法*/Elemtype del_cqueue(sequeuetype *Q){if ( (2) ){printf(“队列为空!\n”);return 1;}else{Q-front(Q-front1)%MAXSIZE;return(Q-queue[Q-front]);}} /*出队算法*/A. (1) (Q-rear1)%MAXSIZEQ-front (2) Q-front(Q-front1)%MAXSIZE;B. (1) (Q-front1)%MAXSIZEQ-rear (2) Q-rear(Q-rear1)%MAXSIZE;C. (1) Q-frontQ-rear (2) Q-queue[Q-rear]x;D. (1) Q-queue[Q-rear]x; (2) Q-frontQ-rear【答案】D3. 写出下列程序执行后的结果SeqQueue Q;InitQueue(Q);int a[4]{5,8,12,15};for(int i0;i4;i) InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)10);while(!QueueEmpty(Q)) printf(“%d ”,OutQueue(Q));执行后的输出结果为_______B___________。A. 5 8 12 15 30B. 12 15 5 30 18C. 8 12 15 30 18D. 12 15 5 18 304. 写出下列程序执行后的结果SeqStack S;InitStack(S);Push(S,3);Push(S,4);Push(S,5);int xPop(S)2*Pop(S);Push(S,x);int i,a[4]{5,8,12,15};for (i0;i4;i) Push(S,a[i]);while(!StackEmpty(S)) Printf(“%d “,Pop(S));执行后的输出结果为________A__________。A. 15 12 8 5 13 3B. 3 5 8 12 13 15C. 15 13 12 8 5 3D. 15 12 13 3 8 55.在下面空格处填写一条语句以使下面的进栈算法完整。void Push(struct SeqStack*s,ElemType x){If (s-topMaxSize-1){printf(“栈满溢出错误\n”);exit(1);}____C____s-data[s-top]x;}A. s-tops-data;B. s-data;C. s-top;D. s-datas-top;6. 在下面空格处填写一条语句以使下面的出栈算法完整。ElemTypePop(struct SeqStack*s,ElemType x){If (StackEmpty(s)){printf(“栈下溢出错误\n”);exit(1);}xs-data[s-top];____A_____return x;}A. s-top--;B. s-data--;C. s-tops-data;D. s-datas-top;
数据结构期末复习:第三章 栈和队列（选择题25道+判断题18道+程序题6道）进栈/出栈/循环队列/链队/递归
数据结构期末复习 第三章 数组和广义表一、选择题1若让元素123依次进栈则出栈顺序不可能为C。A321 B213C312 D1322一个队列的入队序列是1234。则队列的输出序列是B。A4321 B1234C1432 D32413. 一个栈的进栈序列是1020304050则栈的不可能输出序列是B进栈出栈可以交替进行。A10,20,30,40,50 B40,30,50,10,20C40,50,30,20,10 D50,40,30,20,104. 元素46810按顺序依次进栈按该栈的可能输出序列依次入队列该队列的可能输出序列是D进栈出栈可以交替进行。A10846 B10648C84610 D108645向顺序栈中压入新元素时应当A。A先移动栈顶指针再存入元素B先存入元素再移动栈顶指针C先后次序无关紧要D同时进行6在一个栈顶指针为top的链栈中将一个p指针所指的结点入栈应执行C。Atop-nextp;Bp-nexttop-next; top-nextp;Cp-nexttop; topp;Dp-nexttop-next; toptop-next;7在一个栈顶指针为top的链栈中删除一个结点时用 x保存被删结点的值则执行D。Axtop;toptop-next;Bxtop-data;Ctoptop-next; xtop-data;Dxtop-data; toptop-next;8一般情况下将递归算法转换成等价的非递归算法应该设置A。A栈 B队列C堆栈或队列 D数组9表达式a*(bc)-d的后缀表达式是B。Aabcd*- Babc*d- Cabc*d- D-*abcd10判断一个顺序队列sq最多元素为m为空的条件是C。Asq-rear-sq-front m Bsq-rear-sq-front-1 mCsq-frontsq-rear Dsq-frontsq-rear111判断一个循环队列Q最多元素为m为满的条件是C。AQ-frontQ-rear BQ-front!Q-rearCQ-front(Q-rear1)% m DQ-front! (Q-rear1)% m12判断栈s满元素个数最多n个的条件是C。As-top0 Bs-top!0Cs-topn-1 Ds-top!n-113一个队列的入队顺序是a,b,c,d则离队的顺序是B。Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a14如果以链表作为栈的存储结构则退栈操作时C。A必须判断栈是否满 B判断栈元素类型C必须判断栈是否空 D对栈不作任何判断解析以链表作为栈的存储结构链栈时退栈出栈操作需要删除栈顶结点。如果栈为空即栈顶指针为NULL则无法执行退栈操作否则会发生错误。因此退栈前必须判断栈是否空。15在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区主机将要输出的数据依次写入缓冲区中而打印机则从缓冲区中取出数据打印该缓冲区应该是一个B结构。A堆栈 B队列 C数组 D先性表16一个递归算法必须包括B。A递归部分 B终止条件和递归部分C迭代部分 D终止条件和迭代部分17从一个栈顶指针为top的链栈中删除一个结点时用变量x保存被删结点的值则执行A。Axtop-data; toptop-next; Bxtop-data;Ctoptop-next; xtop-data; Dtoptop-next; xdata;18在一个链队中假设f和r分别为队头和队尾指针则删除一个结点的运算为C。Arf-next; Brr-next; Cff-next; Dfr-next;19在一个链队中假设f和r分别为队头和队尾指针则插入s所指结点的运算为B。Af-nexts; fs; Br-nexts;rs;Cs-nextr;rs; Ds-nextf;fs;20在一个不带头结点的链队中假设f和r分别为队头和队尾指针则从该对列中删除一个结点并把结点的值保存在变量x中的运算为C。Axr-datarr-next; Brr-next; xr-dataCxf-dataff-next; Dff-next; xf-data21栈和队列的共同特点是C。A都是先进后出 B元素都可以随机进出C只容许在端点处插入和删除元素 D都是先进先出22栈的插入和删除操作在A进行。A栈顶 B栈底C任意位置 D指定位置23在一个顺序队列中队首指针指向队首元素的C位置。A前一个 B后一个C当前 D后面24当利用大小为n的数组顺序存储一个队列时该队列的最大长度为( B )。A. n-2 B. n-1 C. n D. n125从一个顺序存储的循环队列中删除一个元素时首先需要( C )。A. 队头指针加一 B. 队头指针减一C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素二、判断题1. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。√2. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。×3. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。√解析顺序存取指存取元素时只能按照某种特定的顺序进行不能像数组一样随机访问。如果表述为“栈和队列都是顺序存储的线性表,但它们对存取位置的限制不同。“就是错误的4. 若让元素1,2,3依次进栈则出栈次序1,3,2是不可能出现的情况。×5. 在用单链表表示的链式队列Q中队头指针为Q-front队尾指针为Q-rear则队空条件为Q-front Q-rear。√6. 递归定义的数据结构通常用递归算法来实现对它的操作。√7. 递归的算法简单、易懂、容易编写而且执行效率也高。×8. 递归调用算法与相同功能的非递归算法相比主要问题在于重复计算太多而且调用本身需要分配额外的空间和传递数据和控制所以时间与空间开销通常都比较大。√9. 用非递归方法实现递归算法时一定要使用递归工作栈。×10. 栈是限定在表的一端进行插入和删除操作的线性表又称为先进后出表。√11. 队列的特性是先进后出。×12. 往栈中插入元素的操作方式是先写入元素后移动栈顶指针。×13.循环队列队头指针在队尾指针前一个位置队列是“满”状态。√解析表述为“队头指针在队尾指针下一个位置”更没有歧义14. 在队列的顺序存储结构中当插入一个新的队列元素时尾指针后移当删除一个元素队列时头指针后移。√15. 向一个栈顶指针为h的链栈(结点的指针域为next)中插入一个s所指结点时先执行s-nexth再执行hs操作。√16. 一个递归算法不必包括递归终止条件。×17. 在一个链式队列中若队头指针与队尾指针的值相同则表示该队列至多有1个结点。×18. 在用循环单链表表示的链式队列中可以不设队头指针仅在链尾设置队尾指针。√解析在循环单链表中如果只设置队尾指针rear不设队头指针front队尾指针rear指向最后一个结点第一个结点队头是rear-next因为是循环链表因此通过队尾指针可以访问到队头结点不需要单独设队头指针。三、程序选择题1在下面空格处填写一条语句以使下面的链式队列全部元素出队的算法完整。int write(LinkQueue *q){QueueNode *p;if (q-frontq-rear) /*队空*/{printf(“队空无元素可取”);exit(0);}while (q-front-next ! NULL){pq-front-next;q-front-nextp-next;/*出队*/printf(“%4d”,p-data);free(p); /*释放已出队结点*/}_______C________ /*队空时头尾指针指向头结点*/}A. q-frontq-rear;B. qq-next;C. q-rearq-front;D. pp-next;解析多次执行q-front-nextp-next;后q-front并不会被改变改变的是next的值实际上front始终指向头结点。2. 在下面空格处填写适当的语句以使下面的循环队列的入队和出队算法完整。define MAXSIZE 100;typedef char Elemtype;typedef struct{Elemtype queue [MAXSIZE];int front,rear;}sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x){if ((Q-rear1)%MAXSIZEQ-front){printf(“队列已满!\n”);return 1;}else{Q-rear(Q-rear1)%MAXSIZE;(1)return 0;}} /*入队算法*/Elemtype del_cqueue(sequeuetype *Q){if ( (2) ){printf(“队列为空!\n”);return 1;}else{Q-front(Q-front1)%MAXSIZE;return(Q-queue[Q-front]);}} /*出队算法*/A. (1) (Q-rear1)%MAXSIZEQ-front (2) Q-front(Q-front1)%MAXSIZE;B. (1) (Q-front1)%MAXSIZEQ-rear (2) Q-rear(Q-rear1)%MAXSIZE;C. (1) Q-frontQ-rear (2) Q-queue[Q-rear]x;D. (1) Q-queue[Q-rear]x; (2) Q-frontQ-rear【答案】D3. 写出下列程序执行后的结果SeqQueue Q;InitQueue(Q);int a[4]{5,8,12,15};for(int i0;i4;i) InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)10);while(!QueueEmpty(Q)) printf(“%d ”,OutQueue(Q));执行后的输出结果为_______B___________。A. 5 8 12 15 30B. 12 15 5 30 18C. 8 12 15 30 18D. 12 15 5 18 304. 写出下列程序执行后的结果SeqStack S;InitStack(S);Push(S,3);Push(S,4);Push(S,5);int xPop(S)2*Pop(S);Push(S,x);int i,a[4]{5,8,12,15};for (i0;i4;i) Push(S,a[i]);while(!StackEmpty(S)) Printf(“%d “,Pop(S));执行后的输出结果为________A__________。A. 15 12 8 5 13 3B. 3 5 8 12 13 15C. 15 13 12 8 5 3D. 15 12 13 3 8 55.在下面空格处填写一条语句以使下面的进栈算法完整。void Push(struct SeqStack*s,ElemType x){If (s-topMaxSize-1){printf(“栈满溢出错误\n”);exit(1);}____C____s-data[s-top]x;}A. s-tops-data;B. s-data;C. s-top;D. s-datas-top;6. 在下面空格处填写一条语句以使下面的出栈算法完整。ElemTypePop(struct SeqStack*s,ElemType x){If (StackEmpty(s)){printf(“栈下溢出错误\n”);exit(1);}xs-data[s-top];____A_____return x;}A. s-top--;B. s-data--;C. s-tops-data;D. s-datas-top;
