文档介绍：北京邮电大学2000考研题
注意事项:
;
;
3 .算法应说明基本思路,应对主要数据类型, 变量出说明,所写算法应思路清晰简明易懂,应加必要注释。
,c语言等你所熟悉的高级语言编写,但要注明语种
判断对错(10分,每题1分)
任何无向图都存在生成树。
采用二叉链表作存储结构,树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。
强连通图的各顶点均可达。
在任何情况下,归并排序都比简单插入排序快。
在二叉树中插入结点,则此二叉树便不再是二叉树了。
霍夫曼树的结点个数不能是偶数。
抽象数据类型只是用来描述一些抽象的事。
在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。
二叉树是一般树的特殊情形。
文件系统采用索引结构是为了节省存储空间。
选择填空(20分)
栈和数组分别是线性表的_______和________结构。

M阶B-树是一棵________
-+1平衡排序树
算法的计算量的大小称为计算的________。

设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为:_______

一个有n个结点的图,最少有_____个连通分量,最多有________个连通分量。
-1
在排序算法中每一项都与其它项进行比较,计算出小于该项的个数,已确定该项的位置叫:________

对图中每个结点都按以该结点为弧头的邻接点建立一个单链表的存储结构称为____

顺序文件采用顺序结构实现文件的存储,对大型的顺序文件的少量修改,要求重新复制整个文件,代价很高,采用______的方法可降低所需的代价。

简要计算(10分)
给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
banana H()—Head()、T()—Tail()从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
有一组关键字(8,20,35,12,39,10,16,19,15),给出下面再等概率情况下查找成功的平均查找长度(10分)
按顺序建立一棵二叉排序数,画出该二叉排序树;
按顺序建立一棵平衡二叉排序数,画出该平衡二叉排序树。
已知一图如右图所示(15