搜索
哈尔滨工业大学1999年数据结构考研试题（图2、3缺失）一.名词分析（15分）1.广义表2.最小生成树3.散列表4.堆5.随机文件二.试分别画出具有3个结点的树和3个结点的二元树的所有不同形态（同构的算一个）。（6分）三.本题给出一个子程序的框图，如图2，试填完完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表F1，F2，F3中的相同整数。假定调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所示。（15分）（注：在图2中的框图中：found和exit均为布尔型的变量，可取值为true和false。Val是整型变量，用来存放F1，F2，F3中无相同的整数found的值为false，否则found的值为true。F1^.link表示访问found结点的link域）。四假设一株二元树，按其后根顺序的结点排序为：H，I，D，J，E，B，F，G，C，A而按中根顺序的结点排序为：H，D，I，B，E，J，A，C，F，G（1）试画出这株二元树。（7分）（2）画出它的线索二元树。（7分）五已知集合S={7，3，4，6，19，14，16，9，22，11}，试按照自左而右的顺序依次取出S中的每个元素，逐步建立一株对应于S的二元查找树。试画出所得到的二元查找树（不要求给算法）。（8分）六本题给出的是将数组a的元素a1,a3…,an从大到小排序的子程序的框图，如图3，填空完善此算法框图。该子程序采用改进的选择排序方法，该方法基本于以下思想：在选择第一大元过程中：a1与aj(j=n,n–1…,2)逐个比较，若发现aj1a1,则aj1与a1交换，交换后新的aj1有性质aj1=at(j1tn)。若再有aj2ai(j2j1),aj2与at(j2t=n)。如在挑选第一大元过程中，与a1交换的元素有k(k=0)个，依次为aj1,aj2,…,ajk,哈尔滨工业大学2001年数据结构考研试题考试科目：数据结构报考专业：计算机科学与技术一．填空（总分：10分，每一题2分）1．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定为x的结点后插入一个新结点的时间复杂度为________。2．广义表（a，（a，b），d，e，((I,j,),k)）的长度是________,深度是________。3．对于一个具有n个结点的二员树，当它为一棵________二元树时具有最小高度，当它为一棵_______时，具有最大高度。4．在顺序文件中，要存取第I个记录，必须先存取______个记录。5．求最短路径的dijkstra算法的时间复杂度为________。二．选择填空：（总分10分，每小题2分）1．若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用______存储方式最节省时间。（1）顺序表；（2）双链表；（3）头结点的双循环链表；（4）单循环链表2．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为______个（1）4（2）5（3）6（4）73．在一个图中，所有顶点的度数之和等于所有边数______倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的_____倍（1）1/2（2）2（3）1（4）44．下列排序算法中，________,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。（1）选择（2）冒泡（3）归并（4）堆5．散列文件使用散列函数将记录的关键字值计算转化为记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的_______方法是散列文件的关键。（1）散列函数（2）除余法中的质数（3）冲突处理（4）散列函数和冲突处理三回答下列问题（总分15分，每小题3分）1数据结构与数据类型有什么区别？2什么是循环队列？3简述线索二元树的概念。4何为有向图的遍历？5什么是索引顺序文件？四．分别画出和下列树对应的各个二元树。五．试设计一个算法，判断链表L是否是递减的。六．判断以下序列是否为堆，如果不是，则把它调整为堆。(1)(12,24,33,65,33,56,48,92,86,70)(2)(25,56,20,23,40,38,29,61,35,76,28,100)七．设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O…maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。八．假设用于通讯的电文仅有6个字母abcdef组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这6个字母设计哈夫曼编码九．试写一算法，判断以邻接表方式存储的有向图中是否存在有顶点Vi到顶点Vj的路（ij）。注意：算法中涉及的图的基本操作必须在存储结构上实现。哈尔滨工业大学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分）