南京航空航天大学数据结构与程序设计2002考研试题研究生入学考试试题考研真题
● 摘要
南京航空航天大学2002年数据结构与程序设计考研试题
考试科目：数据结构配程序设计
说明：下列每道题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 之间路径上的结点。
八、已知一棵树用孩子－兄弟链表存储。编程，计算该树的叶子数。