内容发布更新时间 : 2024/12/27 22:50:33星期一 下面是文章的全部内容请认真阅读。
哈尔滨工业大学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)逐个比较，若发现aj1>a1,则aj1与a1交换，交换后新的aj1有性质aj1>= at ( j1
哈尔滨工业大学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）7
3． 在一个图中，所有顶点的度数之和等于所有边数______倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的_____倍
（1） 1/2 （2）2 （3）1 （4）4 4． 下列排序算法中，________,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。
（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的路
（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。
哈尔滨工业大学2000年数据结构考研试题
一． 名词解释：（12分） 1． 抽象数据类型； 2． 算法的时间复杂性； 3． 散列法(hashing)； 4． 索引文件。 二． 填空：(12分)
1． 在单链表中设置头结点的作用是_________________________________。 2． n个顶点的连通无向图，其边的条数至少为________________________。 3． 线索二元树的左线索指向其_______________，右线索指向其____________。
4． 树在计算机内的表示方式有___________，_____________，________________。
5． 排序（sorting）有哪几种方法_______________，_____________，____________，_____________，____________。
三．判断下列叙述是否正确，若你认为正确，请画“ “，否则画” “。