一个字符串sscie
ce,其非空子串的数目是________。
10.有
个顶点的强连通有向图G至少有________条弧。1.一棵二叉树的先序序列和中序序列分别如下,
先序序列ABCDEFGHIJ中序序列CBDEAGIHJF(1)画出该二叉树。(3分)
(2)写出其后序序列3分)
2.给出用Kruskal算法构造下列带权图的最小生成树的过程。
3
V1
V2
1
5
4
3
V3
V6
4V4
1
6
2V5
3已知一个长度为12的表(6,8,412,210,7,39,1,11,5。(1)将表中的元素依次插入到一个初始为空的二叉排序树中,画出该二叉排序树并求其在等概率下的平均查找长度。(3分(2)若先对表中的记录排序,构成有序表后再对其进行折半查找,画出判定树并求其在等概率下的平均查找长度。(3分)
4.已知哈希表地址空间为0。。10,哈希函数为H(keykeyMOD11,采用链地址法处理冲突,将下面数据序列依次插入该哈希表中,并求出在等概率下查找成功时的平均查找长度。
12,24,1,3438,44,2722。
5.假定用于通信的电文仅由8个字母a,b,c,d,e,dfg,h组成,各个字母在电文中出现的频率分别为5,23,3,6,10,11,36,4。要求:1)以这些频率作为叶子结点的权值构造Huffma
树。2分
(2试为这8个字母设计不等长Huffma
编码。(2分)
A
b
c
d
e
f
g
h
f(3)计算出电文总长度。2分)1。有两个不带头结点的单循环链表,链表头指针分别为a和b。编写一个过程将链表b链到链表a之后链接后的链表仍保持循环链表形式。2试编写一个计算二叉树的叶子结点数的算法。要求二叉树采用链式存储结构。3。请写出监视哨设在高下标端的插入排序算法。062
1具有
〉0个结点的完全二叉树的深度为
(
Alog2
Blog2
Clog2
1
Dlog2
1
2一个栈的进栈序列是a,b,c,d,e则栈的不可能的输出序列是
(
)
AabcdeC。decba
BedcbaD。dceab
3数据在计算机存储器内表示时物理地址与逻辑地址相同且连续,称之为(
)
A存储结构
B逻辑结构
C顺序存储结构
D链式存储结构
4。对二叉排序树的左子树中所有结点与右子树中所有结点的关键字大小关系是(
)
A小于
B。大于
C等于
D。不小于
5。按照二叉树的定义,具有3个节点的二叉树______种
(
)
A2
B3C4
D。5
6。广义表(a))的表尾是
)
A.a
B。(aC.()
D(a)
7.设有两个串p和q,求在q在p中首次出现的位置的运算称为
(
)
A。模式匹配B连接C。求子串
D求串长
8。引入二叉线索树的目的是
(
)
A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方r