文档介绍：北京邮电大学99考研题
注意事项:
;
;
3 .算法应说明基本思路,应对主要数据类型, 变量出说明,所写算法应思路清晰简明易懂,应加必要注释。
,c语言等你所熟悉的高级语言编写,但要注明语种。
一、选择填空。
1字符串‘ababaabab’的nextval 为( );
a(0,1,0,1,04,1,0,1) b(0,1,01,0,2,1,0,1)
c(0,1,0,1,0,0,0,1,1) d (0,1,0,1,0,1,1,1 )
2广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为( );
head(tail(head(tail(tail(A)))))
a(g) b(d)
3输入序列为(A,B,C,D ),则不可能得到的输出序列有( );
a(A,B,C,D) b(D,C,B,A) c(A,C,D,B) d(C,A,D,B )
4散列函数有一个共同性质即函数值应按( ) 取其值域的每一个值;
a 最大概率 b最小概率 c 同等概率 d 平均概率
5 直接插入序列在最好情况下时间复杂度为( );
a O(logn) b O(n) c O(n*logn) d(n2)
二、判断是否正确。(10分)
1(101,88,46,70,34,45,58,66,10)是堆;
2 将一棵树转成二叉树,根结点没有左子树;
3 用树的前序遍历和中序遍历可以导出树的后序遍历;
4 即使不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作,所得的输出序列也应一定相同;
5 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。
三、有一个高个比他人至少高一头,找他的人都说根本不用和别人比较,一眼就能看到他。你认为此话正确吗?为什么?请简要描述两种求个数中最大值的方法,并给出所须的最少比较次数。(10分)
A
四、下面是邻接表的存储图,画出此图,比写出从点c开始按优先深度遍历该图的结果。(10分)
D
B
F
D
B
C
A
D
E
D
E
^
F
E
五、下面是求无向连通图最小生成树的一种方法;
将图中所有有向边按权重从大到小排序为(e1,e2,……em)
i:=1
while (所剩边书>=顶点树)
begin
从图中删去 ei
若图不再连通,则恢复ei
i:=i+1
end.
试证明这个算法生成的图是原图的最小代价生成树。
六、已知无向图G和G’互为补图(结点相同,边不重叠,两图合并是完整图),试证明G或G’是连通的.(10)
七、用序列(46,88,45,39,70,58,101,10,66,34)建一个排序二叉树,画出该树,并在等概率下查找成功的平均查找长度.(10)
八、写出下面程序片段的结果(10)。
program ex (input,output);
type
ttt=Array[1..20] of integer;
var
l,j,k,l,n:integer;
a:ttt;
FUNCTION P(VAR a:ttt;var m,n:integer):integ