- 设S是一个长度为n的非空字符串，其中字符各不相同，则其互异的非平凡字串（非空且不同于s本身）个数为_____
A. 2n-1 B.n2 C.n(n+1)/2 D.(n+2)(n-1)/2
【答案】D
【解析】
方法1：代入法，假设n=1,A选项:1。B选项：1。C选项1。D选项：0。
只有D选项与其他不同，所以选D。
方法2：假如n=1,且这个字符串是a。那么非空且不等于a本身的字符串没有。所以个数是0。只有D选项是。 - 设某二叉树采用二叉链表表示（即节点的两个指针分别指示左、右孩子）。当该二叉树包含k节点时，其二叉链表节点中必有_______个空的孩子指针。
A.k-1 B.k C.k+1 D.2k
【答案】C
【解析】：画图代入：
上面这个二叉树，只有1个节点（节点必须有左右孩子），空孩子指针有2个。
上图左侧只有1个节点，空孩子指针有2个。上图右侧有2个节点，空孩子指针有3个。代入ABCD四个选项，只有C选项符合规律，所以选C。
3.拓扑排序是有向无环图中所有顶点的一个线性序列，若有向图中存在弧<v，w>或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是_______
A. 41235 B.43125 C.42135 D.41325
【答案】A
【解析】拓扑排序只要遵循下面规则即可：（1）选没有前趋的点开始。（2）删除这个点以及关联的边。（3）重复（1）（2）。
上图中度为0的点是4，所以开头是4。如果把4这个点去除掉，那么 剩下的部分应该是这样：
那么这个图中没有前趋的点是1。如果把1这个点去掉后没有前趋的点是2。如果把2这个点去掉后，没有前趋的点是3，最后是5。所以结果最终排序是41235
3.一下关于哈夫曼树的叙述，正确的是_______
A.哈夫曼树一定是满二叉树，其每层节点数都达到最大值。
B.哈夫曼树一定是平衡二叉树，其每个节点左右子树的高度差为-1、0或1。
C.哈夫曼树中左孩子节点的权值小于父节点，右孩子节点的权值大于父节点。
D.哈夫曼树中叶子节点的权值越小则距离树根越远、叶子节点的权值越大则距离树根越远。
【答案】D
【解析】哈夫曼是最优二叉树，是一类带权路劲长度最短的二叉树。
A选项，哈夫曼树不一定是满二叉树。B选项，平衡二叉树的定义是：坐左子树和右子树的高度只差不超过1，且它的左子树和右子树均为平衡二叉树。哈夫曼树不一定能是平衡二叉树。C选项，哈夫曼树中权值最小的两个节点互为兄弟节点，跟节点的权值为其左右子树根节点的权值之和，所以C选项错误。
4.若一个栈初始为空，其输入序列是1，2，3….n-1,n，其输出序列的第一个元素是k(1<=k<=n/2)，则输出序列的最后一个元素是_____
A. 1 B.n C.n-1 D.不确定的
【答案】D
【解析】。一开始选A，后来发现没有指定出栈顺序，那么出栈顺序有很多，比如1进栈，1出栈，2进栈，3进栈，3出栈，2出栈。这样的例子很多，所以不能确认最后一个谁出栈。
5.以下关于哈希（Hash,散列）查找的叙述中，正确的是____
A.哈希函数应尽可能复杂些，以消除冲突。
B.构造哈希函时应尽量使关键字的所有组成部分都能起作用。
C.进行哈希查找时，不再需要与查找表中的元素进行比较。
D.在哈希表中只能添加元素不能删除元素。
【答案】B
【解析】哈希表中的元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系计算出的值，即为该元素的存储地址。所以在构造哈希函数时应尽量使关键字的所有组成部分起作用。