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