士谔书院导办向你发来了lqq生日party的请柬，可是请柬最后的信息被加密了。请柬的第一行歪歪扭扭地写着什么“DS六一赛暨lqq庆生赛选择题”。请你完成以下15道选择题，获取lqq生日party的详细信息。
注意，本题采用Special Judge（赛时WA 0是正常现象），将在比赛结束后统一评判，请把答案用大写字母写在提交框的一行中（且不要空题）。
例如：
1. 以下关于数据结构的说法中错误的是（ ）。
A. 数据结构相同，对应的存储结构也相同
B. 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作3个方面
C. 数据结构操作的实现与存储结构有关
D. 设计逻辑结构时可不考虑存储结构
2. 设一个栈的输入序列是 1，4，3，2，5,则下列序列中，是栈的合法输出序列的是()
A. 5 1 4 3 2
B. 2 5 1 3 4
C. 2 3 1 4 5
D. 3 4 1 5 2
3. 若二叉树有40个叶节点，则该二叉树的节点总数至少为（）
4. 对线性表进行二分查找时，要求线性表必须 （）。
A．以顺序方式存储
B．以链接方式存储，且结点按关键字有序排序
C．以链接方式存储
D．以顺序方式存储，且结点按关键字有序排序
5. 仅从形态上看，具有n个节点且深度也为n的二叉树一共有( )种。
6. 一棵具有2011个节点的树中叶节点的个数为117，该树经过转换后对应的二叉树中无右子树的节点有（）个
| A.116 |
B.115 |
C.1894 |
D.1895 |
7. 若已知一个栈的入栈顺序是1、2、3、4.其出栈序列为P1、P2、P3、P4、，则P2、P4不可能是（）
| A. 2、4 |
B. 2、 1 |
C. 4 、 3 |
D. 3 、 4 |
8. 对包含n个元素的散列表进行查找，平均查找长度为（ ）。
9. 当4个元素的进栈序列确定后，由这4个元素组成的可能的出栈序列有()种
10．当采用分块查找时，数据的组织方式为 ()
A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
11. 如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为（ ）。
| A. (front+size-1)%m |
B. (front+size)%m |
C. front+size-1 |
D. front+size |
12. 依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（ ）。
13. 用链表方式存储的队列，在进行插入运算时（ ）。
| A. 仅修改头指针 |
B. 头、尾指针都要修改 |
C. 仅修改尾指针 |
D. 头、尾指针可能都要修改 |
14. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
| A. 1和5 |
B. 2和4 |
C. 4和2 |
D. 5和1 |
15. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f依次进入栈S。若每个元素出栈后立即进入队列Q, 且6个元素出队的顺序是b,f,e,d,c,a，则栈S的容量至少是( )。
