词分析(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<t<n )。若再有aj2 > ai ( j2 < j1 ),aj2与
at (j2 < t <= n )。如在挑选第一大元过程中,与a1交换的
元素有k ( k >= 0 )个,依次为aj1,aj2,…,ajk,作者: onlyone 时间: 07-7-27 12:59
哈尔滨工业大学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}
八. 已知一个非空二元树,其按中根和后根遍历的结果分别为:
中根:C G B A H E D J F I
后根:G B C H E J I F D A
试将这样二元树构造出来;若已知先根和后根的遍历结果,能否构造这棵二元树,为什么?(8分)
九.已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小树(假设以 为起点,试画出构造过程)。(8分)
十.试编写一个算法,他能由大到小遍历一棵二元树。(10分)
十一。假设二元树用左右链表示,试编写一算法,判别给定二元树是否为完全二元树?(14分)作者: onlyone 时间: 07-7-27 13:02
哈尔滨工业大学2001年研究生入学考试试题---数据结构