哈尔滨工业大学数据结构考研试题及答案

哈尔滨工业大学数据结构考研试题及答案哈尔滨工业大学2000年数据结构考研试题一.名词解释：(12分)1.抽象数据类型;2.算法的时间复杂性;3.散列法(hashing);4.索引文件。二.填空：(12分)1.在单链表中设置头结点的作用是_________________________________。2.n个顶点的连通无向图，其边的条数至少为________________________。3.线索二元树的左线索指向其_______________，右线索指向其____________。4.树在计算机内的表示方式有___________，_____________，________________。5.排序(sorting)有哪几种方法_______________，_____________，____________，_____________，____________。三.判断下列叙述是否正确，若你认为正确，请画“√”，否则画“×”。1.存在这样的二元树，对它采用任何次序的遍历，结果相同。()2.二元树就是结点度为2的树。()3.若连通图上各边权值均不相同，则该图的最小生成树是唯一的。()4.无向图的邻接矩阵一定是对称矩阵，但有向图的邻接矩阵一定是非对称矩阵。()5.完全二元树中，若一个结点没有左儿子，则必是树叶。()四.堆与二元查找树的区别?(6分)五.快速分类法的基本思想是什么?(6分)六.设F={T1,T2,T3}是森林，试画出所有对应的二元树，其森林如图所示：(6分)七.依次读入数据元素序列{a，b，c，d，e，f，g}j进栈每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行则栈空时弹出的元素构成的序列是以下那些序列?(8分){d，e，c，f，b，g，a}，{f，e，g，d，a，c，b}{e，f，d，g，b，c，a}{c，d，b，e，f，a，g}八.已知一个非空二元树，其按中根和后根遍历的结果分别为：中根：CGBAHEDJFI后根：GBCHEJIFDA试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么?(8分)九.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树(假设以为起点，试画出构造过程)。(8分)十.试编写一个算法，他能由大到小遍历一棵二元树。(10分)十一.假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树?(14分)