波波的数据结构

波波的数据结构属实上的快，这里将会写些pta的解析，算是复习 预习，帮助我与大家期末不挂科

1-1 在用数组表示的循环队列中，front值一定小于等于rear值 F 解析：环形循环队列font的值有可能大于rear 1-2 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。T 解析：顺序存储结构都是要定义数组大小的，与链式结构不同 1-3 循环队列执行出队操作时会引起大量元素的移动。F 解析：出队对队首指针进行操作就行 1-4 栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。T 解析：队首出队列，队尾进队列 1-5 n个元素进队的顺序和出队的顺序总是一致的。T 解析：队列先进先出，栈后进先出 1-6 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算 T 解析：队尾指针减队首指针就是元素个数

2-1 若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：（B） A.1->2->3 B.2->3->4 C.4->1->2 D.答案不唯一 解析：先进先出，对象4入队后1->2->3->4，对象1出队 2-2 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：（D） A.b a c d e B.d b a c e C.e c b a d D.d b c a e 解析：A．可由左入，左入，右入，右入，右入得到；B．可由左入，左入，右入，左入，右入得到；C．可由左入，左入，左入，右入，左入得到；所以不可能得到D。 2-3 若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？（A） A.2和0 B.2和2 C.2和4 D.2和6 解析：rear指向队尾的一个元素，font指向队首元素的前一位 2-4 如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：（B） A.m-1 B.m C.m+1 D.不能确定 解析：这是特殊的循环队列，正常的是m-1个 2-5 在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算(B)。 A.f->next=s; f=s; B.r->next=s; r=s; C.s->next=s; r=s; D.s->next=f; f=s; 2-6 设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（B ）的输出序列。 解析：队列先进先出 2-7 现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：（C） A.1, 2, 5, 6, 4, 3 B.2, 3, 4, 5, 6, 1 C.3, 4, 5, 6, 1, 2 D.6, 5, 4, 3, 2, 1 2-8 设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize，此外该队列再没有其他数据成员，则队列的队满条件是（C ）。 A.Q.front == Q.rear

B.Q.front+Q.rear >= maxSize

C.Q.front == (Q.rear +1) % maxSize

D.Q.rear == (Q.f ront+1) % maxSize 解析：当队满时，队尾指针的下一位就是队首指针 2-9 关于栈和队列的下列说法正确的是（B） A.栈的插入操作是在栈顶进行，插入时需将栈内所有元素后移； B.栈是后进先出的结构，出栈时除了栈顶元素，其余元素无需移动； C.循环队列的出队操作删除的是队头元素，采用循环队列存储时，其余队列元素均需要移动； D.链队列的入队操作在表尾进行，操作时间与队列长度成正比 解析：A，C不需要后移,D时间复杂度为O（1） 2-10 最不适合用作链队的链表是（A）。 A.只带队头指针的非循环双链表 B.只带队头指针的循环双链表 C.只带队尾指针的循环双链表 D.只带队尾指针的循环单链表 解析：A中查找队尾指针的时间复杂度为O（n） 2-11 循环队列的队空条件为（ D）

A.(sq.rear+1) % mazsize ==(sq.front+1) % maxsize;

B.(sq.rear+1)% maxsize ==sq.front+1

C.(sq.rear+1) % maxsize ==sq.front

D.sq.rear ==sq.front 解析：队空时队首指针等于队尾指针 2-12 依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ C）。 A.a B.b C.c D.d 解析：删除了a,b 2-13 循环队列___C_。 A.不会产生溢出 B.不会产生上溢出 C.不会产生假溢出 D.以上都不对 解析：循环队列在data数组空间满时不能再进队元素，这称为上溢出；而在队空时出队元素称为下溢出。所谓假溢出是指队中有空位置，但由于队满条件设置不合理而导致不能进队元素。循环队列克服了假溢出但仍可能会产生上溢出和下溢出。 2-14 已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为（C　）。 A.5 B.6 C.16 D.17 解析：首先要明白，font指针所在处是没有元素的，数组一共有21个位置，4,5,6,7,8为空，所以队列长度为21-5=16 2-15 用单链表表示的链队的队头在链表的（A）位置。 A.链头 B.链尾 C.链中 D.均可以 2-16 在少用一个元素空间的循环队列(m为最大队列长度)是满队列的条件（ B）。

A.rear==front

B.(rear+1)%m==front

C.(rear+1)==front

D.front==(front+1)%m 解析：可以把循环队列看成一个环，队满时队尾指针与队首指针相连