全2024数据结构考试内部题库含答案解析（全考点）

数据结构考试内部题库含答案解析（全考点）若用数组・来实现循环队列,且当前和

1.A[

0..5]rear front的值分别为和,当从队列中删除一个元素，再加上两个15元素后，和的值分别为（）rear front・•A:3和4・•B:3和0・•C:5和0・•D:5和1解析循环队列中，每删除一个元素，队首指针（）front=front+l%6,每插入一个元素,队尾指针rear=（）rear+l%6上述操作后,front=0rear=3o zo答案B、在一个链队列中，假设队头指针为队尾指针为2front,所指向的元素需要入队，则需要执行的操作为（）rear,x•A:front=x,front=front-next•B:x-next=front-next,front=x•C:rear-next=x,rear=x.A:只有表头结点指针，没有表尾指针的双向循环链表・•B:只有表尾结点指针，没有表头指针的双向循环链表.•C:只有表头结点指针，没有表尾指针的单向循环链表••D:只有表尾结点指针，没有表头指针的单向循环链表解析对于双向循环链表，不管是表头指针还是表尾指针，都可以很方便地找到表头结点，方便在表头做插入或删除操作而单循环链表通过尾指针可以很方便地找到头结点，但通过头指针找尾结点则需要遍历一次链表对于C,插入和（）删除结点后，找尾结点需要花费0n的时间答案C、向一个栈顶指针为的链栈（不带头结点）中插入5top一个结点，则执行（）x•A:top-next=x;•B:x-next=top-next;top-next=x•C:x-next=top;top=x•D:x-next=top;top=top-next解析链表采用不带头结点的单链表表示时，进栈操作在首部插入一个结点x即x-next=top,插入完后需将top指向该插入的结点xo答案C、一个栈的输入序列为・・，输出序列的第一个61,2,3,.,n元素是则第个输出元素是i,j・•A:i-j-1・•B:i-j・•C:j-i+1・•D:不确定解析当第i个元素第一个出栈时，则i之前的元素可以依次排在i之后出栈，但剩余的元素可以在此时进栈并且也会排在i之前的元素出栈，所以第j个出栈的元素是不确定的答案D

7、已知一个栈的入栈序列是，其出栈序列为1,2,3,

4......--I..I,则，」不可能是（）・•A:2,4・•B:2,1・•C:4,3・•D:3,4解析逐个判断每个选项可能的入栈出栈顺序答案C、一个栈的入栈序列为・・出栈序列纂8l,

23.,n,若一,则—可能取值的个数是（）o=3•A:n-3•B:n-2•C:n-1•D:无法确定解析3之后的4,

5...,n取的数（持续进栈直到该数入栈后立即出栈）接下来分析1和2:可以当，二1时可取2;当，二2时，I-----I二4时，」可取除1,3,4之外的所有数；故是3之前入栈的数（可能是1或2）,也可以是4,可能取值的个数为n-l答案Co、下列关于栈的叙述中，错误的是（）9I.采用非递归方式重写递归程序时必须使用栈n.函数调用时，系统要用栈保存必要的信息m.只要确定了入栈次序，即可确定出栈次序iv.栈是一种受限的线性表，允许在其两端进行操作・.A仅I・•B仅I、口、m・•c仅I、川、IV・•D:仅］I、m、iv解析I的反例计算斐波拉契数列迭代实现只需要一个循环即可实现m的反例入栈序列为1,2,进行Push,Push,Pop,Pop操作，出栈次序为2,1;进行Push,Pop,Push,Pop操作，出栈次序为1,

2.IV的反例栈是一种受限的线性表，只允许在一端进行操作答案C队列的“先进先出〃特性是指（）

10.I.最后插入队列中的元素总是最后被删除n.当同时进行插入、删除操作时，总是插入操作优先m.每当有删除操作时，总要先做一次插入操作iv.每次从队列中删除的总是最早插入的元素•A:I・•B:I和IV・•cII和m・•D:IV解析队列〃先进先出〃的特性表现在先进队列的元素先出队列，后进队列的元素后出队列，进队列对应的是插入操作，出队列对应的是删除操作工和IV均正确答案B・•D:rear-next=x x-next=null,rear=xz解析插入操作时，先将结点x插入到链表尾部，再让rear指向这个结点x C的做法不够严密，因为是队尾，所以队尾ox-next必须置为空答案D、若以作为双端队列的输入序列，则既不能由31,2,3,4输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是（）・•A:1,2,3,4・•B:4,1,3,2・•C:4,2,3,1・•D:4,2,1,3解析使用排除法先看可由输入受限的双端队列产生的序列设右端输入受限，1,2,3,4依次左入，则依次左出可得4,3,2,1,排除A;右出、左出、右出、右出可得到4,1,3,2,排除B;再看可由输出受限的双端队列产生的序列设右端输出受限，1,2,3,4依次左入、左入、右入、左入，依次左出可得到4,2,1,3,排除Do答案C、已知循环队列存储在一维数组中，且队列非4空时和分别指向队头元素和队尾元素若初始front rear时队列为空，且要求第一个进入队列的元素存储在处,A

[0]则初始时和的值分别是front rear••A:0,0••B:0,n-1••C:n-1,0••D:n-1,n-1解析根据题意，第一个元素进入队列后存储在A

[0]处，此时front和rear值都为0入队时由于要执行orear+1%n操作，所以若入队后指针指向0,则rear初值为n-1,而由于第一个元素在A

[0]中，插入操作只改变rear指针，所以front为0不变答案B、循环队列放在一维数组・・中，指向队头5A[O..M1]endl元素，指向队尾元素的后一个位置假设队列两端end2均可进行入队和出队操作，队列中最多能容纳个元M-1素初始时为空下列判断队空和队满的条件中，正确的是・•A:队空:endl==end2;队满:endl==end2+l modM・•B:队空endl==end2;队满end2==endl+l modM-1・•C:队空:end2==endl+l modM;队满endl==end2+l modM・•D:队空endl==end2+l modM;队满end2==endl+l modM-1解析endl指向队头元素，可知出队操作是先从A[endl]读数,然后endl再加l end2指向队尾元素的后一个位置,可知o入队操作是先存数到A[end2]然后end2再加

1.若用A⑼7存储第一个元素，队列初始时，入队操作是先把数据放到A

[0]中,然后end2自增,即可知end2初值为0;而endl指向的是队头元素,队头元素在数组A中的下标为0,所以得知endl的初值也为0,可知队空条件为endl==end2;然后考虑队列满时，因为队列最多能容纳M-1个元素，假设队列存储在下标为到M-2的M-1个区域，队头为A

[0],队尾为A[M-2],此时队列满，考虑在这种情况下endl和end2的状态，endl指向队头元素，可知endl=0end2指向队尾元素的后一个位置,可知end2=M-2+,（）l=M-l,所以队满的条件为endl==end2+l modMo答案;A、执行（）操作时，需要使用队列作为辅助存储空间6・•A:查找散列（哈希）表・•B:广度优先搜索图.•C:前序（根）遍历二叉树・•D:深度优先搜索图解析图的广度优先搜索类似于树的层序遍历，都要借助于队列答案B、串的数组为7ababaaababaa nextvalo・・A:0,1,0,1,1,2,0,1,0,1,0,2・•B:0,1,0,1,1,4,1,1,0,1,0,2・•C:0,1,0,l,0,4,2,1,0,1,0,4・•D:0,1,1,1,0,2,1,1,0,1,0,4解析nextval从0开始，可知串的位序从1开始第一步，令nextval[l]=next[l]=0oI*11--―|I从j=2开始，依次判断—是否等于―？若是则将next]修正为next[next[j]],直至两者不相等为止答案C、一棵度为的树中，若有个度为的结点，84T20410个度为的结点，个度为的结点，个度为的结312101点，则树的叶结点个数是（）T•A:41•B:82•C:113•D:122解析I---I设树中度为ii=0,l,2,3,4的结点数分别为二，树中结点总数为n,则n二分支数+1,而分支数又等于树中各结点的度之和，即n=l+=10+2+30+80=122=10+1+10+20=41=82，即树T的叶结+1—+1―+1—+—依题意，—+21—1+31—+4点的个数是82答案BO+++、已知表头元素为的单链表在内存中的存储状态如下1c表所示现将存放于处并插入单链表，若在f1014H f逻辑上位于和之间，则的“链接地址〃依次是a ea,e,f在这里插入图片描述•A:1010H,1014H,1004H•B:1010H,1004H,1014H•C:1014H,1010H,1004H•D:1014H,1004H,1010H解析答案D、已知头指针指向一个带头结点的非空单循环链表，2h,其中是指向直接后继结点的指针,next结点结构为是尾指针，是临时指针现要删除该链表的第一个元素,q正确的语句序列是（）O在这里插入图片描述•A:h-next=h-next-next;q=h-next;freeq;•B:q=h-next;h-next=h-next-next;freeq;•C:q=h-next;h-next=q-next;ifp!=qp=h;freeq;•D:q=h-next;h-next=q-next;ifp==qp=h;freeq;在这里插入图片描述解析如图1所示，要删除带头结点的非空单循环链表中的第一个元素，就要先用临时指针q指向待删结点，q=h-next;然后将q从链表中断开，h-next=q-next（这一步也可写成h-next=h-next-next）址匕时要考虑一种特殊情况，若待删结点是链表的尾结点，即循环单链表中只有一个元素（P和q指向同一个结点），如图2所示，则在删（）除后要将尾指针指向头结点，即if p二二q p二h;最后释放q结点即可答案D、栈和队列具有相同的（）3••A:抽象数据类型••B:逻辑结构••C:存储结构••D:运算解析栈和队列的逻辑结构都是相同的，都属于线性结构，只是它们对数据的运算不同答案B、设链表不带头结点且所有操作均在表头进行，则下列最4不适合作为链栈的是（）O。