中科院计算机技术研究所数据结构-1999考研试题研究生入学考试试题考研真题
● 摘要
中科院计算机技术研究所1999年硕士研究生入学试题
考试科目：数据结构
一. 选择题. （20分，每空2分）
1.____的遍历仍需要栈的支持.
(1) 前续线索树(2)中序线索树 (3)后序线索树
2. 若度为m 的哈夫曼树中，其叶结点个数为n, 则非叶结点的个数为＿＿＿．
（１）n-1 (2)|_n/m_|-1 (3)上取整 (n-1)/(m-1)4)[上取整n/(m-1)]-1 (5)[上取整(n+1)/(m+1 )]-1
3. 最优二叉树（哈夫曼树），最优查找树均为平均查找路径长度 wihi 最小的树, 其中对最优二叉树,n 表示___,对最优查找树,n 表示 ____;构造这两种树均为——。*（1）结点数（2）叶结点数 （3）非叶结点数 （4）度为2的结点数 （5）需要一张N 个关键字的有序表 （6）需要对N 个关键字进行动态插入（7）需要N 个关键字的查找概率表（8）不需要任何前提。
4. 对于前序遍历与中序遍历结果相同的二叉树为_____;对于前遍历和后序遍历 结果相同的二叉为_____.
(1) 一般二叉树 (2) 只有根结点的二叉树 (3)根结点无左孩子的二叉树 (4)根结点无右孩子的二叉树 (5)所有结点只有左子数的二叉树 (6)所有结点只有右子树的二叉树.
5.M 路B+树是一棵_____,其结点中关键字最多为___个, 最少为___个..
(1) M 路平衡查找树 (2)M路平衡索引树 (3) M 路TRIE 树 (4)M路键树(5)M-1
(6)M (7)M+1 (8)上取整(M/2)-1 (9) 上取整(M/2) (10) 上取整(M/2)+1
二. 填空题（10分，每空1分）
1. 对于给定的N 个元素, 可以构造出的逻辑结构有___._____. _____.. ____四种.
2. 具有N 个关键字的B-树的查找路径长度不会大于________.,
3. 克鲁司卡尔算法的时间复杂度为_____,它对_____图较为适合.
4. 深度为可（设根的层数为一）的完全二叉树至少有______个结点, 至多有_____个结点,K 和结点数N 之间的关系是_____.
三. 问答题（10分，每题5分）
1.一棵非空的有向数中恰有一个顶点入度为0, 其他顶点入度为一, 但一个恰有一个顶点入度为0, 其他顶点入度为一的有向图却不一定是一棵有向数, 请举例说明.
1
相关内容
相关标签