2、栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是A.1B.2C.3D.43.若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是A：dcebfaB：cbdaefC：dbcaefD：afedcb4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是A：bacdeB：dbaceC：dbcaeD：ecbad5.元素a,b,c,d,
3、e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3B.4C.5D.66.已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是A.0,0B.0,n-1C.n-1,0D.n-1,n-17.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，
4、1，7，5，6，2，4，则其遍历方式是A．LRNB.NRLC.RLND.RNL8.下列二叉排序树中，满足平衡二叉树定义的是9.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A．39B.52C.111D.11910.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III11.下列线索二叉树中（用虚线表示线索
5、），符合后序线索树定义的是12.在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是A：13，48B：24，48C：24，53D：24，9013.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是A：41B：82C：113D：12214.对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是A：该树一定是一棵完全二叉树B：树中一定没有度为1的结
6、点C：树中两个权值最小的结点一定是兄弟结点D：树中任一非叶结点的权值一定不小于下一级任一结点的权值15.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A.257B.258C.384D.38516.若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,117.已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是A.115B.116C.1895D.189
7、618.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,3419.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III20.若无向图G-（V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是A：6B：15C：16D：212
8、1.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是A：4B：3C：2D：122.下列关于图的叙述中，正确的是Ⅰ.回路是简单路径Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列，则该图不存在回路A.仅ⅡB.仅Ⅰ、ⅡC.仅ⅢD.仅Ⅰ、Ⅲ23.下列叙述中，不符合m阶B-树定义要求的是A.根节点最多有
