中科院计算机技术研究所11019年硕士生入学考试试题.docx

中科院计算机技术研究所11019年硕士生入学考试试题 中科院计算机技术研究所11019年硕士生入学试题 数据结构和程序设计 一、选择题(20 分每空2分) 1.___ 的遍历仍需要栈的支持 1.前序线索树 2.中序线索树 3.后序线索树 2.若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为___ 1.n-1 2.[n/m]-1 3.[(n-1)/(m-1)] 4.[n/(m-1)]-1 5.[(n+1)/(m+1)]-1 3.最优二*树(哈夫曼树)、最优查找树均为平均查找路径长度∑wh最小的树,其中对最优二*树,n表示___,对最优查找树,n表示___; 构造这两种树均___ 1.结点数 2.叶结点数 3.非叶结点数 4.度为二的结点数 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.对于给定的n个元素,可以构造出的逻辑结构有___,___,___,___四种 2.具有n个关键字的B-树的查找路径长度不会大于___ 3.克鲁斯卡尔算法的时间复杂度为___, 他对___图较为适合 4.深度为k(设根的层数为1)的完全二*树至少有___个结点, 至多有___个结点, k 和结点数n之间的关系是___ 三、问答题(10 分,每题5分) 1.一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1.但一个恰有一个顶点的入度为0，其他顶点入度为一的有向图却不一定是一棵有向树。

请举例说明之 2.若有n个元素以构成一个小根堆，那么如果增加一个元素为K(n+1)，请用文字简要说明你如何在log2(n) 的时间内将其重新调整为一个堆？ 四、阅读下述程序,指出程序的输出10 分) void g(int**); main(){ int line[101],i; int *p=line; 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第3页 共3页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页第 3 页 共 3 页。