● 双端队列是指在队列的两个端口都可以加入和删除元素,如下图所示,现在要求元素进队列和出队列必须在同一端口。即从a端进队的元素必须从a端出,从b端进队的元素必须从b端出。则对于四个元素的序列a.b.c.d,若要。求前两个元素a.b从a端口按次序全部进入队列。后两个元素Cd从b端口按次序全部进入队列,则不可能得到的出队序列是(59)。

- A.d、a、b、c B.d、c、b、a
- C.b、a、d、c D.b、d、c、a
双端队列要求元素进出队列必须在同一端口,即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出。这样使得双端队列具有了栈的特点,即后进入的元素先出队。
● 设S是一个长度为n的非空字符串,其中的字符各不相同,则其互异的非平凡子串(非空且不同于S本身)个数为 (57) 。
- (57) A.2n-1 B.n² C.n(n+1)/2 D.(n+2) (n-1)/2
● 某n阶的三对角矩阵A如下图所示,按行将元素存储在一堆数组M中,设a1,1存储在M[1],那么ai,j(1<=i,j<=n且ai,j位于三条对角线中),存储在M(57)。

- A.i+2j B.2i+j C.i+2j-2 D.2i+j-2 (带入)
● 已知某二叉树的先序遍历序列为A B C D E F、中序遍历序列为B A D C F E,则可以确定该二叉树( )。
- A.是单支树(即非叶子结点都只有一个孩子)
- B.高度为4(即结点分布在4层上)
- C.根结点的左子树为空
- D.根结点的右子树为空
● 具有3个节点的二叉树有(60)种形态。
- (60)A.2 B.3 C.5 D.7
● 具有三个结点的二叉树有五种,可推测出具有四个节点的二叉树有(58)种。
- (58)A.10 B.11 C.14 D.15
● 对下面的二叉树进行顺序存储(用数组 MEM 表示),已知结点 A、B、C 在 MEM 中对应元素的 下标分别为 1、2、3,那么结点 D、E、F 对应的数组元素下标为( )。

- A.4、5、6 B.4、7、10
- C.6、7、8 D.6、7、14
二叉树的顺序存储图一般为(空节点要占位置):

二叉树的链式存储图为:

● 图G的邻接矩阵如下图所示(顶点依次表示为v0、v1、v2、v3、v4、v5),G是( )。对G进行广度优先遍历(从v0开始),可能的遍历序列为( )。

- A.无向图
- B.有向图
- C.完全图
- D.强连通图
- A.v0、v1、v2、v3、v4、v5
- B.v0、v2、v4、 v5、v1、v3
- C.v0、v1、v3、v5、v2、v4
- D.v0、v2、v4、v3、v5、v1

● 设散列函数为 H(key)key%11对于关键碍序列(23,40,91,17,19,10,31,65,26),用线性探测法解决冲突构造的哈希表为(60)。

哈希表存储和查找过程