南京航空航天大学2002年GIS专业考研《数据结构与程序设计》试题

数据结构配程序设计 说明：下列每道题10分，编程题可用任何一种编程语言编写

一、将下列稀疏矩阵的非零元素表示成三元组的形式和十字链表的形式。

二、设一棵二叉树的层次遍历序列为ABDEGHJK，中序遍历序列为GDJHKBEA。

（1）画出这棵二叉树示意图

（2）说明建立这棵二叉树的原理

三、回答下列B树（有些教材中称为B-树）问题：

（1）一棵4阶4层（根为第一层，叶子为第二层）的B树，至少有多少关键字，至多有多少关键字

（2）在含有n个关键字的m阶B树中进行查找时，最多访问多少个结点。

四、哈希表中使用哈希函数H（key）=3 * key % 11,并采用开放定址法处理冲突，随机探测再散列的下一地址公式为：

　　　　　d1=H (key )

di=( di-1 +7 * key ) % 11 （I=2,3…..）

试在0到10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）画出Hash表示意图，并求在等概率情况下查找成功的平均查找长度。

五、求出一棵滿k叉树的叶子结点数n和所有非叶子结点数m之间的关系，给出求解过程。

六、已知两个链表A和B，其元素值递增排列。编程，将A和B合并成一个递减有序（相同值只保留一个）的链表C，并要求利用原表结点。

七、已知一棵二叉树用二叉链表存储，root 指向根结点，p指向树中任一结点。编程，输出从root 到p 之间路径上的结点。

八、已知一棵树用孩子－兄弟链表存储。编程，计算该树的叶子数。

九、设有n 个整数组成的序列，每个整数为－1，0，1之一。编写一个时间复杂度为O（n）的算法，使该序列按负数、零、正数的次序排好。

十、已知n个顶点的带权图用邻接矩阵表示，编写函数，实现用Kruskal算法构造最小生成树，要求对函数中所使用的变量和内容做详细的注释说明。