1. An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. ✓
2. 在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。 ✓
3. 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。✗
4. 顺序栈中元素值的大小是有序的。 ✗这种说法是错误的。
顺序栈是一种数据存储结构，它主要是利用顺序存储方式来实现栈这种后进先出（LIFO）的数据结构。
栈的操作主要是入栈（将元素压入栈顶）和出栈（将栈顶元素弹出），重点在于元素的进出顺序，而不是元素值的大小顺序。在顺序栈中，元素可以按照任意的顺序被压入栈中，并没有要求元素值是有序排列的。
例如，对于一个顺序栈，可以先将元素5压入栈，接着将元素3压入栈，这时候栈中的元素顺序是3在栈顶，5在栈底，元素值大小是无序的。
5. 栈顶元素和栈底元素有可能是冋一个元素。 ✓
6. 栈是一种对进栈、出栈操作总次数做了限制的线性表。✗栈本身对进栈和出栈操作的总次数没有限制。
7. 对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。 ✓
8. 两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。 ✓
9. 序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。 ✓
10. 若用data[1..m]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次。 ✗
11. 在用数组表示的循环队列中，front值一定小于等于rear值。✗这种说法是错误的。
在循环队列中， front 表示队头元素的位置， rear 表示队尾元素的位置。循环队列是一个环形的存储结构，当进行入队和出队操作时，队头和队尾指针会不断移动。
有两种情况来判断队列是否为空或者满：
- 队列为空时，通常 front = rear 。
- 队列满时，一般有两种判断方式。一种是牺牲一个存储单元来区分队满和队空，此时队满的条件是 (rear + 1) % 数组长度= front ；另一种是设置一个标志位来区分队满和队空。
当不断地进行出队操作后， front 会不断向后移动，可能会出现 front > rear 的情况。例如，初始时 front = 0 ， rear = 0 ，经过一系列的出队操作后， front 的值会大于 rear 的值。
12. 队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。✗
13. n个元素进队的顺序和出队的顺序总是一致的。 ✓
14. 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。✓ 这种说法是正确的。
在环形队列（循环队列）中，通常利用队首指针 front 和队尾指针 rear 来确定队列中元素的个数，常见的计算方式有以下两种情况：
牺牲一个存储单元来区分队满和队空的情况
队列元素个数计算公式为： (rear - front + 数组长度) % 数组长度 。例如，循环队列用长度为 10 的数组存储， front 为 3 ， rear 为 8 ，那么元素个数就是 (8 - 3 + 10) % 10 = 5 个。
通过设置标志位等其他方式区分队满和队空的情况
同样可以依据 front 和 rear 按相应规则来计算元素个数，总体思路也是结合队列存储的数组长度以及两者的相对位置关系来算出实际的元素个数。
所以确实能根据队首指针和队尾指针的值来计算环形队列中元素的个数。
15. 若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。
16. 可以通过少用一个存储空间的方法解决循环队列假溢出现象。✗
17. 在对不带头结点的链队列作出队操作时，不会改变头指针的值。 ✗这种说法是错误的。
在不带头结点的链队列中，队头指针 front 指向队头结点。当进行出队操作时，如果队列中只有一个元素，那么出队操作后队列为空，此时需要将队头指针 front 赋值为 NULL ；如果队列中有多个元素，出队操作会使队头指针 front 指向下一个结点。
例如，有一个不带头结点的链队列，队列中有元素A和B，队头指针 front 指向A。当A出队后， front 就会指向B。所以在不带头结点的链队列作出队操作时，头指针的值可能会改变。
18. 循环队列也存在着空间溢出问题。这种说法是正确的。
循环队列虽然解决了普通队列的假溢出问题，但它仍然会出现空间溢出的情况。
循环队列的存储空间是固定的，假设其容量为n。当队列为满时，如果再执行入队操作，就会发生空间溢出。判断队满的条件一般是(rear + 1) \% n = front（其中rear是队尾指针，front是队首指针），此时如果继续入队就会产生溢出，因为已经没有空闲的空间来存放新元素了。
19. 循环队列执行出队操作时会引起大量元素的移动✗
20. 队列中允许插入的一端叫队头，允许删除的一端叫队尾。 ✗这种说法是错误的。在队列中，允许插入的一端是队尾，允许删除的一端是队头。就好比排队买东西，人们是从队尾进入队伍（插入元素），在队头离开队伍（删除元素）。
21. 采用顺序存储结构的循环队列，出队操作会引起其余元素的移动。 ✗
22. 队列适合解决处理顺序与输入顺序相同的问题。✓这种说法是正确的。
队列是一种先进先出（FIFO）的数据结构。当数据按照一定的顺序进入队列（输入顺序）后，处理这些数据时，也是按照它们进入队列的先后顺序来进行的。
例如，在计算机系统中，打印任务队列就是一个典型的应用。用户提交的打印任务按照提交的先后顺序进入打印队列，打印机在处理这些任务时，同样是按照先提交先打印的顺序，也就是处理顺序和输入顺序相同，从而保证公平性和有序性。
23. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 ✗
24. 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。 这种说法是正确的。
1. 栈的顺序存储结构（顺序栈）
- 栈是一种特殊的线性表，它限定只能在一端进行插入和删除操作，这一端称为栈顶。在顺序存储结构中，栈通常用一个数组来实现。
- 当栈顶指针（通常用top表示）达到数组的最大下标（假设栈的大小为n，top = n - 1）时，如果再进行入栈操作，就会发生栈溢出。因为此时已经没有足够的空间来存放新的元素了。
2. 队列的顺序存储结构（顺序队列）
- 队列是一种先进先出的数据结构，在顺序存储结构中，同样会受到存储空间的限制。
- 对于顺序队列，当队尾指针（通常用rear表示）达到数组的最大下标，且队首指针（通常用front表示）不为0时，如果再进行入队操作，就会出现溢出情况。虽然循环队列可以在一定程度上缓解这种情况，但当循环队列真正满了的时候，还是会溢出。
25. 栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。✓
26. 栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。✗
27. 栈和队列逻辑上都是线性结构。✓
28. 中缀表达式 a+b*c+(d*e+f)*g转换成后缀表达式,正确的答案为:abc*+de*f+g*+。转换的一种方法
1)先按照运算符的优先级对中缀表达式加括号，变成( ( a+(b*c) ) + ( ((d*e)+f) *g ) )
2)将运算符移到括号的后面，变成((a(bc)*)+(((de)*f)+g)*)+
3)去掉括号，得到abc*+de*f+g*+
29. 若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？+(+
30. 表达式a*(b+c)-d的后缀表达式是：a b c + * d -
31. 若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？将链表头设为top
32. 利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行：top--
33. 设有一个递归算法如下
int fact(int n)
{ //n大于等于0
if(n<=0) return 1;
else return n * fact(n-1);
}则计算fact(n)需要调用该函数的次数为（n+1）。
34. 若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( top--; V[top]=x; )。
35. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶元素所在的下标，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ top[1]+1=top[2] ）。
36. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为(SXSSXSXX )。
37. 循环顺序队列中是否可以插入下一个元素（与队头指针和队尾指针的值有关）
38. 循环队列放在一维数组A[0...M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（队空：end1==end2;队满：end1==(end2+1)mod M）。
39. 数组Ｑ[ｎ]用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ （n+r-f)%n）。
40. 最不适合用作链队的链表是（）。答案是A。
1. 分析选项A
- 对于只带队头指针的非循环双链表，在进行入队操作（在队尾插入元素）时，需要遍历整个链表才能找到队尾。因为是非循环链表，从队头开始遍历到队尾的时间复杂度是O(n)，n是链表的长度。这在频繁入队操作的情况下效率很低，不适合作为链队的链表。
2. 分析选项B
- 只带队头指针的循环双链表，虽然只有队头指针，但是由于是循环双链表，从队头可以很容易地找到队尾。可以通过队头指针向后遍历，当遇到队头节点的前驱节点时就是队尾，时间复杂度是O(1)，比较适合作为链队的链表。
3. 分析选项C
- 只带队尾指针的循环双链表，队尾指针直接指向队尾元素，在入队操作时，可以直接在队尾插入元素，时间复杂度是O(1)。出队操作（从队头删除元素）时，通过队尾指针也能很容易地找到队头，因为是循环双链表，所以也很适合作为链队的链表。
4. 分析选项D
- 只带队尾指针的循环单链表，入队操作直接在队尾进行，时间复杂度是O(1)。出队操作（从队头删除元素）时，通过队尾指针可以在O(1)时间内找到队头（因为是循环单链表），所以也适合作为链队的链表。
41. 现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是3, 4, 5, 6, 1, 2
42. 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：4
43. 
选D(不选c)
44. 程序如下：
int s(int n) { return (n<=0) ? 0 : s(n-1) +n; }
void main() { cout<< s(1); }
程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是（main()->S(1)->S(0)） 。以下是对这段C++ 代码含义的具体解释
1. int s(int n) 函数部分
这是一个自定义的名为 s 的函数，它接受一个整数类型的参数 n ，函数的返回值类型也是整数。
函数体内部使用了三目运算符（ ? : ）来决定返回值，具体逻辑为：
- 如果 n <= 0 这个条件成立，那么函数直接返回 0 。
- 如果 n <= 0 不成立，也就是 n 大于 0 时，函数会进行递归调用，返回 s(n - 1) + n 的值。递归调用意味着函数会在自身内部再次调用自己，每次调用时参数 n 的值减 1 ，直到 n 小于等于 0 为止，然后将每次递归调用时的 n 值进行累加（例如第一次 n = 1 ，会递归调用 s(0) ，返回值就是 s(0) + 1 ，以此类推）。
2. void main() 函数部分
main 函数是C++ 程序的入口点，这里定义的 main 函数返回类型为 void （表示无返回值）。
在 main 函数内部，只有一条语句 cout<< s(1); ，它的作用是调用前面定义的 s 函数，并将参数 1 传递给 s 函数，然后把 s 函数的返回值输出到标准输出（通常是屏幕）上。
总体来讲，这段代码的功能是通过递归的方式计算一个基于参数 n 的累加值（从 n 依次递减到 0 的所有整数累加），并在 main 函数中调用该递归函数并输出结果（当传递参数为 1 时，计算的就是 1 + 0 的值并输出）。
45. 令P代表入栈，O代表出栈。当利用堆栈求解后缀表达式1 2 3 + * 4 –时，堆栈操作序列是：PPPOOPOOPPOOPO
46. 从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：X= ST->data; ST = ST->next;
47. 若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：
（1）从S1中依次弹出两个操作数a和b；
（2）从S2中弹出一个运算符op；
（3）执行相应的运算b op a；
（4）将运算结果压入S1中。
假定S1中的操作数依次是{ 5, 8, 3, 2 }（2在栈顶），S2中的运算符依次是{ *, -, + }（+在栈顶）。调用3次F()后，S1栈顶保存的值是：15
48. 如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：m(答案： m 个。
解析：
在常规的循环队列中，使用队首指针 front 和队尾指针 rear 来表示队列范围时，为了区分队满和队空的情况，往往会牺牲一个存储空间，也就是最多能存放 m - 1 个元素（假设数组大小为 m ）。
而本题中采用队头指针 front 和队列元素个数 size 来表示队列范围，就不存在需要通过少用一个存储空间来区分队满和队空的问题了。只要队列元素个数 size 不超过数组大小 m ，就可以正常存放元素，所以这样的循环队列可以容纳的元素个数最多就是 m 个。)
49. 如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为：(front+size-1)%m
50. 线性表、堆栈、队列的主要区别是什么？堆栈和队列都是插入、删除受到约束的线性表。答案是B。
1. 分析选项A
- 线性表、堆栈和队列都可以用指针（链式存储结构）或者数组（顺序存储结构）来实现。例如，线性表可以用链表（基于指针）或者数组来存储元素；堆栈可以用链栈（基于指针）或者顺序栈（基于数组）实现；队列可以用链队列（基于指针）或者顺序队列（基于数组）实现。所以选项A错误。
2. 分析选项B
- 堆栈是一种特殊的线性表，它只允许在一端（栈顶）进行插入和删除操作，遵循后进先出（LIFO）原则。队列也是特殊的线性表，只允许在一端（队尾）插入，在另一端（队头）删除，遵循先进先出（FIFO）原则。它们都是对线性表插入和删除操作进行了约束的结构，选项B正确。
3. 分析选项C
- 堆栈也可以用循环链表实现。例如，可以将循环链表的表头作为栈底，表尾作为栈顶，入栈操作就是在表尾插入元素，出栈操作就是在表尾删除元素。所以选项C错误。
4. 分析选项D
- 堆栈和队列都是线性结构。线性结构是指数据元素之间存在一对一的线性关系的数据结构，堆栈和队列中的元素之间的关系满足线性结构的定义，只是它们的操作有特殊的限制。所以选项D错误。
51. 在一个不带头结点的非空链式队列中,假设f和r分别为队头和队尾指针,则插入s所指的结点运算是( r->next=s; r=s; )。
52. 给定程序时间复杂度的递推公式：T(1)=1，T(N)=2T(N/2)+N。则对该程序时间复杂度最接近的描述是：O(NlogN)。
53. 程序P1和P2时间复杂度的递推公式：
P1: T(1)=1, T(N)=T(N/2)+1;
P2: T(1)=1, T(N)=2T(N/2)+1;
则下列关于两程序时间复杂度的结论中最准确的是：P1是O(logN)，P2是O(N)